Chained Hash Table | The Personal Website of Dustin Boston

A Chained Hash Table is a data structure that resolves collisions using linked lists. Each slot in the hash table array points to a chain (linked list) that stores all elements hashing to the same index. When inserting, searching, or deleting an element, the algorithm hashes the key to determine the appropriate slot and traverses the corresponding chain to perform the operation.

code.ts

/**
 * @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;
  }
}

test.ts

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();
  });
});