Recently I was wondering if there are alternatives to the Java Collections Implementations and if they have a better performance than the java.util package. Especially the performance of HashMaps was of interest. At the company I work at we have keep lots of business data entries in memory and those entries are stored in HashMaps.

In several Articles I read that other implementaions are faster than java.util.HashMap. So I was conducting a performance check.

Alternatives

The alternatives to java.util that I considered were:

 <dependency>
        <groupId>net.sf.trove4j</groupId>
        <artifactId>trove4j</artifactId>
        <version>3.0.3</version>
    </dependency>
    <dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>15.0</version>
    </dependency>
    <dependency>
      <groupId>commons-collections</groupId>
      <artifactId>commons-collections</artifactId>
      <version>3.2.1</version>
    </dependency>
    <dependency>
        <groupId>javolution</groupId>
        <artifactId>javolution</artifactId>
        <version>5.5.1</version>
    </dependency>

Result

java.util.HashMap is the fastest implementation to date! I checked if different constructors have an impact to the performance of the individual HashMap. It took on average 45ms to get all Objects out of a HashMap with 1.000.000 items, and it took on average 80ms to put 1.000.00 items into the HashMap. Here is the data:

The performance of the java.util.HashMap(1_000_000,1f) testrun seems to be impacted by the startup and optimizing of the code by the JVM. I think this value is not accurate. A reordering of the testruns supports this thesis.

Lets take a look at the results in a chart:

Conclusion

The java.util.HashMap implementaion is still faster than other implementations. At this point it is not worthwhile to use other libraries in most cases.

In Java 7 there seem to be major Collection improvements as this article noted that in Java 6 the Trove library was faster than in java.util.HashMap. Using constructors with a predetermined initial map size improves inserting into the map, but not by a large extend.

Links

• http://javolution.org/target/site/apidocs/javolution/util/FastMap.html
• http://karussell.wordpress.com/2009/09/03/java-collections-are-there-alternatives/
• http://stackoverflow.com/questions/3972127/hashmap-alternatives-for-memory-efficient-data-storage
• http://stackoverflow.com/questions/3973431/performance-of-collection-class-in-java
• http://karussell.wordpress.com/2009/09/03/java-collections-are-there-alternatives/

Source

Environment:

java version “1.7.0_40”
Java(TM) SE Runtime Environment (build 1.7.0_40-b43)
Java HotSpot(TM) 64-Bit Server VM (build 24.0-b56, mixed mode)

The sourcecode of the performance Test:

package info.klewitz.hashmap;

import com.google.common.collect.Maps;
import gnu.trove.map.hash.THashMap;
import javolution.util.FastMap;
import org.apache.commons.collections.FastHashMap;
import org.apache.commons.collections.FastTreeMap;
import org.springframework.util.StopWatch;
import org.testng.annotations.AfterClass;
import org.testng.annotations.AfterMethod;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class HashMapSpeedTest {

  public static final int SIZE = 1_000_000;
  private Set<String> objects;
  private StopWatch stopWatch;

  @BeforeClass
  public void setUp(){
    System.out.println("creating " + SIZE + " objects");
    System.out.println("Implementation;get();put()");
    objects = getObjects();
    stopWatch = new StopWatch();
  }

  @DataProvider
  public Object[][] mapProvider(){
    return new Object[][]{
        { new HashMap<String,Object>(SIZE,1f),"SIZE,1f" },
        { new HashMap<String,Object>(SIZE,10f),"SIZE,10f" },
        { new HashMap<String,Object>(SIZE,0.3f),"SIZE,0.3f" },
        { new HashMap<String,Object>(SIZE,0.1f),"SIZE,0.1f" },
        { new HashMap<String,Object>(),"" },
        { new HashMap<String,Object>(SIZE),"SIZE" },
        { new THashMap<String,Object>(),""},
        { new THashMap<String,Object>(SIZE), "SIZE"},
        { new THashMap<String,Object>(SIZE,1f), "SIZE,1f"},
        { new FastMap<String,Object>(), ""},
        { new FastMap<String,Object>(SIZE), "SIZE"},
        { new FastHashMap(),""},
        { new FastHashMap(SIZE),"SIZE"},
        { new TreeMap<String,Object>(),""},
        {Maps.newHashMap(),""},
        { new FastTreeMap(),""},
    };
  }

  @Test(dataProvider = "mapProvider",singleThreaded = true)
  public void test(Map<String,Object> map,String typeExtension) {
    String type = map.getClass().getName() + "("+typeExtension+")";

    stopWatch.start(type+"put()");
    for(String o:objects){
      map.put(o,o);
    }
    stopWatch.stop();
    long putTime = stopWatch.getLastTaskTimeMillis();

    stopWatch.start(type+"get()");
    for(String o:objects){
      map.get(o);
    }
    stopWatch.stop();
    long getTime = stopWatch.getLastTaskTimeMillis();
    System.out.println(type + ";" + getTime + ";" + putTime);
    map.clear();
    System.gc();
  }

  @AfterClass
  public void tearDown() throws Exception {
    System.out.println(stopWatch.prettyPrint());
  }

  private Set<String> getObjects() {
    Set<String> objects = new HashSet<>();
    for(int i=0;i< SIZE;i++){
      objects.add("" + i);
    }
    return objects;
  }
}