Hashing

In this assignment you will be implementing some basic mechanisms of a hash table to implement a Dictionary that uses hashing to store and search for items in its collection. You have been given many files for this assignment. I have provided an Employee class in "Employee.[hpp|cpp]" and a KeyValuePair class in "KeyValuePair.[hpp|cpp]". You will not need to make any changes to these files or classes, they should work as given for this assignment. You will be adding and implementing some member functions to the HashDictionary class. The initial "HashDictionary.[hpp|cpp]" file contains a constructor and destructor for a HashDictionary as well as some other accessors and operators already implemented that are used for testing. You will be implementing a closed hash table mechanism using quadratic probing of the slots. You will also implement a version of the mid-square hashing function described in our textbook (Shaffer section 9.4.3 on closed hashing mechanisms).

For this assignment you need to perform the following tasks.

1. Your first task is to implement methods to define the probe sequence for closed hashing. Add a member function named probe() to the HashDictionary class. Be aware that the HashDictionary class is a templatized on <Key, Value> templates, thus when you implement the class methods you need to templatize the class methods correctly. You can look at the example implementations of size() and the constructors to remind yourself how to do this correctly. In any case, probe() is a member function that takes two parameters, a Key and an integer index value. We are not using secondary hashing (as described in our textbook) so the Key value will actually not be used in your function. However, keep it as a parameter as the general abstraction/API for the probe function should include it for cases where secondary hashing is used. probe() should be a const class member function, as calling it does not change the dictionary. Finally probe() will return an ineger as its result. Your probe() funciton should implement a quadratic probing scheme as described in our Shaffer textbook section 9.4.3 on pg. 338. Use c1 = 1, c2 =2, c3 = 2 as the parameters for your quadratic probe (the tests of probe() assume your probe sequence is using these parameter values for the quadratic function).

2. You second tasks is to implement a hash function for integer like keys using the described mid-square hashing function (Shaffer 9.4.1 Example 9.6 pg. 327). We will create a slight variation of this algorithm for our hashing dictionary. First of all the hash() member functions should take a Key as its only input parameter, and it will then return a regular int as its result. Since this is a hash function, the integer value should be in the range 0 - tableSize-1, so don’t forget to mod by the tableSize before returning your hash result. hash() should work like this. First of all, you should square the key value that is passed in. Then, assuming we are working with a 32 bit int, we want to only keep the middle 16 bits of the square of the key to use for our hash. There are many ways to work with and get the bits you need, but most likely you will want to use C bitwise operators to do this. For example, a simple method to get the middle 16 bits is to first mask out the upper 8 bits using the bitwise & operator (e.g. key & 0x00FFFFFF) will mask out the high order 8 bits to 0). Then once you have removed the upper most significant 8 bits, you can left shift the key by 8 bits, thus dropping out the lower least significant 8 bits (e.g. key >> 8). Performing a mask of the upper 8 bits and shifting out the lower 8 bits will result in you only retaining the middle 16 bits. If your system is using 64 bit integers rather than 32 bit integers, perform the mid-square method but retain the middle 32 bits of the result. You can use the sizeof(int) method to determine how many bytes are in an int on your system. I will give a bonus point if you write your hash() function to correctly work for both 32 and 64 bit values by testing sizeof(int) and doing the appopriate work to get the middle bits. Again after you square the key and get the middle bits, make sure you modulo the result to get an actual has index in the correct range.

3. The third task is to add the insert() method to your HashDictionary so that you can insert new key/value pairs into the dictionary. insert() should take a constant Key reference and a constant Value reference as its input parameters (note that both of these parameters should be declared as const, and they should both be reference parameters, so use the & to indicate they are passed by reference). Your insert() function does not return a result, so it will be a void function. The algorithm for insert is described in Shaffer 9.4.3 on pg. 334. You need to call and use the probe() and hash() funciton you created in the first 2 steps to correctly define/implement your closed hashing probe sequence. The basica algorithm is that you use hash() to determine the initial home slot, and probe() gives an offset you should add. Basically you have to search the hashTable using the probe sequence until you find an empty slot. Once you find an empty slot, you should create a new instance of a KeyValuePair<Key, Value> object, that contains the key and value that were provided as input parameters to your insert() function. This KeyValuePair instance should then be inserted into the table at the location where you find the first empty slot on the probe sequence. Also don’t forget to update the valueCount paramemter of the HashDictionary class that keeps track of the number of items currently in the dictionary.

4. Finally you will also implement the find() method to search for a particular key in your dictionary. The find() member function takes a single Key parameter as input (it should be a const Key& reference parameter). The find() function will return a Value as a result, which will be the Value of the record associated with the given Key if it was found in the dictionary, or an empty Value() object if it was not found. The find() method uses the same probe sequence as insert() implemented by your probe() and hash() methods. So you should again search along the probe sequence, until you either find the key you were given to search for, or else find an empty slot. Then at the end, if you found the key in the hashTable you should return the value that corresponds to the key that was searched for. If the search failed and you found an empty slot on your probe sequence, you should instead return an empty Value() object, which is used as an indicator for a failed search. In this assignment you will be given a lot of starting code. As usual, there is an "assg-13.cpp" file which contains commented out tests of the code/functions you are to write. You have been given and "Employee.[hpp|cpp]" file containing a simple definition of a (non-templated) class/record that holds a few pieces of information about a theoretical Employee. We use this class to create a hash dictionary for testing with the employee id as the key, and the Employee record as the associated value in our Dictionary. You have also been given a template class in the file "KeyValuePair.[hpp|cpp]". This contains a templatized container to holding a key/value pair of items. You will not need to add any code or make any changes in the Employee or KeyValuePair class files. You have also been given a "HashDictionary.[hpp|cpp]" file containing beginning definitions of a HashDictionary class. The member functions you need to add for this assignment should be added to these files. Here is an example of the output you should get if your code is passing all of the tests and is able to run the simulation. You may not get the exact same statistics for the runSimulation() output, as the simulation is generating random numbers, but you should see similar values.

----- testing Employee record and KeyValuePair class -----------

test key: 42

test value: blue

( id: 3, Derek Harter, 1234 Main Street, Commerce TX, 12345.67 )

-------------- testing quadratic probing -----------------------

Newly created hash dictionary should be empty, size: 0

probe index: 0 returned probe value: 2

probe index: 1 returned probe value: 5

probe index: 5 returned probe value: 37

-------------- testing mid-square hashing ----------------------

Assuming 32 bit (4 byte) ints for these tests: 4

hash key: 3918 returned hash value: 1

hash key: 48517 returned hash value: 6

hash key: 913478 returned hash value: 5

hash key: 8372915 returned hash value: 4

counts for slot[0] = 143055

counts for slot[1] = 143040

counts for slot[2] = 143362

counts for slot[3] = 142399

counts for slot[4] = 142966

counts for slot[5] = 142658

counts for slot[6] = 142520

-------------- testing dictionary insertion --------------------

After inserting 4 employees:

Slot: 0

Key : 362817371

Value: ( id: 362817371, Carol Black, 8913 FM 24 Cooper TX, 28.50 )

Slot: 1

Key : 438901234

Value: ( id: 438901234, Derek Harter, 123 Main St. Commerce TX, 58.23 )

Slot: 2

Key : 0

Value: ( id: 0, , , 0.00 )

Slot: 3

Key : 192834192

Value: ( id: 192834192, Alice White, 384 Bois'darc. Campbell TX, 45.45 )

Slot: 4

5

Key : 998439281

Value: ( id: 998439281, Bob Green, 92 Washington Apt. 5 Greenville TX, 16.00 )

Slot: 5

Key : 0

Value: ( id: 0, , , 0.00 )

Slot: 6

Key : 0

Value: ( id: 0, , , 0.00 )

-------------- testing dictionary search -----------------------

Search for id: 438901234

Found employee: ( id: 438901234, Derek Harter, 123 Main St. Commerce TX, 58.23 )

Search for id: 362817371

Found employee: ( id: 362817371, Carol Black, 8913 FM 24 Cooper TX, 28.50 )

Unsuccessful Search for id: 239481432

Found employee: ( id: 0, , , 0.00 )