Create a Program to Implement Hash Tables in C++ Assignment Solution

Instructions

Write a program to implement hash tables in C++.

Requirements and Specifications

Source Code

#include "ExtensibleHashTable.h" #include #include #include using namespace std; // Create a hash table ExtensibleHashTable::ExtensibleHashTable(int bucketCapacity) { globalDepth = 1; capacity = 2; this->bucketCapacity = bucketCapacity; // Initialize 1 bucket which is pointed by 2 addresses buckets = new Bucket*[capacity]; buckets[0] = new Bucket(globalDepth, bucketCapacity); buckets[1] = buckets[0]; } // Copy constructor ExtensibleHashTable::ExtensibleHashTable(const ExtensibleHashTable &other) { copy(other); } // Delete all pointers ExtensibleHashTable::~ExtensibleHashTable() { dispose(); } // Copy assignment operator ExtensibleHashTable &ExtensibleHashTable::operator = (const ExtensibleHashTable &other) { if (this == &other) return *this; dispose(); copy(other); return *this; } // Insert a new value void ExtensibleHashTable::insert(int element) { int hashIndex = element % capacity; // Do regular insertion as long as it is not full if (!buckets[hashIndex]->isFull()) { buckets[hashIndex]->insert(element); return; } // Check if all of the elements in the bucket are the same as element (e.g. all duplicate) // we need to throw an exception because this will cause // infinite splitting of buckets if (buckets[hashIndex]->countOccurrence(element) == bucketCapacity) throw runtime_error("Oh snap bucket is filled with all identical values."); // If it is full, we need to double the capacity if the local depth is equal to the global depth, // otherwise we just do split buckets to the other half if (buckets[hashIndex]->getLocalDepth() >= globalDepth) { int newCapacity = capacity * 2; // The new table's global depth increases and to be used // as basis for local depths of new buckets globalDepth++; Bucket **newBuckets = new Bucket*[newCapacity]; // Retain the original buckets for the first half, those that are new will have new empty buckets for (int i = 0, j = capacity / 2; i < capacity / 2; i++, j++) { if (buckets[j] == buckets[i]) buckets[j] = new Bucket(globalDepth, bucketCapacity); } // Move the buckets to the new hash table for (int i = 0; i < capacity; i++) newBuckets[i] = buckets[i]; // The last half mirrors the buckets of the first half of the new hash table for (int i = capacity, j = 0; i < newCapacity; i++, j++) newBuckets[i] = newBuckets[j]; newBuckets[hashIndex]->increaseLocalDepth(); // The hash entry that has been fully filled, will need to have its contents re-hashed int newBucketIndex = capacity + hashIndex; newBuckets[newBucketIndex] = new Bucket(globalDepth, bucketCapacity); int numElements = newBuckets[hashIndex]->size(); int *elements = new int[numElements]; int k = 0; while (!newBuckets[hashIndex]->isEmpty()) elements[k++] = newBuckets[hashIndex]->popFront(); for (k = 0; k < numElements; k++) newBuckets[elements[k] % newCapacity]->insert(elements[k]); delete[] elements; // Finally put the new value into the new table newBuckets[element % newCapacity]->insert(element); // Delete and replace the old delete[] buckets; buckets = newBuckets; capacity = newCapacity; } else { // So in here we split the bucket, no expansion of hash table int newBucketIndex = hashIndex + (capacity / 2); buckets[newBucketIndex] = new Bucket(globalDepth, bucketCapacity); // The hash entry that has been fully filled, will need to have its contents re-hashed int numElements = buckets[hashIndex]->size(); int *elements = new int[numElements]; int k = 0; while (!buckets[hashIndex]->isEmpty()) elements[k++] = buckets[hashIndex]->popFront(); for (k = 0; k < numElements; k++) buckets[elements[k] % capacity]->insert(elements[k]); delete[] elements; // Finally put the new value into the new table buckets[element % capacity]->insert(element); } } // Print the content of the hash table void ExtensibleHashTable::print() { // Print the first half for (int i = 0; i < capacity / 2; i++) { cout << i << ": " << buckets[i] << " --> "; buckets[i]->print(); cout << endl; } // The second half of the hash table next, which usually mirrors the first half for (int i = 0, j = capacity / 2; i < capacity / 2; i++, j++) { cout << j << ": " << buckets[j] << " --> "; // No printing is necessary if it's a reflection of the last half if (buckets[j] != buckets[i]) buckets[j]->print(); cout << endl; } } // Find the element if it's on the table bool ExtensibleHashTable::find(int element) { int hashIndex = element % capacity; return buckets[hashIndex]->find(element); } // Remove all occurrence of the element bool ExtensibleHashTable::remove(int element) { int hashIndex = element % capacity; return buckets[hashIndex]->remove(element); } // Copy (deep copy) another hash table void ExtensibleHashTable::copy(const ExtensibleHashTable &other) { globalDepth = other.globalDepth; capacity = other.capacity; bucketCapacity = other.bucketCapacity; buckets = new Bucket*[capacity]; // Initialize the space for first half, the first half always have their own buckets // The second half, points to the buckets on the first half in parallel only if // it wasn't split for (int i = 0, j = capacity / 2; i < capacity / 2; i++, j++) { buckets[i] = other.buckets[i]->copy(); if (other.buckets[j] != other.buckets[i]) buckets[j] = other.buckets[j]->copy(); else buckets[j] = buckets[i]; } } // Delete everything void ExtensibleHashTable::dispose() { for (int i = 0, j = capacity / 2; i < capacity / 2; i++, j++) { if (buckets[i] != buckets[j]) { delete buckets[i]; delete buckets[j]; } else { delete buckets[i]; } } delete[] buckets; }