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

问题描述

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

What factors should I take into account when I need to choose between a hash table or a balanced binary tree in order to implement a set or an associative array?

推荐答案

这个问题不能回答，在一般情况下，我害怕了。

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)

• 不是所有的哈希表使用链表如斗。一个流行的替代方法是使用一个更好的桶，例如一个二进制树或另一哈希表（与另一散列函数），......
• 在一些哈希表没有使用水桶都：看到开放寻址（他们与其他的问题，很明显）
• 有一种叫做线性再散列（它的实现细节质量），这就避免了停了世界 - 和 - 老调重弹的陷阱。基本上，在迁移阶段，您只能插入在新表，也可以移动一老进入了新的表。当然，迁移阶段是指双查询等...

二叉树

• 重新均衡是昂贵的，你可以考虑跳过名录（也能更好地用于多线程访问）或伸展树。
• 在一个良好的分配器可以包节点一起在存储器（更好的缓存行为），尽管这并不减轻指针查找问题。
• 在B树和变种还提供打包

让我们不要忘记，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...

最后，对于集合，您也不妨考虑概率数据结构，如布鲁姆过滤器。

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

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