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.
Visualization
Interactive visualization for Hash Table (Hash Map)
Interactive visualization with step-by-step execution
Implementation
1class HashTable<K, V> {
2 private buckets: Array<Array<[K, V]>>;
3
4 constructor(capacity: number = 16) {
5 this.buckets = new Array(capacity).fill(null).map(() => []);
6 }
7
8 private hash(key: K): number {
9 const str = String(key);
10 let hash = 0;
11 for (let i = 0; i < str.length; i++) {
12 hash = (hash << 5) - hash + str.charCodeAt(i);
13 }
14 return Math.abs(hash) % this.buckets.length;
15 }
16
17 set(key: K, value: V): void {
18 const index = this.hash(key);
19 const bucket = this.buckets[index];
20
21 for (let i = 0; i < bucket.length; i++) {
22 if (bucket[i][0] === key) {
23 bucket[i][1] = value;
24 return;
25 }
26 }
27 bucket.push([key, value]);
28 }
29
30 get(key: K): V | undefined {
31 const index = this.hash(key);
32 const bucket = this.buckets[index];
33
34 for (const [k, v] of bucket) {
35 if (k === key) return v;
36 }
37 return undefined;
38 }
39}Deep Dive
Theoretical Foundation
Hash tables use a hash function to compute an index (hash code) from the key, mapping it to a bucket in an underlying array. When multiple keys hash to the same index (collision), techniques like chaining (linked lists at each bucket) or open addressing (probing for next available slot) resolve conflicts. A good hash function distributes keys uniformly across buckets to minimize collisions.
Complexity
Time
O(1)
O(1)
O(n)
Space
O(n)
Applications
Industry Use
Database indexing and caching
Implementing Sets and Maps
Symbol tables in compilers
DNS resolution
Blockchain (merkle trees use hashing)
Password storage (with cryptographic hashes)
Deduplication in file systems
Counting frequencies in data analysis
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.
Heap (Priority Queue)
A complete binary tree data structure that satisfies the heap property: in a max heap, parent nodes are greater than or equal to children; in a min heap, parents are less than or equal to children. Heaps provide O(1) access to the maximum/minimum element and O(log n) insertion and deletion. They're typically implemented as arrays for efficiency and are the foundation of heap sort and priority queues.