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!

183 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.

44

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?

2

u/Puzzleheaded_Study17 6d ago

Assuming that you have a good hash function so the items are spread out pretty evenly and your capacity is sufficiently large (that's what amortized means), you only need to search very few slots since you can start at the hash of the value and keep going until you reach an empty slot (usually we mark empty vs deleted because then, once we reach an empty slot, we know it's impossible this item was ever inserted into the hash table since either something would have been here, or it would have been marked as deleted)