Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Realize the principle of

The bottom of a language is an algorithm, so the bottom of switch-case is an algorithm: arrays and binary lookup.

Switch-case is a conditional statement, meaning that if the condition is met, then the corresponding instruction is executed, i.e., find the condition! So find! That’s the search in the algorithm!

So why array and binary lookup?

In fact, the status value of switch-case can only store one int size, such as byte, char, shor, int, etc. Not if the size is greater than an int, such as long, double, etc. So why is String ok? Because switch(String) takes the hashcode of String, and hashCode is exactly the size of an int.

It is because the status value is an int size, so the status value can be sorted. If the status value is compact, the status value will be optimized to tableswitch(can be understood as an array). The search efficiency is O(1). If the status values are scattered, then lookupswitch is optimized, and binary lookup is used to find the condition.

Now to prove it, assume the following code:

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; }}Copy the code

We use the javac directive to get the test. class object, and then use javap-verbose test. class to get the bytecode as follows (only the key parts are pasted here):

public void test(int); Descriptor: (I)V // void flags: (0x0001) ACC_PUBLIC // Code of the function is public: Stack =1, locals=3, args_size=2 // The stack depth is 1, the local variable table is 2, and the number of parameters is 2 0: bipush 10 2: ISTORE_2 3: ILoAD_1 4: Tableswitch {// 1 to 3 Tableswitch 1:32 2:37 3:42 default: 47}Copy the code

And you can see that we did optimize tableswitch, because our case values are “contiguous”, contiguous must be compact, so does the compact have to be contiguous? Not too! We modify the code as follows:

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; }}Copy the code

Now, our case values are 1, 3, 5, not consecutive, so let’s go ahead and look at the bytecode in 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 and 4 1: 40 2: 55 3: 45 4: 55 5: 50 default: 55}Copy the code

As you can see, it automatically fills in the 2 and the 4, so it’s continuous, so it’s an array, and then you can locate it by subscript, so it’s O(1) time.

Now, let’s change case 3 to case 100, all else unchanged, and look at the bytecode:

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 changed to lookupswitch 1:40 5:51 100:45 default: 56}Copy the code

We see that it is now lookupswitch, and we also see that the case values are sorted in order to use binary lookup.

Because the gap between 5 and 100 is so severe that it is impossible to insert 95 values for O(1) time complexity, you can see that the JVM is humane in time and space.

Two points to note here:

  • If tableswitch is generated, it must be compact rather than small. For example, if 10001,10002,10003 is optimized to tableswitch, and if 1,100,200 is optimized to lookupswitch only.
  • If the case value is String, then lookupswitch is optimized because HashCode is generally discrete (to avoid collisions).

To optimize the

With that in mind, how can we optimize in our code? Very simple!

  • First: we try to make case values as contiguous or compact as possible, never write XJB to fit x, and try not to use strings (because HashCode is naturally scattered).

  • Second: If the business is complex, or for extensibility, you can use HashMap for optimization, after all, the time complexity of HashMap is O(1) in most cases, and the future modification will also meet OCP.

To sum up, we can know that:

  • 1 It is recommended to use hashMap to handle switch-case compound condition scenarios.
  • Swtich-case can be used if the condition is simple or extensibility is not considered, but it is not necessary to use String as the case value, and it is recommended that the case value must be compact.