title: What is the optimal capacity and load factor for a fixed-size HashMap?
body: <p>I'm trying to figure out the optimal capacity and load factor for a specific case. I think I got the gist of it, but I'd still be thankful for a confirmation from someone more knowledgable than me. :)</p>
  
  <p>If I know that my HashMap will fill up to contain, say, 100 objects, and will spend most of the time having 100 objects, I'm guessing that the optimal values are initial capacity 100 and load factor 1? Or do I need capacity 101, or are there any other gotchas?</p>
  
  <p>EDIT: OK, I set aside a few hours and did some testing. Here are the results:</p>
  
  <ul>
  <li>Curiously, capacity, capacity+1, capacity+2, capacity-1 and even capacity-10 all yield exactly the same results. I would expect at least capacity-1 and capacity-10 to give worse results.</li>
  <li>Using initial capacity (as opposed to using default value of 16) gives noticable put() improvement - up to 30% faster.</li>
  <li>Using load factor of 1 gives equal performance for small number of objects, and better performance for larger number of objects (>100000). However, this does not improve proportionally to the number of objects; I suspect there is additional factor that affects the results.</li>
  <li>get() performance is a bit different for different number of objects/capacity, but though it might slightly vary from case to case, generally it's not affected by initial capacity or load factor.</li>
  </ul>
  
  <p>EDIT2: Adding some charts on my part as well. Here's the one illustrating difference between load factor 0.75 and 1, in cases where I initialize HashMap and fill it up to full capacity. On y scale is time in ms (lower is better), and x scale is size (number of objects). Since size changes linearly, the time required grows linearly as well.</p>
  
  <p>So, let's see what I got. The following two charts show the difference in load factors. First chart shows what happens when HashMap is filled to capacity; load factor 0.75 performs worse because of resizing. However, it's not consistently worse, and there are all sorts of bumps and hops - I guess that GC has a major play in this. Load factor 1.25 performs the same as 1, so it's not included in the chart.</p>
  
  <p><img src="https://i.stack.imgur.com/zPXiC.jpg" alt="fully filled"></p>
  
  <p>This chart proves that 0.75 was worse due to resizing; if we fill the HashMap to half capacity, 0.75 is not worse, just... different (and it should use less memory and have unnoticably better iteration performance).</p>
  
  <p><img src="https://i.stack.imgur.com/UmPGa.jpg" alt="half full"></p>
  
  <p>One more thing I want to show. This is get performance for all three load factors and different HashMap sizes. Consistently constant with a little variation, except for one spike for load factor 1. I'd really want to know what that is (probably GC, but who knows).</p>
  
  <p><img src="https://i.stack.imgur.com/8Ajbx.jpg" alt="go spike"></p>
  
  <p>And here's the code for those interested:</p>
  
  <pre><code>import java.util.HashMap;
  import java.util.Map;
  
  public class HashMapTest {
  
    // capacity - numbers high as 10000000 require -mx1536m -ms1536m JVM parameters
    public static final int CAPACITY = 10000000;
    public static final int ITERATIONS = 10000;
  
    // set to false to print put performance, or to true to print get performance
    boolean doIterations = false;
  
    private Map&lt;Integer, String&gt; cache;
  
    public void fillCache(int capacity) {
      long t = System.currentTimeMillis();
      for (int i = 0; i &lt;= capacity; i++)
        cache.put(i, "Value number " + i);
  
      if (!doIterations) {
        System.out.print(System.currentTimeMillis() - t);
        System.out.print("\t");
      }
    }
  
    public void iterate(int capacity) {
      long t = System.currentTimeMillis();
  
      for (int i = 0; i &lt;= ITERATIONS; i++) {
        long x = Math.round(Math.random() * capacity);
        String result = cache.get((int) x);
      }
  
      if (doIterations) {
        System.out.print(System.currentTimeMillis() - t);
        System.out.print("\t");
      }
    }
  
    public void test(float loadFactor, int divider) {
      for (int i = 10000; i &lt;= CAPACITY; i+= 10000) {
        cache = new HashMap&lt;Integer, String&gt;(i, loadFactor);
        fillCache(i / divider);
        if (doIterations)
          iterate(i / divider);
      }
      System.out.println();
    }
  
    public static void main(String[] args) {
      HashMapTest test = new HashMapTest();
  
      // fill to capacity
      test.test(0.75f, 1);
      test.test(1, 1);
      test.test(1.25f, 1);
  
      // fill to half capacity
      test.test(0.75f, 2);
      test.test(1, 2);
      test.test(1.25f, 2);
    }
  
  }
  </code></pre>