| COMP1927 14s2 | COMP1927 14s2 Final Exam | Computing 2 |
In the q2 directory is an implementation of a simple HashTable ADT, along with a main program to test it. The ADT contains functions to build, remove and display hash tables, as well as a function to insert new keys into the table (in this table, keys are integer values). It uses collision resolution via chaining (i.e. it builds linked lists of keys that have the same hash value). The HashTable ADT implements its chains using a simple List ADT. It also has a private (and very simple) hash function, and an incomplete function to expand the size of the table, once the chains become too long.
As supplied, the program creates a hash table with 3 slots, reads numbers (keys) from standard input and builds a hash table using these keys. The hash table maintains its original 3 slots, regardless of how many keys are added, and the chains will grow longer and longer as more keys are added, e.g.
$ seq 1 15 | ./q2 # with q2 as supplied
[ 0] 3->6->9->12->15
[ 1] 1->4->7->10->13
[ 2] 2->5->8->11->14
In the output from the program, the hash table is displayed one slot at a time, first showing the slot index (aka hash value) in square brackets (e.g. [ 0]) then showing all of the keys in the chain associated with that hash value. Since the hash function is implemented simply as (key%nslots), the above shows all of the keys with hash(key)==0 on the first line of output, all of the keys with hash(key)==1 on the second line of output, and so on.
Your task for this question is to implement the expand() function, which takes a hash table, doubles the number of slots in the table and rehashes all of the existing keys to their new slots (chains). You can achieve this however you like, but the pointer to the HashTable object must not be changed (i.e. you keep the same HashTable object but change what's stored in it and linked from it). Also, you are not allowed to change the List ADT to achieve this (since you only submit HashTable.c, changing List.c won't help your submission) and you may only access the chains via the interface given in List.h. (Hint: valuesFromList() is useful).
After you implement the expand() function correctly, the hash table will have more slots, but the chains will be shorter and searches will be more efficient, e.g.
$ seq 1 15 | ./q2 # with q2 including expand()
[ 0] 12
[ 1] 1->13
[ 2] 2->14
[ 3] 3->15
[ 4] 4
[ 5] 5
[ 6] 6
[ 7] 7
[ 8] 8
[ 9] 9
[10] 10
[11] 11
The q2 directory contains the following:
The Makefile compiles the List and HashTable ADTs and the main program in main.c to produce an executable program called q2. This program reads integer keys from standard input, builds a hash table, and then displays the hash table (in the format shown above).
You compile and test the q2 program using the following commands:
$ make q2 # build the q2 program $ check q2 # apply the tests in the tests directory to the q2 program
You can find out more about the behaviour of the q2 program by looking at the files in the tests directory. The files named tX are test scripts. Each test script has a corresponding file tX.exp which contains the expected output from running that test. If you want to run the tests individually, use commands like:
$ sh tests/t1
You can add debugging code to main.c, HashTable.c or List.c if you want, but make sure that you remove it before testing and submitting, otherwise your output won't match the expected output and you'll fail all of the tests. You can add any auxiliary functions to HashTable.c that you think are necessary.
Once you are satisfied with your program, submit it using the command:
$ submit q2
This will make a copy of the HashTable.c file from the q2 directory as your answer for this question. You can run the submit command as many times as you like, but make sure that your final submission compiles without any errors or warnings. Test your program thoroughly, possibly using test cases additional to those supplied. Your program will be tested using additional test cases to the examples in the q2/tests directory.