Hash Table with Chaining
Hash Table with Chaining is a fundamental data structure that uses a hash function to map keys to array indices, handling collisions by maintaining a linked list at each index. This approach provides O(1) average-case time complexity for insert, search, and delete operations. Hash tables are the backbone of dictionaries, sets, caches, and databases.
Visualization
Interactive visualization for Hash Table with Chaining
Hash Table with Chaining:
- • Collision resolution via linked lists
- • Time: O(1) average
Interactive visualization with step-by-step execution
Implementation
1class HashNode<K, V> {
2 constructor(public key: K, public value: V, public next: HashNode<K, V> | null = null) {}
3}
4
5class HashTable<K, V> {
6 private table: (HashNode<K, V> | null)[];
7 private size: number = 0;
8 private capacity: number;
9 private loadFactor: number = 0.75;
10
11 constructor(capacity: number = 16) {
12 this.capacity = capacity;
13 this.table = new Array(capacity).fill(null);
14 }
15
16 private hash(key: K): number {
17 const str = String(key);
18 let hash = 0;
19 for (let i = 0; i < str.length; i++) {
20 hash = ((hash << 5) - hash) + str.charCodeAt(i);
21 hash |= 0; // Convert to 32-bit integer
22 }
23 return Math.abs(hash) % this.capacity;
24 }
25
26 put(key: K, value: V): void {
27 if (this.size / this.capacity > this.loadFactor) {
28 this.rehash();
29 }
30
31 const index = this.hash(key);
32 let node = this.table[index];
33
34 // Update existing key
35 while (node) {
36 if (node.key === key) {
37 node.value = value;
38 return;
39 }
40 node = node.next;
41 }
42
43 // Insert new key
44 const newNode = new HashNode(key, value, this.table[index]);
45 this.table[index] = newNode;
46 this.size++;
47 }
48
49 get(key: K): V | undefined {
50 const index = this.hash(key);
51 let node = this.table[index];
52
53 while (node) {
54 if (node.key === key) return node.value;
55 node = node.next;
56 }
57
58 return undefined;
59 }
60
61 delete(key: K): boolean {
62 const index = this.hash(key);
63 let node = this.table[index];
64 let prev: HashNode<K, V> | null = null;
65
66 while (node) {
67 if (node.key === key) {
68 if (prev) prev.next = node.next;
69 else this.table[index] = node.next;
70 this.size--;
71 return true;
72 }
73 prev = node;
74 node = node.next;
75 }
76
77 return false;
78 }
79
80 private rehash(): void {
81 const oldTable = this.table;
82 this.capacity *= 2;
83 this.table = new Array(this.capacity).fill(null);
84 this.size = 0;
85
86 for (const node of oldTable) {
87 let current = node;
88 while (current) {
89 this.put(current.key, current.value);
90 current = current.next;
91 }
92 }
93 }
94}Deep Dive
Theoretical Foundation
Hash table with chaining uses an array of linked lists (or buckets). A hash function h(key) maps keys to indices in range [0, m-1] where m is table size. When multiple keys hash to same index (collision), they're stored in linked list at that index. Load factor α = n/m (elements/buckets) determines performance: average chain length is α. If α > threshold (typically 0.75), table is resized and all elements are rehashed. Good hash functions distribute keys uniformly to minimize collisions. Time: O(1) average for all operations, O(n) worst case if all keys collide into one chain. Space: O(n + m).
Complexity
Time
O(1)
O(1)
O(n)
Space
O(n)
Applications
Industry Use
Symbol tables in compilers and interpreters
Database indexing (hash indexes)
In-memory caches (LRU, LFU caches)
Associative arrays (Python dict, JavaScript Map)
Sets (Python set, Java HashSet)
DNS lookup tables
Deduplication systems
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.