This is the constructor for the HashTable class. It initializes a hash table with a specified size and sets up the table as a vector of vectors, allowing for collision handling with separate chaining.
HashTable(int size) : size(size)
{
table.resize(size);
}This is the destructor for the HashTable class. It ensures that all dynamically allocated memory is properly freed when the hash table is no longer in use. The C++ vector automatically handles memory deallocation, so no explicit memory cleanup is needed.
// Destructor (not strictly needed due to vector auto clean-up, but defined for good practice)
HashTable::~HashTable()
{
// Vector's destructor will handle the cleanup automatically, so nothing to do here
}The insert method adds a value to the hash table by computing the hash value (using modulo division by the size of the table) and storing it in the appropriate bucket. If the bucket is full due to collisions, insertion fails.
bool insert(const T &value)
{
if(this->lookup(value))
return false;
int bucket = std::hash<T>{}(value) % size;
table[bucket].push_back(value);
return true;
}The lookup method checks whether a given value exists in the hash table by computing its hash and searching through the list of elements in the corresponding bucket.
bool lookup(const T &value)
{
int bucket = std::hash<T>{}(value) % size;
for (auto &elem : table[bucket])
{
if (elem == value)
{
return true;
}
}
return false;
}The deleteHash method removes a value from the hash table by computing the hash value and searching for the element in the corresponding bucket.
void deleteHash(const T &value)
{
int bucket = std::hash<T>{}(value) % size;
table[bucket].remove(value);
}This main function demonstrates how to initialize the hash table, insert values, and check for the presence of values using the lookup function.
#include "HashTable.h"
#include <iostream>
#include <string>
int main()
{
// Create a hash table with a certain size
HashTable<int> ht(10);
// Test inserting elements
std::cout << "Inserting elements into the hash table..." << std::endl;
ht.insert(1);
ht.insert(2);
ht.insert(3);
ht.insert(10); // This will collide with 1 if hash function is modulo size
// Test lookup
std::cout << "Looking up elements..." << std::endl;
std::cout << "Element 2 found: " << (ht.lookup(2) ? "Yes" : "No") << std::endl;
std::cout << "Element 5 found: " << (ht.lookup(5) ? "Yes" : "No") << std::endl;
// Test deletion
std::cout << "Deleting element 2..." << std::endl;
ht.deleteHash(2);
std::cout << "Element 2 found after deletion: " << (ht.lookup(2) ? "Yes" : "No") << std::endl;
// Re-insert and test
std::cout << "Re-inserting element 2..." << std::endl;
ht.insert(2);
std::cout << "Element 2 found after re-inserting: " << (ht.lookup(2) ? "Yes" : "No") << std::endl;
return 0;
}Comments
Be the first one to comment!