title: Java HashMap performance optimization / alternative
body: <p>I want to create a large HashMap but the <code>put()</code> performance is not good enough. Any ideas?</p>
  
  <p>Other data structure suggestions are welcome but I need the lookup feature of a Java Map:</p>
  
  <p><code>map.get(key)</code></p>
  
  <p>In my case I want to create a map with 26 million entries. Using the standard Java HashMap the put rate becomes unbearably slow after 2-3 million insertions. </p>
  
  <p>Also, does anyone know if using different hash code distributions for the keys could help? </p>
  
  <p>My hashcode method:</p>
  
  <pre><code>byte[] a = new byte[2];
  byte[] b = new byte[3];
  ...
  
  public int hashCode() {
      int hash = 503;
      hash = hash * 5381 + (a[0] + a[1]);
      hash = hash * 5381 + (b[0] + b[1] + b[2]);
      return hash;
  }
  </code></pre>
  
  <p>I am using the associative property of addition to ensure that equal objects have the same hashcode. The arrays are bytes with values in the range 0 - 51. Values are only used once in either array. The objects are equal if the a arrays contain the same values (in either order) and the same goes for the b array. So a = {0,1} b = {45,12,33} and a = {1,0} b = {33,45,12} are equal.</p>
  
  <p>EDIT, some notes:</p>
  
  <ul>
  <li><p>A few people have criticized using a hash map or other data structure to store 26 million entries. I cannot see why this would seem strange.  It looks like a classic data structures and algorithms problem to me. I have 26 million items and I want to be able to quickly insert them into and look them up from a data structure: give me the data structure and algorithms.</p></li>
  <li><p>Setting the initial capacity of the default Java HashMap to 26 million <em>decreases</em> the performance.</p></li>
  <li><p>Some people have suggested using databases, in some other situations that is definitely the smart option. But I am really asking a data structures and algorithms question, a full database would be overkill and much slower than a good datastructure solution (after all the database is just software but would have communication and possibly disk overhead).</p></li>
  </ul>