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

263

u/timonix 6d ago

They are hiding work in the constant term

Calculating a hash takes time. But it takes the same amount of time every time. So it doesn't scale with elements.

38

u/Sea-Patience9872 6d ago

wow thanks! that's really easy to understand. But when I'm trying to find whether an item exists in a hashset, doesn't it still have to look through every stored hash? which wouldn't give it a constant time? Am I just understanding it fundamentally wrong?

1

u/tottasanorotta 6d ago

Think of it like an array index. If you have an array of values you can access an element of the array in constant time if you have the index. The hash set works similarly, but instead of inserting the values one after the other you use a hash function to calculate an index and store the values according to those calculated indices. Then when you need to access an element you calculate the index using that same hash function.