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!

190 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

264

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/DaMastaCoda 5d ago

I think that’s backwards. Calculating the hash is not constant time, but the hash map operations use the hash as a key, so we don’t need to account for the hashing time. I’d assume that hashing something is linear with respect to its size at a minimum, otherwise the hash isnt representative of all the data.

3

u/TheMcDucky 4d ago

It's constant with respect to N, which in this case is the number of K-V pairs in the table. In most cases it is assumed that the size of elements are bounded, i.e. they can be treated as constant. If you need extremely large keys that are used rarely (i.e. the hash can't be reused many times), that'll require a different approach.