Hash tables and collision handling
A hash table converts a key into an array index with a hash function, giving average O(1) lookup, insertion, and deletion. That single property is why hash maps appear in more interview solutions than any other structure — they turn nested scans into single passes.
The interesting part is what happens when two keys land in the same bucket. The visualizer shows both strategies: separate chaining, which stores a list per bucket, and open addressing, which probes for the next free slot.
Time and space complexity
| Operation | Average | Worst | Notes |
|---|---|---|---|
| Insert | O(1) | O(n) | Worst case when all keys collide |
| Lookup | O(1) | O(n) | Degrades to a scan of one bucket |
| Delete | O(1) | O(n) | Open addressing needs tombstones |
| Resize / rehash | O(n) | O(n) | Triggered past the load factor |
| Storage | O(n) | O(n) | — |
How to use this visualizer
Choose a collision strategy: separate chaining or linear probing.
Insert keys and watch the hash function map each one to a bucket.
Force a collision and follow how the strategy resolves it.
Watch the load factor climb and trigger a resize.
Frequently asked questions
A collision occurs when two distinct keys hash to the same bucket index. Separate chaining stores a linked list or tree per bucket and appends the new entry. Open addressing instead probes for another slot — linearly, quadratically, or by double hashing. Chaining degrades more gracefully under load; open addressing is more cache-friendly when the table is sparse.
With a good hash function and a bounded load factor, keys spread evenly so each bucket holds a constant number of entries, making lookup constant time. If every key hashes to the same bucket — through a poor hash function or adversarial input — the table degenerates into a single list and lookup becomes a linear scan.
The load factor is the ratio of stored entries to buckets. As it rises, collisions become frequent and operations drift away from O(1). Most implementations resize — allocating a larger bucket array and rehashing every key — once the load factor passes a threshold, commonly 0.75.