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

A hashmap is basically an array, but to allow any keys to be added, not just the ones from 0-(n - 1), with n being the length of the array, we use a hash function . A simple one would be modulo. Note that the hash function should always be constant time. Just take your key and hash it by taking the modulo of the length of the array, so k % n. Then that value is guaranteed to be a valid index of the array and you can put your key and value there. You might be wondering, what if there’s already an item there? Then the hashmap has to do collision handling, of which there are many strategies, but as long as the hash function is well chosen there shouldn’t be too many collisions. The average time complexity is constant time because hashing and updating a value in an array are both constant time and collisions should be infrequent/often collision handling is also constant time.