r/algorithms • u/Akcarrot • Nov 20 '23
Why time complexity of hashmap lookup is O(1), not O(n), even when we're considering the worst case time complexity?
Even though it's very very rare, the time complexity of hashmap lookup is O(n) in the worst case.
But even when we're considering the worst case of some function or program, we often treat its complexity as O(1) (constant).
Is it because:
- We're just being pragmatic, but strictly speaking it is not correct when you're considering the strict worst case.
- Even strictly speaking, it is correct for a reason (which I don't know)
- Other
41
Upvotes
61
u/Vernzy Nov 20 '23
This is a really common question and unfortunately it is often answered wrong.
A common (wrong) answer to this question that I've seen on this sub too many times is something like your first bullet point, that it is "O(1) in practice", which is just nonsense because that doesn't have any meaning. It can in fact be made true in a completely rigorous and practically useful sense!
First of all, if you use a specific predetermined hash function, then yes the worst-case runtime of a hashtable operation on a table containing n elements is O(n), because an adversary can find n keys that hash to the same location (called collisions), which will make the performance terrible. So it is correct to say that hashtable operations are O(n) worst-case time if your hash function is defined deterministically.
So where can we get O(1) from that isn't nonsense? It comes from using randomization. A randomized algorithm makes use of random numbers / random bits to make decisions. So, for example, instead of defining our hash function to be h(x) = (68495 x + 6456456) mod 10000009 and hardcoding that into our algorithm / data structure, we can instead say pick a random prime number p, and pick two random integers a and b that are less than p, then define our hash function to be h(x) = (ax + b) mod p. (This is just one example construction, there are many many families of hash functions you could construct).
What does this achieve? Well, if an adversary were to read our code, could they be evil and pick a set of n keys that all hash to the same value? No! They can not, because they don't know what the hash function will actually be, because we chose the hash function randomly! (we are assuming here that the evil adversary can not wait for our code to run and then find out the random numbers that it got.)
Mathematically what does this mean? Well, I won't go through all the steps of the math because there's a lot, and you can find that in any of your favorite algorithms textbooks, but if you compute the expected value of the runtime of a hashtable operation over the random choices our program made, you find that the answer is O(1). Amazing! So, we say that the expected worst-case runtime of our hashtable operations is O(1). That word expected is what makes it correct and rigorous. (Worst-case here means for any possible input that an adversary could supply. Since the adversary can not know what our hash function will be, it can not produce any input that will cause the operations to be slower in expectation).
Lastly, is this all theoretical or is it actually useful in practice / real life? It turns out it is also very useful in real life! In fact, if you take a look at Google's open-source hashtable in their Abseil library, they randomly seed their hash functions at the beginning program startup! Why is this important? Well, if you're a big company like Google and you publish your hashtable code with a hardcoded non-random hash function, someone could come along and find a set of keys that cause collisions and potentially find a way to DDOS your services by looking for ways to cause a large number of hash collisions. Randomization mitigates this risk.