[Verse 1]
When your hash table's full and collisions arise
You need a strategy that's clever and wise
Open addressing keeps everything tight
In one single array, no pointers in sight
Linear probing takes the simplest route
When a slot is taken, just step to compute
Move one step forward, then one step more
Until you find space or you've checked the floor
Primary clustering starts to appear
When data groups up, performance you'll fear
But it's easy to code and understand clear
Linear probing gets the job done here
[Chorus]
Open addressing, three ways to go
Linear steps forward, nice and slow
Quadratic jumps with distance that grows
Double hash when the table overflows
Probe and search until you find space
Keep your load factor in the right place
Open addressing, memory's embrace
One array holds the whole database
[Verse 2]
Quadratic probing tries to break the chain
Distance equals i-squared, reducing the pain
One, four, nine, sixteen, spreading it wide
Secondary clustering still can't hide
But it's better than linear for most of your needs
Avoiding those clusters where linear feeds
The formula's simple, implementation's clean
Best middle ground that you've ever seen
[Chorus]
Open addressing, three ways to go
Linear steps forward, nice and slow
Quadratic jumps with distance that grows
Double hash when the table overflows
Probe and search until you find space
Keep your load factor in the right place
Open addressing, memory's embrace
One array holds the whole database
[Verse 3]
Double hashing brings two functions to play
First one maps your key to start the way
Second one gives you the step size right
Uniform distribution, clustering takes flight
Hash one mod table size for position start
Hash two mod table size for stepping part
Make sure that second hash is relatively prime
Or you'll loop forever, wasting your time
[Bridge]
When deletion comes around
Mark the slot as deleted found
Don't leave it empty, that breaks the chain
Tombstone markers keep searches sane
Load factor matters, keep it low
Point seven five is the way to go
Higher loads mean longer probe sequences grow
Performance drops and searches slow
[Chorus]
Open addressing, three ways to go
Linear steps forward, nice and slow
Quadratic jumps with distance that grows
Double hash when the table overflows
Probe and search until you find space
Keep your load factor in the right place
Open addressing, memory's embrace
One array holds the whole database
[Outro]
Choose your method based on your need
Linear's simple if clustering you can feed
Quadratic's balanced for general case
Double hashing for uniform space
Open addressing, memory efficient and clean
Best hash table method you've ever seen