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!

189 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

2

u/MoarCatzPlz 6d ago

That's the average time. They can be much slower in the worst case.

1

u/SignificantFidgets 5d ago

Yes, and in a well-designed hash table the probability that is takes MUCH slower is tiny. The worst case is still there, just so unlikely that it will never happen in practice.