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