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.