You are to implement 2 different hash tables, with different hashing functions.

Question

You are to implement 2 different hash tables, with different hashing functions. All of them should implement the following interface:

public interface HashTable<String,V> {

public void add(String key, V value);

public V remove(String key);

public V lookup(String key);

public Object[] getValuesList();

public void printReport();

}

The printReport() method should print to the console the following statistics:

The Load Fator, that is, the ratio of used to total number of buckets.

The longest chain in the table, that is, the maximum number of collisions for a particular bucket.

The Density Factor, that is, the ratio of elements stored elements to total number of buckets.

The Chanining Factor, that is, the average length of any chain in the table.

The 2 types of hashing functions you are to implement are:

Additive Hashing

XOR-Shift (Rotational) Hashing

The hash tables should implement resizing and rehashing. The V[] getSortedList(V[] list) method should return a sorted list with all the elements in the array.

Explanation / Answer

#include #include #include #include using namespace std; const int TABLE_SIZE = 128; class HashNode { public: int key; int value; HashNode(int key, int value) { this->key = key; this->value = value; } }; class DeletedNode:public HashNode { private: static DeletedNode *entry; DeletedNode():HashNode(-1, -1) {} public: static DeletedNode *getNode() { if (entry == NULL) entry = new DeletedNode(); return entry; } }; 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); } 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; } 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 Y
• Subjects

---

---

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