c++ - 使用链表数组实现哈希表

Question

这个问题困扰了我很长时间，今天我阅读了与哈希表相关的详细文章。在不检查任何实现示例的情况下，我想尝试从头开始编写哈希表。

单独的链接方法给了我实现哈希表的想法。任何有数据结构经验的人都可能认为这个问题是个笑话，但我是一个初学者，没有直接研究代码，我想讨论我的实现效率。它会是有效的还是比这更可取的任何其他基本想法？

Answer 1

我认为对于初学者，您还可以查看在 boost 库中实现的一些哈希映射的源代码（或文档）。它被称为 unordered_map。（链接在这里）

只要您不了解这些实现并且想要使用散列并且因为它不在 STL 中而感到恼火，您就会有兴趣编写自己的快速数据存储。
但是现在实现散列映射已经非常困难了，以至于 C++11 在它的 STL 中有 unordered_map。你会看到那里有很多更有趣的东西。

注意：单独的链接称为桶哈希。其实boost 使用的是桶哈希，见这个链接。也许您宁愿查找一些性能比较。那些执行 perf 的人很可能会编写足够好的实现。

Answer 2

使用封闭寻址，另一种选择是使用自平衡二叉搜索树，例如红黑树/std::map 或堆树，用于内部数据结构，甚至是具有不同散列算法的另一个散列图。

使用开放寻址，线性探测的另一种替代方法是二次探测和双散列；还有一些不太常用的策略，例如布谷鸟哈希、跳房子哈希等。

实现哈希表的关键是选择正确的哈希算法、调整大小策略（负载因子）和冲突解决策略。最佳策略高度依赖于您期望的工作负载类型，因为每种方法都需要权衡取舍。