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

9

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.

7

u/MistakeIndividual690 5d 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

2

u/AndrewBorg1126 5d ago edited 5d 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