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

#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;

}