美文网首页
swtich-case的实现原理与优化

swtich-case的实现原理与优化

作者: 蜗牛是不是牛 | 来源:发表于2022-11-03 21:42 被阅读0次

实现原理

语言的底层就是算法,所以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;
    }
}

我们使用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
            }

可以看到,我们确实是优化成了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;
    }
}

现在,我们的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行字节码
            }

可以看到,这里自动补上了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
            }

我们发现,现在变为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();
}

将来要添加case或删除case,只要在actions中添加或删除值就行,美滋滋。
综上,我们可以知道:

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

来自:https://juejin.cn/post/7011863135837487118

相关文章

网友评论

      本文标题:swtich-case的实现原理与优化

      本文链接:https://www.haomeiwen.com/subject/zdmutdtx.html