Hashmap Get/Put Complexity

HashMap get/put complexity

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 due to walking through all entries in the same hash bucket (e.g. if they all have the same hash code). 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.

In JDK 8, HashMap has been tweaked so that if keys can be compared for ordering, then any densely-populated bucket is implemented as a tree, so that even if there are lots of entries with the same hash code, the complexity is O(log n). That can cause issues if you have a key type where equality and ordering are different, of course.

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.

Time Complexity of HashMap methods

The source is often helpful: http://kickjava.com/src/java/util/HashMap.java.htm

• remove: O(1)
• size: O(1)
• values: O(n) (on traversal through iterator)

What is the time complexity of HashMap insertion and retrieval inside of a for loop?

It's O(n) for traversing the for loop for the elements and O(1) for the HashMap, the final answer is O(n), see more in here.

HashMap with O(log(N)) time complexity operations

Edited to correct the answer after the helpful comments of The Vee and Tom Elias.

You can't implement addToKey and addToValue by iterating over all the elements, since that requires, as you realized, linear time.

Instead, you can keep a keyDelta and valueDelta int instance variables that hold the value (or the sum of all values) that should be added to each key and value respectively. This is assuming addToKey and addToValue are supposed to add a numeric value to the keys or values.

addToKey and addToValue will only need to update those instance variables, which would take O(1).

The get(x) operation will search for the key x - keyDelta and return its corresponding value after adding valueDelta to it.

Note that add(x,y) also requires a change, since key-value pairs added to the Map should not be affected by previous calls to addToKey or addToValue. This can be achieved if insert(x,y) will actually insert the pair x - keyDelta, y - valueDelta to the map.

If you use a TreeMap to implement the mapping of keys to values, get and insert would take O(logN).

What is the complexity of HashMap#replace?

tl:dr

HashMap#replace runs in O(1) amortized;

and under the premise that the map is properly balanced, which Java takes care of during your put and remove calls, also non-amortized.

Non-amortized

The fact whether it also holds for non-amortized analysis hinges on the question regarding the implemented self-balancing mechanism.

Basically, due to replace only changing the value which does not influence hashing and the general structure of the HashMap, replacing a value will not trigger any re-hashing or re-organization of the internal structure.

Hence we only pay for the cost of locating the key, which depends on the bucket size.

The bucket size, if the map is properly self-balanced, can be considered a constant. Leading to O(1) for replace also non-amortized.

However, the implementation triggers self-balancing and re-hashing based on heuristic factors only. A deep analysis of that is a bit more complex.

So the reality is probably somewhere in between due to the heuristics.

---

Implementation

To be sure, let us take a look at the current implementation (Java 16):

@Override
public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

The method afterNodeAccess is a dummy for subclasses and is empty in HashMap.
Everything except getNode runs in O(1) trivially.

getNode

getNode is the canonical implementation of locating an entry in a HashMap, which we know runs in O(1) for a proper self-balancing map, like Javas implementation. Let's take a look at the code:

/**
 * Implements Map.get and related methods.
 *
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

This method basically computes the hash hash = hash(key), then looks up the hash in the table first = tab[(n - 1) & (hash = hash(key))] and starts iterating through the data structure stored in the bucket.

Regarding the data structure for the bucket, we have a little branching going on at if (first instanceof TreeNode).

Bucket

The buckets are either simple implicitly linked lists or red-black-tree.

Linked List

For the linked list, we have a straightforward iteration

do {
     if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);

which obviously runs in O(m) with m being the size of the linked list.

Red-Black-Tree

For the red-black-tree, we have

return ((TreeNode<K,V>)first).getTreeNode(hash, key);

Lookup in a red-black-tree is O(log m), with m being the size of the tree.

Bucket size

Javas implementation makes sure to re-balance the buckets by rehashing if it detects that it gets out of hands (you pay for that on each modifying method like put or remove).

So in both cases we can consider the size of the buckets as constant or, due to the heuristics involved with self-balancing, close to a constant.

Conclusion

Having the buckets at constant size, effectively, makes getNode run in O(1), leading to replace running in O(1) as well.

Without any self-balancing mechanism, in worst case it would degrade to O(n) if a linked list is used and O(log n) for a red-black-tree (for the case that all keys yield a hash collision).

Feel free to dig deeper into the code but it gets a bit more complex down there.

Time complexity for HashMap put/get inside for?

O(3N) and O(N) would be just considered O(N).

---

I guess, maybe getOrDefault() would be an option, if I'd correctly recall:

for (int i = 0; i < n.length(); i++) {
    int aux = n[i];

    map.put(aux, map.getOrDefault(aux, 0) + 1);
}

and your time and memory complexity would be both O(N).

---

I think another more readable version would be:

for (int i = 0; i < n.length(); i++) {
    int aux = n[i];

    map.put(aux, -~map.getOrDefault(aux, 0));
}

-~x is just a bitwise operation for x + 1 (-~x = x + 1). However, you can use whichever you would be comfortable.

---

Thanks to ciamej in the comment!

---

Related Topics