问题描述
我应该考虑哪些因素时，我需要一个哈希表或平衡二叉树之间进行选择，以实现一组或一个关联数组？
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平衡二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！