[Verse 1]
Hash table's packed, collision's imminent
Linear probing's the first defense we implement
Index occupied? Slide one slot to the right
Sequential scanning till we find empty sight
Array wraps around when we hit the boundary
Clustering forms like urban density
Primary clusters grow, performance degrades
But insertion succeeds when space cascades
[Chorus]
Linear steps, quadratic leaps, double hash the beat
Three collision strategies, make your table complete
Probe and stride, calculate, never lose the key
Open addressing mastery, set your data free
[Verse 2]
Quadratic probing breaks the linear chain
Add i-squared offset, scatter the strain
One, four, nine, sixteen jumps ahead
Secondary clustering still raises its head
Same hash values follow identical paths
But dispersal improves, check the aftermath
Load factor matters, keep it under half
Prime table sizes make the probing last
[Chorus]
Linear steps, quadratic leaps, double hash the beat
Three collision strategies, make your table complete
Probe and stride, calculate, never lose the key
Open addressing mastery, set your data free
[Bridge]
Double hashing brings two functions alive
First determines position, second sets the stride
Step size varies by the key's unique trait
No more clustering, results are first-rate
Hash one, hash two, never make them same
Greatest common divisor ruins the game
Coprime with table size, that's the rule
Maximum distribution, ultimate tool
[Verse 3]
Deletion needs tombstones, mark don't erase
Probe sequences broken without proper trace
Search keeps going past the vacant space
Insert can reuse what deletion displaced
Rehashing required when load gets high
Expand the table, make the ratios fly
Copy each element, rehash every key
Performance restored, complexity's free
[Outro]
Three techniques mastered, collisions resolved
Open addressing problems completely solved