What is the time complexity of open addressing?

Average case O(1) below α ≈ 0.7. Worst case O(n). Space complexity is O(m). Load factor cannot exceed 1, and performance collapses well before it.

Open addressing

medium

Everything lives in the table, which is far friendlier to the cache than following chain pointers. Watch linear probing form clusters, then switch to double hashing and watch them scatter.

Average O(1) below α ≈ 0.7Worst O(n)Space O(m)

Loading the open addressing engine…

Where to go next

Hash table with chaining

medium

Collisions share a bucket, and load factor is everything.

Resizing and rehashing

medium

Why one insert in a thousand costs O(n).

Bit manipulation playground

medium

Set, clear, toggle - and the two identities worth memorising.