0

CLRS的《算法简介》一书通过假设统一散列来分析开放寻址方案，该假设基本上说每个键的探测序列同样可能是 m! <0,1,2,...m-1> 的排列。本书随后介绍了三种方案：

  1. 线性探测
  2. 二次探测
  3. 双重哈希

它说所有这些上述技术保证每个键 k 的排列是 <<0,1,2,...m-1> 。但是，它们都没有满足统一散列的假设，因为它们都不能生成超过 m^2 个不同的探测序列。双散列具有最多的探测序列并且似乎给出了最好的结果。

为什么我们想要最大数量的探测序列？当探测序列最少时，我们不是得到最好的性能吗？我确信这里缺少一些基本知识。我想我对探针和探针序列感到困惑。

4

1 回答 1

0

这里的主要思想是我们需要一个函数f，将大数字（或者可能是String本质上由数字表示的 s）映射到更易于管理的较小数字。
这些较小的数字通常直接用作数组中的索引，以便我们可以获得O(1)由HashTable.
该函数f通常是散列函数。
现在的问题是，由于我们从一个较大的空间转到一个较小的空间，我们必然会发生冲突（这会影响我们的访问时间保证）。
对于我们如何处理冲突（假设我们已经决定使用哈希函数）有多种方法，你提到了其中的 3 种。

Linear Probing是最简单的冲突解决策略，我们基本上按顺序搜索数组，直到找到一个空单元格。尽管实现起来很简单，但效率不高，因为它会导致我们的hashtable.
总而言之，由于具有相同哈希值的两个项目发生碰撞，而且在替代位置发生碰撞的项目也发生碰撞，因此性能下降。

Quadratic ProbingLinear试图通过尝试占据比原始探测点更远的单元格来改进。尽管它改进了很多，Linear Probing但它引入了辅助聚类（具有相同散列探测的元素在数组中也具有相同的替代位置）。

Double Hashing进一步改进Quadratic Probing，理论上（我认为）它应该具有与线性相同的数量或探针。

双散列具有最多数量的探测序列，并且似乎给出了最好的结果......为什么我们想要最大数量的探测序列？

是的，理论上它更好Quadratic。这里的意思是 IMO 是要探测的位置最远，因此消除了替代位置（而不是原始存储桶）中相同哈希或不同哈希的元素之间的冲突

于 2012-08-18T20:09:57.310 回答