Java – what makes HashMap Putifabsent is faster than containskey?

topic

How can the HashMap method putifabsent conditionally execute put faster than before calling containskey (x)?

For example, if you do not use putifabsent, you can use:

if(!map.containsKey(x)){ 
   map.put(x,someValue); 
}

I thought putifabsent was a convenient method to call containskey and put it on HashMap However, after running the benchmark, putifabsent is significantly faster than using containskey followed by put I checked Java Util source code, try to see what's going on, but it's a little too mysterious for me Does anyone know that putifabsent seems to work with better time complexity? This is my assumption based on running some code tests, in which my code runs 50% faster when using putifabsent It seems to avoid calling get (), but how?

example

if(!map.containsKey(x)){
     map.put(x,someValue);
}

VS

map.putIfAbsent(x,somevalue)

Hashmap. Putifabsent java source code

@Override
public V putIfAbsent(K key,V value) {
    return putVal(hash(key),key,value,true,true);
}

final V putVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n,i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash,null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this,tab,hash,value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash,null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab,hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Solution

The HashMap implementation of putifabsent only searches for the key once. If the key cannot be found, the value is put into the relevant bin (already found) This is what putval does

On the other hand, use map Containskey (x) followed by map Put (x, somevalue) performs a lookup on the key in the map twice, which takes more time

Note that put also calls putval (put calls putval (hash (key), false, true) and putifabsent calls putval (hash (key), true)), so putifabsent has the same performance and calls just put, which is faster than calling containskey and put