HashMap vs Switch statement performance

Question

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.

Answer 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?

Answer 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. You should NOT try to improve performance for the case, 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?

Answer 3

TL/DR

Base it on code readability and maintainability. Both are cost O(1) and provide almost no difference (though switches generally will be slightly faster).

In this particular case a map would be faster, as a switch returns an address and then must go to that address to identify the return value. (A rare case example). If your switch is just calling functions anyways, a Map would also be faster.

To make things faster, I would ensure using numeric cases and avoid using strings via constants or enumerators (typescript).

(edited) I confirmed by expectation: How does Java's switch work under the hood? with switches.

More detailed answer

In the weeds:

A switch statement will usually be higher performance. It creates a lookup table and goto reference and starts at that point. However there are exceptions.

When you utilize a simple switch such as return map.get(x) vs. switch(1=>'a', 2=>'b', etc). That is because the map can directly return the value desired where the switch will stop map the addresses and continue until break or the end is met.

In any event, they should be extremely similar in execution cost.

Think about maintainability and readability of the code

Using a map decouples the data, which can gain the benefit of creating "switch" cases dynamically. More detailed below.

If there are several complex functions/processes you need to handle, it may be easier to read/write if you utilize a map instead. Especially if the switch statement starts to exceed 20 or 30 options.

Personally used case example for maps:

I have been utilize the following pattern for flux (Redux/useReducer) in React applications for some time.

I create a central map where I map the trigger as the key, and the value is a functional reference. I can then load cases where and when it makes sense.

Initially I used this to be able to break the use cases down to reduce file size and group cases of similar function together in a more organized fashion. Although I later evolved it to be loaded in domains and configured the events and data in a domain hook, like useUser, useFeedback, useProfile, etc...

Doing so allowed me to create the default state, initialization functions, events, and so forth into a logical file structure, it also allowed me to keep the footprint low until needed.

One note to keep in mind

Using a map does not allow for drop through, though most people consider this code smell anyways. At the same time it protects from accidental fall through.

Answer 4

In your case, since you are using an Integer key for your HashMap and a plain 'int' for your switch statement, the best performing implementation will be the switch statement unless the number of passes through this section of code is very high (tens or hundreds of thousands).

Answer 5

If I have that kind of example I use Guava ImmutableMaps (sure You can use java 9 builder as well).

private static final Map<String, String> EXAMPLE = ImmutableMaps.<String, String>>builder()
    .put("a", "100")
    .put("b", "200")
    .build(); 

That way they are immutable and initated only once.

Sometimes I use strategy pattern that way:

private static final Map<String, Command> EXAMPLE = ImmutableMaps.<String, String>>builder()
    .put("a", new SomethingCool())
    .put("b", new BCool())
    .build(); 

private static final Command DEFAULT= new DefCommand();

Use:

EXAMPLE.getOrDefault("a", DEFAULT).execute(); //java 8

About performance just pick readability. You will thank me later (1 year later) :D.