#include "Hash.h" #include using namespace std; HashEntry::HashEntry() { key = ""; value = -1; next = NULL; } HashEntry::HashEntry(string k, int val) { key = k; value = val; } // Class to represent entire hash table HashTable::HashTable(int s) { bucket = new HashEntry * [s]; //Initialise all elements of array as NULL for (int i = 0; i < s; i++) bucket[i] = NULL; slots = s; size = 0; } int HashTable::getSize() { // return size of table return size; } bool HashTable::isEmpty() { // if table is empty return true return getSize() == 0; } int HashTable::getIndex(string key) { //hashCode is a built in function of Strings //takes key and size of the list int Key = 0; for (int i = 0; i < key.length(); i++) { Key = 37 * Key + key[i]; } if (Key < 0) Key *= -1; return Key % slots; } void HashTable::insert(string key, int value) { // Apply hash function to find index for given key int hashIndex = getIndex(key); //cout << "hashIndex : " << hashIndex < next != NULL) { temp = temp -> next; } temp -> next = new HashEntry(key, value); size++; } } void HashTable::display() { HashEntry * temp; for (int i = 0; i < slots; i++) { if (bucket[i] != NULL) { cout << "HashIndex : " << i << " "; temp = bucket[i]; while (temp != NULL) { cout << "(key = " << temp -> key << " , value = " << temp -> value << " )"; temp = temp -> next; } } cout << endl; } } void HashTable::resize() { cout << "resize" << endl; slots *= 2; HashEntry ** tempBucket = new HashEntry * [slots]; int hashIndex; HashEntry * tmp; for (int i = 0; i < slots; i++) tempBucket[i] = NULL; HashEntry * temp; for (int i = 0; i < slots / 2; i++) { if (bucket[i] != NULL) { temp = bucket[i]; while (temp != NULL) { hashIndex = getIndex(temp -> key); if (tempBucket[hashIndex] == NULL) tempBucket[hashIndex] = new HashEntry(temp -> key, temp -> value); else { //find next free space tmp = tempBucket[hashIndex];; while (tmp -> next != NULL) { tmp = tmp -> next; } tmp -> next = new HashEntry(temp -> key, temp -> value); } temp = temp -> next; } } } bucket = tempBucket; } int HashTable::search(string key) { int hashIndex = getIndex(key); if (bucket[hashIndex] == NULL) { cout << "Value Not Found!" << endl; return -1; } if (bucket[hashIndex] -> key == key) { return bucket[hashIndex] -> value; } else { //find next free space HashEntry * temp = bucket[hashIndex]; while (temp != NULL) { if (temp -> key == key) { return temp -> value; } temp = temp -> next; } cout << "Value Not Found!" << endl; return -1; } } void HashTable::Delete(string key) { int hashIndex = getIndex(key); if (bucket[hashIndex] == NULL) { cout << "Value To Be Deleted Not Found!" << endl; return; } if (bucket[hashIndex] -> key == key) { if (bucket[hashIndex] -> next != NULL) { bucket[hashIndex] = bucket[hashIndex] -> next; } else { bucket[hashIndex] = NULL; } } else { //find next free space HashEntry * temp = bucket[hashIndex]; HashEntry * prev = bucket[hashIndex]; while (temp != NULL) { if (temp -> key == key) { if (temp -> next != NULL) { prev -> next = temp -> next; temp = temp -> next; } else prev -> next = NULL; return; } prev = temp; temp = temp -> next; } cout << "Value to be deleted not Found!" << endl; } }

Introduction to Arrays

Introduction to Linked Lists

Introduction to Stacks/Queues

Introduction to Graphs

Introduction to Trees

Trie

Introduction to Heap

Introduction to Hashing

Conclusion

A Quick Overview of Hash Tables

Complete Implementation #