Description
1. Project Description
In this project, you design and implement a hash table data structure. A hash table is a data
structure where values are mapped to a position in a table using a hash function. For this
project, you will implement a double hash table in which collisions are resolved using double
hashing. We will use hash functions sufficiently even so as to allow all expected constant-time
operations to be O(1).
2. You will implement a C++ Template Class
You will implement the double hash table as a C++ template class. A template class is a class
that allows for variable types. This means that your double hash table could store numbers of
type int or double, depending on how the object of this class is declared:
DoubleHashTable my_int_ht;
DoubleHashTable my_double_ht;
The first declaration declares a hash table that will hold integers while the second declares a
hash table that will hold numbers of double type. In section 5 of this document, and in the
provided source code, we refer to this variable type as T.
3. How to Test Your Program
We use drivers and tester classes for automated marking, and provide them for you to use while
you build your solution. We also provide you with basic test cases, which can serve as a sample
for you to create more comprehensive test cases. To compile and test your code enter the
following commands:
• g++ Double_hash_table_driver.cpp -o Double_hash_table_driver
• ./Double_hash_table_driver int < int.in
• ./ Double_hash_table_driver double < double.in
4. How to Submit Your Program
Once you have completed your solution, and tested it comprehensively, you need to build a
compressed file, in tar.gz format, with should contain the file:
• DoubleHashTable.h
Build your tar file using the UNIX tar command as given below:
• tar –cvzf xxxxxxxx_pn.tar.gz DoubleHashTable.h
where xxxxxxxx is your UW user id (ie. jsmith), and n is the project number which is 4 for this
project. All characters in the file name must be lower case. Submit your tar.gz file using LEARN,
in the drop box corresponding to this project.
5. Class Specifications
The DoubleHashTable class implements a hash table using double hashing. Notice that the
expected running time of each member function is specified in parentheses at the end of the
function description. It is important that your implementation follows this requirement strictly
(submissions that do not satisfy these requirements will not be given full marks). For run-time
requirements, and for the section below providing details on the hash functions to use, the
number of elements in the hash table is n and the size of the hash table is M.
2
5.1 Hash Functions
The primary hash function (that determining the bin) is the object statically cast as an int
(see documentation for static_cast), taking this integer module M (i % M) and adding M if
the value is negative. The secondary (odd) hash function (that determining the jump size)
is derived from the integer divided by M, and applying the module of M to the result of this
integer division((i / M) % M) . This value is again made positive, if necessary, by adding M. Add
1 to this function if the resulting value is even in order to make it odd when necessary.
Member Variables
The DoubleHashTable class has at least the following members variables (you may need
additional member variables):
• T *array – An array of objects of type T. This array will contain the values placed in the
hash table
• state *array_state – An array of objects of type “state” – to store the status of the bin.
The state of a bin is one of three possible values: EMPTY, OCCUPIED, or DELETED
• int count – The number of elements currently in the hash table
• int array_size – The capacity of the hash table
• int power – This is associated with the capacity of the hash table (array_size = 2power )
Constructor
DoubleHashTable ( int m = 5 )
The constructor takes an argument m and creates a hash table with 2m bins, indexed from 0 to
2m − 1. The default value of m is 5. Notice that you need to allocate and initialize two arrays, one
for storing the values in the hash table, and the other one for storing the status of the bins.
Destructor
~ DoubleHashTable ()
The destructor deletes the memory allocated for the hash table. Notice that the hash table has
been represented using two arrays, and they both need to be deleted.
Accessors
This class has six accessors:
• int size() const – Return the number of elements currently stored in the hash table. (O(1))
• int capacity() const – Return the number of bins in the hash table. (O(1))
• bool empty() const – Return true if the hash table is empty, false otherwise. (O(1))
• bool member( T const & ) const – Return true if object obj is in the hash table and false
otherwise. (O(1))
• T bin( int n ) const – Return the entry in bin n. The behaviour of this function is
undefined if the bin is not filled. It will only be used to test the class with the expected
locations. (O(1))
• void print() const – A function which you can use to print the class in the testing
environment. This function will not be tested.
Mutators
This class has three mutators:
• void insert( T const & ) – Insert the new object into the hash table in the appropriate bin
as determined by the two aforementioned hash functions and the rules of double
hashing. If the table is full, throw an overflow exception. (O(1))
• bool remove( T const & ) – Remove the object from the hash table if it is in the hash table
(returning false if it is not) by setting the corresponding flag of the bin to deleted. (O(1))
• void clear() – Remove all the elements in the hash table. (O(M))
