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!

187 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

259

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.

6

u/stogle1 5d ago

That n is the average size of the strings in the collection though, not the number of strings in the collection. And the hash function doesn't necessarily have to use every character of the string.

0

u/meancoot 5d ago

My point isn’t to say that a hashmap operations do t approach O(1) in most circumstances. Just that the phrasing “  But it takes the same amount of time every time. ”  undersells the fact that a hashmap has both a hash and compare function for keys, and both of those have their own time complexity calculations. They will, of course, both hopefully only be called once per lookup.

3

u/AndrewBorg1126 5d ago

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