C++：在哈希表中查找和使用switch语句哪个更快？

Question

我有一个代码模式，可以将一个整数转换为另一个整数。就像这样：

int t(int value) {
    switch (value) {
        case 1: return const_1;
        case 3: return const_2;
        case 4: return const_3;
        case 8: return const_4;
        default: return 0;
    }
}

它目前大约有50个条目，也许以后会有更多，但可能不超过一两百个。所有的值都是预定义的，当然我可以按照它们的值来排序case标签。所以问题是，哪种方法更快——这种方法还是将其放入哈希映射中（我没有访问std::map，所以我说的是在我的SDK中可用的自定义哈希映射）并在该表中执行查找？也许这有点过早优化，不过...但我只需要你们的意见。

提前谢谢。

编辑：我的情况值将在0到0xffff范围内。关于哈希映射更易读的观点。我不确定它真的会更易读，因为我仍然需要用值填充它，所以常量映射表仍然需要在我的代码中某个地方。

编辑2：已经给出了许多有用的答案，非常感谢。我想在这里添加一些信息。我的哈希键是整数，我的整数哈希函数基本上只是一个乘法和整数溢出：

EXPORT_C __NAKED__ unsigned int DefaultHash::Integer(const int& /*aInt*/)
{
_asm mov edx, [esp+4]
_asm mov eax, 9E3779B9h
_asm mul dword ptr [edx]
_asm ret
}

因此，它应该非常快速。

- Haspemulator

---

不应该从虚空返回，虽然这是过早优化，但我个人会选择一个好的哈希表（出于可读性的原因）。 - smallB

(1) std::map 不是哈希表（C++11 中的 std::unordered_map 是）。 (2) 我们应该如何评估那个自定义哈希表的质量？它可能是非常糟糕的，也可能很出色。 - user395760

顺便提一下，也许考虑使用具有命名对的“枚举”而不是“switch”？这将完全消除函数调用。 - kevlar1818

“我只需要你们的意见” - 不，你不需要。我们的意见关于哪个更快几乎毫无价值，因为我们没有你的哈希映射实现、你的编译器、你的实际数据或者你应用程序的其余部分。所有这些都可能影响哪个更快（以及差异是否明显），所以任何人真正能说的就是它们可能都很快，但通常情况下切换会更快。 - Steve Jessop

使用数组。请见下面我的答案。 - Thomas Matthews

Answer 1

switch结构语句更快（或至少不会更慢）。

这主要是因为switch结构语句将静态数据提供给编译器，而哈希映射等运行时结构则没有。

如果可能的话，编译器应该将switch结构语句编译成代码指针数组：数组的每个项目（由索引标识）都指向相关联的代码。在运行时，这需要O(1)时间，而哈希映射可能需要更长的时间：通常情况下是O(log n)，最坏情况下是O(n)，而且内存访问次数更多。

- peoro

---

在O(n)时间复杂度下的哈希映射是一种相当糟糕的哈希映射。 - unkulunkulu

在我的教育中，我认为哈希应该是O(1)，最坏的情况下（发生许多碰撞）是O(N)。另外，我认为开关的速度取决于您要区分的值。如果它们是具有固定步长的闭合范围，则开关会很快。但是如果是[1, 100000000]这样的随机输入范围呢？ - Nobody moving away from SE

不要使用switch语句，而是使用二分查找，这将具有O(log(n))的复杂度，而哈希表的复杂度为O(1)。显然，还有哈希函数的开销，但就时间复杂度而言，这似乎不太合适。 - Alex Huszagh

@AlexanderHuszagh：当切换索引是连续的时候，不需要使用二分查找。当索引是非连续的时候，编译器可以生成一个静态优化的哈希表（这仍然比动态构建的哈希表好）。总的来说，编译器和你的运行程序将拥有类似数量的信息，但switch语句将能够在编译时处理此信息并使用一些启发式算法进行优化，这些算法很可能比我们在运行时能够实现的任何东西都要好。 - peoro

@peoro 如果数据是连续的，你也可以使用静态数组：如果数据是非连续的，虽然你不太可能注意到主要差异，在非常大的尺寸下，具有相当大系数的O(1)开始击败具有小系数的O(log(n))。你大多数是正确的，但上面的例子显然不是连续的。 - Alex Huszagh

Answer 2

我会发表我的5分建议：

当条目数约为50个时，std :: unordered_map（基于哈希，O（1））通常比std :: map（基于树，O（ln（N）））慢，并且它们都比boost :: flat_map（排序向量 O（ln（N）））慢，我倾向于在这种情况下使用后者。并非总是能将 switch 编译为跳转表，而当它可以时，您可以自己将值（或函数）放入矢量中并按索引访问。否则，switch 稍微比 boost::flat_map 快一点。

请注意开头的“通常”一词，如果您关心此代码片段的性能，请进行分析（并与我们分享结果:)).

- Slava

---

一如既往，要找到好的答案，看最底部的回复即可。 - CDR

Answer 3

使用switch语句比在哈希表中查找更快。

然而，如果您需要更改映射，则使用映射会导致代码更易读。您可以通过从文件中读取结果轻松地使用映射来实现这一点。在switch语句中，您必须更改代码并重新编译。

- Jeff Foster

Answer 4

这个开关将更快。如果只有少量的情况，就像你的例子一样，它将使用一个if链。如果有大量的情况，并且它们相当紧凑，它可以选择生成跳转表，这只需要几条指令。(顺便说一句，你不必按顺序排列这些情况。)哈希映射是O(1)，但可能需要10-40条指令。

- Mike Dunlavey

---

关于case的排序：我在某处读到，应该这样做以实现更高的执行速度。那么你说这是错误的吗？你能详细说明一些吗？ - Haspemulator

@Hasp - 如果代码变成if链，第一个情况可能会稍微快一点。如果编译器决定使用跳转表，则无济于事。 - Bo Persson

@Haspemulator：Bo的说法基本上是对的。你可能有很多稀疏的情况（比如1000000、2000000、3000000等），导致编译器生成一个长的if链。那么在最坏的情况下，你的程序可能总是要一直运行到最后一个情况。 - Mike Dunlavey

Answer 5

根据定义，数组具有最快的访问时间。

switch语句比较值，然后使用跳转表（即函数指针的数组）。

哈希表从数据中计算哈希值，然后在内存中搜索树或将哈希值用作索引到数组。由于计算哈希值而慢。

在大多数现代平台上，64k不是很大的数据量，可以被静态分配为常量数组。

数组技术的一个问题是要考虑您未考虑的键。一个例子是使用唯一的哨兵值。当返回该值时，您知道您有一个未知的键。

我建议使用static const值数组。

- Thomas Matthews

Answer 6

我同意使用数组，但我没有足够的声望来投票支持它。这只是65536个条目，所以除非你在严重的内存限制下并且/或者你返回的是非常大的东西，否则你最好使用一个静态的const数组。有一个64k int的数组通常只有256kB，并且如果你可以使用short或char，它将是一半或四分之一的大小。我认为你能从switch语句中得到的最好的结果是对于它的代码指针数组之外的值，一个条件分支和第二个条件分支跳转到值在数组内的代码。能够执行“return my_array[value]”将只导致一次内存获取（可能来自L3缓存）。

为了可读性，你可以把数组放在它自己的文件中，并用类似每行10或16个条目的网格排列所有的值。然后你用每个条目数字的前一部分注释每一行（例如“// 0x12A?”），并有定期的注释行与列对齐，填写条目数字的最后一位（例如“// 0 1 2 3 4 5 6 7 8 9 A B C D E F”）。我已经为几个256个条目的数组做过这样的事情，这比switch语句容易得多。我还使用了64k个条目的数组进行快速整数对数的计算，这变得更加复杂，但我能够编写一个程序来生成所有的数组代码。

对于这样大的东西，除非你处理更多的条目，否则代码管理可能不会更容易，但这取决于你的编辑器和技能。维护这样的数组只是调整图表中的一个点而不是寻找可能在“case 1: return const_1;”的长列表中或不在其中的值。几个for循环就足以生成一个64k条目的数组，这些数组被适当地注释和填充默认值。

为了访问安全性，你可以考虑使用某种边界检查。这可以通过boost的前提条件、抛出异常或特殊返回，如果数字超出范围，或者简单地“return my_array[value&0xffff]”来实现。然而，你可能对传入值有足够强的保证，不需要任何这些。

- jbo5112

Answer 7

哈希表的速度取决于两个因素：哈希函数的速度和碰撞的数量。当所有值在事先已知的情况下，可以创建一个完美哈希函数，它不会存在碰撞。如果您能生成仅由几个算术操作组成的完美哈希函数，则其速度可能比开关更快。

- Mark Ransom

Answer 8

我认为哪种方法更快并不明显。您可能需要对两种方法进行分析。

哈希表的复杂度应该是O(1)。

使用非连续键的switch语句（至少在GCC中）可以优化为二分查找，其复杂度为O(log n)。

另一方面，任何在哈希表上执行的操作都比在switch语句中执行的操作要耗费更多的时间。

- UncleBens

Answer 9

哈希表的时间复杂度通常为O(1)，不考虑冲突的情况下。 C++标准没有规定switch语句的实现方式，但它可以作为跳转表来实现，其时间复杂度也是O(1)，或者可以作为二分查找来实现，其时间复杂度为O(log n)，或者根据case语句的数量等进行组合。

因此，简而言之，在小规模的情况下，switch语句更快，但在大规模的情况下，哈希表可能会胜出。

- RoundPi