- （単純）このコードの結果は何ですか？
switch(5){ default: System.out.print(0); case 1: System.out.print(1); break; case 4: System.out.print(4); case 2: System.out.print(2); }
- 次の2つのオプションはほぼ同じです。 少し異なるリテラル。
少なくともJITを無効にすると// 1 switch("BBBBBB"){ case "AaAaAa": break; case "AaAaBB": break; case "AaBBAa": break; case "AaBBBB": break; case "BBAaAa": break; case "BBAaBB": break; case "BBBBAa": break; case "BBBBBB": break; }
// 2 switch("BBBBBB_8"){ case "AaAaAa_1": break; case "AaAaBB_2": break; case "AaBBAa_3": break; case "AaBBBB_4": break; case "BBAaAa_5": break; case "BBAaBB_6": break; case "BBBBAa_7": break; case "BBBBBB_8": break; }
（-Djava.compiler = NONE） 、最初のスイッチの実行が数倍遅くなるのはなぜですか？ ループで確認してください！ このようなコードを使用してJITを実行することはできませんが、少しプレイすると、わずかな違いが顕著になります。 - （少なくともJDK 7で）n個のケース間で同じ値を見つけるためのアルゴリズムの計算の複雑さは何ですか？
回答：
- 01
- hashCode（）メソッドは、最初のスイッチのすべての行に対して同じ値を返します。 以下の詳細。
- 場合によっては、O（1）、O（log n）、さらにはO（n）に達することもあります。
正しくしましょう。 ケース値は、簡潔にするためにキーを呼び出します。
テーブルスイッチ
最初のタスクの例を見てみましょう。 それをコンパイルし、結果のバイトコードを逆アセンブルします。
javap -c Main.class
0: iconst_5 // 5 1: tableswitch { // 1 to 4 // 3 1: 39 // 39, 56, 32, 49 – 2: 56 3: 32 4: 49 default: 32 } 32: getstatic #27 // Field java/lang/System.out:Ljava/io/PrintStream; 35: iconst_0 36: invokevirtual #33 // Method java/io/PrintStream.print:(I)V 39: getstatic #27 // Field java/lang/System.out:Ljava/io/PrintStream; 42: iconst_1 43: invokevirtual #33 // Method java/io/PrintStream.print:(I)V 46: goto 63 // break 49: getstatic #27 // Field java/lang/System.out:Ljava/io/PrintStream; 52: iconst_4 53: invokevirtual #33 // Method java/io/PrintStream.print:(I)V 56: getstatic #27 // Field java/lang/System.out:Ljava/io/PrintStream; 59: iconst_2 60: invokevirtual #33 // Method java/io/PrintStream.print:(I)V 63: return
特に1というラベルの付いた命令に興味があります。これは、例外なく、最小から最大へのキーのすべての値の遷移アドレスを含むテーブル（配列）を作成したことを意味します。 スイッチ実行アルゴリズムは次のようなものです（擬似コード）：
if (val<low || val>high){ jump default; }else{ jump table[val - low]; }
この例では、低== 1、高== 4、表== {39、56、32、49}です。 低から高までのすべてのキーが順番にテーブルに存在する必要があるため、コンパイラはキー3を追加し、デフォルトと同じ動作を設定する必要がありました。
命令32から開始して、すべてのケースとデフォルトのコードは、ソースコードに配置されている順序です。 大まかに言うと、ここでコンパイラはキーハンドラの連続コードを生成します。 一致が見つかった後、最初の休憩が発生するまで実行が続く理由が明らかになったと思います。
LookupSwitch
合理的な疑問が生じます。キーの値が非常にまばらな場合はどうなりますか？ 1つと1,000,000の2つしかない場合、100万の要素を持つ配列を作成するのは非常に賢明ではありません。 この例では、キーを10分の4に置き換えます。これで十分です（突然ではない場合、増やします）。 バイトコードを確認します（ハンドラーのバイトコードはほぼ同じままであるため、表示されません）。
1: lookupswitch { // 3 1: 43 2: 60 10: 53 default: 36 }
ここでもテーブルが設定されますが、ペアの場合：キーは遷移ラベルです。 JVM仕様では、検索方法は指定されていませんが、検索は線形にできますが、検索を高速化するにはキーをソートする必要があるとされています。 おそらく、いくつかの実装は線形検索を使用します。 これは、スイッチO（n）の複雑さに関して（理論的ではありますが）私が知っている最初のケースです。 次に、別のより具体的なものが表示されます。
本物の男の子と女の子が尋ねます：コンパイラーはどのように選択するかを決定しますか？tableswitchまたはlookupswitch？ そして、最も現実的なものはOpenJDKソースをダウンロードし（他のJDK実装では選択方法が異なることに注意してください）、openjdk / langtools / src / share / classesのcom.sun.tools.javac.jvm.Gen.javaクラスのvisitSwitchメソッドを調べます。
// Determine whether to issue a tableswitch or a lookupswitch // instruction. long table_space_cost = 4 + ((long) hi - lo + 1); // words long table_time_cost = 3; // comparisons long lookup_space_cost = 3 + 2 * (long) nlabels; long lookup_time_cost = nlabels; int opcode = nlabels > 0 && table_space_cost + 3 * table_time_cost <= lookup_space_cost + 3 * lookup_time_cost ? tableswitch : lookupswitch;
table_space_cost-このサイズには、範囲内のすべての値の数に加えて、lo、hi、default_addressの1つの値、および選択した切り替え方法（tableswitch）のマーカーが含まれます。
table_time_cost -3つの操作：範囲（最小および最大）へのエントリをチェックし、テーブルからアドレスラベルを抽出します。
lookup_space_cost-各キーとアドレスのペアに2つの値、さらにテーブルのサイズの値、default_address、および選択された切り替え方法（lookupswitch）のマーカー。
lookup_time_cost-最悪のケースが想定されます-線形検索。
そして、あなたが見るように、アルゴリズム自体は単純です。 魔法の3番（「これらの人々は私たちの鼻をほじるのを禁じている」（c））は、おそらく経験的です。
文字列比較
「String.hashCodeは簡単に衝突する可能性があります。String.equalsは遅すぎるかもしれません。おそらく文字列がインターンされているのでしょうか？」
switch(""){ case "AA": break; case "BB": break; }
0: ldc #27 // String 2: dup 3: astore_0 4: invokevirtual #29 // Method java/lang/String.hashCode:()I 7: lookupswitch { // 2 2080: 32 2112: 44 default: 73 } 32: aload_0 33: ldc #35 // String AA 35: invokevirtual #37 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 38: ifne 56 41: goto 73 44: aload_0 45: ldc #41 // String BB 47: invokevirtual #37 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 50: ifne 66 53: goto 73 56: getstatic #43 // Field java/lang/System.out:Ljava/io/PrintStream; 59: iconst_1 60: invokevirtual #49 // Method java/io/PrintStream.println:(I)V 63: goto 73 66: getstatic #43 // Field java/lang/System.out:Ljava/io/PrintStream; 69: iconst_2 70: invokevirtual #49 // Method java/io/PrintStream.println:(I)V 73: return
つまり、コンパイルの段階で、すべてのキーのハッシュコードが計算されます。 LookupSwitchは、ハッシュに一貫性がある場合でも、常に文字列に対して実行されます。 実行されると、条件式のハッシュコードが計算され、ハッシュキーと比較されます。 一致する場合、String.equals（）メソッドを使用して文字列も比較（アドレス32〜53）し、衝突を防ぎます。 そして、成功した場合、対応する式（56〜70）の実装への移行。
また、同じハッシュを持つ複数のキーがある場合はどうなりますか？
switch(""){ case "Aa": break; case "BB": break; }
7: lookupswitch { // 1 2112: 24 default: 62 } 24: aload_0 25: ldc #35 // String Aa 27: invokevirtual #37 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 30: ifne 45 33: aload_0 34: ldc #41 // String BB 36: invokevirtual #37 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 39: ifne 55 42: goto 62 45: getstatic #43 // Field java/lang/System.out:Ljava/io/PrintStream; 48: iconst_1 49: invokevirtual #49 // Method java/io/PrintStream.println:(I)V 52: goto 62 55: getstatic #43 // Field java/lang/System.out:Ljava/io/PrintStream; 58: iconst_2 59: invokevirtual #49 // Method java/io/PrintStream.println:(I)V 62: return
次に、これらのキーはlookupswitchの1つのハッシュキーの下で結合され、キーが一致する場合、このハッシュを使用してすべての行を反復処理し、String.equals（）を使用してそれらを比較します。 2番目の質問の例では、最大8つの比較を実行します。 次に、複雑度O（n）の2番目のケースを示します。
結論
JIT用でない場合は、スイッチの最適化について考えることができます。 しかし、tableswitchがlookupswitch（JITを有効にした場合）よりも著しく高速になる良い例を見つけることができませんでした。 まあ、おそらくこれ：
1.値が1からNまでのN個のキーがあるとします。この場合、tableswitchが使用されます。
2.同じキーで、さらに1つ以上の値で、Nよりはるかに大きい値です。この場合、lookupswitchが使用されます。
（JITを無効にすると、すべてが明確になり、違いは明白です。）
JITとの違いはありません。 おそらく彼はすべてのキーをいくつかの範囲に分割し、それらをテーブルスイッチのように扱います。 ただし、N = 721から始めて、2番目の例のパフォーマンスが急激に低下しました。
結論として、非常にワイルドなアドバイスだけがそれ自体を示唆しています。冗談だと考えてください。 そして、このループで同じハッシュを持つ文字列キーの束があれば、他の実装方法を考えてください。