HashTable.h

#ifndef HASHTABLE_H
#define HASHTABLE_H

// Hash table implementation using separate chaining
// This header file defines the HashTable class, which provides methods for
// inserting, retrieving, and removing key-value pairs. It also includes
// methods for calculating the load factor and resizing the hash table when
// necessary. The hash table uses an array of linked lists to handle
// collisions, and it employs a hash function to map keys to bucket indices.

#include <iostream>
using namespace std;

class HashTable {
  friend ostream &operator<<(ostream &os, const HashTable &ht);

private:
  // The array of prime numbers is used to determine the size of the hash table
  static const int HASH_SIZES[];

  // Load factor threshold is used to determine when to rehash the hash table
  static const double LOAD_FACTOR_THRESHOLD;

  // Number of buckets in the hash table
  int buckets;

  // Number of elements in the hash table
  int count;

  // Each bucket in the hash table is represented by a linked list
  struct Node {
    int key;
    int value;
    Node *next;
  };

  // Array of pointers to the head of each linked list (bucket)
  Node **table;

  // Hash function to map keys to bucket indices
  int hash_function(int key);

  // Rehash the hash table when the load factor exceeds a certain threshold
  void rehash();

public:
  // Constructor to initialize the hash table with a default size
  HashTable();

  // Destructor to clean up memory
  ~HashTable();

  // Copy constructor
  HashTable(const HashTable &other);

  // Assignment operator
  HashTable &operator=(const HashTable &other);

  // Get the current size of the hash table
  int size() const;

  // Calculate the load factor of the hash table
  double load_factor() const;

  // Insert a key-value pair into the hash table
  void insert(int key, int value);

  // Retrieve a value by key from the hash table
  // Returns -1 if the key is not found
  int get(int key);

  // Remove a key-value pair from the hash table
  void remove(int key);
};

#endif