hash.cpp

#include <iostream>
#include <string>
#include "hash.h"

using namespace std;

// Constructor
HashTable::HashTable(int k) {
    // Initialize the table with k slots
    table_size = k;              
    table = new Node*[table_size];

    // Initialize each slot to nullptr
    for (int i = 0; i < table_size; ++i) {
        table[i] = nullptr;
    }
}

// Destructor
HashTable::~HashTable() {
    // Delete all the nodes in the table
    for (int i = 0; i < table_size; ++i) {
        Node* current = table[i];
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }

    delete[] table;
}

// Hash function
int HashTable::hash_function(string text) {
    // initialize the hash value
    unsigned long hash = 0;
    
    // loop through each character in the text
    for (char c : text) {
        // shift the hash value left by 15 bits, add the character
        hash = (hash << 15) + hash + c;
        // xor the hash value with the hash value shifted right by 23 bits
        hash ^= (hash >> 23);         
    }
    // return the hash value modulo the table size
    return static_cast<int>(hash % table_size);
}

// Insert a key into the hash table
void HashTable::insert(string key) {
    // initialize the index to the hash value modulo the table size
    int index = hash_function(key) % table_size;   
    string value = key;

    // create a new node with the key and value
    Node* new_node = new Node(key);        

    // insert the new node at the beginning of the slot
    new_node->next = table[index];
    table[index] = new_node;
}

// Print the contents of the first 5 slots
void HashTable::print_first_five_slots() {
    // loop through the first 5 slots
    for (int i = 0; i < 5 && i < table_size; ++i) {
        // print the slot number
        cout << "Slot " << i << ":";
        // initialize the current node to the head of the slot
        Node* current = table[i];
        // if the slot is empty, print a newline
        if (current == nullptr) {
            cout << endl;  
        } else { // otherwise, print the keys in the slot
            while (current != nullptr) {
                cout << " " << current->key;
                current = current->next;
            }
            cout << endl;  
        }
    }
}

// Print the lengths of the slots
void HashTable::print_slot_lengths() {
    // loop through each slot
    for (int i = 0; i < table_size; ++i) {
        // initialize the length of the slot to 0 and the current node to the head of the slot
        int length = 0;
        Node* current = table[i];
        // count the number of nodes in the slot
        while (current != nullptr) {
            length++;
            current = current->next;
        }
        // print the slot number and the length
        cout << "Slot " << i << ": " << length << endl;
    }
}

// Print the standard deviation
void HashTable::print_standard_deviation() {
    // initialize the mean, variance, and standard deviation
    double mean = 0.0;
    double variance = 0.0;
    double standard_deviation = 0.0;
    // loop through each slot
    for (int i = 0; i < table_size; ++i) {
        // initialize the length of the slot to 0 and the current node to the head of the slot
        int length = 0;
        Node* current = table[i];
        // count the number of nodes in the slot
        while (current != nullptr) {
            length++;
            current = current->next;
        }
        // add the length to the average length
        mean += length;
    }
    // calculate the average length
    mean = mean / table_size;

    // loop through each slot
    for (int i = 0; i < table_size; ++i) {
        // initialize the length of the slot to 0 and the current node to the head of the slot
        int length = 0;
        Node* current = table[i];
        // count the number of nodes in the slot
        while (current != nullptr) {
            length++;
            current = current->next;
        }
        // add the squared difference between the length and the mean to the variance
        variance += pow((length - mean),2);
    }
    // calculate the standard deviation from the variance
    standard_deviation = sqrt(variance / table_size);

    cout <<  standard_deviation << endl;
}