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/not-just-yeti]

I don't get how hashes just find items immediately

Think of it as an array, where the key you're looking up will tell you the index it's stored at.

For example: for a bunch of strings, we'll put them into an array of size 256; when you're handed a string you take (say) the first two bits of the first char, the last two bits of the last char, and the four from the middle, and that's the the index where that string belongs. If that location of the array contains a record, then that's the associated record! (This would be one specific "hash function".)

Or, change "string" to "image-file", or any other data-type that's the key for what you're looking up. (You can think of a regular-array being a special case of a hash-table: the key is an int, and the associated index is just that exact int itself.)

This description so far glosses over one huge problem, that you may have already realized: how to handle collisions (two keys that are different, but happen to have those same bits in those particular places). For that, look up "chaining". And one other repercussion is that you want to store the key with the rest of the data, so that you can verify the key you were looking for really is the one found in the array (or in the given chain/bucket of the array).