Description
This lab continues our study of Hash Tables. In this lab implement a Hash Table with open addressing. You are free to choose which open addressing routine to use, but you must implement a programmable load factor. Implement a Hash Table whose constructor take an integer (the initial size of the hash table) and a load factor, insert, remove, and get. Hints: if the value is not found in the Hash Table return a value using the default constructor.
WARNING: The loadFactor function must work properly for you to pass any tests.
| #ifndef HASH_TABLE_H
#define HASH_TABLE_H /* HashTable via open addressing */ template<class K, class V> class HashTable { private: /* Class to begin filling out…*/ public: /* Initialize the Hash Table with size size. */ HashTable(const int size, const float loadFactor); /* Deconstructor shall free up memory */ ~HashTable(); /* Map key -> val. * Return true if sucessful (it is unique.) * Otheriwise return false. */ bool insert(const K &key, const V &val); /* Print out the HashTable */ void print() const; /* Remove the val associated with key. * Return true if found and removed. * Otherwise return false. */ bool remove(const K &key); /* Retrieves the V val that key maps to. */ V& operator[](const K &key); /* Returns the current loadfactor for the Hash table (not the one * passed in.) * NOTE: When you hit the load factor, double the size of your array. |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| * WARNING: This function must work properly for you to pass ANY tests.
*/ float percentFull(); }; int hashcode(int key); int hashcode(const std::string &key); #include “hashtable.cpp” #endif |
37
38
39
40
41
42
43
44
45
46
47
Write some test cases:
Create some test cases, using cxxtestgen, that you believe would cover all aspects of your code.
Memory Management:
Now that are using new, we must ensure that there is a corresponding delete to free the memory. Ensure there are no memory leaks in your code! Please run Valgrind on your tests to ensure no memory leaks!
