哈希表与平衡二叉树

Question

当我需要在哈希表或平衡二叉树之间进行选择以实现集合或关联数组时，应该考虑哪些因素？

Answer 1

我恐怕这个问题一般都无法回答。

问题是哈希表和平衡二叉树的类型很多，它们的性能差别很大。

因此，天真的答案是:这取决于您需要的功能。如果不需要排序，则使用哈希表，否则使用平衡的二叉树。

为了得到更详细的答案，让我们考虑一些备选方案。

哈希表 (请参阅维基百科的条目中的一些基本知识)

• 并不是所有的哈希表都使用链接列表作为桶。一种流行的替代方法是使用“更好”的桶，例如二叉树，或者另一个哈希表(带有另一个哈希函数)，
• 有些哈希表根本不使用桶:参见Open (很明显，它们附带了其他问题)
• 有一种叫做线性重哈希(它是实现细节的质量)的东西，它避免了“停止世界和重新哈希”的陷阱。基本上，在迁移阶段，您只需插入“新”表，并将一个“旧”条目移到“新”表中。当然，迁移阶段意味着双重查找等等.

二叉树

• 再平衡是昂贵的，你可以考虑跳转列表(也更好的多线程访问)或显示树。
• 一个好的分配器可以将节点“打包”到内存中(更好的缓存行为)，尽管这并不能缓解指针查找问题。
• B-树和变体也提供“包装”。

让我们不要忘记，O(1)是一个渐近复杂性。对于少数元素，系数通常更重要(性能方面)。尤其是当你的哈希函数慢的时候.

最后，对于集合，您也可能希望考虑概率数据结构，比如布卢姆滤波器。

Answer 2

如果不需要按任何顺序保存数据，哈希表通常会更好。如果必须对数据进行排序，二叉树会更好。

Answer 3

在现代体系结构中，值得注意的一点是:哈希表通常会比二叉树具有更少的内存读取，如果其负载因子较低的话。由于与燃烧CPU周期相比，内存访问往往要花费相当大的代价，因此哈希表通常更快。

在下面的二叉树中，假设是自平衡的，就像红色的黑树、AVL树或踏板树。

另一方面，如果您在决定扩展哈希表时需要重新散列哈希表中的所有内容，这可能是发生的代价高昂的操作(摊销)。二叉树没有这个限制。

二叉树更容易在纯函数语言中实现。

二叉树有一个自然排序顺序和一种自然的方式来遍历树的所有元素。

当哈希表中的加载因子较低时，您可能会浪费大量内存空间，但是使用两个指针，二叉树往往占用更多的空间。

哈希表几乎是O(1) (取决于处理负载因子的方式)和Bin (Lg n)。

树木往往是“一般的表演者”。他们没有做得特别好，但也没有做得特别糟糕。