Mic*_*ael 12 hashtable binary-search-tree data-structures
使用数组实现Hashtable时,我们继承了数组的常量时间索引.使用二进制搜索树实现Hashtable的原因是什么,因为它提供了使用O(logn)的搜索？为什么不直接使用二进制搜索树？
Duk*_*ing 19
如果元素没有总顺序(即没有为所有对定义"大于"和"小于"或元素之间不一致),则无法比较所有对,因此可以' t直接使用BST,但没有什么阻止你通过哈希值索引BST - 因为这是一个整数值,它显然有一个总顺序(虽然你仍然需要解决冲突,这有办法处理具有相同哈希值的元素).
但是,BST相对于散列表的最大优点之一是元素按顺序排列 - 如果我们按散列值排序,则元素将具有任意顺序,并且此优势将不再适用.
至于为什么人们可能会考虑使用BST而不是数组来实现哈希表,它会:
没有需要调整数组大小的缺点 - 使用数组,你通常用数组大小修改哈希值,如果数组已满,则调整数组大小,重新插入所有元素,但是使用BST,你可以直接插入不变的哈希值进入BST.
如果我们希望任何单个操作永远不会花费超过一定的时间(如果我们需要调整阵列大小,这很可能会发生),这可能是相关的,整体性能是次要的,但可能有更好的方法来解决这个问题.
减少哈希冲突的风险,因为你没有使用数组大小进行修改,因此可能的哈希值可能会大得多.这将降低获得哈希表的最坏情况性能的风险(当大部分元素散列到相同值时).
实际的最坏情况表现取决于您如何解决冲突.这通常使用O(n)最坏情况性能的链表进行.但是我们也可以用BST实现O(log n)性能(如果带有一些哈希的元素数量高于阈值,就像在Java的哈希表实现中那样) - 也就是说,让你的哈希表数组中每个元素都指向一个BST,其中所有元素具有相同的哈希值.
可能使用更少的内存 - 使用数组你不可避免地会有一些空索引,但是使用BST,这些根本就不需要存在.虽然这不是一个明确的优势,但如果它是一个优势.
如果我们假设我们使用不太常见的基于数组的BST实现,则此数组也将具有一些空索引,这也需要偶尔调整大小,但这是一个简单的内存副本,而不是需要重新插入具有更新哈希的所有元素.
如果我们使用典型的基于指针的BST实现,指针的额外成本似乎会超过在数组中有一些空索引的成本(除非数组特别稀疏,这往往是哈希表的坏迹象)无论如何).
但是,由于我个人从未听说过这种情况,所以从预期的O(1)到O(log n),操作成本的增加可能是不值得的.
通常,选择确实是直接使用BST(没有哈希值)和使用哈希表(使用数组).