Hash Table (Open Addressing)

Stores every key directly in the table, probing forward one slot at a time on a collision. No pointers means excellent cache behaviour, but collisions form clusters that lengthen each other — watch a run of occupied slots grow and start absorbing unrelated keys.

Best

O(1)

Average

O(1/(1-α))

Worst

O(n)

Space

O(n)