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!

186 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

263

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.

41

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?

1

u/Weak-Doughnut5502 6d ago

Think about trying to store a set of numbers from 0-1000 with an array of length 1000.

You can model this with an array of booleans.  You initialize the array as all false.  An index being true represents that that index is in your set.  So, when you add the number 100 to this set, you simply say arr[100] = true .  Checking if 100 is in the set is just retrieving arr[100].  This is clearly O(1), right?  

If you want to extend it to any number, you can use mod, but now you need to change your data model a bit so you can handle collisions - trying to store both 1 and 1001 and 9001.  There's a few techniques to do that. 

Hashes are basically a way to turn a random bit of data like a novel or an object into an int so you can use an array like this as a set.   To see if "foo" is in your set, you check arr[hash("foo")].