c - K&R 书中的散列函数

Question

考虑这个函数：

unsigned hash(char *s)
{
  char *p;
  unsigned hashval;
  for(p = s; *p; p++)
    hashval = *p + 31 * hashval;
  return hashval;
}

如何测量s将返回错误结果的字节数，例如溢出？我在 32 位平台上。

Answer 1

如果您将其更改为阅读

unsigned hash(const char *s)
{
  const unsigned char *p;
  unsigned hashval = 0;
  for (p = (const unsigned char *) s; *p; p++)
    hashval = *p + 31u * hashval;
  return hashval;
}

那么由于整数溢出，不再有任何未定义行为的可能性，因为算术中涉及的所有类型都是无符号的，所以一切都包装了 mod 2 ⁿ（其中n是unsignedin 位的宽度）。我还修复了未初始化变量的使用，并制作了sand p const，这可能会改进优化和/或捕获函数体中的错误。

（我现在不记得确切的算术转换规则；一开始可能不可能。但是，这样写显然不可能。）

顺便说一句，现在已知有更好的哈希函数：如果您没有强烈的理由这样做，我建议使用SipHash。

Answer 2

几个想法：

首先，在散列函数中会出现溢出。

其次，由于您的函数包含 a 31*hashval，并且 string 中的每个元素的值必须至少为 1，因此您会期望在溢出之前可以拥有的最长字符串是所有 \x01 的字符串，它会溢出散列当它的长度为 6 时（由于该*31操作将整个数字分布在左侧的 5 位上，因此会有进位，这意味着您可能会影响第六位，并且 6*6 = 36 > 32 ）。当字节更大时，数字会更少（第一个字节几乎定义了行为 - 当它很大时，您可能会在五个字节后溢出）。用真实的位和字节更容易显示这一点。我将使用 a*32而不是*31算法（不太正确，但不用担心进位，你会明白的）：

byte      hash is less than:
0000a000  00000000 00000000 00000000 0000a000
10000000  00000000 00000000 000000a0 10000000
b0000000  00000000 00000000 a0100000 b0000000
c0000000  00000000 00a01000 00b00000 c0000000
d0000000  0000a010 0000b000 00c00000 d0000000
anything  OVERFLOW!

As was pointed out above, you can improve the predictable behavior of your (rather poor) hashing algorithm by declaring everything as unsigned integer; I would also recommend initializing the hash (and a value other than zero might be a good idea), rather than assuming that the compiler will set it to zero (I am not 100% sure that's defined behavior). Finally, if you are wondering about overflow, and want to get a warning, I would modify the code as follows:

for(p = s; *p; p++) {
    if((hashval > 0xFFFFFFFF/31) || (*p>>1 + 31 * (hashval>>1)) > 0x7FFFFFFF) {
        printf("hash is about to overflow at character %c\n", *p);
    }
    hashval = *p + 31 * hashval;
}