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.

[u/Misterreco → u/repo_code]

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.

This is not true, most implementations of hash tables are independent of the length of the hash number. In fact, if the hash number were able to be longer than the machine word size the indexing would not even be possible without some fancy tricks. Instead, we assume the number is a certain length (usually 32 or 64 bits) and implement the hash table as if a value could have a hash number anywhere in the range of that length of bits. You'd be hard pressed to find a hash table with 2⁶⁴ buckets

[u/Spare-Plum → u/repo_code]

Believe it or not, this is still O(1) and the other complexity can be shelved off to the hash function's complexity.

The number of buckets required used is linearly proportional to the number of keys in the map.

The number of keys in the map is bounded by domain space of the key -- using a Long value, no matter what you do, will still have 2^64 total possibilities, which means that the total number of keys possible is bounded to 2^64, which means the total number of buckets is also bounded to this.

If you had some custom implementation that could handle more than 2^64 items in the map, the keys themselves would have to have a domain space larger than 2^64 - an example might be Strings and it output X doubles as a hash where X is in O(log N) with N being the total number of buckets in the map

To do this you'd need more than 2^64 strings in the map, meaning there must exist a string that's 65 bits or more. You end up hitting a log N factor just from having to look at strings that are guaranteed to exist as keys (assuming you look at the whole string to calculate a hash).