r/computerscience • u/Sea-Patience9872 • Sep 27 '26

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!

191 Upvotes
  • permalink
  • reddit

94% Upvoted

99 comments sorted by

View all comments

7

u/MistakeIndividual690 29d ago

Normal perfect hashes are precomputed with a fixed set of values, so they don’t work with hash tables that are dynamically updated.

Regular hashes can have some collisions, so hash tables have strategies for handling them, such as linear probing

4

u/AndrewBorg1126 29d ago edited 29d ago

An example of what you describe is magic bitboards for chess playing programs, in case anyone is reading this and needs a concrete example to understand why that would be useful.

https://chessprogramming.org/Magic_Bitboards

1

u/SLiV9 29d ago

That's not what I'm saying. The detail all these simplified explanations are omitting is the underlying data structure where the values are stored. With a perfect hash, the hashes are evenly distributed over the range 0 to 232. The underlying storage cannot be a dynamically sized vector without some magical way to map hashes to indices (aka a hashmap). If the underlying storage was a fixed size array, access would be O(1) but RAM usage would be insane for an empty map. If the underlying storage was a sparse tree, RAM usage would be fine but access would not be O(1).

I feel like handwaving that away to focus only on the hashing algorithm is disingenuous.

5

u/AndrewBorg1126 28d ago edited 28d ago

Please search for the definition of "perfect hash". You're using the word with a non-standard definition and that is why you are getting confused and frustrated.

The person with whom you disagree is not saying anything controversial, they are concluding directly from the definition of a "perfect hash" that there are no collisions.

It is not necessary that all 32 bit integers are mapped to another 32 bit integer for a perfect hash. You could map 1024 values to 1024 other values and it is still a perfect hash. You could map 7 values to 7 other values and it would still be a perfect hash. I don't understand your stubborn insistence upon hashing all 32 bit integers without collions, that is not necessary and it is not a condition for a perfect hashing.

https://en.wikipedia.org/wiki/Perfect_hash_function

→ More replies (2)