这个哈希函数有名称吗？

Question

我已经使用了Elk Scheme interpreter很长一段时间并且有时浏览它的源代码。

我注意到它在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;
}

源代码中没有任何内容描述该函数。

这个哈希函数有名称吗？ 是否在某处记录了散列方案？

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，但他们不想使用那种类型的全部范围（或者确保它在变成签名值时从不是负面的）？