switch-case的实现原理与优化方案

LloydFinch 9/25/2021 JavaJVM

# 实现原理

语言的底层就是算法，所以switch-case的底层也是算法: 数组和二分查找。

switch-case是一个条件语句，也就是说: 如果满足条件，那么就执行对应的指令，也就是: 找条件！那么就是查找！也就是算法里的查找！

那么为什么是数组和二分查找呢？

其实switch-case的状态值只能存放一个int的大小，比如byte，char，shor，int等。如果大于一个int的大小就不可以，比如long，double等。那么String为什么也可以呢？因为switch(String)会取String对应的hashcode，而hashcode正好是一个int的大小。

正是因为状态值是一个int的大小，所以可以对状态值进行排序，如果状态值是紧凑的，那么就会将状态值优化为tableswitch(可以理解为数组)，查找效率就是O(1)的；如果状态值是分散的，那么就会优化为lookupswitch，然后使用二分查找来找条件。

现在我们来证明，假设有如下代码:

public void test(int a){
    int b = 10;
    switch(a) {
        case 1: 
            b = 1;
        break;
        case 2: 
            b = 2;
        break;
        case 3: 
            b = 3;
        break;
        default:
            b = 4;
        break;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们使用javac指令得到Test.class对象，然后使用javap -verbose Test.class得到字节码如下(这里只粘出关键部分):

public void test(int);
    descriptor: (I)V // 表示函数参数类型是int，返回类型是void
    flags: (0x0001) ACC_PUBLIC // 表示函数是public的
    Code:
      stack=1, locals=3, args_size=2 // 栈深度为1，局部变量表为2，参数个数为2
         0: bipush        10
         2: istore_2
         3: iload_1
         4: tableswitch   { // 1 to 3 看这里，优化成了tableswitch
                       1: 32 // 表示case到1就执行第32行字节码
                       2: 37
                       3: 42
                 default: 47
            }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

可以看到，我们确实是优化成了tableswitch，因为我们case的值是"连续的"，连续的肯定是紧凑的，那么紧凑必须是连续的吗？非也！我们修改代码如下:

public void test(int a){
    int b = 10;
    switch(a) {
        case 1: 
            b = 1;
        break;
        case 3: 
            b = 3;
        break;
        case 5: 
            b = 5;
        break;
        default:
            b = 4;
        break;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

现在，我们的case值是1、3、5，不连续了，我们继续javap一下来看字节码:

public void test(int);
    descriptor: (I)V
    flags: (0x0001) ACC_PUBLIC
    Code:
      stack=1, locals=3, args_size=2
         0: bipush        10
         2: istore_2
         3: iload_1
         4: tableswitch   { // 1 to 5 这里自动补上了2和4
                       1: 40
                       2: 55 // 执行第55行字节码
                       3: 45
                       4: 55 // 也是执行第55行字节码
                       5: 50
                 default: 55 // 也是执行第55行字节码
            }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以看到，这里自动补上了2和4，变为连续的了，为的就是凑齐一个数组，然后可以直接根据下标进行查找定位，从而达到O(1)的时间复杂度。而且2和4跟default一样，都执行第55行字节码，因为本来就没有2和4，就按default处理。

现在，让我们修改case 3为case 100，其他不变，然后看字节码:

public void test(int);
    descriptor: (I)V
    flags: (0x0001) ACC_PUBLIC
    Code:
      stack=1, locals=3, args_size=2
         0: bipush        10
         2: istore_2
         3: iload_1
         4: lookupswitch  { // 3 变为lookupswitch了
                       1: 40
                       5: 51
                     100: 45
                 default: 56
            }

1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们发现，现在变为lookupswitch了，并且还发现，case的值按照顺序排序了，这是为了使用二分查找。

因为从5到100断层比较严重，我们不可能为了O(1)的时间复杂度去插入95个值，可以看出JVM在时间和空间还是衡量的比较人性化的。

这里需要注意两点:

tableswitch的生成的条件是"紧凑"而不是"数值小"，比如10001，10002，10003也会优化成tableswitch，而1，100，200就只能优化成lookupswitch。
如果case的值是String，那么会优化成lookupswitch，因为hashcode一般都是比较分散的(避免碰撞嘛)。

# 优化

明白了上述原理，我们怎么在代码中优化呢？很简单!

第一: 我们尽可能的让case的值连续，或者紧凑，千万别为了装x而xjb写，而且尽量不使用String(因为hashcode本来就比较分散)。
第二: 如果业务比较复杂，或者出于拓展性考虑，那么可以使用hashmap来优化，毕竟hashmap的时间复杂度大部分情况都是O(1)的，而且将来修改也满足OCP。

比如上述代码我们就可以这样用hashmap来优化:

// 首先定义一个Action接口:
public interface Action {
    int action();
}

// 然后初始化
private HashMap<Integer, Action> actions = new HashMap<>();
{
    actions.put(1, () -> 1); // case 1
    actions.put(3, () -> 3); // case 3
    actions.put(5, () -> 5); // case 5
}

// test函数就可以简写为如下:
public void test(int a) {
    int b = actions.get(a).action();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

将来要添加case或删除case，只要在actions中添加或删除值就行，美滋滋。

综上，我们可以知道:

1 建议优先使用hashmap来处理switch-case这种复合条件的场景。
2 如果条件比较简单，或者不必考虑拓展性，可以使用swtich-case，但是建议非必要不使用 String来作为case值，而且建议case值一定要紧凑。

switch-case对String的特殊处理

AndroidUFO

Choose mode