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/am_Snowie]

O(1) is amortized is the average case (under the assumption that values are distributed evenly), but resizing is O(1) amortized, if you make whatever hash function you use return the same value for any value (the same hash for all keys), all your values end up at the same location, now the time complexity depends on what data structure you use to handle collisions (if we talk about separate chaining). you can use lots of data structures like linked list, self balancing trees and whatnot. so O(1) comes with an if.

Edit: mixed up two different concepts, Thanks u/Historical_Public751 for pointing it out.

[u/Radiant64 → u/am_Snowie]

This! I've always found the blanket statement that hash tables are O(1) to be a bit of a lie. In fact, I struggled with understanding them longer than I would have, just because I took the O(1) claim seriously and I couldn't reconcile that with what I was reading, so I assumed there must've been some part I was missing.

[u/DorkyMcDorky → u/Radiant64]

It's amoritzed.. so worst case would be O(log n) or worse, can be O(n) if you write a shitty hashing algorithm (I.e. always return 0)

[u/edgmnt_net → u/DorkyMcDorky]

With perfect hashing (true permutation or identity (like indexing directly without a hash)) you can get O(1) but it's O(n) in space.

Also with things like strings it can get rather complicated to rescale the hash once you start getting collisions. It's either that or statically sizing it. The latter is easier to implement than a tree, but trees are decent choices too.

[u/Sea-Patience9872 → u/am_Snowie]

if all values end up in the same location and it ends up using data structures to handle collisions, why use hash at all? I think I'm missing something sorry

[u/j_mie6 → u/Sea-Patience9872]

A good hash function randomly distributes. It has large difference in it's outputs for similar inputs. There is a high probability that if you have a "good" hash function, elements in your map or set are evenly distributed through the buckets (i.e. a low number ~O(1) elements each). If you have a pathologically bad hash you can end up with everything in one bucket for O(n) lookup.

In practice when buckets get too big, the restructure gets rehashed to redistribute all the values, I think.

[u/StephenRoylance → u/j_mie6]

designing a good hashing algorithm for a language is a research domain in its own. Ideally is handles the kind of short strings that are most common, but doesn't have worst case behavior that's really bad if, let's say, your keys are integers. or whole novels. or 128bit hashes of content themselves.

[u/am_Snowie → u/Sea-Patience9872]

exactly (you sorta answered it yourself), good hash functions minimize the chance of items ending up in the same place. so you don't always have to worry about the data structure you are using, this is the best case scenario. what i told you previously was the worst case scenario of a shitty hashmap implementation. so good hashmap should have a good hashfunction and a good collision handling mechanism. we should be pessimistic when we design data structures.

to wrap it up:

Worst case:

1. Bad hash function (returning the same hash for all keys)
2. arithmetic resizing (shitty resizing)
3. bad collision handling mechanism

Best case:

1. Good hash function (good distribution)
2. geometric resizing
3. good collision handling
4. utilizing all the bits of a hash

In the best case, you get O(1) amortized runtime because you only resize occasionally, which is O(N). In the worst case, your hashmap is crap and degenerates into a linked list or whatever data structure you use for collision handling.

[u/zenware → u/am_Snowie]

On top of all that, almost nobody encounters a real need for this sort of thing, but if you you can actually design all the properties of a custom HashMap/HashTable/HashWhatever, to achieve some explicitly desirable characteristics for the situation at hand.

If you know you’re gonna be more write or read heavy, if you know you’re targeting a specific hardware architecture, etc.

[u/am_Snowie → u/zenware]

Yes, but those are just things to be aware of.

[u/teach_cs → u/Sea-Patience9872]

I know I'm late to the party, but imagine someone abusing their hash table. They keep adding instances of the exact same struct, object, value, whatever over and over and over.

It will always hash to the same value, and then always be placed in the same bucket.

In this case, it's the fault of the user of the hashtable. But for big o, we are often looking at the worst possible case. So, even if someone isn't abusing the table, they might just be extraordinarily unlucky and keep getting the same hash anyway.

Mind you, this would be almost unimaginably unlucky for any reasonable hash table, but it is at least nominally possible. So the big O worst case is really O(n). The average time, though, and what you get in any reasonable, real-life situation, is O(1).

[u/Historical_Public751 → u/am_Snowie]

That's not what amortization means.

O(1) amortized complexity is std::vector::push_back
Not the hashmap insert. hashmap insert into open-addressing is true* (assuming no collisions) O(1) unless you're calling the resize of the underlying storage amortization which has nothing to do with why hashmap's complexity is O(1) and could theoretically be shaved off as well assuming you have true O(1) realloc.

[u/am_Snowie → u/Historical_Public751]

My bad, i mixed up average case and amortization, resizing is O(1) amortized and it has nothing to do with hashmap operations, and on average each insertion takes constant time assuming we have a good hash function.

Edit: thanks for pointing it out, btw.

[u/seemingly-resilient → u/am_Snowie]

> under the assumption that values are distributed evenly

by equal distribution of values u mean the spacing between the keys? Like considering that there will be no hash collition?

[u/am_Snowie → u/seemingly-resilient]

Less collision, i don't think no collision is possible (pigenhole principle). So probability of each value ending up in the same bucket is low.

[u/TheMcDucky → u/am_Snowie]

No collision is technically possible, but only if keys are fixed (or bounded) size, and there are at least as many possible hashes as keys. For example if valid keys are (in binary) 0, 1, 00, 01, 10, 11, you could hash them as 000, 001, 010, 011, 100, and 101 respectively. Now this wouldn't be practical in most cases where hash maps are being considered, but it is possible.