C++ You will write the code to resize a hash table. Modify the code below. Increase the hash table size from 10 to 50. Write a function to calculate the greatest number of key-value pairs in any bucket in the hash table. Write a function to resize the hash table. Calculate the size of the resized hash table by selecting the next prime number that is greater than or equal to the maximum number of buckets in the original hash table multiplied by 2. (next prime number ≥ (N * 2)). Resize when any list in any bucket contains more than four key-value pairs. Update the control function to randomly generate 200 key-value pairs and add them to the hash table. If any bucket contains more than four key-value pairs, resize the hash table. Print the hash table before it is resized and after it is resized. using namespace std; class HashTable{ private: static int const BUCKET_CNT = 10; list> bucket[BUCKET_CNT]; public: bool isEmpty(); int hashFunction(int key); void InsertItem(int key, string value); void RemoveItem(int key); void PrintTable(); }; bool HashTable::isEmpty() { int sum{}; for (int i{}; i < BUCKET_CNT; i++) { sum += bucket[i].size(); } if (!sum) { return true; } return false; } int HashTable::hashFunction(int key) { return key % BUCKET_CNT; } void HashTable::InsertItem(int key, string value) { int hashValue = hashFunction(key); auto& buList = bucket[hashValue]; auto buItr = begin(buList); bool keyExists = false; for (; buItr != end(buList); buItr++) { if (buItr->first == key) { keyExists = true; buItr->second = value; cout << "[WARNING] Key exists. Value replaced." << endl; break; } } if (!keyExists) { buList.emplace_back(key, value); } return; } void HashTable::RemoveItem(int key) { int hashValue = hashFunction(key); auto& buList = bucket[hashValue]; auto buItr = begin(buList); bool keyExists = false; for (; buItr != end(buList); buItr++) { if (buItr->first == key) { keyExists = true; buItr = buList.erase(buItr); break; } } if (!keyExists) { cout << "[WARNING] Key not found. Pair not removed." << endl; } return; } void HashTable::PrintTable() { for (int i{}; i < BUCKET_CNT; i++) { if (bucket[i].size() == 0) continue; auto buItr = bucket[i].begin(); for (; buItr != bucket[i].end(); buItr++) { cout << "[INFO] Bucket: " << i; cout << " Key: " << buItr->first; cout << " Value: " << buItr->second << endl; } } return; } int main() { HashTable HT; HT.InsertItem(101, "Dennis"); HT.InsertItem(201, "Wendy"); HT.InsertItem(102, "Travis"); HT.InsertItem(202, "Lexi"); HT.InsertItem(302, "Addie"); HT.InsertItem(402, "Jaxon"); HT.InsertItem(103, "Scott"); HT.InsertItem(203, "Emily"); HT.InsertItem(303, "Owen"); HT.InsertItem(403, "Greg"); HT.InsertItem(104, "Tyler"); HT.InsertItem(204, "Jasmine"); HT.PrintTable(); HT.RemoveItem(204); HT.RemoveItem(100); HT.PrintTable(); return 0; }
C++
You will write the code to resize a hash table. Modify the code below.
- Increase the hash table size from 10 to 50.
- Write a function to calculate the greatest number of key-value pairs in any bucket in the hash table.
- Write a function to resize the hash table. Calculate the size of the resized hash table by selecting the next prime number that is greater than or equal to the maximum number of buckets in the original hash table multiplied by 2. (next prime number ≥ (N * 2)).
- Resize when any list in any bucket contains more than four key-value pairs.
- Update the control function to randomly generate 200 key-value pairs and add them to the hash table. If any bucket contains more than four key-value pairs, resize the hash table. Print the hash table before it is resized and after it is resized.
using namespace std;
class HashTable{ private: static int const BUCKET_CNT = 10; list<pair<int, string>> bucket[BUCKET_CNT]; public: bool isEmpty(); int hashFunction(int key); void InsertItem(int key, string value); void RemoveItem(int key); void PrintTable(); }; bool HashTable::isEmpty() { int sum{}; for (int i{}; i < BUCKET_CNT; i++) { sum += bucket[i].size(); } if (!sum) { return true; } return false; } int HashTable::hashFunction(int key) { return key % BUCKET_CNT; } void HashTable::InsertItem(int key, string value) { int hashValue = hashFunction(key); auto& buList = bucket[hashValue]; auto buItr = begin(buList); bool keyExists = false; for (; buItr != end(buList); buItr++) { if (buItr->first == key) { keyExists = true; buItr->second = value; cout << "[WARNING] Key exists. Value replaced." << endl; break; } } if (!keyExists) { buList.emplace_back(key, value); } return; } void HashTable::RemoveItem(int key) { int hashValue = hashFunction(key); auto& buList = bucket[hashValue]; auto buItr = begin(buList); bool keyExists = false; for (; buItr != end(buList); buItr++) { if (buItr->first == key) { keyExists = true; buItr = buList.erase(buItr); break; } } if (!keyExists) { cout << "[WARNING] Key not found. Pair not removed." << endl; } return; } void HashTable::PrintTable() { for (int i{}; i < BUCKET_CNT; i++) { if (bucket[i].size() == 0) continue; auto buItr = bucket[i].begin(); for (; buItr != bucket[i].end(); buItr++) { cout << "[INFO] Bucket: " << i; cout << " Key: " << buItr->first; cout << " Value: " << buItr->second << endl; } } return; } int main() { HashTable HT; HT.InsertItem(101, "Dennis"); HT.InsertItem(201, "Wendy"); HT.InsertItem(102, "Travis"); HT.InsertItem(202, "Lexi"); HT.InsertItem(302, "Addie"); HT.InsertItem(402, "Jaxon"); HT.InsertItem(103, "Scott"); HT.InsertItem(203, "Emily"); HT.InsertItem(303, "Owen"); HT.InsertItem(403, "Greg"); HT.InsertItem(104, "Tyler"); HT.InsertItem(204, "Jasmine"); HT.PrintTable(); HT.RemoveItem(204); HT.RemoveItem(100); HT.PrintTable(); return 0; }
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
