我的AP计算机科学课程最近学习了哈希表，以及线性探测如何导致集群问题，结果证明这并不是持续的时间插入/搜索。我们的导师告诉我们，二次探测是减少聚类的好方法，原因很明显。我想知道，如果只剩下一个元素，二次探测是否需要一段时间才能找到它。我写了一个快速程序（如果你愿意，我可以插入源代码，但我认为无论如何都不会有人读它），测试一下是否发生了这种情况。
首先，我证明了，如果没有一个数组索引永远不会被登录，那么如果你总是试图添加到任何一个索引中，就会找到它。这是因为这样做，它要么最终会命中数组中的每个索引，要么不会。如果二次探测命中每个索引，那么您可以在任何点选择任何索引，并且它总是会结束，所以长度数组总是有效的。如果它不能击中每一个实例，你就会发现做不到的事情。
然后，我制作了一个我感兴趣的长度的布尔值数组，如果索引0不为真，则将其设置为真，否则，如果不是，则将索引1%length设置为真；否则，如果不。。。否则，如果不是，则将索引n%length设置为true。。。
我没有检查1名前锋和1名后卫，但正如你所看到的，这一点一开始并不重要。
因此，在四个元素的数组中，二次探测将找到索引0和1，但（在约46000^2%的长度内）从未找到索引2或3。如果我也向后看，它会找到索引3（（0-1）%4+4）%4==3），但仍然没有找到索引2。
经过一番思考，我发现我想看看是否有任何一对数字，x和n，其中x和n都是整数，其中以下方程评估为真：
x^2 == 4*n+2
也就是说，任何整数的两倍以上都是一个平方数。
如果可以证明对于所有整数x和n，没有一对会导致这是真的，这意味着二次探测永远不会到达长度为4的数组中的索引2。
我认为这和说抛物线是一样的：
y=(x^2-2)/4
不包含（x，y）对，其中x和y都是整数，但我不能完全确定。
我刚刚花了两个小时来研究这个问题，这就是我所能弄清楚的。
我知道有时二次探测找不到点；这不是我感兴趣的。我该如何证明，要么这永远不会奏效，要么如果我使用足够大的数字，这最终会终止。此外，如果你能把数学放在你在BC微积分学的东西下面，那就太好了。
非常感谢！
好吧，经过深思熟虑，我想我已经找到了解决方案，我想如果其他人有同样的问题，我会把它发布在这里。在上面给出的具体例子中（即长度为4的表中的索引2），该程序将永远运行下去。为了使它停止，它需要是真的，有一个整数x，对于它，x^2-2可以被4整除。我发现的解决方案来自偶数和奇数的性质。我认为这很容易理解，但并不适用于其他情况，所以我仍然希望得到一个一般的答案。
x^2-2是偶数当且仅当x^2是偶数，因为从一个数字中减去2不会改变它是否是偶数。
注意：我们不能说没有偶数平方数，因为其他的平方数都是偶数。
x^2是一个完美的正方形，因为x是一个整数。这意味着，如果写出x的素数因子分解，它在每个因子之上都会有一个偶数指数。这是因为一个完美的正方形是通过将相同的数字乘以它自己而产生的。
正如问题中所述，我们希望证明不存在4*n+2是完美平方的整数。现在，4*n+2一定不是4的倍数[当然，它比4的倍数多2]。因此，我们试图证明每个是2的倍数的完美正方形也是4的倍数，这意味着没有超过4的倍数的两个是完美正方形的例子，因为所有的完美正方形都被证明是2的倍。
由于每个平方数的每一个因子都有一个偶数，所以它必须是2的偶数次幂的倍数，而不是奇数。如果它确实是2的倍数到大于1的幂，那么它也是4的倍数。任何因子为2的平方数都必须有第二个因子，因为因子为2只可能来自两个数中的一个，这两个数相乘得到完美的平方。由于这些数字一定是相等的，要么它们都有一个2，数字是4的倍数，要么两者都没有，甚至都不在第一位。
因此，在上面提到的哈希表中，二次探测将永远不会终止，因为它永远不会找到那个点。另外，很抱歉数学上的答案，我更喜欢计算机科学的，但Comp的理论。科学。当你开始证明事情的时候，你开始稍微进入数学领域。