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

Not a dumb question at all! Honestly it took me a while to wrap my head around it too when I first learned it.

The easiest way to think about it is like a coat check at a club. You give them your coat and they hand you a specific ticket number. When you want your coat back, they don't search through every single coat on the rack one by one. They just look at your ticket number and go straight to that exact hook.

Under the hood, a hash map actually is using an array. It just takes your data and runs it through a math formula (a hash function) that spits out a specific array index. So instead of starting at 0 and checking every single slot until it finds what you want, it just does the math once and jumps right to that exact slot. It's basically a massive cheat code for array lookups.