为什么要使用二叉搜索树实现哈希表？

Question

为什么要使用二叉搜索树实现哈希表？

data-structureshashtablebinary-search-tree

20

使用数组实现哈希表时，我们继承了数组的常数时间索引。为什么要使用二叉搜索树实现哈希表，因为它提供了O(logn)的搜索时间？为什么不能直接使用二叉搜索树？

- Michael

1

可能是二叉搜索树相对哈希表的优势的重复问题。 - Abdullah Shoaib

13

阿卜杜拉，我特别询问了使用二叉搜索树实现哈希表的问题，而不是哈希表与二叉搜索树的比较。 - Michael

2

什么是具有二叉搜索树的哈希表？键是否被散列并存储在数组中，并按树形排列？还是每个桶中的元素存储为树而不是列表？ - Miserable Variable

2

这个问题的动机是什么？你是否遇到过用BST实现的哈希表？或者是在每个桶中使用BST来加快搜索冲突的速度？ - Adrian McCarthy

@MiserableVariable 从所有意图来看，它使用BST实现了一个哈希表。对于最终用户而言，它看起来/工作起来就像一个“真正的”哈希表，尽管有稍微不同的性能考虑。 - Joel B

显示剩余2条评论

4个回答

2

优点：

潜在的节省空间，因为我们不需要分配一个大数组
可以按顺序迭代键，有时很有用

缺点：

查找时间复杂度为O(log N)，比链式哈希表保证的O(1)更差。

- bluepanda

3

链式哈希表的最坏情况时间复杂度为O(N)。当每个值都发生碰撞时会出现这种情况。如果你用平衡二叉树或字典树替换数组，那么查找时间可以说是常数级的，因为关键字中的位数是固定的，不直接依赖于哈希表中的项数。 - dgatwood

0

由于哈希表的要求是O(1)查找，如果具有对数查找时间，则不是哈希表。尽管使用二叉搜索树可以在处理冲突时提供一些好处（嗯，不太可能出现问题），但通常情况下，这并不值得权衡——我想不出任何情况，在使用哈希表时不想要保证的O(1)查找时间。

或者，还有一种可能性是通过BST变体来保证对数插入和删除，其中数组中的每个索引都有一个对应的BST节点的引用。这样的结构可能会变得有点复杂，但可以保证O(1)查找和O(logn)插入/删除。

- Phillip Carter

1

你只是在争论它的称呼和是否存在，而没有真正回答为什么要使用它。 - Bernhard Barker

1

时间对哈希键的长度取对数是对数级别的（哈希键的长度是恒定值），而不是对哈希中元素数量取对数。因此，它仍将是一个常量时间算法。 - dgatwood

@dgatwood，我认为你错了。哈希键的长度如何是对数级别的？仅通过查看密钥的哈希值，如何找到树中应该返回哪个节点？那我们为什么要使用二叉搜索树呢？如果不需要搜索，让我们使用二叉树吧。我认为它是O(logn)，其中n是树中元素的数量，而不是哈希键的长度。 - Baskaya

1

如果我正确理解原始问题，它是关于根据哈希结果中的位将桶本身存储在基于二叉树的数据结构中。当然，我考虑这样做的原因是通过不存储未使用的桶来节省内存，而所描述的方法则使用相同或更多的内存，具体取决于您如何解释它，因此我不认为所述方法与简单的索引查找相比有什么好处，但这是一个单独的讨论。 - dgatwood

0

我发现这个东西是在找有没有人做过。我猜可能不是。

今天早上我想到了一个把二叉树实现为由索引存储的行数组的想法。第一行有1，第二行有2，第三行有4（是的，是2的幂）。这种结构的优点是可以使用位移和加减法来遍历树，而不必使用额外的内存来存储双向或单向引用。

这将允许您基于某种可哈希输入快速搜索哈希值，以发现该值是否存在于其他存储中。或者进行哈希冲突（或部分冲突）的搜索。我想不出还有什么其他用途，但对于这些用途来说，它会非常的快。很可能大多数旋转操作都会完全在CPU缓存中执行，并被写成漂亮的线性块放入主存储器中。

它的主要用途将是对随机输入值进行排序。如果数组中的块是两部分，例如哈希和另一个存储的标识符，您可以快速进行比较并快速插入，以发现具有哈希值的项目在另一个位置被保存（例如文件系统节点的UUID，甚至是文件名或其他短标识字符串）。

我会让其他人去想其他的用途，但我正在使用它来作为图论工作搜索表的一部分，以识别Cuckoo Cycle变体的部分碰撞。

我现在正在研究步行公式，以下是：

i = 数组元素的索引

向上走（转到父级）：

i>>1-(i+1)%2

（显然，您可能需要测试i是否为零）

向左走（向下和向左）：

i<<1+2

（这个和下一个也需要针对结构的2^depth进行测试，以便不会走出边缘并回到根）

向右走（向下和向右）：

i<<1+1

正如您所看到的，每次步行都是基于索引的简短公式。左右移位和加法，升序时则需要位移、加法和模数运算。两个指令向下移动，四个指令向上移动（在汇编语言中，或者像上面的C和其他高级语言操作符表示法中）。

编辑：我可以从进一步的评论中看出，缩短插入时间的好处肯定会有益处。但我认为传统的基于向量的二叉树提供的好处远不及密集版本。密集版本，其中所有节点都在连续的数组中，当它被搜索时，自然地将通过内存以线性方式遍历，这应该有助于减少缓存未命中，从而显着降低搜索的延迟，以及与随机访问相比，通过块顺序流式传输存在延迟问题。

https://github.com/calibrae-project/bast/blob/master/pkg/bast/bast.go

这是我目前正在实现的一个名为“Bifurcation Array Search Tree”的WiP状态。为了快速插入/删除和不会太慢地搜索排序哈希集合，我认为这对于有大量数据通过结构进出或更准确地说，对于更实时的应用程序来说将会非常有益。

- Louki Sumirniy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

如果元素没有全序（即所有对的“大于”和“小于”未被定义或元素之间不一致），则无法比较所有对，因此不能直接使用BST，但是没有任何阻止您通过哈希值索引BST-由于这是一个整数值，它显然具有全序（尽管仍需要解决冲突，即有一种处理具有相同哈希值的元素的方法）。

然而，BST相对于哈希表最大的优势之一在于元素是有序的-如果我们按哈希值排序，元素将具有任意顺序，这个优势将不再适用。

至于为什么考虑使用BST实现哈希表而不是数组，它会：

不需要调整数组大小的缺点 - 对于数组，通常会将哈希值与数组大小取模，并在数组满时调整数组大小并重新插入所有元素，但是使用二叉搜索树，您可以直接将不变的哈希值插入到二叉搜索树中。

如果我们希望任何单个操作永远不会超过一定的时间（如果我们需要调整数组大小，这很可能会发生），那么这可能是相关的，而总体性能则次要，但是可能有更好的方法来解决这个问题。
具有较低的哈希冲突风险，因为您不会将其与数组大小取模，因此可能哈希数的数量会显着增加。这将减少哈希表的最坏情况性能的风险（当大量元素哈希到相同值时的情况）。

实际的最坏情况性能取决于如何解决冲突。这通常通过链接列表进行处理，以获得O(n)的最坏情况性能。但是，我们也可以使用BST获得O(log n)的性能（如Java的哈希表实现中所做的那样，如果某些哈希的元素数量超过阈值）-也就是说，让您的哈希表数组中的每个元素指向一个BST，其中所有元素具有相同的哈希值。
可能使用更少的内存 - 对于数组，您不可避免地会有一些空索引，但对于BST，这些索引根本不需要存在。虽然这不是一个明显的优点，如果它是优点的话。

如果我们假设使用较少见的基于数组的BST实现，则此数组也将具有一些空索引，并且这也需要偶尔调整大小，但这只是一个简单的内存复制，而不需要重新插入所有具有更新哈希值的元素。

如果我们使用典型的基于指针的BST实现，则指针的额外成本似乎会超过在数组中具有一些空索引的成本（除非数组特别稀疏，这通常是哈希表的不好迹象）。

但是，由于我个人从未听说过这样做，因此可以推断出其好处不值得从预期的O(1)到O(log n)的操作成本增加。

通常，选择确实在使用BST直接（无哈希值）和使用哈希表（带有数组）之间。