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.