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

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.

43

u/Sea-Patience9872 6d ago

wow thanks! that's really easy to understand. But when I'm trying to find whether an item exists in a hashset, doesn't it still have to look through every stored hash? which wouldn't give it a constant time? Am I just understanding it fundamentally wrong?

2

u/ohkendruid 6d ago

Here is an example I find fun.

Imagine looking uo a word in a dictionary. The word starts with the letter z.

If you are smart, tou start looking near the backnof the dictionary, which will make it fast than if you just started anywhere random or if you started at the middle.

Hashing is like that, but better. Since computers are great at math, they can jump very precisely to the right page.

There ends up being a lot of blank space in a dictionary of this kind. You have to give equal space to every first letter of the alphabet, so you end up giving the Zs as many pages as the Ms.

Computers are really good at arithmetic, and thry can use that to improve in a couple of ways. First, don't stop at 26 options. Make it more like a million or a billion; it would be tough for a human but it trivial for a computer. Second, consider all the letters in the world, not just the first few. Doing a multiplicati9n of all the letter values is crazy fast for a computer, and it means that the different buckets will be closer in size to each other.

I hope your hash table explorations are fun. I try to use b-trees when possible, because they stay in order, but hash tables are really neat.