跳表切换案例问题
我试图了解跳转表及其在switch case语句之间的关系。
我被告知跳转表是编译器生成的O（1）结构，它使得查找值基本上与您可以获得的速度一样快。 但是在某些情况下，Hashtable / Dictionary可能会更快。 我还被告知这只有在开关盒包含ordered数据值时才有效。
有人可以确认或否认这一点并解释跳转表是什么，它的重要性和时间复杂性与使用字典或散列表相比。 谢谢。
跳转表是用于将控制转移到另一个位置的抽象结构。 转到，继续和中断是相似的，除了它们总是转移到特定位置而不是许多可能性。 特别是，该控制流程与函数调用不同。 （维基百科关于分支表的文章是相关的。）
switch语句是如何在C / C ++中编写跳转表。 在这种常见情况下，仅提供有限forms（只能切换整数类型）以使实现更容易和更快。 （如何有效地实现跳转表对于整数类型的研究要比一般情况更多。）一个典型的例子是Duff的设备 。
但是， 通常不需要跳转表的完整function ，例如每个case都有break语句。 这些“有限的跳转表”是一种不同的模式 ，它只利用跳转表的良好研究效率，并且在每个“动作”独立于其他动作时是常见的。
跳转表的实际实现采用不同的forms，主要是如何完成索引映射的键。 该映射是“词典”和“哈希表”之类的术语，而这些技术可以独立于跳转表使用。 说一些代码“使用跳转表”并不意味着你有O（1）查找。
编译器可以自由选择每个switch语句的查找方法，并且不能保证你会得到一个特定的实现; 但是，应考虑编译器选项，如优化速度和优化尺寸。
您应该研究数据结构，以了解它们所施加的不同复杂性要求。 简而言之，如果“词典”是指平衡的二叉树，则它是O（log n）; 哈希表取决于其哈希函数和冲突策略。 在switch语句的特定情况下，由于编译器具有完整信息，因此它可以生成完美的散列函数 ，这意味着O（1）查找。 但是，不要仅仅考虑整体算法的复杂性而迷失方向：它隐藏了重要的因素。
跳转表基本上是指向代码段的指针数组，用于处理switch语句中的各种情况。 当您的案例密集时（例如，某个范围内的每个可能值都有一个案例），最有可能生成它。 例如，给出如下声明：
switch (i) { case 1: printf("case 1"); break; case 2: printf("case 2"); break; case 3: printf("case 3"); break; }
它可以生成大致相当于这样的代码：
void case1() { printf("case 1"); } void case2() { printf("case 2"); } void case3() { printf("case 3"); } typedef void (*pfunc)(void); pfunc functions[3] = {case1, case2, case3}; if ((unsigned)i<3) functions[i]();
这具有O（K）复杂性。 典型的哈希表也具有大致O（K）的预期复杂度，尽管最坏的情况通常是O（N）。 跳转表通常会更快，但通常只有在表格非常密集的情况下才会使用，而哈希表/字典即使在情况非常稀疏的情况下也能正常工作。
假设您有一系列过程：
void fa() { printf("a\n"); } ... void fz() { printf("it's z!\n"); } typedef void (*F)(); F table[26]={fa,fb,...,fz};
假设您接受来自用户的输入字符（来自az）并运行fc：
char c; switch(c) { case 'a': fa();break; case 'b': fb();break; ... case 'z': fz();break; default: exit(-1); }
理想情况下，这将被替换为：
if (c<'a' || c>'z') exit(-1); else (*table[c-'a'])();
当然，您可能会使表格更大，因此无需进行范围检查。
编译器会为任意代码执行此操作，而不仅仅是函数调用，并且可以通过存储要跳转到的地址（实质上是goto）来执行此操作。 C不直接支持任何类型的计算goto（索引到表或其他方式），但它的CPU指令非常简单。
根据具体情况，编译switch语句可以采用多种forms。 如果情况紧密相连，那就不用考虑了：使用跳转表。 如果案例相距很远，请使用if（case == value）或使用map。 或者编译器可以使用组合：跳转表的岛，如果检查跳转表范围。
跳转表是一个简单的函数指针数组，你可以大致像这样画一个跳转表：
int (*functions[10])(); /* Array of 10 Function Pointers */
根据我的理解，这与case语句一样使用：每个condition，case _，将是这个数组的索引，例如：
switch( a ) { case 1: // (*functions[1])() // Call function containing actions in case of 1 ... case 2: // (*functions[2])() // Call function containing actions in case of 2 ...
每个案例，转变为简单的函数[a]。 这意味着访问函数[9]与访问函数[1]一样快。 给你你提到的O（1）时间。
显然，如果你有案例1和案例4907，这不是一个好方法，你提到的哈希表/字典方法可能会发挥作用。
进一步阐述杰瑞的答案和其他人
鉴于：
int x=1; switch (i) { case 1: x=6; break; case 2: x++; // Fall through case 3: x+=7; break; }
你可能会有如下内容：
int f1() {return 6;} int f2() {return 1+f3();} int f3() {return 8;}
编译器可以使用跳转表来索引{f1, f2, f3}
在创建具有f1, f2, f3的表时，编译器可以进行内联f1, f2, f3直接将x设置为6,9,8
但是如果你编写了这些函数，并推出了自己的跳转表， f1,f2,f3可以在任何地方，但是编译器会知道将它们放在靠近switch地方，可以创建比你想象的更好的代码局部性。
请注意，在许多情况下，编译器将生成一个防护，以检查i是否在范围内（或处理default ），如果您确定它始终是其中一种情况，您可以跳过
有趣的是，对于少数情况，并且在不同的编译器标志（依赖于编译器）下， switch不会使用表，而只会执行ifs，类似于：
if (i==1) x=f1(); else if (i==2) x=f2(); else if (i==3) x=f3();
或者它可以优化这个（简单测试是一条指令）：
x=(i==1) ? f1() : (i==2) ? f2() : (i==3) ? f3() : x;
最好的建议是查看生成的程序集，看看编译器对你的架构上的代码做了什么，如果有一个跳转表，Linux / intel上的g ++将生成如下所示的内容
（ 注意我必须转到5个case语句来强制跳转表，它使用ifs低于那个case语句的数量 ）
请注意，跳转表中的小孔将执行default
int foo(int i) { int x=1; switch (i) { case 1: x=6; break; case 2: x++; // Fall through case 3: x+=7; break; case 4: x+=2; break; case 5: x+=9; break; } return x; }
将生成以下汇编代码（ //评论是我的 ）：
cmp edi, 5 //make sure it is not over 5 ja .L2 //jump to default case mov edi, edi jmp [QWORD PTR .L4[0+rdi*8]] // use the jump table at label L4: .L4: .quad .L2 // if i=0, set x=1 (default) .quad .L9 // f1() see below .quad .L10 // f2() see below .quad .L6 // f3() see below .quad .L7 // f4() see below .quad .L8 // f5() see below .L10: mov eax, 9 // x=9 ret .L9: mov eax, 6 // x=6 ret .L8: mov eax, 10 // x=10 ret .L6: mov eax, 8 // x=8 ret .L7: mov eax, 3 // x=3 ret .L2: mov eax, 1 // default, x was 1, noop is: x=1 ret