Java Performance: Map vs If/Else

December 17, 2010

I came across an interesting javascript article the other day on how not to write javascript: Google Closure: How not to write JavaScript

The interesting part of this article that caught my eye was using a map instead of a switch or if/else statement to check for string comparisons. This got me thinking of whether the same would hold true for Java. So, the question is ” which is faster: using an if/else to match results or map-based operations”? At first thought, you might think if/else since the VM optimizes the bytecode and there is no requirement to setup a call stack to invoke a method. However, if/else has to use equals which must walk the string characters matching each one. In the case of maps, they are optimized for fast lookups using buckets via the hash codes. Thus, you generally only have a few instances to invoke equals against rather than each one (in the case when a value is last in the list). So let’s get to the results…click to continue reading.

If/Else Lookup

public boolean verify(String test) {
    if ("abcde".equals(test)) {
        return true;
    }
    else if ("fghij".equals(test)) {
        return true;
    }
    else if ("klmno".equals(test)) {
        return true;
    }
    else if ("pqrst".equals(test)) {
        return true;
    }
    else if ("uvwxyz".equals(test)) {
        return true;
    }
    else {
        return false;
    }
}

Map-based Lookups

public boolean verify(String test) {
    return MAP.containsKey(test);
}

To actually test the instances, I loop 10,000 times checking for each known string once to force it to hit each instance:

Map<String, Boolean> MAP = new HashMap<String, Boolean>();
String[] test = { "abcde", "fghij", "klmno", "pqrst", "uvwxyz" };
for (String a : test) { MAP.put(a, Boolean.TRUE); }
 
long start1 = System.nanoTime();
for (int i = 0; i < 10000; i++) {
    for (int j = 0; j < test.length; j++) {
        if (!verify(test[j])) {
            System.out.println("invalid: ".concat(test[j]));
        }
    }
}

Running this code against JDK 1.6 results in the following results when run locally on a dual-core laptop:

If/Else: 3.23 ms
Map: 2.70 ms

Obviously the difference is minimal, but when you are talking about thousands of invocations in a large scale webserver, every millisecond counts and adds up.

So, in general, maps can actually be a good alternative than long if/else methods (or switch statements circa JDK 7/8). Every use case is different though, so this rule may not always be the case and should be tested in individual deployments.

2 Responses to “Java Performance: Map vs If/Else”

  1. The performance difference is surprising – especially when the strings used in your test should have been all intern’d, and so the equals method should have been using object identity instead of walking the chars.

  2. @CapMorgan, the difference isn’t in the equals method so much as the number of times it is invoked. At a worst case scenario, if/else will call equals on each string in the if else blocks. Maps, on the other hand as a worst case scenario will only call equals on those strings within the matching bucket which would be a subset. So its O(n) compared to O(1)-O(n).