ToolSphere

Hash Table Simulator

Computer science

Insert keys into a hash table and watch every probe for chaining, linear probing, quadratic probing and double hashing.

Hash table simulator

Insert keys with h(k) = k mod m and watch every probe for chaining, linear probing, quadratic probing and double hashing.

SlotContents
0—
1—
212
323, 3
444
535
6—
77
8—
9—
Keyh(key)ProbesLanded
2333slot 3
4444slot 4
1222slot 2
3555slot 5
777slot 7
333slot 3

Summary

Load factor 0.60 · total probes 6

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Hash Table Simulator

  1. 1Enter the keys to insert, in order, and the table size m.
  2. 2Choose a collision strategy: chaining, linear probing, quadratic probing or double hashing.
  3. 3Read the final table and, for each key, exactly which slots it probed before it landed.
  4. 4Compare strategies on the same keys to see how differently they resolve the same collisions.

About Hash Table Simulator

Hash Table Simulator

Inserts a sequence of keys into a fixed-size table using h(k) = k mod m, and shows every probe along the way — not just the final layout, which is where most manual working goes wrong.

The four strategies, and how they actually differ

Separate chaining never probes a second slot: every key that hashes to slot i is simply appended to a list at slot i. It is the simplest to reason about and the only strategy here whose slots can hold more than one key.

Linear probing walks forward one slot at a time from the hash — slot h, h+1, h+2, and so on, wrapping around. It is fast in practice because it reads memory sequentially, but it suffers from primary clustering: once several keys land near each other, they all extend the same run of full slots, making that run more likely to catch the next collision too.

Quadratic probing walks h, h+1², h+2², h+3² instead of h+1, h+2, h+3, which spreads keys out and avoids primary clustering — but introduces secondary clustering (any two keys that hash to the same slot follow the exact same probe sequence from then on), and it is not guaranteed to find an empty slot even when one exists, unless the table size is prime and the table stays at most half full.

Double hashing uses a second hash function to set the step size itself, so two keys with the same initial hash almost always take different steps thereafter. It avoids both clustering problems and is the closest of the three open-addressing methods to the ideal of uniform probing, at the cost of needing a well-chosen second hash function.

Load factor and when a table needs resizing

Load factor α is the fraction of slots in use. For chaining, performance degrades gracefully as α grows past 1 (chains just get longer). For open addressing, α must stay below 1 by definition — the table cannot hold more keys than it has slots — and performance degrades sharply as α approaches 1, since near-full tables force ever-longer probe sequences. Most implementations resize once α passes roughly 0.7.

Why quadratic probing can reject a key from a table that isn't full

This is the detail coursework problems are built to test. With a non-prime table size, the sequence of offsets 0², 1², 2², 3²… does not visit every slot — it can cycle through only a subset of them and repeat, so a key can be reported as rejected while empty slots exist elsewhere in the table. The fix in practice is a prime table size kept below roughly half full, which guarantees quadratic probing visits enough distinct slots to always succeed.

Frequently asked questions

What is primary clustering, and why does linear probing suffer from it?

Primary clustering is when several keys land in adjacent slots and merge into one long run of occupied slots. Because linear probing always steps forward by exactly 1, any key that hashes into that run has to walk through the whole thing, which makes the run grow even longer and catch proportionally more future collisions.

Why did quadratic probing reject a key when the table wasn't full?

Quadratic probing's offsets (0, 1, 4, 9, 16...) only cover every slot when the table size is prime and the table is at most half full. With other sizes, the offsets can cycle through a subset of slots and repeat, so the algorithm gives up before finding one of the genuinely empty slots elsewhere in the table.

How is double hashing different from quadratic probing?

Quadratic probing uses the same fixed sequence of offsets (0, 1, 4, 9...) for every key. Double hashing computes a second hash of the key itself to decide the step size, so two different keys that collide at the same slot almost always then follow different paths — which is what avoids secondary clustering.

What is the maximum load factor for open addressing, and why?

It can never reach or exceed 1, because every key needs its own slot with no chaining to fall back on — at load factor 1 the table is completely full. In practice, probe sequences get so long above roughly 0.7 that most implementations resize well before that point.

Why does chaining allow a load factor above 1?

Because each slot holds a list rather than a single key, so multiple keys can share one slot indefinitely. A load factor of 2 simply means each chain averages 2 keys; performance degrades smoothly with chain length rather than hitting a hard wall the way open addressing does.

Have a suggestion for Hash Table Simulator?Share your feedback ↗