Due date:
First solution: Thurs May 26 2:00pm
Second solution: Wed June 2 5:00pm
If you experience difficulty, ask for help early. Do not wait until the last minute to ask for help.
This is an assignment in using pointers and dynamic memory allocation. Accompanying this assignment is an implementation of hash tables. This is not an application, but is a library module that might be used in many applications. You can find the implementation in directory /export/stu/3510 on the Sun machines in Austin 320, in files table.cc and table.h. Copy those files so that you can work on them.
The implementation has the difficulty that it has a fixed size table, and the table can fill up. Your assignment is to modify the table implementation so that the table does not fill up.
It is not acceptable merely to increase the fixed size to some very large value. That would be wasteful of memory when few things are actually put into the table. Instead, your new implementation must reallocate the table when it runs out of memory. Do this by adding another field to the table type, indicating the physical size of the array --- that is, how many slots the cell array currently has. When the cell array becomes nearly full, allocate a new, larger array, and copy everything that was in the old array into the new array. Be sure to update the field that indicates the physical size of the array of cells.
Watch out. In a hash table, the position of an item is computed based on a hash function, and the position computation depends on the physical size of the hash table. So when the physical size changes, the positions of entries also change. To copy the old values into the new array, you will need to do hashInsert calls, so that the positions are set correctly. Think about this.
When you allocate a new array, don't get just one more cell. If you do, then a growing hash table becomes very expensive, since each insertion needs to make a copy of the entire table. One idea is to double the size of the table when it is reallocated. At any rate, increase the size by some factor that is greater than one.
You will need to modify function hashFull. Do not delete it, since it is part of the data type, even if now a useless one. Your hash tables never fill up. Think carefully about the correct implementation of hashFull. Read the contract for hashFull to see what its advertised behavior is.
A second difficulty is that this implementation allows the table to become almost completely full. A hash table of the kind implemented here that is almost completely full is very inefficient to search. It is better to keep at least 1/4 of the cells empty. Modify the implementation to reallocate the table when it becomes 3/4 full. Be careful: if you use integer arithmetic, you might get incorrect results. For example, in C++, 3/4 is 0. How can you test whether a > (3/4) b using only integer arithmetic? Can you rearrange this inequality so that it does not require division?
Email me your solution, as described in the syllabus. Attach both your header file and your .cc file. Be sure that your name is in both files. Do not attach your test file. Do not put any part of your program in the body of the message.
I will compile your solution and link it to my test file. Be sure that your solution is prepared to link with my tester. It must, therefore, have the same function prototypes as the original implementation. If you change the function prototypes, it will be inconsistent with what my test program expects.
Note: Your solution is expected to compile. Solutions that do not compile will receive no credit.