c++ - 散列函数说明

Question

今天在类里面复习了这个:

const int tabsize = 100000;

int hash(string s) {
    const int init = 21512712, mult = 96169, emergency = 876127;
    int v = init;
    for (int i=0; i<s.length(); i+=1)
        v = v * mult + s[i];
    if (v < 0) v = -v;
    if (v < 0) v = emergency;
    return v % tabsize;
}

在弄清楚最后 2 个 if 语句应该做什么时遇到了一些麻烦。

有什么想法吗？

谢谢

Answer 1

第一个if语句处理有符号整数的溢出行为。因此，如果整数太大而无法回绕并变为负数，则此 if 语句可确保仅返回正整数。

第二个if语句用于处理 v 为 2147483648 的罕见情况.

请注意，带符号的 32 位正整数最多只能达到 2<sup>31</sup> - 1 or 2147483647。而负面可以下降到-2<sup>31</sup> or -2147483648 .

这个数字是负数，即使取反也是负数。这就是紧急电话号码的用途

int main() {
    int t = -2147483648;
    std::cout << (-t) << std::endl;
}