Every source says hash table lookup is O(1), then the next paragraph admits that collisions make it O(n) in the worst case. Both cannot be the headline figure.
If the worst case really is linear, why is O(1) the number everyone quotes?
Accepted Answer
Because the O(1) is an average, and the average is the honest number to quote as long as you say so.
With a decent hash function and a load factor kept below about 0.75, the expected chain length is a small constant. Lookup is one hash plus a short walk, and neither grows with n.
The O(n) worst case needs every key to land in the same bucket. With a random hash that is astronomically unlikely, so it is not what you plan around.
What you should plan around is that "decent hash function" is doing real work in that sentence.
And that is not only a theoretical worry, which is the part usually left out.
If an attacker can choose your keys and knows your hash function, they can deliberately make every key collide and turn your O(1) lookup into O(n). That is a real denial of service technique, and it took down real web frameworks around 2011 because form fields went straight into a hash map.
The fix is a randomly seeded hash per process, which is why most modern standard libraries do exactly that. So the honest version is that O(1) holds for inputs you did not let an adversary pick.
Also worth separating the two costs. Hashing the key depends on the key length, not on n. Walking the bucket depends on the load factor, not on n. Neither term has an n in it, which is where the O(1) comes from.
1 more answer and the discussion on each one are open to members.
Join free to read the rest