Hash Table

Both loops above walk until they reach a slot they can stop at, and a table whose slots are all live keys offers none: lookup spins forever on a key that is absent, and insert spins forever on a key it cannot place. Nothing inside either loop can detect that, so the guarantee has to come from outside it - an open-addressed table is grown while at least one slot is still free, which makes the load factor a correctness rule and not only a speed one. Lookup runs out of stopping points sooner than insert, because it stops only at a genuinely empty slot and reads a marker as occupied, so a table churned by deletes can lose its last null while holding few live keys. The cheap guard is to bound each loop by the table size and treat exhaustion as a failure rather than a hang.

A run of L filled slots in a row absorbs any key whose home is one of those L slots, so the empty slot at the end of the run is L + 1 times more likely to be taken next than a lone empty slot is. Long runs therefore get longer, and two runs that touch merge into one much longer run. That is primary clustering, and it is the whole reason the other probe schemes exist: quadratic probing jumps 1, 4, 9 slots out to leave the cluster, and double hashing gives each key a stride of its own so two keys never share a path. Linear probing still wins often in practice, because its next slot is the next address in memory and several probe steps come free inside one cache line.

The 1 + key % (size - 1) in the double hashing line is not decoration. A stride of 0 probes the same slot forever, and a stride that shares a factor f with the table size only ever reaches size / f of the slots, so an insert can fail while most of the table is empty. A prime size makes every stride below it coprime automatically, which is why double hashing implementations nearly always use primes. Plain quadratic probing has the same coverage problem, and the usual fix is the triangular form home + step * (step + 1) / 2 on a power-of-two table, which is guaranteed to visit every slot exactly once.

Once deletes leave markers, insert must not stop at the first marker and write there. The key may already be sitting further along the same probe path, and writing early leaves two copies of it, of which lookup will only ever find the first. The correct shape is to remember the first marker, keep probing until a genuinely empty slot proves the key is absent, and only then go back and use the remembered slot. The insert above takes the short cut for readability. Note what the correct version costs: even an insert that could have stopped at the first marker still walks the whole path to an empty slot, so it is the absence check that sets the price, not the write.