Hash Table Search

Hashing is a technique to convert a range of key-value pairs into a range of indices of an array. It allows for nearly instantaneous data retrieval, providing $O(1)$ average-case performance for search, insert, and delete operations.

Load Factor

0.00

Bucket 0Hash(K) % 13

Empty

Bucket 1Hash(K) % 13

Empty

Bucket 2Hash(K) % 13

Empty

Bucket 3Hash(K) % 13

Empty

Bucket 4Hash(K) % 13

Empty

Bucket 5Hash(K) % 13

Empty

Bucket 6Hash(K) % 13

Empty

Bucket 7Hash(K) % 13

Empty

Bucket 8Hash(K) % 13

Empty

Bucket 9Hash(K) % 13

Empty

Bucket 10Hash(K) % 13

Empty

Bucket 11Hash(K) % 13

Empty

Bucket 12Hash(K) % 13

Empty

How Hashing Works

A Hash Table uses a mathematical formula (the hash function) to map a search key into an index within an underlying array. This allows us to jump directly to the data we need, bypasssing the need for comparisons like those found in Binary Search.

Hash Function

A good hash function should distribute keys uniformly across the table to minimize collisions. The common formula used is:
Index = Hash(Key) % Table_Size

Collision Resolution

When two keys hash to the same index, a "collision" occurs. This visualization uses Separate Chaining, where each bucket stores a linked list of all items mapped to that index.

Performance Metrics

Time Complexity

Avg: O(1)
Worst: O(n)

Space Complexity

O(n + k)
(k = table size)

Load Factor (α)

Ratio of items to table size. Above 0.7 usually triggers a resize.

Quick Reference

Search: Calculates hash, jumps to bucket, traverses list.
Insert: Calculates hash, adds to bucket (usually O(1)).
Remove: Calculates hash, finds in bucket, unlinks node.

Code Breakdown

"Separate Chaining" logic implemented in this demo.

Pseudocode

JavaScript

1// Basic Search logic
2function search(key) {
3  const index = hash(key) % size;
4  const bucket = table[index];
5 
6  for (let item of bucket) {
7    if (item.key === key) return item;
8  }
9  return null;
10}

Did you know?

Hash tables power most of the world's caches, databases, and language features (like JS Objects or Python Dictionaries).

Full Implementation

Python (Dictionary-like)

Pseudocode

Python

1class HashTable:
2    def __init__(self, size=13):
3        self.size = size
4        self.table = [[] for _ in range(size)]
5 
6    def _hash(self, key):
7        return hash(key) % self.size
8 
9    def insert(self, key):
10        idx = self._hash(key)
11        if key not in self.table[idx]:
12            self.table[idx].append(key)
13 
14    def search(self, key):
15        idx = self._hash(key)
16        return key in self.table[idx]
17 
18    def remove(self, key):
19        idx = self._hash(key)
20        if key in self.table[idx]:
21            self.table[idx].remove(key)

TypeScript Example

Pseudocode

TypeScript

1class HashTable<T> {
2  private buckets: T[][];
3  private size: number;
4 
5  constructor(size = 13) {
6    this.size = size;
7    this.buckets = Array.from({ length: size }, () => []);
8  }
9 
10  private hash(key: string): number {
11    let h = 0;
12    for (let i = 0; i < key.length; i++) {
13      h = (h * 31 + key.charCodeAt(i)) >>> 0;
14    }
15    return h % this.size;
16  }
17 
18  public insert(key: string, val: T): void {
19     // implementation...
20  }
21}

How Hashing Works

Hash Function

A good hash function should distribute keys uniformly across the table to minimize collisions. The common formula used is:
Index = Hash(Key) % Table_Size

Collision Resolution

When two keys hash to the same index, a "collision" occurs. This visualization uses Separate Chaining, where each bucket stores a linked list of all items mapped to that index.

1// Basic Search logic 2function search(key) { 3 const index = hash(key) % size; 4 const bucket = table[index]; 5 6 for (let item of bucket) { 7 if (item.key === key) return item; 8 } 9 return null; 10}

Full Implementation

Python (Dictionary-like)

Pseudocode

Python

1class HashTable:
2    def __init__(self, size=13):
3        self.size = size
4        self.table = [[] for _ in range(size)]
5 
6    def _hash(self, key):
7        return hash(key) % self.size
8 
9    def insert(self, key):
10        idx = self._hash(key)
11        if key not in self.table[idx]:
12            self.table[idx].append(key)
13 
14    def search(self, key):
15        idx = self._hash(key)
16        return key in self.table[idx]
17 
18    def remove(self, key):
19        idx = self._hash(key)
20        if key in self.table[idx]:
21            self.table[idx].remove(key)

TypeScript Example

Pseudocode

TypeScript

1class HashTable<T> {
2  private buckets: T[][];
3  private size: number;
4 
5  constructor(size = 13) {
6    this.size = size;
7    this.buckets = Array.from({ length: size }, () => []);
8  }
9 
10  private hash(key: string): number {
11    let h = 0;
12    for (let i = 0; i < key.length; i++) {
13      h = (h * 31 + key.charCodeAt(i)) >>> 0;
14    }
15    return h % this.size;
16  }
17 
18  public insert(key: string, val: T): void {
19     // implementation...
20  }
21}