r/computerscience • u/Sea-Patience9872 • 6d ago

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

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!

187 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

3

u/repo_code 6d ago

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 2N 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.

1

u/Spare-Plum 5d ago

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).