探针数目与探针序列数目对开口寻址性能的影响

Question

“CLRS算法简介”一书通过假设统一散列来分析开放寻址方案，基本上说每个键的探测序列都可能是m中的任意一个！<0,1,2，.m-1>的排列书中接着介绍了三种方案：

1. 线性探测
2. 二次探测
3. 双散列

上面提到的所有这些技术都保证了<<0,1,2的排列，.m-1>适用于每个k键。但是它们都不能满足均匀散列的假设，因为它们都不能产生超过m^2不同的探针序列。双哈希有最多的探针序列，似乎是最好的结果。

为什么我们要最大数量的探针序列？当探针序列最少时，我们没有得到最好的性能吗？我相信这里有一些我缺少的基本面。我想我被探针和探针序列搞混了。

Answer 1

这里的主要思想是，我们需要一个函数f，它将大数字(或者可能是本质上由数字表示的String)映射到更易于管理的较小的数字中。

这些较小的数字通常直接用作数组中的索引，这样我们就可以获得由HashTable保证的内容访问时间HashTable。

这个函数f通常是哈希函数。

现在的问题是，由于我们从一个更大的空间到一个更小的空间，我们必然会发生碰撞(这会影响我们的访问时间保证)。

对于我们如何处理冲突(假设我们已经决定使用一个散列函数)，有多种方法，您可以提到其中的3种。

Linear Probing是最简单的冲突解决策略，我们基本上是按顺序搜索数组，直到找到一个空单元。虽然这很容易实现，但它并不有效，因为它会导致我们的hashtable中的数据集群。

总之，性能下降是因为具有相同散列的两个项都会发生碰撞，但也会导致在其他位置发生冲突的项。

Quadratic Probing试图通过尝试占据比原始探测点更远的单元格来改进Linear。尽管它在Linear Probing上有了很大改进，但它引入了二次聚类(具有相同散列探针的元素以及数组中相同的替代位置)。

Double Hashing在Quadratic Probing上做了进一步的改进，理论上(我认为)它应该有与线性相同的数目或探针。

双哈希有最多的探针序列，似乎能得到最好的结果.为什么我们要最大数量的探针序列？

是的，从理论上讲，Quadratic更好。这里的意思是，要探测的位置距离最远，因此在替代位置(比原始桶)中消除了相同散列或不同散列元素之间的冲突。