c - 像K＆R book一样的哈希函数

考虑这个函数：

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

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

最佳答案

如果你把它改成

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 2n（其中n是unsigned的宽度（以位为单位）。我还修复了未初始化变量的使用，并进行了s和pconst，这可能会改进优化和/或捕获函数体中的错误。
（我现在不记得确切的算术转换规则了，一开始可能不可能。然而，这样写显然是不可能的。）
顺便说一句，现在有很多更好的散列函数：如果你没有强有力的理由这样做，我建议你使用SipHash。