关于线性探测（哈希表）有一件事对我来说并不直观。如果我将 key1 其哈希结果放入数组索引 1。然后我放入 key2 -> 数组索引 2。然后我将 key3 -> 再次放入数组索引 1，这将转到数组索引 3。然后当我搜索 key3 我应该去通过包含与我的哈希完全不同的键的索引。这不是浪费吗？如果序列真的很大并且包含许多键（例如，我有 20 个元素，然后为 null，对于导致数组索引从 0 到 20 的任何键，我必须遍历所有索引，尽管它们与我的哈希值不同我可以通过单独的链接来消除它）。
或者我们的散列函数（如果写得足够好）在索引之间平均分配键并且我们不断调整数组的大小以最大半满这一事实减轻了这种情况？
当有许多碰撞时，线性探测是次优的。请注意，冲突的数量不仅取决于散列，还取决于表中的槽数（通常是素数），因为索引是散列的整数除以表长度的余数。
但是请注意，除了让冲突键一个挨一个还可能还利用 CPU 缓存，这将在一次读取中从 RAM 中带来许多元素。因此，（原则上）不要认为检查 20 个探针所需的时间是检查一个探针所需时间的 20 倍，因为 CPU 及其缓存内部发生的事情比进入 RAM 快得多。虽然没有魔法。如果每次比较的计算都丢弃了缓存中的内容，那么部分节省的内容将丢失。
您发现的问题确实会影响线性探测的性能。当您尝试查找某个元素时，您可能必须从最初的哈希探测开始的地方看很远才能找到您的元素。
话虽如此，线性探测在实践中非常快，这主要是由于参考的局部性。在内存中查找某些内容的成本并不统一——如果您在最近已读过的内容附近查找地址，则内存区域很可能已被拉入缓存并且查找内容的成本极低。因此，在实践中这些探测的成本通常比您自然预期的要低，因为这些探测可能非常快。
但是，这并不意味着您可以忽略这个事实。有很多问题需要注意。首先，随着表的负载因子增加，到达其他元素的成本开始使查找花费的时间越来越长。通常，您会看到人们以大约 75% 的负载系数重新散列到更大的表格中。其次，您需要有一个非常好的散列函数，因为如果您有一个低质量的散列，将许多元素放到相似的位置，由于您提到的原因，您将获得非常糟糕的性能。
您可以使用几种技术来缓解这种情况。罗宾汉散列的工作原理是在元素被放下后移动元素，以便离家较近的元素被推得更远，为离家更近的元素腾出空间。这使查找的平均成本略高，但显着降低了查找的最坏情况成本（换句话说，它减少了查找成本的方差，以换取增加该查找成本的预期值）。跳房子散列的工作原理是限制元素可以移动的最大距离并维护一个位掩码，指示附近哪些元素可能匹配，从而减少查找事物所需的工作量。和新的谷歌flat_map从线性探测开始，并使用非常聪明的散列和并行内存操作来使查找速度非常快。