title: What makes Hashmap.putIfAbsent faster than containsKey followed by put?
body: <p><strong>Question</strong></p>
  
  <p>How is the HashMap method putIfAbsent able to perform a put conditionally in a way thats faster than calling containsKey(x) prior? </p>
  
  <p>For example, if you didn't use putIfAbsent you could use:</p>
  
  <pre><code> if(!map.containsKey(x)){ 
     map.put(x,someValue); 
  }
  </code></pre>
  
  <p>I had previously thought putIfAbsent was convenience method for calling containsKey followed by a put on a HashMap. But after running a benchmark putIfAbsent is significantly faster than using containsKey followed by Put. I looked at the java.util source code to try and see how this is possible but it's a bit too cryptic for me to figure out. Does anyone know internally how putIfAbsent seems to work in a better time complexity? Thats my assumption based on running a few code tests in which my code ran 50% faster when using putIfAbsent. It seems to avoid calling a get() but how?</p>
  
  <p><strong>Example</strong></p>
  
  <pre><code>if(!map.containsKey(x)){
       map.put(x,someValue);
  }
  </code></pre>
  
  <p><strong>VS</strong></p>
  
  <pre><code>map.putIfAbsent(x,somevalue)
  </code></pre>
  
  <p><strong>Java Source Code for Hashmap.putIfAbsent</strong></p>
  
  <pre><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&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, i;
      if ((tab = table) == null || (n = tab.length) == 0)
          n = (tab = resize()).length;
      if ((p = tab[i = (n - 1) &amp; hash]) == null)
          tab[i] = newNode(hash, key, value, null);
      else {
          Node&lt;K,V&gt; e; K k;
          if (p.hash == hash &amp;&amp;
              ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
              e = p;
          else if (p instanceof TreeNode)
              e = ((TreeNode&lt;K,V&gt;)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 &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st
                          treeifyBin(tab, hash);
                      break;
                  }
                  if (e.hash == hash &amp;&amp;
                      ((k = e.key) == key || (key != null &amp;&amp; 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 &gt; threshold)
          resize();
      afterNodeInsertion(evict);
      return null;
  }
  </code></pre>