0

我的 AP 计算机科学课程最近了解了哈希表以及线性探测如何导致聚类问题，结果证明并不是真正的恒定时间插入/搜索。我们的讲师告诉我们，由于显而易见的原因，二次探测将是减少聚类的好方法。我想知道是否有可能如果只剩下一个元素，那么二次探测需要一段时间才能找到它。我写了一个快速程序（如果你愿意，我可以插入源代码，但我认为无论如何都不会有人阅读它）测试是否发生这种情况。

首先，我证明了如果没有永远不会登陆的数组索引，那么如果你总是尝试添加到任何一个索引，它就会被找到。这是因为通过这样做，它最终会命中数组中的每个索引，或者不会。如果二次探测命中每个索引，那么您可以在任何点选择任何索引并且它总是会结束，因此长度数组总是有效的。如果它不能击中每一个实例，你就会发现你不能这样做。

然后，我创建了一个我感兴趣的任何长度的布尔数组，如果索引 0 不为真，则将其设置为真，否则将索引 1%length 设置为真，否则将索引 4%length 设置为如果不是，则为 true ...否则将 index 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

也就是说，任何整数的 4 倍以上是平方数。

如果对于所有整数 x 和 n 都可以证明没有任何对会导致该结果为真，则意味着二次探测永远不会到达长度为 4 的数组中的索引 2。

我认为这与说抛物线是一回事：

y=(x^2-2)/4

不包含 (x, y) 对，其中 x 和 y 都是整数，但我不完全确定。

我刚刚花了两个小时来解决这个问题，这就是我能够弄清楚的全部。

我知道有时二次探测找不到位置。那不是我感兴趣的。我将如何证明这将永远行不通，或者如果我使用足够大的数字，这将最终终止。此外，如果您可以将数学保留在您在 BC 微积分中学习的内容中，那就太好了。

非常感谢！

4

1 回答 1

2

好的，经过一番思考，我想我有解决方案，我想我会把它贴在这里，以防其他人有同样的问题。在上面给出的具体示例中（即长度为 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. 的理论。科学。当你开始证明事情时，它开始稍微进入数学领域。

于 2015-12-18T03:14:11.470 回答