javascript - 哈希字符串函数 djb2 正确避免冲突？

Question

我正在研究 javascript 中 hasmap 的哈希字符串函数。并查看我在网上找到的这段代码，我不确定该功能是否正确:

HashMap._hashString = function(string) {
    var hash = 5381;
    for (var i=0; i<string.length; i++) {
        hash = (hash << 5) + hash + string.charCodeAt(i);
        hash = hash & hash;
    }
    //Reduce the chance of collisions by incorporating the string length,
    //and randomize the hashes to prevent malicious collisions.
    return hash ^ string.length ^ this._secret;
};

这条线有意义吗？

        hash = hash & hash;

在这行代码中:

    return hash ^ string.length ^ this._secret;

我知道将字符串的长度添加为哈希计算的一个因素将有助于解决冲突，但为什么我要通过 XOR 运算添加这个因素？为什么不使用任何其他位运算符？

我也在阅读这篇文章，以进一步了解哈希算法:

http://www.cse.yorku.ca/~oz/hash.html

Answer 1

Does it make any sense to have this line?

   hash = hash & hash;

该行的目的是将值限制在 32 位范围内。 hash & hash 看起来像空操作，但应用按位运算符会 chop 任何溢出。它给出了与此相同的结果:

 hash = hash & 0xFFFFFFFF

In this line of code:

return hash ^ string.length ^ this._secret;

I understand that adding the length of the string as a factor for the hash to evaluate would help to work with the collisions, but why would I add this factor with a XOR operation? Why not using any other bit operator?

使用 & 或 | 你会丢失信息:相同长度的不同输入会有更高的碰撞机会。特别是，长度为 2 的幂的 & 将是灾难性的，因为它只能产生 2 个不同的值(长度本身或零)。或者 | 的长度大部分为 1 位(如 0xffff):这将再次限制可能的结果。

执行 + 将是一个可行的替代方案，但您需要确保结果再次保持在 32 位范围内。