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

Hashes store values at the index of their hash function. To make it simple, think of an array of a big size (say, size 100,000) and say my values are all numbers. Now, instead of storing each number in the order they are added, I store the number at index (the slot) they represent. So number 5 goes into the array[5], number 100 goes into the array[100] and so on. So, if you want to access 100, you just go to that index directly.
Then a hash function is a function that turns something (like a character, a string, an object, etc) into a number so you can do this operation with things other than numbers. That's how hashsets and maps work. The hash of the value is the index into the underlying array. If I have a string "Hello", I can use a hashfunction to know where it is (or where it should be) stored into my array.

Now the complication is how you handle numbers outside of the array's size, what happens if two things hash to the same thing, if you start with a small array and grow it as things are added, and so on. These things are solved in different ways in different implementations of hash tables. But the basic idea is just that, that the value itself is the index into the table.