哈希表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)。

在决定使用哪种实施方式时,需要考虑以下因素:

  1. 全部订单关系的可用性。
  2. 有效的哈希函数的等价关系。
  3. 元素数量的一个首要的知识。
  4. 了解插入,删除和查找的速度。
  5. 比较和散列函数的相对复杂性。

如果你只需要访问单个元素,散列表更好。 如果你需要一系列的元素,除了二叉树之外别无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。