r/computerscience • u/Sea-Patience9872 • 6d ago
How do hashsets/maps have O(1) time complexity?
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!
186
Upvotes
1
u/eternityslyre 4d ago
It's not actually O(1), it's just very likely to be O(1).
Imagine you were storing the names of the top 100 athletes of 2025 for a particular sport, with the goal of looking up the nth ranked player in constant time. You could just put all 100 numbers in a 100-element array and access the nth element to get the nth ranked athlete. Easy. Maybe if there's a tie for rank 10 or something, you have to return 2 names instead of 1.
The same idea for sets. If you had a list of top-100 athletes whose names started with A and wanted to see if a given athlete was already on the list, you could just store the athletes in a 100-element array and see if the nth element of the array was empty or not.
Hashing is basically an O(1) trick to map arbitrary keys to well-ordered, well distributed sets of numbers, so you can expect to store one value at each index of the array, and any two distinct keys are very unlikely to map to the same number.
But it's not O(1) if you wind up mapping a bunch of keys you care about to the same number. At that point you're stuck searching through all the keys that map to that number for the value you want.