Hash function
h(k) = ((k mod m) + m) mod m
k is the integer key; m is the current table capacity. This normalization keeps the bucket index between 0 and m − 1, even when k is negative. With separate chaining, place the key in bucket h(k).
Hash Table Collision & Load Factor Lab
Explore how a hash function maps keys into a finite table, how collisions are resolved, and why performance changes as the load factor rises. Compare separate chaining with linear probing, then watch the table grow and rehash when it crosses its load threshold.
Step inserts one key and reports its probes. Reset returns to the empty table using the entered key sequence.
Keys inserted: 0 / 8
Capacity: 7
Load factor: 0.00
Collisions: 0
Probes this key: —
Insertion trace
Press Step to place the first key.
Input sequence
Table view
The displayed bucket indices show where the current keys reside. A resize changes capacity m, so the hash values are recomputed for every key.
The table begins with seven empty buckets.
Linear probing function
p(k, i) = (h(k) + i) mod m
Start with probe count i = 0. If that slot is occupied, increment i and check again, up to m positions. The first open slot receives k. If every slot is full, the table must grow before insertion.
Example · capacity m = 7
For k = 16, h(16) = 2. If bucket 2 already contains 9, separate chaining adds 16 to that bucket’s chain.
Linear probe sequence
p(16, 0) = 2 → occupied
p(16, 1) = 3 → next slot
If slot 3 is empty, insert 16 there after two probes.
What load factor means
For chaining, α = number of keys ÷ buckets and may exceed 1. For open addressing, each slot holds at most one key, so keeping α below 1 is essential. As α rises, linear probing tends to inspect longer clusters.
When α exceeds the selected threshold, the table grows to the next prime at least twice as large and all keys are rehashed.