#include #include #include #include #include #include using namespace std; //If true, some more output describing changes in the hash table will be shown bool OUT=true; //Hash function for strings unsigned str_hash(string &s){ unsigned r=0; for (unsigned int i=0; i>32); } template class HashTable{ public: //Creates a hash table using hash function f HashTable(unsigned(*f)(K&)){ hashfunc=f; cap=16; size=0; buckets.resize(cap); } //Enlarges the number of buckets void inflate(){ if (OUT) cout << "Inflating\n"; buckets.resize(2*cap); for (int i=0; icap/4*3) inflate(); int h = hashfunc(key)%cap; //get the hash value of key if (OUT) cout << "Inserting key " << key << " with hash " << hashfunc(key) << " to bucket " << h << "\n"; //keep the linked list in the bucket sorted, find the place to insert (key, value) auto it = buckets[h].begin(); while (it!=buckets[h].end() && (*it).first &other){ for (pair p: other.toStack()) insert(p); } //Returns the number of buckets int numbuckets(){ return cap; } //Returns the number of entries (key-value pairs) int count(){ return size; } //Creates a stack (vector will be good) containing all entries of this hash table vector> toStack(){ vector> v; for (int i=0; i> toQueue(){ queue> q; for (int i=0; i> toBST(){ map m; for (int i=0; i> getList(int hash){ list>l; if (hash>=0 && hash > > buckets; unsigned(*hashfunc)(K&); }; int main(){ /* cout << long_hash(-1) << "\n"; cout << long_hash(20) << "\n"; cout << long_hash((1LL<<32)+21) << "\n";*/ //Let's test the hash table! HashTable ages(&str_hash); ages.insert("Amy", 15); ages.insert("Bob", 16); ages.insert("Chris", 30); ages.insert("Dave", 8); cout << "Is Chris present? " << boolalpha << ages.containsKey("Chris") << "\n"; ages.insert("Eve", 28); ages.insert("Fred", 26); ages.insert("George", 33); ages.insert("Hugo", 40); ages.insert("Ian", 19); ages.insert("John", 21); ages.insert("Kate", 32); ages.insert("Lili", 20); ages.insert("Marley", 5); cout << "We have " << ages.count() << " entries\n"; int x = ages.find("Chris"); cout << "Chris is " << x << "\n"; x = ages.find("Bob"); cout << "Bob is " << x << "\n"; x = ages.find("Kate"); cout << "Kate is " << x << "\n"; x = ages.find("Marley"); cout << "Marley is " << x << "\n"; ages.insert("Kate", 34); x = ages.find("Kate"); cout << "Kate is now " << x << "\n"; ages.remove("this foo is not a key"); ages.remove("Chris"); cout << "Is Chris present? " << boolalpha << ages.containsKey("Chris") << "\n"; cout << "We have " << ages.count() << " entries\n"; return 0; }

Challenge: Mutant Hash Table