C++ question: Using a standard dictionary, and a table size that approximates a

Question

C++ question:

Using a standard dictionary, and a table size that approximates a load factor of 1,
compare the number of collisions produced by the hash function in Figure 5.4 and
the hash function in Figure 5.55. (Please program in C++ with explanations)

/** Figure 5.4
* A hash routine for string objects.
*/
unsigned int hash( const string & key, int tableSize )
{
unsigned int hashVal = 0;

for( char ch : key )
hashVal = 37 * hashVal + ch;

return hashVal % tableSize;
}

/** Figure 5.55
* FNV-1a hash routine for string objects.
*/
unsigned int hash( const string & key, int tableSize )
{
unsigned int hashVal = 2166136261;

for( char ch : key )
hashVal = ( hashVal ˆ ch )* 16777619;

return hashVal % tableSize;
}

Explanation / Answer

#include #include #include #include using namespace std; const int TABLE_SIZE = 128; /* * HashEntry Class Declaration */ class HashEntry { public: int key; int value; HashEntry(int key, int value) { this->key = key; this->value = value; } }; /* * HashMap Class Declaration */ class HashMap { private: HashEntry **table; public: HashMap() { table = new HashEntry * [TABLE_SIZE]; for (int i = 0; ikey != key) { hash = HashFunc(hash + 1); } if (table[hash] != NULL) delete table[hash]; table[hash] = new HashEntry(key, value); } /* * Search Element at a key */ int Search(int key) { int hash = HashFunc(key); while (table[hash] != NULL && table[hash]->key != key) { hash = HashFunc(hash + 1); } if (table[hash] == NULL) return -1; else return table[hash]->value; } /* * Remove Element at a key */ void Remove(int key) { int hash = HashFunc(key); while (table[hash] != NULL) { if (table[hash]->key == key) break; hash = HashFunc(hash + 1); } if (table[hash] == NULL) { cout

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.