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!
