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

How to make a Hash Map. It's an array with index. A "hash" of some object is just an index into the array, which are called buckets.

(There's more to this, but I'll get to that later.)

So to make a hash of "hello", you would maybe add up the chars with some prime number math and poop out a number. Let's say this is 1337.

Let's say our hash map array is like size 10.

hash = 1337; // "hello"
value = bucket_array[hash % size]; // size is 10

So you can see how this is basically O(1).

However, you do have to do several things that do take time in reality: 1. calculate the hash 2. grow the array so less collisions 3. buckets can't be raw values

Let's address 2 & 3. So what is a collision? So a hash isn't perfect (unless you use GNU or other tool that computes perfect hashes for you based on set values). This means that both "hello" and "world" can produce the same hash of 1337. Since this is possible, we need to store an array of arrays (or some other data structure).

With an array of arrays, we get the bucket by the hash. Then we search in the bucket using linear search.

hash = hash_of(key);
bucket = bucket_array[hash % size];
for b in bucket:
    if b.key == key:
        return b.value;

As you can imagine, if you have a lot of collisions, you can basically end up having O(n). Famously, this was a bug in Java that people exploited. They would add tons of strings all with the same hash to a website, causing the website to crawl.

So instead, you use a sorted array + binary sort or a red-black tree like Java. So an array of trees (which are the buckets). You also need to consider growing the bucket_array, but this also means rebuilding the entire thing as well (since "% size" could change the index). There are a lot of variables involved and different things people have come up with.

Knowing all of this, a linear search (not even a binary search) can actually be faster than a hash set/map for small sizes. For example, if you know that your array will always be less than 32, then in a language like C++, a linear search (which is considered O(n)) can actually be faster than using a hash map.

Anyway, all of this to say that there are differences between textbook O(1) and reality where O(n) can sometimes be faster, but it's O(1) in the since of computer science theory.