// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. #include "dictionary.h" #include "KVpair.h" // Dictionary implemented with a hash table template class hashdict : public Dictionary { private: KVpair* HT; // The hash table int M; // Size of HT int currcnt; // The current number of elements in HT Key EMPTYKEY; // User-supplied key value for an empty slot int p(Key K, int i) const // Probe using linear probing { return i; } int h(int x) const { return x % M; } // Poor hash function int h(char* x) const { // Hash function for character keys int i, sum; for (sum=0, i=0; x[i] != '\0'; i++) sum += (int) x[i]; return sum % M; } void hashInsert(const Key&, const E&); E hashSearch(const Key&) const; public: hashdict(int sz, Key k){ // "k" defines an empty slot M = sz; EMPTYKEY = k; currcnt = 0; HT = new KVpair[sz]; // Make HT of size sz for (int i=0; i void hashdict:: hashInsert(const Key& k, const E& e) { int home; // Home position for e int pos = home = h(k); // Init probe sequence for (int i=1; EMPTYKEY != (HT[pos]).key(); i++) { pos = (home + p(k, i)) % M; // probe Assert(k != (HT[pos]).key(), "Duplicates not allowed"); } KVpair temp(k, e); HT[pos] = temp; } // Search for the record with Key K template E hashdict:: hashSearch(const Key& k) const { int home; // Home position for k int pos = home = h(k); // Initial position is home slot for (int i = 1; (k != (HT[pos]).key()) && (EMPTYKEY != (HT[pos]).key()); i++) pos = (home + p(k, i)) % M; // Next on probe sequence if (k == (HT[pos]).key()) // Found it return (HT[pos]).value(); else return NULL; // k not in hash table }