Guava ImmutableMap has noticeably slower access than HashMap

While working on a memory benchmark of some high-throughput data structures, I realized I could use an ImmutableMap with only a little refactoring.

Thinking this would be an improvement, I threw it into the mix and was surprised to discover that not only was it slower than HashMap, in a single-threaded environment it appears to be consistently slower even than ConcurrentHashMap!

You can see the full benchmark

The meat of the test is pretty simple, time how long it takes to get a large number of random strings that may exist in the map.

public static void timeAccess(Map<String,String> map) {
    Random rnd = new Random(seed);
    int foundCount = 0;

    long start = System.nanoTime();

    for(int i = 0; i < loop; i++) {
        String s = map.get(RndString.build(rnd));
        if(s != null)
            foundCount++;
    }

    long stop = System.nanoTime() - start;

    System.out.println("Found "+foundCount+" strings out of "+loop+" attempts - "+
        String.format("%.2f",100.0*foundCount/loop)+" success rate.");
    System.out.println(map.getClass().getSimpleName()+" took "+
        String.format("%.4f", stop/1_000_000_000.0)+" seconds.");
    System.out.println();
}

And running this against a HashMap, a ConcurrentHashMap, and an ImmutableMap, all containing the same values, consistently showed a dramatic slowdown when using ImmutableMap - often upwards of 15% slower. The more sparse the map (i.e. the more often map.get() returned null) the greater the disparity. Here's the result of a sample run:

Found 35312152 strings out of 100000000 attempts - 35.31 success rate.
HashMap took 29.4538 seconds.

Found 35312152 strings out of 100000000 attempts - 35.31 success rate.
Concurre