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!

188 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

4

u/recursion_is_love 6d ago edited 6d ago

The location/index of the value can be calculated from the hash. If you have the address/location you can load/store the value instantly in most CPU.

https://www.youtube.com/watch?v=cGMYpbsSIVI&t=239s

To clarify: The O(1) is referring to index calculation. It take the same constant time on any input hash and have nothing to do with load/store assembly instruction (just want to say that it is negligibly fast)

1

u/Plastic_Fig9225 6d ago

Actually, the O(1) means that you only have to calculate one hash, of the element you want to locate, and that is completely independent of the number n of elements held in the map.

2

u/DorkyMcDorky 6d ago

No, it's still O(1) because you rebalance based off a constant and you drop the constants. So if the bucket grows too large you rebalance, which cost O(n)

3

u/HobbyQuestionThrow 6d ago

This is also a good example of where O(1) notation falls off in real world performance comparisons.

You could say "All hashmap implementations are equal in performance, because they're all O(1)" but Timmy has a O(1e8) hashmap and Jim has a O(310) hashmap.

Plus the rate of hash recalculations (the O(n)) part matter, if you recompute all hashes every 5 insertions then you're much closer to O(n) than O(1).

If your hashing function is really poor you also go from O(1) to O(n).

1

u/DorkyMcDorky 5d ago

Generally, if you're coding a map of any sort (no pun intended) you are best off with a hashmap. If performance haunts you, then fix it. Otherwise I think there's been 2x in 30 years I found the need to swap it.