这个哈希函数有名称吗？

Question

我曾经使用过Elk Scheme 解释器相当长一段时间，并且有时会查看其源代码。

我注意到它在 symbol.c 中包含了以下哈希函数：

int Hash (char const *str, unsigned int len) {
    register int h;
    register char const *p, *ep;

    h = 5 * len;
    if (len > 5)
        len = 5;
    for (p = str, ep = p+len; p < ep; ++p)
        h = (h << 2) ^ *p;
    return h & 017777777777;
}

源代码中没有描述这个函数的内容。

这个哈希函数有一个名称吗？
这个哈希方案在某个地方有文档记录吗？

- R Sahu

---

那个东西很老了。我想知道在Scheme代码中是否有某个点可以看到Scheme中的哈希，他们不得不保留旧的哈希。 - Joshua

@Joshua，它在代码库中只使用了一次：h = Hash(str, len) % OBARRAY_SIZE; 其中 h 的类型为 int。h 用作数组的索引。 - R Sahu

看起来这基本上是一个使用不同常量的FNV算法。奇怪的是它只查看前5个字符... - Shawn

不幸的是，Subversion提交日志也没有包含有用的解释性信息。 - Maxpm

Answer 1

所以，它本质上是与经典的Fowler-Noll-Vo哈希算法相同，但不是使用特别选择的质数作为哈希乘数，而是使用4（将数字左移2位等同于乘以4）。哈希的初始种子值也不同; 5 * len而不是一个常量值。

它只哈希字符串的前五个字符，这是一个奇怪的选择，我相信作者有一些很好的理由。

最后一行return h & 017777777777;也很有趣。那个八进制常数，假设一个典型的32位2的补码int，INT_MAX。如果计算64位哈希，但仅返回低32位，则会看到这样的东西，但在32位类型上，它是无操作的。也许作者对可移植性到具有更大int类型的系统感到困扰？但如果它仅用于取模数组长度的返回哈希值的一个位置，那么为什么要麻烦呢？或者也许h旨在成为一个unsigned int，但他们不想使用该类型的全部范围（或确保在转换为有符号值时永远不会为负数）？

- Shawn

---

return h & 017777777777; 这样写是有意义的，因为解释器已经移植到许多硬件平台上。可能其中一个或多个平台使用了64位的 int。我当然很欣赏这种预见性。 - R Sahu

没有质数的FNV不是真正的FNV，虽然我不指望人们知道这个。如果调用者不进行模素数运算，则会具有糟糕的重新散列特性。 - Joshua