algorithm - 哈希算法的困惑

Question

我对为什么要从 H_i 中减去 H_i+1 来计算 k+i² 感到困惑。如果 H_i 在等式中代表 i² 那么 H_i+1 是如何影响 k 的，为什么是减法而不是加法？

Answer 1

思路是这样的。在[二次探测[https://en.wikipedia.org/wiki/Quadratic_probing ), 你搜索位置 (涉及) H₁, H₂, H₃, ... H_i , H_{i + 1}, ... 在一个循环中，您可以避免为 i² 重新计算每个我。

假设您已经计算出 H_i = k + i²。那么 H_{i + 1} = k + (i + 1)² = k + i² + 2i + 1 = H< sub>i + 2i + 1。因此，如果您已经计算出 H_i，则只需为 H_{i + 1< 添加 2i + 1/sub>}.