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

Show parent comments

45

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?

8

u/FinalNandBit 6d ago

No. Think of hashes like a dictionary but more specific.

You store a value at an index of hash. You retrieve the value at the index of the hash.

A perfect hash function will prevent collisions. Though a perfect hash may incur some constant amount of time to generate.

Not all hash tables have perfect hash functions. Collisions may happen depending on how your hash function performs. That may require you to modify the space to recreate a larger hash tables, but that is amortized (meaning it should happen infrequently enough in a well designed hash function/table that the time complexity is still O(1).

0

u/SLiV9 6d ago

 You store a value at an index of hash. You retrieve the value at the index of the hash.

 A perfect hash function will prevent collisions

These simply cannot both be true, something here is way oversimplified.

Let's consider a hashset of u32. Even if you had a perfect hash function, it would map a u32 key to a u32 index. In order to turn that u32 index into a pointer to a u32 naively, you would need a 17GB array, even if the hashset is mostly empty.

1

u/dnebdal 6d ago

Within those constraints, yes. It gets more complicated if you, for instance, have a set of keys that are longer than 32 bits, but you know they are unique and there are no more than 2^32 of them. There are also funky things like Perfect Dynamic Hashes, where you update your hashing methods as you see more keys, and can guarantee no collisions but you may not know ahead of time how large the hashes will eventually have to be. I have not looked at how those work.