Why should a HashMap be used(in functions) to determine which value to return(for a key) when an if else construct can do the job in better time?

Question

While I was recently working at a big company, I noticed that the programmers there followed this coding style:

Suppose I have a function that returns 12 if the input is A, 21 if the input is B, and 45 if the input is C.

So I can write the function signature as:

int foo(String s){
    if(s.equals("A"))      return 12;
    else if(s.equals("B")) return 21;
    else if(s.equals("C")) return 45;
    else throw new RuntimeException("Invalid input to function foo");
}

But on code review I was asked to change the function to the following:

int foo(String s){
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    map.put("A", 12);
    map.put("B", 21);
    map.put("C", 45);
    return map.get(s);
}

I can't convince myself on why the second code is better than the first. The second code would definitely take more time to run.

The only reason to use the second code can be that it offers better readability. But if the function is getting called many times then wouldn't the second function slow down the running time of the utility calling it?

What do you think about this?

Answer 1

The point is to move the creation of the hashmap outside the function and do it once (or just less times than otherwise).

private static final Map<String, Integer> map;
static{
    Map<String, Integer> temp = new HashMap<String, Integer>();
    temp.put("A", 12);
    temp.put("B", 21);
    temp.put("C", 45);
    map = Collections.unmodifiableMap(temp);//make immutable
}

int foo(String s){
    if(!map.containsKey(s))
        throw new RuntimeException("Invalid input to function foo");

    return map.get(s);
}

However java has since java7 been able to have (final) strings in switches:

int foo(String s){
    switch(s){
    case "A":
        return 12;
    case "B": 
        return 21;
    case "C": 
        return 45;
    default: throw new RuntimeException("Invalid input to function foo");
}

Answer 2

In your second example, the Map should be a private static member to avoid redundant initialization overhead.

For large amounts of values, the map will perform better. Using a hashtable, one can look up the answer in constant time. The multiple-if construct has to compare the input to each of the possibilities until it finds the right answer.

In other words, the map lookup is O(1) while the ifs are O(n) where n is the number of possible inputs.

Map creation is O(n), but is only done once if it is static constant state. For a lookup performed frequently the map will outperform the if statements in the long run, at the cost of slightly more time when the program is starting up (or the class is loaded, depending on language).

That being said, the map is not always the right tool for this job. It is nice when there are a lot of values, or the values must be configurable through a text file, user input, or database (in which case the map acts as a cache).

Answer 3

There are two speeds in software: the time it takes to write/read/debug the code; and the time it takes to execute the code.

If you can convince me (and your code reviewers) that the hashmap function is indeed slower than the if/then/else (after refactoring to make a static hashmap) AND you can convince me/reviewers that its called enough times to make an actual difference, then go ahead and replace the hashmap with the if/else.

Otherwise, the hashmap code is eminently readable; and (probably) bugfree; you can determine that quickly just by looking at it. You can't really say the same thing about the if/else without really studying it; the difference is even more exaggerated when there are hundreds of options.

Answer 4

I greatly prefer the HashMap style answer.

There's a metric for this

There is a code quality metric called Cyclomatic Complexity. This metric basically counts the number of different paths through the code (how to compute Cyclomatic Complexity).

For every possible execution path a method becomes harder and harder to both understand AND fully test for correctness.

It boils down to the fact that "controlling keywords" like: ifs, elses, whiles, etc... leverage boolean tests that can be wrong. Repeated use of "controlling keywords" produces fragile code.

Additional Benefits

Also, the "map-based approach" encourages developers to think of the input-output pairs as a dataset that can be extracted, reused, manipulated at runtime, tested, and verified. For example, below I rewrote "foo" so that we are not permanently locked into "A->12, B->21, C->45":

int foo(String s){
    HashMap<String, Integer> map = getCurrentMapping();
    return map.get(s);
}

rachet_freak mentions this type of refactor in his answer, he argues for speed and reuse, I am arguing for runtime flexibility (although using a immutable collection can have enormous benefits depending on the situation)

Answer 5

Data is better than code. Not least because it's too tempting to add yet another branch to code, yet adding a row to a table is tough to get wrong. This question is a small instance of this. You're writing a lookup table. Either write an implementation, complete with conditional logic and documentation, or write the table out then lookup in it.

A table of data is always a better representation of some data than code is, modulo optimisation passes. How difficult the table is to express may be language dependent - I don't know Java, but would hope it can implement a look up table more simply than the example in the OP.

This is a lookup table in python. If this is viewed as inviting conflict, please consider that the question is not tagged java, the refactoring is language agnostic and that most people don't know java.

def foo(s):
    return {
               "A" : 12,
               "B" : 21,
               "C" : 45,
           }[s]

The idea of restructuring the code to reduce runtime has merit, but I'd much rather use a compiler that hoists the common setup than do so myself.