HashMap vs Switch statement performance

A HashMap essentially has O(1) performance while a switch state can have either O(1) or O(log(n)) depending on if the compiler uses a tableswitch or lookup switch.

Understandably, if a switch statement is written as such,

switch (int) {
    case 1:
    case 2:
    case 3:
    case 4:
    default:
}

then it would use a tableswitch and clearly have a performance advantage over a standard HashMap. But what if the switch statement is sparse? These would be two examples that I would be comparing:

HashMap<Integer, String> example = new HashMap<Integer, String>() {{
        put(1, "a");
        put(10, "b");
        put(100, "c");
        put(1000, "d");
}};

.

switch (int) {
    case 1:
        return "a";
    case 10:
        return "b";
    case 100:
        return "c";
    case 1000:
        return "d";
    default:
        return null;
}

What would provide more throughput, a lookupswitch or HashMap? Does the overhead of the HashMap give the lookupswitch an advantage early but eventually tapers off as the number of cases/entries increase?

Edit: I tried some benchmarks using JMH, here are my results and code used. https://gist.github.com/mooman219/bebbdc047889c7cfe612 As you guys mentioned, the lookupswitch statement outperformed the HashTable. I'm still wondering why though.

Solution 1:

The accepted answer is wrong here.

http://java-performance.info/string-switch-implementation/

Switches will always be as fast as if not faster than hash maps. Switch statements are transformed into direct lookup tables. In the case of Integer values (ints, enums, shorts, longs) it is a direct lookup/jmp to the statement. There is no additional hashing that needs to happen. In the case of a String, it precomputes the string hash for the case statements and uses the input String's hashcode to determine where to jump. In the case of collision, it does an if/else chain. Now you might think "This is the same as HashMap, right?" But that isn't true. The hash code for the lookup is computed at compile time and it isn't reduced based on the number of elements (lower chance of collision).

Switches have O(1) lookup, not O(n). (Ok, in truth for a small number of items, switches are turned into if/else statements. This provides better code locality and avoids additional memory lookups. However, for many items, switches are changed into the lookup table I mentioned above).

You can read more about it here How does Java's switch work under the hood?

Solution 2:

It depends:

1. If there are a few items | fixed items. Using switch if you can ( worst case O(n))

2. If there are a lot of items OR you want to add future items without modifying much code ---> Using hash-map ( access time is considered as constant time)

3. For your case. You should not worry about performance because the difference in execution time is nanoseconds. Just focus on readability/maintainability of your code. Is it worth optimizing a simple case to improve a few nanoseconds?