Hash Tables Data Structure in TypeScript: A Comprehensive Guide

A hash table maps keys to values with O(1) average-case lookups. That's the pitch. Here's how it actually works.

Take a key. Run it through a hash function to produce a numeric index. Store the value at that index in an array. To retrieve it, hash the key again, jump to that index, grab the value. No scanning, no searching.

The catch: two different keys can produce the same index. That's a collision, and how you handle it determines the hash table's real-world performance.

Implementation

class HashTable<K, V> {
  private buckets: [K, V][][];
  private size: number;

  constructor(capacity = 16) {
    this.buckets = new Array(capacity).fill(null).map(() => []);
    this.size = 0;
  }

  private hash(key: K): number {
    const str = String(key);
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) % this.buckets.length;
    }
    return hash;
  }

  set(key: K, value: V): void {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    const existing = bucket.find(([k]) => k === key);
    if (existing) {
      existing[1] = value;
    } else {
      bucket.push([key, value]);
      this.size++;
    }
  }

  get(key: K): V | undefined {
    const index = this.hash(key);
    const pair = this.buckets[index].find(([k]) => k === key);
    return pair ? pair[1] : undefined;
  }

  delete(key: K): boolean {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    const idx = bucket.findIndex(([k]) => k === key);
    if (idx === -1) return false;
    bucket.splice(idx, 1);
    this.size--;
    return true;
  }

  getSize(): number {
    return this.size;
  }
}

const table = new HashTable<string, number>();
table.set('apple', 5);
table.set('banana', 8);
console.log(table.get('apple'));  // 5
table.delete('banana');
console.log(table.get('banana')); // undefined

Collision Resolution

When two keys hash to the same index, you need a strategy:

Chaining (used above): Each bucket is a list. Colliding entries coexist in the same bucket. Simple and works well when the load factor stays low.

Open addressing: When a collision occurs, probe for the next available slot. Linear probing, quadratic probing, and double hashing are variants. (Open Addressing)

Load Factor and Resizing

The load factor is size / capacity. As it increases, collisions become more frequent and performance degrades toward O(n).

Good hash table implementations resize (usually double the capacity) when the load factor exceeds a threshold (commonly 0.75). This keeps operations close to O(1).

Performance

Worst case happens when every key hashes to the same index. A good hash function makes this extremely unlikely.

Where Hash Tables Show Up

• Object/Map in JavaScript: {} and Map are hash tables under the hood.
• Caching: Store computed results by key for instant retrieval.
• Database indexing: Hash indexes enable O(1) lookups for exact-match queries.
• Symbol tables: Compilers use hash tables to look up variable names during compilation.
• Deduplication: Track seen values for O(1) duplicate detection.
• Counting frequencies: Map elements to their counts.

Related articles:

• Hashing Algorithm
• Implementing HashMap

Hash tables are arguably the most important data structure in practical programming. If you need fast key-based access and don't need ordered iteration, a hash table is almost always the answer.