如何证明二次探测不会以散列结束 table
How to prove that quadratic probing does not end for a hash table
我的 AP 计算机科学 class 最近了解了哈希表以及线性探测如何导致聚类问题并证明不是真正的常数时间 insertion/searching。我们的讲师告诉我们，出于显而易见的原因，二次探测是减少聚类的好方法。我想知道是否有可能如果只剩下一个元素，二次探测需要一段时间才能找到它。我写了一个快速程序（如果你愿意，我可以插入源代码，但我不认为任何人都会阅读它）测试是否发生了这种情况。
首先，我证明了如果不存在一个永远登陆不上的数组索引，只要你一直尝试添加到任何一个索引上，就会找到它。这是因为通过这样做，它要么最终命中数组中的每个索引，要么不会。如果二次探测命中每个索引，那么您可以在任何时候选择任何索引并且它总是会结束，因此长度数组总是有效。如果它不能击中每个实例，你就会发现你不能这样做。
然后，我创建了一个我感兴趣的任意长度的布尔值数组，如果索引 0 不为真，则将其设置为真，否则将索引 1%length 设置为真（如果未另行设置）如果不是，则索引 4%length 为真...否则，如果不是，则将索引 n%length 设置为真...
我没有检查 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
即任意整数的4倍以上的2是平方数。
如果对于所有整数 x 和 n 都可以证明没有任何一对会导致它为真，这意味着二次探测永远不会到达长度为 4 的数组中的索引 2。
我觉得这和说抛物线是一样的：
y=(x^2-2)/4
不包含 x 和 y 均为整数的 (x, y) 对，但我不完全确定。
我刚刚花了两个小时来解决这个问题，这就是我所能弄清楚的。
我知道有时候二次探查找不到点；那不是我感兴趣的。我将如何证明这永远行不通，或者如果我使用足够大的数字，这最终会终止。另外，如果您可以将数学保留在您在 BC 微积分中学到的内容下，那就太好了。
非常感谢！
好的，经过深思熟虑，我想我找到了解决方案，我想我会 post 在这里，以防其他人有同样的问题。在上面给出的具体示例中（即长度为 4 的 table 中的索引 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 并且该数字是 4 的倍数，要么两者都没有，甚至不在第一位。
因此，在上面提到的散列table中，二次探测将永远不会终止，因为它永远不会找到那个点。另外，对于数学答案感到抱歉，我更喜欢计算机科学，但更喜欢 Comp 的理论。科学。当你开始证明事物时，开始稍微进入数学区域。
我的 AP 计算机科学 class 最近了解了哈希表以及线性探测如何导致聚类问题并证明不是真正的常数时间 insertion/searching。我们的讲师告诉我们，出于显而易见的原因，二次探测是减少聚类的好方法。我想知道是否有可能如果只剩下一个元素，二次探测需要一段时间才能找到它。我写了一个快速程序（如果你愿意，我可以插入源代码，但我不认为任何人都会阅读它）测试是否发生了这种情况。
首先，我证明了如果不存在一个永远登陆不上的数组索引，只要你一直尝试添加到任何一个索引上，就会找到它。这是因为通过这样做，它要么最终命中数组中的每个索引，要么不会。如果二次探测命中每个索引，那么您可以在任何时候选择任何索引并且它总是会结束，因此长度数组总是有效。如果它不能击中每个实例，你就会发现你不能这样做。
然后，我创建了一个我感兴趣的任意长度的布尔值数组，如果索引 0 不为真，则将其设置为真，否则将索引 1%length 设置为真（如果未另行设置）如果不是，则索引 4%length 为真...否则，如果不是，则将索引 n%length 设置为真...
我没有检查 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
即任意整数的4倍以上的2是平方数。
如果对于所有整数 x 和 n 都可以证明没有任何一对会导致它为真，这意味着二次探测永远不会到达长度为 4 的数组中的索引 2。
我觉得这和说抛物线是一样的：
y=(x^2-2)/4
不包含 x 和 y 均为整数的 (x, y) 对，但我不完全确定。
我刚刚花了两个小时来解决这个问题，这就是我所能弄清楚的。
我知道有时候二次探查找不到点；那不是我感兴趣的。我将如何证明这永远行不通，或者如果我使用足够大的数字，这最终会终止。另外，如果您可以将数学保留在您在 BC 微积分中学到的内容下，那就太好了。
非常感谢！
好的，经过深思熟虑，我想我找到了解决方案，我想我会 post 在这里，以防其他人有同样的问题。在上面给出的具体示例中（即长度为 4 的 table 中的索引 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 并且该数字是 4 的倍数，要么两者都没有，甚至不在第一位。
因此，在上面提到的散列table中，二次探测将永远不会终止，因为它永远不会找到那个点。另外，对于数学答案感到抱歉，我更喜欢计算机科学，但更喜欢 Comp 的理论。科学。当你开始证明事物时，开始稍微进入数学区域。