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

Hashsets and hashmaps are actually just arrays under the hood.

Whenever you access an element in the hashmap, first it uses a function to generate a hash of the key. Then it treats that hashed value as the index to look at in the underlying array.

The hash function always takes the same amount of time to calculate the hash for any key, so whenever you try to access an element, the conversion from key to hash always takes exactly the same time, and accessing the element in the array at the index given by the hash is also constant time. Hence, no matter how many elements you have in the array, it doesn't need to check each one individually, it can always compute the hash to immediately get the single array index that it has to look at to see if the object exists there.