哈希容器和红黑树对决 (STL 基准测试)
4.44/5 (18投票s)
哈希容器和非哈希容器的基准测试
引言
本文介绍了一个基准测试应用程序，该应用程序将红黑二叉树容器（map、set 等）与哈希容器进行对比。本文不是数据结构的教程。有关红黑二叉树如何工作的更多信息，您可以参考这个 Wikipedia 链接。有关哈希容器，您可以阅读 Marius Bancila 撰写的这篇优秀的 Codeguru 文章。
红黑二叉树是一种非常快速的搜索树数据结构：它可以在 32 步内找到 40 亿项中的任何一项。它的 O 记法是 O(log2n)，而哈希容器的平均情况是 O(1)，最坏情况是 O(元素总数)。哈希容器搜索耗时不是 O(1) 的唯一情况是由于被搜索的项与其他不同的项共享相同的哈希值，并且哈希容器必须逐一比较它们才能找到精确匹配。有关性能比较的更多信息，请查看这个 Boost 库链接。
基准测试
对于 map 和 multimap 的基准测试，键值对中的键是一个英文词典中的单词（string），值是一个随机数。这是可以的，因为值在搜索中没有被使用。对于 set 和 multiset 的基准测试，元素是一个英文词典中的单词（string）。Set 是一种类似于 map 的数据结构，没有值对。与 map 和 set 不同，multimap 和 multiset 允许同一个键/元素被插入多次，并且不强制唯一性。我使用 std::wstring 作为键/元素的原因是哈希容器已经为 std::wstring 编写了预定义的哈希函数。如果我使用自己自定义的数据类型，我可能需要编写自己的自定义哈希函数。
对于 map、multimap、set 和 multiset 的插入，我调用了 insert 方法。对于 multiset 和 multimap 的插入，我插入了相同的项两次。对于 map 和 set 的搜索，我调用了 find 方法。对于 multiset 和 multimap 的搜索，我使用了 equal_range 方法。
在基准测试中，我们将测试 STL、遗留哈希容器（稍后详述）、Visual C++ 10 无序容器和 Boost 1.44 无序容器。我刚刚提到的遗留哈希容器自 Visual Studio 2003 起就存在于 stdext 命名空间中。我们也将测试它们，看看它们与 C++0x 无序容器相比表现如何。顺便说一下，如果您还不知道，C++0x 和 Boost 的哈希容器被称为 unordered_xxx（例如，unordered_map）。基准测试应用程序将在容器未填充时填充容器，然后运行基准测试，但填充时间不包含在基准测试结果中。我没有测试容器填充是因为我发现填充速度相当快。
基准测试使用一个随机数来索引 std::vector，以从上述容器中选择一个要搜索的项（string）。您可以在基准测试应用程序中更改随机数生成器的种子。
Map 基准测试
基准测试进行了 500 万次搜索。分数越低越好。
我们可以看到，哈希容器比 STL map 的性能好 2 倍。哈希容器的计时大致相同。
MultiMap 基准测试
基准测试同样进行了 500 万次搜索。分数越低越好。
我们可以看到 Boost unordered_multimap 的计时比 STL multimap 快 4 倍。
Set 基准测试
我们可以看到，set 基准测试结果与之前的 map 结果相似。
MultiSet 基准测试
我们可以看到，multiset 基准测试结果与之前的 multimap 结果相似。正如我们所见，哈希容器一贯优于其红黑树对应项，我们可能会倾向于在代码中使用哈希容器。在大多数情况下，哈希容器可以无缝替换其红黑树对应项，除了可能缺少一些方法，并且需要为自定义数据类型编写哈希函数。例如，当您获取它们的迭代器时，它们是无序的，不像红黑树版本。您需要自己研究它们的区别。
构建基准测试应用程序
请以发布模式构建应用程序。调试模式的应用程序运行速度太慢。读者必须下载 Boost 1.44，并将您的 Visual C++ 10 include 路径指向 Boost 1.44，如果您尚未在开发机器上安装 Boost 库。
基准测试框架
该应用程序是一个基准测试框架；每个基准测试套件都是一个独立的 Win32 DLL。基准测试应用程序将在启动时加载所有具有特定函数签名的 DLL。如果您出于某种原因想添加自己的基准测试 DLL（例如，您想测试 SGI 哈希容器）到应用程序文件夹，基准测试应用程序也会将其拾取。DLL 的数量几乎没有限制。当然，您添加的越多，基准测试时间越长，图表的条形图就越细。要编写您自己的基准测试 DLL，只需创建一个新的 Win32 DLL 项目，然后从任何现有 DLL 复制源代码。您可以只更改包含的头文件为您想要测试的新容器的头文件，并且可能还需要更改容器类名。这样，您就拥有了一个新的基准测试 DLL。DLL 的测试顺序根据 GetIndex() 进行。
- STL DLL
GetIndex()返回5。 - Legacy Hash DLL
GetIndex()返回10。 - VC10 unordered DLL
GetIndex()返回15。 - Boost unordered DLL
GetIndex()返回20。
因此，要将您的 DLL 插入到其他 DLL 之前，您的 GetIndex() 应该返回 1 到 4 之间的值。
结论
我欢迎任何关于我如何正确或错误地进行此基准测试以及如何改进它的反馈（无论好坏）。如果我的基准测试不能很好地反映数据搜索在真实世界场景中的使用方式，也请告知我。我写这篇文章不是为了教学，而是为了向比我优秀的读者学习。感谢您的阅读！
注意事项：在 unordered_map 中使用字符串作为键，当记录数达到数百万时，会增加哈希冲突的可能性，可能导致性能比 STL map 更差。请参见 链接。
历史
- 2010年9月8日：首次发布
- 2010年12月28日：更新源代码和二进制文件（已附加），以修复用户指定超过 5000 万次搜索时进度条可能出现的整数（计算）溢出错误