Java HashMap Performance

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:

Implementation get() in ms put() in ms
java.util.HashMap(1_000_000,1f) 60 1728
java.util.HashMap(1_000_000,10f) 43 104
java.util.HashMap(1_000_000,0.3f) 42 78
java.util.HashMap(1_000_000,0.1f) 42 112
java.util.HashMap() 40 87
java.util.HashMap(1_000_000) 41 76
gnu.trove.map.hash.THashMap() 77 250
gnu.trove.map.hash.THashMap(1_000_000) 70 74
gnu.trove.map.hash.THashMap(1_000_000,1f) 161 155
javolution.util.FastMap() 119 272
javolution.util.FastMap(1_000_000) 100 116
org.apache.commons.collections.FastHashMap() 65 125
org.apache.commons.collections.FastHashMap(1_000_000) 64 87
java.util.TreeMap() 269 305
java.util.HashMap() 48 89
org.apache.commons.collections.FastTreeMap() 269 331

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

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

2 thoughts on “Java HashMap Performance

  1. AirConcurrentMap is our Java ConcurrentNavigableMap that is very fast at scanning (iterating, forEach, and a proprietary internal threaded scan). It would be great to see a comparison of these scan techniques for various Maps. In our tests, it is the fastest available as Map size increases. Also, it is concurrent and ordered, like ConcurrentSkipListMap, and very memory efficient. Generally it is best for large Maps, above about 1K entries. We have many tests of our own, including simple tests, Java Microbenchmarking Harness tests, and our own tests with pretty charts. It is at boilerbay.com. It is free for non-commercial use, and licensed for commercial use with or without source.

    We also have a commercial Java embedded database called InfinityDB which is an extended ConcurrentNavigableMap at boilerbay.com. The performance is less than the in-memory Maps. It is transactional, compressing, caching, robust, extensible, simple, nosql, DBA-free, and has dynamic schema evolution.

Leave a Reply

Your email address will not be published. Required fields are marked *