HashTable.cpp

// HashTable.cpp
#include "HashTable.h"
#include <string.h>

// Node constructor
Node::Node(int val) : value(val), next(nullptr) {}

// LinkedList constructor
LinkedList::LinkedList() : head(nullptr) {}

// LinkedList destructor
LinkedList::~LinkedList() {
    Node* current = head;
    while (current != nullptr) {
        Node* next = current->next;
        delete current;
        current = next;
    }
}

// LinkedList method to add a value at the end
void LinkedList::push_back(int number) {
    if (head == nullptr) {
        head = new Node(number);
    } else {
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = new Node(number);
    }
}

// LinkedList method to check if a value exists
bool LinkedList::contains(int number) {
    Node* current = head;
    while (current != nullptr) {
        if (current->value == number) {
            return true;
        }
        current = current->next;
    }
    return false;
}

// HashTable constructor
HashTable::HashTable(int initialCapacity) : capacity(initialCapacity), currentSize(0) {
    table = new LinkedList[capacity];
}

// HashTable destructor
HashTable::~HashTable() {
    delete[] table;
}

// Hash function
int HashTable::hashFunction(int key) {
    return key % capacity;
}

// Get the current size of the hash table
int HashTable::getSize() {
    return currentSize;
}

// Search for a number in the hash table
char* HashTable::search(int number) {
    int index = hashFunction(number);
    if (table[index].contains(number)) {
        return "SUCCESS";
    }
    return "FAILURE";
}

// Insert a number into the hash table
bool HashTable::insert(int number) {
    if (strcmp(search(number), "SUCCESS") == 0) {
        return false; // Number already exists
    }

    if (currentSize >= capacity * 0.7) {
        rehash();
    }

    int index = hashFunction(number);
    table[index].push_back(number);
    currentSize++;
    return true;
}

// Rehash the table when load factor is high
void HashTable::rehash() {
    int oldCapacity = capacity;
    capacity = 2 * capacity;

    LinkedList* oldTable = table;
    table = new LinkedList[capacity];

    currentSize = 0;
    for (int i = 0; i < oldCapacity; ++i) {
        Node* current = oldTable[i].head;
        while (current != nullptr) {
            insert(current->value);
            current = current->next;
        }
    }

    delete[] oldTable;
}