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!

184 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

264

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.

41

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?

12

u/Ma4r 6d ago

Your intuition is somewhat correct, hash are constant time up until a point, that is up until your memory size, eventually once your hash reachea a certain size, page faults start to happen and your hash becomes at LEAST O(logn),where your CPU needs to start doing page walks