线性探测具有不相等哈希的巨大密钥序列

Question

线性探测（哈希表）有一件事对我来说并不直观。如果我把散列结果的key1放到数组索引1中。然后我放了钥匙2-

或者，我们的散列函数（如果写得足够好的话）在索引中平均分配键，并且我们不断调整数组的大小，使其最大半满，这就减轻了这种情况？

Answer 1

您发现的问题确实会影响线性探测的性能。当您试图查找某个元素时，为了找到您的元素，您可能必须从初始哈希探测开始的地方查找很远的地方。

也就是说，线性探测在实践中非常快，这主要是由于引用的局部性。在内存中查找某些东西的成本是不一致的——如果你在最近读过的东西附近查找一个地址，很可能内存区域已经被拉入缓存，查找东西的成本非常低。因此，这些探测在实践中的成本通常比你自然预期的要低，因为这些探测可能非常快。

然而，这并不意味着你可以忽略这个事实。有许多问题需要注意。首先，随着表的负载系数增加，命中其他元素的成本开始增加，从而导致查找时间越来越长。通常，你会看到人们以大约75%的负荷系数重新回到一张更大的桌子上。第二，你需要有一个非常好的散列函数，因为如果你有一个低质量的散列，把很多元素放到相似的位置，你会得到非常糟糕的性能。

有几种技术可以用来缓解这种情况。罗宾汉散列法的工作原理是，在元素被放置后，移动元素，以便将离家更近的元素推到更远的地方，为离家更近的元素腾出空间。这会使查找的平均成本稍高，但会显著降低查找的最坏情况成本（换句话说，它会降低查找成本的方差，以换取增加该查找成本的预期值）。跳点散列法的工作原理是限制元素可以移动的最大距离，并维护一个位掩码，指示附近哪些元素可能匹配，从而减少查找内容所需的工作量。新的Googleflat_map从线性探测开始，使用非常聪明的散列和并行内存操作，使查找速度极快。

Answer 2

当有许多冲突时，线性探测是次优的。请注意，冲突的数量不仅取决于哈希，还取决于表中的槽数（通常是素数），因为索引是哈希除以表长度的整数的余数。

然而，请注意，与将冲突的键一个接一个相比，还可以利用CPU缓存，这将在一次读取中从RAM中带来许多元素。所以，不要（原则上）认为检查20个探针所需的时间是检查一个探针所需时间的20倍，因为CPU及其缓存中发生的事情要比进入RAM快得多。不过，没有魔法。如果每次比较的计算都会丢弃缓存中的内容，那么节省的部分就会丢失。