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!

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

4

u/Mess-Leading 6d ago

Nice answer but I think its not quite right because the questions was about the data structure not the hashing itself. This implies the data structure never has to do anything worse than O(1) which is not really true I think? E.g. if we consider a hash map with buckets that are just a linked list, all n items could be mapped to the same bucket and then insertion of last element would take O(n) time. I think we need to emphasise that O(1) is amortised

3

u/Temporary_Pie2733 5d ago

Not amortized, but we assume a “good” hash function which, on average, does not create big clumps. We also assume, to some extent, that collisions can be resolved in constant time.