Hash Table

hashkey-valueO(1)-lookup

Press play to start

1const NUM_BUCKETS = 8
2const table: Array<Array<[string, string]>> = Array(NUM_BUCKETS).fill([]).map(() => [])
3function hash(key: string): number {
4  let s = 0
5  for (const c of key) s += c.charCodeAt(0)
6  return s % NUM_BUCKETS
7}
8function insert(key: string, val: string) {
9  table[hash(key)].push([key, val])  // chaining
10}
11function lookup(key: string): string | null {
12  const bucket = table[hash(key)]
13  return bucket.find(([k]) => k === key)?.[1] ?? null
14}

Step 1/0

Complexity

Best:O(1)
Average:O(1)
Worst:O(n)
Space:O(n)

Description

Maps keys to values using a hash function. Provides average O(1) insert, delete, and lookup with chaining for collision handling.

When to use

When you need fast key-value lookups. Used in caches, databases, compilers, and most modern language runtimes.