哈希表与平衡二叉树

Question

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

Answer 1

这个问题无法回答,总的来说,我担心.

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

所以,天真的答案是:它取决于你需要的功能.如果您不需要排序则使用哈希表,否则使用平衡二叉树.

有关更详细的答案,让我们考虑一些替代方案.

哈希表(参见维基百科的一些基础知识)

• 并非所有哈希表都使用链表作为存储桶.一种流行的替代方法是使用"更好"的存储桶,例如二叉树或其他散列表(使用另一个散列函数),...
• 一些哈希表根本不使用存储桶:请参阅打开寻址(显然它们带有其他问题)
• 有一种称为线性重新散列(它是一种实现细节的质量),它避免了"停止世界和重新散列"的陷阱.基本上在迁移阶段,您只需插入"新"表,并将一个"旧"条目移动到"新"表中.当然,迁移阶段意味着双重查找......

二叉树

• 重新平衡成本很高,您可以考虑使用Skip-List(对于多线程访问也更好)或Splay Tree.
• 一个好的分配器可以在内存中"打包"节点(更好的缓存行为),即使这不会缓解指针查找问题.
• B-Tree和变种也提供"包装"

我们不要忘记O(1)是渐近的复杂性.对于少数元素,系数通常更重要(性能方面).如果您的哈希函数很慢,则尤其如此...

最后,对于集合,您可能还希望考虑概率数据结构,例如布隆过滤器.

Answer 2

如果不需要以任何顺序保存数据,散列表通常会更好.如果必须对数据进行排序,则二叉树会更好.

Answer 3

现代架构上值得注意的一点:如果Hash表的加载因子较低,则通常会比二叉树具有更少的内存读取.由于与烧录CPU周期相比,内存访问往往相当昂贵,因此哈希表通常更快.

在下面的二进制树中,假设是自平衡的,如红黑树,AVL树或类似treap.

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

二进制树在纯函数语言中更容易实现.

二叉树具有自然的排序顺序和自然的方式来遍历所有元素的树.

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

哈希表几乎是O(1)(取决于你如何处理负载因子)与Bin树O(lg n).

树木往往是"平均表现者".他们没有什么特别好的,但是他们没有做什么特别糟糕的事情.

Answer 4

二叉搜索树需要密钥之间的总顺序关系.哈希表仅需要具有一致哈希函数的等价或身份关系.

如果总订单关系可用,则排序数组具有与二叉树相当的查找性能,以哈希表的顺序排列的最坏情况插入性能,以及比两者更少的复杂性和内存使用.

如果将最坏情况的查找复杂度增加到O是可接受的,那么散列表的最坏情况插入复杂度可以留在O(1)/ O(log K)(K具有相同散列的元素的数量). K)或O(log K)如果可以对元素进行排序.

如果密钥更改,则树和散列表的不变量都很难恢复,但对于排序的数组,要小于O(n log N).

这些是在决定使用哪种实施时要考虑的因素:

1. 总订单关系的可用性.
2. 为等价关系提供良好的散列函数.
3. 关于元素数量的A-priory知识.
4. 有关插入,删除和查找速率的知识.
5. 比较和散列函数的相对复杂性.

Answer 5

哈希表是更快的查找:

• 你需要一个生成均匀分布的密钥(否则你会错过很多东西并且必须依赖哈希以外的东西;比如线性搜索).
• 哈希可以使用大量的空白空间.您可以保留256个条目,但只需要8个(到目前为止).

二叉树:

• 确定性.O(log n)我想......
• 不需要像哈希表那样的额外空间
• 必须保持分类.在中间添加元素意味着移动其余部分.