哈希表vs平衡二叉树
当我需要在哈希表或平衡二叉树之间进行select以实现集合或关联数组时，应考虑哪些因素？
总的来说，这个问题不能回答，我担心。
问题是哈希表和平衡二叉树有很多种类，其性能差别很大。
所以，天真的答案是：这取决于你需要的function。 如果不需要sorting，则使用散列表，否则使用平衡二叉树。
为了更详细的回答，让我们考虑一些替代scheme。
哈希表 （参见维基百科的一些基础知识）
- 并非所有的散列表都使用链接列表作为存储桶。 一个stream行的select是使用“更好的”桶，例如二叉树，或另一个散列表（使用另一个散列函数），…
- 有些哈希表完全不使用桶：请参阅Open Addressing（显然，它们会带来其他问题）
- 有一种叫做线性重散列的algorithm（这是一个实现细节的质量），它避免了“停止世界和重复”的陷阱。 基本上在迁移阶段，您只能插入“新”表，并且将一个“旧”表项移入“新”表。 当然，迁移阶段意味着双重查找等。
二叉树
- 重新平衡是昂贵的，你可以考虑一个跳过列表（也适用于multithreading访问）或一个Splay树。
- 一个好的分配器可以在内存中“打包”节点（更好的caching行为），尽pipe这不会减轻指针查找问题。
- B-Tree和变种也提供“包装”
我们不要忘记O（1）是一个渐近的复杂度。 对于less数元素，系数通常更重要（性能方面）。 如果你的散列函数很慢，这是尤其如此。
最后，对于集合，你也可以考虑像Bloom Filters这样的概率数据结构。
如果不需要以任何顺序保存数据，散列表通常会更好。 如果数据必须保持sorting，二叉树更好。
现代体系结构的一个值得注意的地方：如果一个哈希表的载入因子很低，那么它的内存读取次数通常比二叉树less。 由于相比于刻录CPU周期，内存访问成本相对较高，哈希表通常更快。
在下面的二叉树被认为是自平衡的，就像一棵红黑树，一棵AVL树或者像一个树 。
另一方面，如果您决定扩展它时需要重新哈希表中的所有内容，这可能是一个代价高昂的操作（摊销）。 二叉树没有这个限制。
二叉树更容易在纯function语言中实现。
二叉树有一个自然的sorting顺序和自然的方式走树的所有元素。
当散列表中的加载因子较低时，可能会浪费大量内存空间，但是使用两个指针时，二叉树趋于占用更多空间。
散列表几乎是O（1）（取决于你如何处理加载因子）与Bin树O（lg n）。
树木往往是“平均表演者”。 没有什么特别好的，但是没有什么特别不好的。
哈希表是更快的查找：
- 你需要一个能够产生均匀分布的密钥（否则你会错过很多，而且必须依赖除hash以外的东西，比如线性search）。
- 哈希可以使用很多空的空间。 您可以保留256个条目，但只需要8个（到目前为止）。
二叉树：
- 确定性。 O（log n）我想…
- 不需要像散列表那样的额外空间
- 必须保持sorting。 在中间添加一个元素意味着将其余的移动。
二叉search树需要键之间的全部顺序关系。 散列表只需要与一致散列函数具有等价关系或标识关系。
如果总体订单关系可用，则sorting后的数组的查找性能与二叉树相当，哈希表顺序中的最坏情况插入性能，以及比两者更less的复杂性和内存使用。
如果可以将最坏情况下的查找复杂度增加到O（1）/ O（log K）（其中K是具有相同散列的元素的数量），则哈希表的最坏情况插入复杂度可以留在O K）或O（log K）如果元素可以sorting。
树和哈希表的不变式在键值改变时恢复是昂贵的，但是对于sorting后的数组而言小于O（n log N）。
在决定使用哪种实施方式时，需要考虑以下因素：
- 全部订单关系的可用性。
- 有效的哈希函数的等价关系。
- 元素数量的一个首要的知识。
- 了解插入，删除和查找的速度。
- 比较和散列函数的相对复杂性。
如果你只需要访问单个元素，散列表更好。 如果你需要一系列的元素，除了二叉树之外别无select。
为了增加上面的其他很好的答案，我会说：
如果数据量不变（如存储常量），使用散列表; 但是，如果数据量将改变，使用一棵树。 这是因为在散列表中，一旦达到加载因子，散列表必须resize。 resize操作可能非常缓慢。
我不认为已经解决的一点是，对于持久的数据结构，树更好。 那就是不可变的结构。 一个标准的哈希表（即使用单个链表的数组）不能修改整个表的修改。 其中一个相关的情况是，如果两个并发函数都有一个散列表的副本，并且其中一个函数改变了表（如果表是可变的，那么这个改变对另一个也是可见的）。 另一种情况如下：
def bar(table): # some intern stuck this line of code in table["hello"] = "world" return table["the answer"] def foo(x, y, table): z = bar(table) if "hello" in table: raise Exception("failed catastrophically!") return x + y + z important_result = foo(1, 2, { "the answer": 5, "this table": "doesn't contain hello", "so it should": "be ok" }) # catastrophic failure occurs 对于一个可变表，我们不能保证函数调用接收的表在整个执行过程中都会保留该表，因为其他的函数调用可能会修改它。
所以，可变性有时不是一件愉快的事情。 现在，解决这个问题的方法是保持表不变，并且更新返回一个新表而不修改旧表。 但是对于一个散列表，这往往是一个昂贵的O（ n ）操作，因为整个底层数组需要被复制。 另一方面，使用平衡树，只需要创buildO（ log n ）个节点就可以生成一棵新树（树的其余部分是相同的）。
这意味着当需要不可变的映射时，高效的树可以非常方便。
如果你有很多稍微不同的集合实例，你可能会希望他们共享结构。 这对于树来说很简单（如果它们是不变的或者写入时复制的）。 我不确定你可以用hashtables做到这一点; 至less不那么明显。
根据我的经验，hastables总是更快，因为树遭受太多的caching效果。
要查看一些真实的数据，可以查看我的TommyDS库http://tommyds.sourceforge.net/的基准页;
在这里你可以看到比较最常用的散列表，树和库可用的性能。
需要注意的一点是关于遍历，最小和最大项目。 哈希表不支持任何种类的有序遍历，或者访问最小或最大项目。 如果这些function很重要，那么二叉树是一个更好的select。
