HashTable.cpp

#include "HashTable.h"
#include <iostream>

using namespace std;

// Static member variables initialization

// The array of prime numbers is used to determine the size of the hash table
const int HashTable::HASH_SIZES[] = {3,   7,   11,  17,  23,  31,  41,  53,
                                     67,  83,  97,  113, 131, 151, 173, 199,
                                     227, 257, 293, 331, 373, 421, 463, 509,
                                     563, 619, 683, 751, 823, 907, 997};

// The load factor threshold is used to determine when to rehash the hash table
const double HashTable::LOAD_FACTOR_THRESHOLD = 0.7;

// TODO(student): Implement constructor to initialize the hash table
// The default hash table size is set to the first prime number in the
// HASH_SIZES array, which is 3.
// It will be resized later if necessary
HashTable::HashTable() {}

// TODO(student): Implement destructor to clean up memory
HashTable::~HashTable() {}

// TODO(student): Implement copy constructor to create a deep copy of the hash
// table
HashTable::HashTable(const HashTable &other) {}

// TODO(student): Implement assignment operator to handle deep copy
HashTable &HashTable::operator=(const HashTable &other) { return *this; }

// Hash function to map keys to bucket indices
// This function uses the modulo operator to ensure the key maps to a valid
// bucket index within the range of the number of buckets
int HashTable::hash_function(int key) { return key % buckets; }

// Function to calculate the load factor of the hash table
// The load factor is defined as the number of elements divided by the number of
// buckets It provides an indication of how full the hash table is, which can
// help in deciding when to rehash the table
double HashTable::load_factor() const {
  return static_cast<double>(count) / buckets;
}

// Function to get the current size of the hash table
int HashTable::size() const { return count; }

// TODO(student): Implement insert function to add key-value pairs
// If the load factor exceeds the threshold, rehash the table
void HashTable::insert(int key, int value) {}

// TODO(student): Implement get function to retrieve values by key
// Return -1 if the key is not found
int HashTable::get(int key) { return -1; }

// TODO(student): Implement remove function to delete key-value pairs
void HashTable::remove(int key) {}

// Rehash the hash table when the load factor exceeds a certain threshold
// TODO(student): Implement rehash function to resize the hash table
void HashTable::rehash() {
  cout << "Size is " << size() << ", Load factor is " << load_factor()
       << ". Need to resize hash table." << endl;

  // Your code to rehash the table

  cout << "Resized, (size: " << size() << ", buckets: " << buckets
       << ", load factor: " << load_factor() << ")" << endl;
}

// Overloaded operator<< to print the hash table
ostream &operator<<(ostream &os, const HashTable &ht) {
  os << "HashTable (size: " << ht.size() << ", buckets: " << ht.buckets
     << ", load factor: " << ht.load_factor() << "):\n";
  for (int i = 0; i < ht.buckets; i++) {
    HashTable::Node *current = ht.table[i];
    if (current != nullptr) {
      os << "[" << i << "]: ";
      HashTable::Node *current = ht.table[i];
      while (current != nullptr) {
        os << "(" << current->key << ", " << current->value << ") -> ";
        current = current->next;
      }
      os << "nullptr\n";
    }
  }
  return os;
}