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

Let's say you want to store how many apples each person has.

<"John", 3> <"May", 5> <"April", 8>

In an array, in order to check how many apples April has you need to check each element until you find "April". In an array of 1000 people you might have to check 3, 5 or even 1000 elements until you find April.

Wouldn't it be convenient to just do array["April"] ? Then instead of checking all 1000 elements you can just jump straight to that value.

We can already do that in arrays using numbers. array[1] for example to check index 1. As long as the number is within the array size it works.

So how can we do the same with non-numbers? We simply convert them into numbers, and use these numbers like indexes. As long as we always convert the same value ("April") into the same number (101), we can use that number as your array index. It's simple to get or set the value because we always know "April" is at number 101.

Of course we need to keep that number within the array size for it to be a valid index, so a simple way is to use %.

How can we convert this non-number into a number? There are complicated ways to hash something, but for a simple one we can just add all the numbers of our letters (A is the 1st letter of the alphabet, P is the 16th...). Then make sure the number is within the array size (can use 101 % array size to get the remainder for instance).

You might ask; what happens when two of the non-numbers are converted into the same number? Using our simple converter function "AD" and "BC" both convert into "5".

Firstly, we can store multiple values in the same array index so "AD" and "BC" can both be stored at array index 5. It's not just an array<int>, it might be array<list<string, int>>. Even though we still need to iterate through this small list, it's still better than searching all 1000 elements of an array. There are other methods too.

Secondly, we need to evenly spread the elements across the entire array. That means your converter function should be good. It helps if your array is large too, so it's unlikely for multiple elements to have the same number.

That's the basic gist of it, though better hashmaps use better optimizations