Design the following hash table data structure in C++: The initial table size is

Question

Design the following hash table data structure in C++: The initial table size is a fix number. The key values are numbers. After inserting a certain number of keys in the hash table the number of elements in the hash table the number of elements become n lg n (n is the size of hash table) at this point a new table with the larger size will be created and the key-value pairs that are stored in the previous hash table will be mapped (Not copy) to this table. If the number of entries to one hash bucket is smaller than 10 then a linked list will be created and the values will be stored in the linked list. Otherwise the linked list will be replaced by a BS-tree and the values will be stored in the BS-tree. Tip: It is important to know that your hashtable should not be a simple array of pointers to linkedlist. It should be array of more complicated type.

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 D
• Subjects

---

---

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