Michael Michael - 5 years ago 367
Java Question

HashMap get/put complexity

We are used to saying that

operations are O(1). However it depends on the hash implementation. The default object hash is actually the internal address in the JVM heap. Are we sure it is good enough to claim that the
are O(1) ?

Available memory is another issue. As I understand from the javadocs, the
load factor
should be 0.75. What if we do not have enough memory in JVM and the
load factor
exceeds the limit ?

So, it looks like O(1) is not guaranteed. Does it make sense or am I missing something ?

Answer Source

It depends on many things. It's usually O(1), with a decent hash which itself is constant time... but you could have a hash which takes a long time to compute, and if there are multiple items in the hash map which return the same hash code, get will have to iterate over them calling equals on each of them to find a match.

In the worst case, a HashMap has an O(n) lookup. Fortunately, that worst case scenario doesn't come up very often in real life, in my experience. So no, O(1) certainly isn't guaranteed - but it's usually what you should assume when considering which algorithms and data structures to use.

And yes, if you don't have enough memory for the hash map, you'll be in trouble... but that's going to be true whatever data structure you use.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download