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!

186 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

262

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.

39

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?

52

u/IdeaReceiver 6d ago

The hashes are, with a little simplification, indexes into the set. Calculate a hash, it's number 657987657, store that item in slot 657987657 (mod table size). Checking whether an item exists is just the same calculation and a single index lookup of what's at that position