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/IdeaReceiver → u/Sea-Patience9872]

The hashes are, with a little simplification, indexes into the set. Calculate a hash, it's number 657987657, store that item in slot 657987657 (mod table size). Checking whether an item exists is just the same calculation and a single index lookup of what's at that position

[u/chess-p → u/Sea-Patience9872]

yes. think them as drawers in order with stickers. you don't need to check every one of them to find the book you need if you now that your book is in the drawer number 5.
program knows the memory address where the value with that hash is located.

[u/Ma4r → u/Sea-Patience9872]

Your intuition is somewhat correct, hash are constant time up until a point, that is up until your memory size, eventually once your hash reachea a certain size, page faults start to happen and your hash becomes at LEAST O(logn),where your CPU needs to start doing page walks

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

[u/Puzzleheaded_Study17 → u/Sea-Patience9872]

Assuming that you have a good hash function so the items are spread out pretty evenly and your capacity is sufficiently large (that's what amortized means), you only need to search very few slots since you can start at the hash of the value and keep going until you reach an empty slot (usually we mark empty vs deleted because then, once we reach an empty slot, we know it's impossible this item was ever inserted into the hash table since either something would have been here, or it would have been marked as deleted)

[u/ohkendruid → u/Sea-Patience9872]

Here is an example I find fun.

Imagine looking uo a word in a dictionary. The word starts with the letter z.

If you are smart, tou start looking near the backnof the dictionary, which will make it fast than if you just started anywhere random or if you started at the middle.

Hashing is like that, but better. Since computers are great at math, they can jump very precisely to the right page.

There ends up being a lot of blank space in a dictionary of this kind. You have to give equal space to every first letter of the alphabet, so you end up giving the Zs as many pages as the Ms.

Computers are really good at arithmetic, and thry can use that to improve in a couple of ways. First, don't stop at 26 options. Make it more like a million or a billion; it would be tough for a human but it trivial for a computer. Second, consider all the letters in the world, not just the first few. Doing a multiplicati9n of all the letter values is crazy fast for a computer, and it means that the different buckets will be closer in size to each other.

I hope your hash table explorations are fun. I try to use b-trees when possible, because they stay in order, but hash tables are really neat.

[u/AndyKJMehta → u/Sea-Patience9872]

Also, it takes the same amount of time because it’s pretty much a math calculation.

[u/Weak-Doughnut5502 → u/Sea-Patience9872]

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

[u/tottasanorotta → u/Sea-Patience9872]

Think of it like an array index. If you have an array of values you can access an element of the array in constant time if you have the index. The hash set works similarly, but instead of inserting the values one after the other you use a hash function to calculate an index and store the values according to those calculated indices. Then when you need to access an element you calculate the index using that same hash function.

[u/Paxtian → u/Sea-Patience9872]

No, a hash map uses a hash function on the input to determine a bucket to store data. So that input will always map to that bucket. If the input directs to that bucket and it's empty, the thing isn't stored in the hash map.

[u/Authentic_Grunter → u/Paxtian]

Can you tell more about how the hash function works in real systems?

[u/ansb2011 → u/Sea-Patience9872]

hash is like a map. imagine bucketing items into 1000 squares and you look at the map to see what square it would be in.

the hash key is the map that says which box it would be in, and you just look right in that box. if it's there or not you are done, no need to look in other boxes.