Dustin Boston

/**
 * @file Chained Hash Table
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

import {LinkedList, type LinkedListNode} from "../linked-list/code.ts";

/**
 * A class representing a chained hash table.
 *
 * This implementation uses a hash function to map keys to linked lists,
 * allowing for efficient insertion, deletion, and search operations. The hash
 * table is designed to handle collisions by chaining nodes in linked lists.
 *
 * @template T - The type of the elements stored in the hash table. Defaults to
 *   `number`.
 */
export class ChainedHashTable<T extends number = number> {
  /**
   * Constructs a new ChainedHashTable instance.
   *
   * @param table - An optional initial table represented as a record where
   *   keys are strings and values are instances of ChainedHashTableLinkedList
   *   containing elements of type T.
   */
  constructor(public table: Record<string, LinkedList<T>> = {}) {}

  /**
   * Inserts a node into the chained hash table. If the hash bucket for the
   * node's key does not exist, it creates a new linked list for that bucket.
   *
   * @param node - The node to be inserted into the hash table.
   */
  insert(node: LinkedListNode<T>): void {
    if (node.value !== undefined) {
      const hash = this.hash(node.value);
      this.table[hash] ||= new LinkedList<T>();
      this.table[hash].insert(node);
    }
  }

  /**
   * Deletes a node from the chained hash table.
   *
   * @param node - The node to be deleted from the hash table.
   */
  delete(node: LinkedListNode<T>) {
    if (node.value !== undefined) {
      const hash = this.hash(node.value);
      const list = this.table[hash];
      if (list) {
        list.delete(node);
      }
    }
  }

  /**
   * Searches for a node with the specified key in the hash table.
   *
   * @param key - The key to search for in the hash table.
   * @returns The node associated with the key if found, otherwise
   *   `undefined`.
   */
  search(key: T): LinkedListNode<T> | undefined {
    const hash = this.hash(key);
    const list = this.table[hash];
    return list ? list.search(key) : undefined;
  }

  /**
   * Optimizing for a hash table with an average of ~20 nodes and 3 nodes per
   * LinkedList, we use the number 7 because it it is a prime number near
   * 20/3, and it is not divisible by the number 2.
   *
   * @returns The hash value for the key.
   * @key - The key to be hashed.
   */
  hash(key: T): number {
    return key % 7;
  }
}

import {describe, expect, test} from "bun:test";
import {LinkedListNode} from "../linked-list/code.ts";
import {ChainedHashTable} from "./code.ts";

function getChainedHashTable() {
  const hashTable = new ChainedHashTable();
  // Insert 20 nodes into 7 buckets
  for (let i = 1; i <= 20; i++) {
    hashTable.insert(new LinkedListNode(i));
  }

  return hashTable;
}

describe("Chained Hash Table", () => {
  test("Insert", () => {
    const hashTable = getChainedHashTable();
    const tableLength = Object.keys(hashTable.table).length;
    expect(tableLength).toBe(7);
  });

  test("Distribution", () => {
    const hashTable = getChainedHashTable();
    const nodeKeys = [];

    for (const key of Object.keys(hashTable.table)) {
      const linkedList = hashTable.table[key];
      let node = linkedList.sentinel.next;
      while (node !== linkedList.sentinel) {
        nodeKeys.push(node.value);
        node = node.next;
      }
    }

    expect(nodeKeys.length).toBe(20);
  });

  test("Search", () => {
    const hashTable = getChainedHashTable();
    const node = hashTable.search(14);
    expect(node?.value).toBe(14);
  });

  test("Delete", () => {
    const hashTable = getChainedHashTable();
    const node = hashTable.search(14);
    if (node === undefined) throw new Error("Search returned undefined");
    hashTable.delete(node);

    // Search for the deleted value
    const deletedNode = hashTable.search(14);
    expect(deletedNode).toBeUndefined();
  });
});