What Is a Hash Table?
A Hash Table maps a key to an array index via a hash function, storing and finding values in average O(1). Python's dict, Java's HashMap, and JavaScript's Map/objects all work this way.
The one-line idea: "compute the key and go straight there." No sorting or sequential scanning — knowing the key lets you compute the location and access it directly.
The Core: Hash Function + Collision Handling
A hash function turns an arbitrary key into an integer, and % capacity makes it an array index. A good hash function scatters keys evenly across all indices.
The catch is collisions — when different keys map to the same index. Two classic fixes:
- •Chaining: make each bucket a linked list and append colliding entries.
- •Open addressing: on a collision, probe for the next empty slot by a fixed rule (e.g., linear probing).
How It Works
Step 1. Insert: put (key, value) at bucket idx = hash(key) % cap. If occupied, follow the collision rule.
Step 2. Search: compute idx the same way, then compare keys directly within that bucket to find the entry (same hash can still mean different keys).
Step 3. Resize (rehash): when the fill ratio (load factor) crosses a threshold, grow the array and re-hash all entries into the new capacity. Fewer collisions keep average performance steady.
The AlgoNote visualization shows which bucket a key lands in and how collisions get resolved, step by step.
Time and Space Complexity
| Operation | Average | Worst |
|---|---|---|
| Insert/search/delete | O(1) | O(n) |
| Space | O(n) | O(n) |
The worst case (all keys in one bucket) is O(n), but a good hash function and proper load-factor management give average O(1).
Walking Through an Example
Capacity 5, chaining, hash(k)=k.
- •insert 12 → bucket 12%5=2
- •insert 17 → bucket 17%5=2 → collides with 12 → chained in the same bucket
- •search 17 → walk the list in bucket 2 and find key 17
Common Mistakes
- •Bad hash function: clustering indices makes collisions explode and approach O(n).
- •Ignoring load factor: without resizing, buckets pile up and slow down.
- •Mutable keys: changing a key after insertion changes its hash, so you can't find it again.
See It in Action on AlgoNote
Watch a key get hashed into a bucket and a collision get resolved by chaining, step by step on AlgoNote.