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. You can find the testing files on the course website. 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 2 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))
