// Created by Sumit Ch Momin #include #include using namespace std; class HASH_NODE { public: string key; string value; HASH_NODE(string key, string value) { this->key = key; this->value = value; } }; class HASH_TABLE { public: int capacity = 6; int size = 0; vector** hashTable = new vector*[capacity]; HASH_TABLE() { for (unsigned int i = 0; i < capacity; i++) { hashTable[i] = new vector; } } // returns the current size of the hash table int getSize() { return size; } // returns the current capacity of the hash table int getCapacity() { return capacity; } // return true if the hash table is empty else false bool isEmpty() { return size == 0; } // generates hash values int hashFunction(string key) { int hash = 1; for (unsigned int i = 0; i < key.size(); i++) { hash *= key[i]; } return hash % capacity; } // search a value and returns the value if key already present in the hash table bool check(string key) { int hash = hashFunction(key); for (unsigned int i = 0; i < hashTable[hash]->size(); i++) { if (key == hashTable[hash]->at(i)->key) { //return hashTable[hash]->at(i)->value; return true; } } return false; } // update the value of a key void update(string key, string newValue) { int hash = hashFunction(key); for (unsigned int i = 0; i < hashTable[hash]->size(); i++) { if (key == hashTable[hash]->at(i)->key) { hashTable[hash]->at(i)->value = newValue; } } } // adds a new value void addData(string key, string value) { bool c = check(key); if (c) { update(key, value); } else { int hash = hashFunction(key); hashTable[hash]->push_back(new HASH_NODE(key, value)); size++; } int lf = loadFactor(); if (lf > 50) { loadFactorControl(); } } // removes a given key, value pair from hash table void removeData(string key) { bool c = check(key); if (c) { int hash = hashFunction(key); for (unsigned int i = 0; i < hashTable[hash]->size(); i++) { if (key == hashTable[hash]->at(i)->key) { //hashTable[hash]->erase(hashTable[hash]->at(i)); hashTable[hash]->at(i) = NULL; break; } } size--; } else { cout << "Key " << key << " not found.." << endl; } } // displays all the values present in the hash table void display() { for (unsigned int i = 0; i < capacity; i++) { cout << i + 1 << " :"; for (unsigned int j = 0; j < hashTable[i]->size(); j++) { if (hashTable[i]->at(j) != NULL) { cout << hashTable[i]->at(j)->value << ", "; } } cout << endl; } } // returns load factor value int loadFactor() { return ((size * 100) / capacity); } // creates new array of bigger size once the load factor exceeds certain limits void loadFactorControl() { cout << "Increasing the size of the array from " << capacity << " to " << capacity * 2 << endl << endl; // copying all the keys and values from the old array to a yemporary array HASH_NODE** temp = new HASH_NODE*[size]; int count = 0; for (unsigned int i = 0; i < capacity; i++) { for (unsigned int j = 0; j < hashTable[i]->size(); j++) { temp[count++] = hashTable[i]->at(j); } } capacity *= 2; vector** temp2 = hashTable; hashTable = NULL; hashTable = new vector*[capacity]; for (unsigned int i = 0; i < capacity; i++) { hashTable[i] = new vector; } int s = size; size = 0; // add all the old values to the new array for (unsigned int i = 0; i < s; i++) { this->addData(temp[i]->key, temp[i]->value); } delete [] temp2; } // returns value for a given key string getValue(string key) { if (check(key)) { int hash = hashFunction(key); for (unsigned int i = 0; i < hashTable[hash]->size(); i++) { if (hashTable[hash]->at(i)->key == key) { return hashTable[hash]->at(i)->value; } } } else { string s = "no key found"; return s; } } }; int main() { HASH_TABLE HT; HT.addData("key1", "book"); HT.addData("key2", "mobile phone"); HT.addData("key3", "laptop"); HT.addData("key9", "Mathematics"); //HT.removeData("key1"); cout << "The value of key9 is " << HT.getValue("key9") << endl; cout << endl << endl; //HT.loadFactorControl(); HT.display(); return 0; }