C++：哪个更快 - 在 hashmap 中查找还是在 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条左右，以后可能会更多，但大概不会超过一百两条。所有值都是预定义的，当然我可以按它们的值对案例标签进行排序。所以问题是，什么会更快 - 这种方法或将其放入哈希映射（我无法访问 std::map，所以我正在谈论我的 SDK 中可用的自定义哈希映射）并在该表中执行查找？也许这有点过早的优化，但......但我只需要你的意见。

提前致谢。

编辑：我的情况值将在 0 到 0xffff 的范围内。以及关于哈希图更好的可读性的观点。我不确定它是否真的具有更好的可读性，因为我仍然需要用值填充它，因此常量映射表仍然需要位于我的代码中的某个位置。

EDIT-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
}

所以它应该相当快。

Answer 1

switch 构造更快（或者至少不慢）。

这主要是因为 switch 构造向编译器提供静态数据，而像哈希映射这样的运行时结构则不然。

如果可能，编译器应将 switch 结构编译为代码指针数组：数组的每一项（由索引索引）都指向关联的代码。在运行时，这需要 O(1)，而哈希映射可能需要更多：平均情况下为 O(log n) 或最坏情况下为 O(n)，通常，并且无论如何都会有更大的恒定数量的内存访问。

Answer 2

我将添加我的 5 美分：

对于大约 50 个 std::unordered_map （基于哈希，O(1)）的条目数，通常比 std::map （基于树的 O(ln(N))）慢，并且两者都其中的速度比 boost::flat_map(sorted vector O(ln(N))) 慢，我倾向于在这种情况下使用它。
switch 并不总是可以编译为跳转表，当它是的时候，您可以简单地将您的值（或函数）自己放入向量中并通过索引访问。否则 switch 比 boost::flat_map 稍微快一些。

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

Answer 3

switch 语句 将比在哈希映射中查找更快。

但是，如果您更改映射，映射将产生更具可读性的代码。您可以通过从文件中读取结果来轻松地使用地图来完成此操作。在 switch 语句中，您必须更改代码并重新编译。

Answer 4

切换会更快。如果情况很少，如您的示例所示，它将使用 if 链。如果情况很多，并且它们相当紧凑，则可以选择生成跳转表，该跳转表只需要几条指令。 （顺便说一句，您不必对案例进行排序。）哈希映射的复杂度为 O(1)，但可能会采用 10-40 条指令。

Answer 5

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

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

hashmap 根据数据计算哈希值，然后搜索内存中的树或使用哈希值作为数组的索引。因为计算哈希值所以慢。

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

数组技术的一个问题是考虑了您没有考虑到的键。一个示例是使用唯一的哨兵值。当返回值时，您就知道您有一个未知的密钥。

我建议使用static const 值数组。

Answer 6

哈希映射的速度取决于两个因素：哈希函数的速度和冲突的数量。当提前知道所有值时，可以创建一个完美的哈希函数，该函数具有没有碰撞。如果您可以生成一个仅包含几个算术运算的完美哈希函数，那么它可能比交换机更快。

Answer 7

我同意使用数组，但我没有投票支持它的声誉。它只有 65536 个条目，因此除非您受到严重的内存限制和/或返回非常大的内容，否则使用静态 const 数组会更好，而不是像您的示例那样 int 。拥有 64k int 数组通常只有 256kB，如果可以使用 Short 或 char，则大小将是该大小的一半或 1/4。我认为您对 switch 语句所能期望的最好结果是为代码指针数组之外的值提供一个条件分支，并为数组内的值跳转到第二个条件分支。能够执行“return my_array[value]”只会导致内存获取（可能来自 l3 缓存）。

为了便于阅读，您可以将数组粘贴在其自己的文件中，并将所有值排列在网格中，每行有 10 或 16 个条目。然后，用每个条目编号的第一部分注释每一行（例如“// 0x12A？”），并定期添加注释行，这些注释行将与列对齐以填充条目编号的最后一位数字（例如“// 0 1 2 3 4 5 6 7 8 9 ABCDE F")。我已经对多个包含 256 个条目的数组执行了此操作，这比 switch 语句更容易管理。我还使用了具有 64k 条目的数组来实现快速整数对数，这使得管理变得更加复杂，但我能够编写一个程序来生成所有数组代码。

对于这么大的东西，代码管理可能不会更容易，直到您处理更多条目，但这取决于您的编辑器和技能。维护这样的数组只是调整图表中的一个点，而不是寻找可能或可能不在“case 1：return const_1;”的长列表中的值。几个 for 循环应该足以生成 64k 条目的数组，这些条目已正确注释并填充了默认值。

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

Answer 8

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

哈希映射的复杂度应该为 O(1)。

开关（具有像您这样的非连续键）可以优化为二分搜索（至少使用 GCC），其复杂度为 O(log n)。

另一方面，在哈希映射上完成的任何操作都将比在交换机上完成的操作昂贵得多。

Answer 9

在不考虑碰撞的情况下，哈希表的时间复杂度一般为O(1)。
C++ 标准没有指定 switch 是如何实现的，但它可以实现为跳转表，时间复杂度为 O(1)，也可以实现为二分查找，时间复杂度为 O(log n) 或组合，具体取决于有多少 case 语句等。

总之，像你的情况这样的小规模，switch 更快，但哈希表可能会在大规模中胜出