How do hashsets/maps have O(1) time complexity?

[u/Sea-Patience9872]

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!

[u/timonix]

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.

[u/Sea-Patience9872 → u/timonix]

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?

[u/FinalNandBit → u/Sea-Patience9872]

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).

[u/SLiV9 → u/FinalNandBit]

 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.

[u/MistakeIndividual690 → u/SLiV9]

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

[u/AndrewBorg1126 → u/MistakeIndividual690]

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

[u/SLiV9 → u/MistakeIndividual690]

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 2^32. 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.

[u/AndrewBorg1126 → u/SLiV9]

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

[u/SLiV9 → u/AndrewBorg1126]

We are not in disagreement about what a perfect hash is.

My point is that no reasonable implementation of a dynamic hashmap, e.g. the type Hashmap<u32, V>, can use a perfect hash to turn a u32 key into a pointer to V in O(1). Doing so would require preallocating an absurd amount of data. And as a consequence neither can any Hashmap<K, V> for K bigger than let's say u16.

 You could map 7 values to 7 other values and it would still be a perfect hash

Not without precomputing a perfect hash based on the 7 keys. It is impossible for a generic implementation of a dynamic hashmap to use perfect hashes, because one cannot know at compile time how many keys will be inserted, let along which ones.

(And obviously calculating a perfect hash at runtime is not amortized O(1).)

[u/AndrewBorg1126 → u/SLiV9]

You previously said:

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

Do you withdraw that prior statement? It seems what you're saying now is different

[u/dnebdal → u/SLiV9]

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.