Hash Tables
A data structure that implements an associative array abstract data type, a structure that can map keys to values.
Hash tables turn keys into bucket positions
A hash table uses a hash function to convert a key like "apple" into an array index. That lets lookups jump to a small part of the table instead of scanning every stored item. The main design challenge is handling collisions, where two different keys map to the same bucket.
The key is hashed into one bucket index. The highlighted path shows where the algorithm is looking or inserting.
In Chaining, collisions collect inside the same bucket. In Linear Probing, the algorithm walks through later buckets until it finds space.
Insert a few keys, then search for one that exists and one that does not.
Switch between Chaining and Linear Probing to see how collision handling changes the table layout.
Press Delete and Reset to replay the same ideas from a clean table.
Visualizing key allocation & collision strategies.
Key -> hash() -> % 8 -> bucket index
System Monitor
Status: Ready for operations
Chaining and probing handle collisions differently
Both strategies start from the same hash result. The difference is what happens next when that bucket is already occupied.
Easy to reason about because the bucket index never changes.
Search may need to scan the short chain inside one bucket.
Works well when the load factor stays moderate.
Stores everything directly in the table array.
Clusters can form when many nearby buckets are occupied.
The probe path becomes part of the search cost.
| Aspect | Chaining | Linear Probing |
|---|---|---|
| Collision handling | Store multiple keys in the same bucket as a short linked list or array. | Search for another open bucket by following a probe sequence. |
| What you see in the demo | A crowded bucket grows a visible chain. | The highlighted path steps across buckets until it finds an open slot. |
| Delete behavior | Delete the matching item from its bucket chain. | Delete from the probed slot, while remembering real implementations often need tombstones. |
| Tradeoff | Simpler collision handling, but buckets can become uneven. | Keeps data inside the table itself, but clustering can slow lookups. |
The short version
- A hash table turns a key into an array index with a hash function.
- Different keys can still land on the same index, which creates a collision.
- Chaining and linear probing solve the same collision problem in different ways.
- Good hashing plus low load factor keeps insert, search, and delete close to O(1) on average.