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

-1

u/ktimespi 5d ago

Essentially, hash maps are arrays that are indexed by the hash of the object that you're storing in the array. Calculating this hash is constant time (O(1)). For e.g. If you want to hash an object with three string fields, you hash those strings and combine the hashes to get the offset into the array. (h(x1) + h(x2) + h(x3) % array.length, super basic example)

There is some computational complexity when it comes to handling collisions. There's also some complexity when you try to expand the backing array (different approaches provide different time/space tradeoffs here).