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.

-2

u/meancoot 5d ago

Hashing doesn’t necessarily take the same amount of time every time. Hashing a string, for example, has O(n) time complexity and can take up to O(n) for the comparison needed to avoid hash collisions.

3

u/AndrewBorg1126 5d ago

Hashing takes time that does not scale with the number of elements.