哈希表与平衡二叉树 [英] Hash table vs Balanced binary tree

问题描述

推荐答案

这个问题一般不能回答，我担心。

This question cannot be answered, in general, I fear.

问题是有很多类型的哈希表和平衡二叉树和他们的表现差异很大。

The issue is that there are many types of hash tables and balanced binary trees, and their performances vary widely.

所以，天真的答案是：这取决于你需要的功能。如果您不需要排序和平衡的二叉树，则使用哈希表。

So, the naive answer is: it depends on the functionality you need. Use a hash table if you do not need ordering and a balanced binary tree otherwise.

对于更详细的答案，让我们考虑一些替代方案。

For a more elaborate answer, let's consider some alternatives.

哈希表（有关基础知识，请参阅维基百科的条目）

Hash Table (see Wikipedia's entry for some basics)

• 并非所有哈希表都使用链表作为存储桶。一个常见的替代方案是使用更好的桶，例如二进制树或另一个哈希表（具有另一个哈希函数），...


• 一些哈希表不使用桶总之：请参阅开放式地址（它们与其他问题一起出现）


• 有一些叫做线性重新哈希（这是实现细节的质量），这避免了停止世界和重塑的陷阱。基本上在迁移阶段，您只需插入新表，并将一个旧条目移动到新表中。当然，迁移阶段意味着双重查询等...

二进制树

• 重新平衡成本高昂，您可以考虑一个跳过列表（更适合多线程访问）或Splay Tree。


• A好的分配器可以将内存中的节点打包在一起（更好的缓存行为），即使这样也不能缓解指针查找问题。


• B-Tree和变体也提供打包

我们不要忘了，O（1）是一个渐近的复杂性。对于少数元素，系数通常更重要（性能方面）。特别是如果你的散列函数很慢...

Let's not forget that O(1) is an asymptotic complexity. For few elements, the coefficient is usually more important (performance-wise). Which is especially true if your hash function is slow...

最后，对于集合，你也可以考虑概率数据结构，如 Bloom Filters 。

Finally, for sets, you may also wish to consider probabilistic data structures, like Bloom Filters.

这篇关于哈希表与平衡二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！