关于线性探测(哈希表)，有一件事对我来说并不直观。 如果我将 key1 的哈希结果放入数组索引 1。然后我将 key2 -> 数组索引 2。然后我将 key3 -> 再次放入数组索引 1，这将转到数组索引 3。 然后，当我搜索 key3 时，我应该遍历包含与我的哈希值完全不同的键的索引。这不是浪费吗？如果序列真的很大并且包含许多键(例如我有 20 个元素，则为 null，对于导致数组索引从 0 到 20 的任何键，我必须遍历所有索引，尽管它们没有与我的相同的哈希值我可以通过单独的链接来消除这个问题)。
或者，我们的散列函数(如果编写得足够好)在索引之间平均分配键，并且我们不断地将数组大小调整为最大半满，这一事实可以缓解这一问题？
最佳答案
当存在许多冲突时，线性探测并不是最佳选择。请注意，冲突的数量不仅取决于哈希，还取决于表中的槽数(通常是素数)，因为索引是哈希整数除以表长度的余数。
但请注意，将冲突的键一个挨着另一个也可能会利用 CPU 缓存，这会在一次读取中从 RAM 中带来许多元素。因此，(原则上)不要认为检查 20 个探测器所需的时间是检查 1 个探测器所需时间的 20 倍，因为 CPU 及其缓存内部发生的情况比 RAM 中发生的情况要快得多。但并没有什么魔法。如果每次比较的计算都丢弃了缓存中的内容，那么部分节省的费用将会丢失。
关于algorithm - 线性探测具有不等哈希的大量键序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53797262/