Что делает Hashmap.putIfAbsent быстрее, чем hasyKey, а затем put?

Question

Вопрос

Каким образом метод putIfAbsent метода HashMap может выполнить установку условия условным способом, который быстрее, чем предыдущий вызов метода hasKey (x)?

Например, если вы не использовали putIfAbsent, вы можете использовать:

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

Ранее я думал, что putIfAbsent - это удобный метод для вызова containsKey, за которым следует вставка в HashMap.Но после запуска теста putIfAbsent выполняется значительно быстрее, чем с использованием containsKey, за которым следует Put.Я посмотрел на исходный код java.util, чтобы попытаться понять, как это возможно, но это слишком загадочно для меня, чтобы понять.Кто-нибудь знает внутренне, как putIfAbsent, кажется, работает в лучшую временную сложность?Это мое предположение, основанное на выполнении нескольких тестов кода, в которых мой код работал на 50% быстрее при использовании putIfAbsent.Кажется, чтобы избежать вызова get (), но как?

Пример

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

VS

map.putIfAbsent(x,somevalue)

Исходный код Java для Hashmap.putIfAbsent

@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, key, value, 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, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, 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;
}

Answer 1

См. Ответ Эрана ... Я хотел бы также ответить на него более кратко.put и putIfAbsent оба используют один и тот же вспомогательный метод putVal.Но клиенты, использующие put, не могут воспользоваться его многочисленными параметрами, которые допускают поведение put-if-present.Публичный метод putIfAbsent раскрывает это.Таким образом, использование putIfAbsent имеет ту же базовую сложность времени, что и put, который вы уже собираетесь использовать в сочетании с containsKey.Использование containsKey становится бесполезным.

Таким образом, суть в том, что приватная функция putVal используется и путами, и putIfAbsent.

Answer 2

Реализация HashMap *1001* ищет ключ только один раз, и если он не находит ключ, он помещает значение в соответствующую ячейку (которая уже была найдена).Вот что делает putVal.

С другой стороны, использование map.containsKey(x) с последующим map.put(x,someValue) выполняет два поиска для ключа в Map, что занимает больше времени.

Обратите внимание, что put также вызываетputVal (put звонит putVal(hash(key), key, value, false, true), а putIfAbsent звонит putVal(hash(key), key, value, true, true)), поэтому putIfAbsent имеет такую ​​же производительность, как и вызов put, что быстрее, чем вызовы containsKey и put.