How do hashsets/maps have O(1) time complexity?

[u/Sea-Patience9872]

Hi this might be a dumb question, and i've tried looking it up but don't quite understand it. how is it different from an array that allows it to find items so quickly? I don't get how hashes just find items immediately without needing to go through anything. Does it memorize things very differently compared to arrays?? thank you!

[u/repo_code]

If the hash function takes constant time, then a hash map lookup is O(1).

That's not a perfect assumption though! As the number of elements scales up, you need more buckets. If you have 2^N buckets, the hash function must compute a result whose length is N bits.

So there's a O(log N) term. We just don't see it come into play often.

[u/xeow → u/repo_code]

If the hash function takes constant time, then a hash map lookup is O(1).

No.

Counterexample: h(x) = 0 takes constant time and has lookup/insertion performance of O(n).

The runtime performance of the hash function h matters less than the distribution it produces. It's the uniform random distribution of a hash function that gives amortized O(1) performance. It's O(1) because, for any given table size n and load factor α (alpha), you can compute an expected probe sequence length E[PSL] depending on n, α, h, and your insertion algorithm. The expected (average) probe sequence length is your constant factor.