title: HashMap rehash/resize capacity
body: <p>A <code>HashMap</code> has such a phrase from it's documentation:</p>
  
  <blockquote>
    <p>If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will <strong>ever</strong> occur.</p>
  </blockquote>
  
  <p>Notice how the documentation says <strong>rehash</strong>, not <strong>resize</strong> - even if a rehash will only happen when a resize will; that is when the internal size of buckets gets twice as big. </p>
  
  <p>And of course <code>HashMap</code> provides such a constructor where we could define this <em>initial capacity</em>. </p>
  
  <blockquote>
    <p>Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).</p>
  </blockquote>
  
  <p>OK, seems easy enough:</p>
  
  <pre><code>// these are NOT chosen randomly...    
  List&lt;String&gt; list = List.of("DFHXR", "YSXFJ", "TUDDY", 
            "AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR");
  
  int maxNumberOfEntries = list.size(); // 9
  double loadFactor = 0.75;
  
  int capacity = (int) (maxNumberOfEntries / loadFactor + 1); // 13
  </code></pre>
  
  <p>So capacity is <code>13</code> (internally it is <code>16</code> - next power of two), this way we  guarantee that documentation part about no rehashes. Ok let's test this, but first introduce a method that will go into a <code>HashMap</code> and look at the values:</p>
  
  <pre><code>private static &lt;K, V&gt; void debugResize(Map&lt;K, V&gt; map, K key, V value) throws Throwable {
  
      Field table = map.getClass().getDeclaredField("table");
      table.setAccessible(true);
      Object[] nodes = ((Object[]) table.get(map));
  
      // first put
      if (nodes == null) {
          // not incrementing currentResizeCalls because
          // of lazy init; or the first call to resize is NOT actually a "resize"
          map.put(key, value);
          return;
      }
  
      int previous = nodes.length;
      map.put(key, value);
      int current = ((Object[]) table.get(map)).length;
  
      if (previous != current) {
          ++HashMapResize.currentResizeCalls;
          System.out.println(nodes.length + "   " + current);
      }
  }
  </code></pre>
  
  <p>And now let's test this:</p>
  
  <pre><code>static int currentResizeCalls = 0;
  
  public static void main(String[] args) throws Throwable {
  
      List&lt;String&gt; list = List.of("DFHXR", "YSXFJ", "TUDDY",
              "AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR");
      int maxNumberOfEntries = list.size(); // 9
      double loadFactor = 0.75;
      int capacity = (int) (maxNumberOfEntries / loadFactor + 1);
  
      Map&lt;String, String&gt; map = new HashMap&lt;&gt;(capacity);
  
      list.forEach(x -&gt; {
          try {
              HashMapResize.debugResize(map, x, x);
          } catch (Throwable throwable) {
              throwable.printStackTrace();
          }
      });
  
      System.out.println(HashMapResize.currentResizeCalls);
  
  }
  </code></pre>
  
  <p>Well, <code>resize</code> was called and thus entries where rehashed, not what the documentation says. </p>
  
  <hr>
  
  <p>As said, the keys were not chosen randomly. These were set-up so that they would trigger the <code>static final int TREEIFY_THRESHOLD = 8;</code> property - when a bucket is converted to a tree. Well not really, since we need to hit also <code>MIN_TREEIFY_CAPACITY = 64</code> for the tree to appear; until than <code>resize</code> happens, or a bucket is doubled in size; thus rehashing of entries happens. </p>
  
  <p>I can only hint to why <code>HashMap</code> documentation is wrong in that sentence, since <em>before</em> java-8, a bucket was not converted to a Tree; thus the property would hold, from java-8 and onwards that is not true anymore. Since I am not sure about this, I'm not adding this as an answer. </p>