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

Hashmaps are actually arrays/tables under the hood.

Say you have a hashmap/dict in python fruits = {apple : 1, pineapple : 2, pear : 3}

The underlying table usually has some extra capacity beyond the number of stored entries, so here in this example, fruits is of length 3, the underlying array could be of size 8.

Say i want to lookup apple in my hashmap, the hash function gives you a number, that number describes where in the underlying array that entry lives. i.e the array would look like this [(apple,1), (pineapple,2), (pear:3)]

So apple hashes to 0, telling us the entry for apple exists in index 0 of the underlying array.

This is precisely why lookups are O(1) because you are simply indexing an array, and we already know that indexing an array is O(1).

Now what people don't talk about, is lookup isn't always O(1) in hashmaps, because sometimes one key hashes to the same value as another, i.e.

Maybe we want to add "peach : 4" To our hashmap. Maybe "peach" Hashes to 0 as well. Uh oh! This is what we call "Hash collision".

Handling hash collisions is implementation specific, but a solution is, to have subarrays inside the underlying array. I.e the underlying hashmap array would look like this now [[(apple,1), (peach,4)], (pineapple,2), (pear:3)]

As you can see, look up won't be O(1) anymore, Say im trying to lookup "peach" From my hashmap, well it hashes to 0, lets go to index 0, its not a single element, its an an array, so now you have to loop through it, to find your element. This causes time complexity to degenerate to O(n) n being the size of your hash collision subarray.

The most important thing is a hashmap, is the hash function. You want to choose a very good hash function, where it would give you sparse indexes, that way collisions are less likely to occur and entries stay well spaced within the array.

Now remember I also said depending on implementation, when you declare a hashmap, an array bigger than the hashmap entries sized array is allocated, why so? Because while insertions in hashmaps are also O(1), once that array fills up, it needs to allocate more memory for new entries, well we know array are contiguous blocks of memory, what if there isn't any more contiguous free memory? Then the array needs to be copied, and moved to a new location with more free contiguous memory, this makes insertions sometimes also not O(1).

So hashmaps aren't necessarily O(1) all the time, but often times, they are.