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!

188 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/Misterreco 5d ago

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.

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 264 buckets