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;
  }
}

Welcome to my new Blog!

I am surprised how well the installation went so far. It`s been some time since I had a Blog or a CMS. Now I am trying to find out how well the design and security of WordPress has become. I played around with Nuke, PostNuke, Joomla and Mambo around the year 2004.

Now the Modularity, Security and Interface Quality of WordPress really impresses me compared to the CMS Systems some time ago.

Let`s see how well it goes!