Understanding JVM Behavior: How Does `switch` Handle String Hash Collisions?

Question

During an interview, I was posed an intriguing question about how the Java Virtual Machine (JVM) handles a switch statement involving a String type. Specifically, I was asked whether the JVM employs LookupSwitch or TableSwitch for this operation. My initial thought was that it would utilize LookupSwitch due to the sparsity of String hashcodes. However, the interviewer added a layer of complexity by asking: "How does the JVM handle hash collisions when two different cases have the same hashcode?"

class Solution {
    static int switchString(String i) {
        int res;
        switch (i) {
            case "A":  // hashcode 65
                res = 0;
                break;
            case "FB":  // hashcode 2236
                res = 1;
                break;
            case "Ea":  // hashcode 2236
                res = 2;
                break;
            default:
                res = 3;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(switchString("Ea"));
    }
}

Can you help clarify how the JVM navigates through switch cases involving String objects, especially when hash collisions are involved?

For the first part question, I found I'm wrong here. the compiler has to pick either, a lookupswitch or tableswitch instruction

Answer 1

I've seen the decompiled .class bytecode

class Solution {
    Solution() {
    }

    static int switchString(String i) {
        byte var3 = -1;
        switch(i.hashCode()) {
        case 65:
            if (i.equals("A")) {
                var3 = 0;
            }
            break;
        case 2236:
            if (i.equals("Ea")) {
                var3 = 2;
            } else if (i.equals("FB")) {
                var3 = 1;
            }
        }

        byte res;
        switch(var3) {
        case 0:
            res = 0;
            break;
        case 1:
            res = 1;
            break;
        case 2:
            res = 2;
            break;
        default:
            res = 3;
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(switchString("Ea"));
    }
}

After examining the decompiled .class bytecode, it's apparent that the approach depends on the sparsity of the hashcodes of the strings, opting for either lookupswitch or tableswitch. In cases of hash collisions, the JVM employs a sequence of equals operations to distinguish between the colliding strings. This process involves a double switch mechanism to manage different cases effectively.

Answer 2

I'm not going to claim being an expert but I concur with your assessment on the LookupSwitch - Regarding hash collision I would imagine that's resolved with the equals() method.

Answer 3

We can reach some conclusions without particularly looking:

• tableswitch is used when the possible values of the expression being switched on are fairly clustered; lookupswitch otherwise. Most hash codes are going to be well spread; if tableswitch gets used at all it'll probably be rare.
• It was never the case that we could use the hashcodes alone to accomplish the switching; we would always have to use .equals anyway to check that we've actually got the right string. So presumably that's how we'll resolve hash collisions, by comparing them. (Conceivably we could fall back to a binary search thing if there were a ton of hash collisions, but for that to be a realistic scenario, the code has to be written adversarially.