因此，假设您有一个使用线性探测的哈希图。
你首先插入一个带有键 X 的值 X，它散列到位置 5，比如说。
然后，您插入一个带有键 Y 的值 Y，它也散列为 5。它将占用位置 6。
然后插入一个带有键 Z 的值 Z，它也散列为 5。它将占用位置 7。
然后删除 Y，所以内存看起来像“X，null，Z”
然后您尝试使用键 Z 插入一个值，它会检查 5，看到它已被占用，检查 6，然后将其插入为空。但是，已经有一个键为 Z 的条目，因此您将有两个键为 Z 的条目，这违反了不变量。
因此，在找到值本身之前，您是否不需要遍历整个地图。如果未找到，则可以将其插入第一个空空间。因此，在某个键上的所有首次插入不是 O(N) 吗？
不。
您遇到的问题是由您错误地删除引起的。
事实上，使用线性探测从表中删除有些困难——以至于许多使用线性探测构建的表根本不支持删除。
也就是说：至少在理论上，在最坏的情况下（插入、删除、查找等），哈希表上的几乎所有操作最终都可能是线性的。无论您编写的哈希函数多么聪明，都有无限的输入可以哈希到任何特定的输出。如果输入的选择非常不幸（或者只是一个糟糕的哈希函数），您最终可能会得到任意百分比的输入，所有这些都产生相同的哈希码。
编辑：如果您坚持使用线性探测支持删除，则基本思想是您需要确保每个条目“链”保持连续。因此，您对密钥进行哈希处理，然后从那里一直走到下一个空桶。您检查每个条目的哈希码，并用哈希到孔之前位置的最后一个连续项目填充“孔”。反过来，这可能会创建另一个洞，您必须用散列到您正在创建的洞之前的某个位置的最后一个项目填充该洞（以此类推，递归地）。
不知道为什么村里的白痴（；））删除了他的帖子，因为他是对的——过度提交/不平衡的哈希表退化为线性搜索。
为了达到 O(1) 的性能，表不能被过度使用（表必须足够大，给定条目的数量），并且哈希算法必须做得很好（避免不平衡），给定键的特征/统计信息价值。
应该注意的是，有两种基本的哈希表方案——线性探测，其中哈希同义词被简单地插入到下一个可用的表槽中，以及链表，其中哈希同义词被添加到给定的表元素之外的链表中哈希值。它们产生大致相同的统计数据，直到过度使用/不平衡，此时线性探测很快就完全崩溃了，而链表只是缓慢地退化。而且，正如其他人所说，线性探测使删除变得非常困难。