Chained Hash Table

/**
 * @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.
 */

/**
 * Represents a node in a chained hash table.
 *
 * @template T - The type of the key to be stored in the node.
 */
class ChainedHashTableNode<T> {
  /**
   * Creates a new instance of a ChainedHashTableNode.
   *
   * @param key - The key to be stored in the node.
   * @param [next] - The next node in the chain.
   * @param [previous] - The previous node in the chain.
   */
  constructor(
    public key: T,
    public next?: ChainedHashTableNode<T>,
    public previous?: ChainedHashTableNode<T>,
  ) {}
}

/**
 * Implements a linked list used in a chained hash table.
 *
 * @template T - The type of elements stored in the linked list.
 */
class ChainedHashTableLinkedList<T> {
  /**
   * Constructs a new instance of the ChainedHashTable class.
   *
   * @param head - The root or first node in the linked list.
   * @param tail - The last node in the linked list.
   */
  constructor(
    public head?: ChainedHashTableNode<T>,
    public tail?: ChainedHashTableNode<T>,
  ) {}

/**
   * Searches for a node with the specified key in the hash table.
   *
   * @param k - The key to search for.
   * @returns The node with the specified key, or `undefined` if not found.
   */
  search(k: T): ChainedHashTableNode<T> | undefined {
    let x = this.head;
    while (x !== undefined && x.key !== k) {
      x = x.next;
    }

return x;
  }

/**
   * Inserts a new node at the beginning of the chained hash table.
   *
   * @param x - The node to be inserted.
   */
  insert(x: ChainedHashTableNode<T>): void {
    x.next = this.head;
    if (this.head !== undefined) {
      this.head.previous = x;
    }

this.head = x;
    x.previous = undefined;
  }

/**
   * Deletes a node from the chained hash table.
   *
   * @param x - The node to be deleted from the hash table.
   */
  delete(x: ChainedHashTableNode<T>): void {
    if (x.previous === undefined) {
      this.head = x.next;
    } else {
      x.previous.next = x.next;
    }

if (x.next !== undefined) {
      x.next.previous = x.previous;
    }
  }
}

/**
 * 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`.
 */
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, ChainedHashTableLinkedList<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: ChainedHashTableNode<T>): void {
    const hash = this.hash(node.key);
    this.table[hash] ||= new ChainedHashTableLinkedList<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: ChainedHashTableNode<T>) {
    const hash = this.hash(node.key);
    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): ChainedHashTableNode<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;
  }
}

// Usage
(() => {
  const hashTable = new ChainedHashTable();

// Insert 20 nodes into 7 buckets
  for (let i = 1; i <= 20; i++) {
    hashTable.insert(new ChainedHashTableNode(i));
  }

if (Object.keys(hashTable.table).length !== 7) {
    throw new Error('Hash table should have 7 buckets');
  }

const node = hashTable.search(14);
  if (node === undefined) throw new Error('Search returned undefined');
  if (node.key !== 14) throw new Error('Search returned incorrect node');

hashTable.delete(node);
  if (hashTable.search(14) !== undefined) {
    throw new Error('Node was not deleted');
  }
})();