Data Structures in TypeScript - Hash Table

A Hash table is a data structure with a highly efficient lookup, which store key values pairs. Each key is generated by a hash function based on the value being stored. Also, the hash table has to handle collisions that happens when the same key is generated for different values.

  [1]
  [2] = ["A"] // value A store in the key 2
  [3]
  [4] = ["B"] 

Whenever we need to retrieve a value we use its key, so this operation will be done in a constant time, considering that a good hash function is being used and the values are uniformly distributed across the hash table, which means fewer collisions. Inserting a value into a hash table, is pretty straightforward, just generate the key, and use it to find the right position in the hash table.

A basic hash function

A hash function should be easy to compute because it will be used whenever is necessary to insert or search a value, also this function has to provide uniform distribution across the hash table in order to avoid clustering which would affect the hash table performance.

For this example, our hash table will store strings, so the hash function will sum the ASCII values of each character, then it will divide that sum by the size of the hash table and get the reminder using the modulo operator (%), the result will be the key.

// hash function
hash(value: string): number {
  const sum = value
      .split("")
      .reduce((acc: number, char: string) => acc + char.charCodeAt(0), 0);

  // force sum into the hash table size
  return sum % this.size;
}

How to handle collisions

Collisions happen when the same key is generated for different values, a common strategy to handle collisions is Separate chaining:, instead of storing the value directly in the hash table, we store it in a Linked List, and the generated key points to that Linked list. If there were too many collisions, searching a value would take a linear time complexity O(n) instead of O(1), this time can be reduced to O(log n) using another data structure like a Binary Search Tree.

[1]
[2] = ["A"] ->
[3]
[4] = ["B"] -> ["C"] -> ["D"] -> // collisions happened, so these 3 values are in the same linked list

Implementation

Here is an implementation of a Hash Table in TypeScript

class HashTable {
  private size: number;
  private data: LinkedList<string>[] = [];

  constructor(size: number) {
    this.size = size;
  }

  hash(value: string): number {
    const sum = value
      .split("")
      .reduce((acc: number, char: string) => acc + char.charCodeAt(0), 0);

    // force sum into the hash table size
    return sum % this.size;
  }

  insert(value: string): void {
    const index = this.hash(value);

    if (!this.data[index]) {
      this.data[index] = new LinkedList<string>(
        (a: string, b: string) => a === b
      );
    }

    this.data[index].append(value);
  }

  search(value: string): string | null {
    const index = this.hash(value);

    if (this.data[index]) {
      return this.data[index].search(value)!.data;
    }

    return null;
  }
}

const hashTable = new HashTable(10);

hashTable.insert("aabb");
hashTable.insert("bbcc");
hashTable.insert("abcd");

console.log(hashTable.search("abcd"));