3

我正在尝试学习如何在 Javascript 中进行一些基本的哈希处理，并且遇到了以下算法：

var hash = 0;
for (i = 0; i < this.length; i++) {
    char = str.charCodeAt(i);
    hash = ((hash<<5)-hash)+char;
    hash = hash & hash;
}

我真的不明白它是如何工作的，我希望你能帮助我。特别是我不明白(hash<<5)-hash和hash = hash & hash。谢谢您的回复。

注意：对于寻找源代码的任何人，它都是 Java 的 String.hashCode() 的实现： http ://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method

4

5 回答 5

3

步骤

  hash = ((hash << 5) - hash) + char;

有效地：

  hash = ((hash * 32) - hash) + char;

然后，

  hash = hash & hash;

仅当数字溢出整数范围（32 位或 31 位）时才会更改值。（我不会那样做，但这是风格问题。）

在该代码中，应声明变量“i”和“char”：

var hash = 0, i, char;
于 2013-09-14T15:58:18.683 回答
2

<< 和 & 是按位运算。一个是移位，另一个是对它们进行运算。

0010 << 2变成1000因为一切都向左移动了。

0101 & 1110变为0100，因为只要两个值对于该特定位都为 1，则结果为 1。

@Pointy 的回答解释了hash = hash & hash（& 相同的值）完成了什么，我不确定它做了什么。

看：

https://en.wikipedia.org/wiki/Bitwise_operation https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

于 2013-09-14T15:53:12.297 回答
2

散列的一种常用技术是从 0 开始。然后将现有散列值乘以素数，最后将新元素添加到其中。

在这种情况下：

((hash << 5) - hash)

实际上是“哈希 * 31”。应用左移运算符 , <<5 次就像将数字乘以 2, 5 次。或者，将其乘以 2^5，即 32。然后它们减去一次，得到 31。

这hash & hash实际上是一个“什么都不做”操作，&对一个数字执行逻辑 AND ( ) 本身返回相同的数字，它不“做任何事情”，但它可以用来强制数字并确保它仍然是一个整数。数字表示可能存在一些 JS 诡计，这就是第二行的用途。

如果这只是原始 C，那它就是hash = hash * 31 + char.

于 2013-09-14T16:01:27.820 回答
0

hash << 5将 hash 的值移到“左”5 位。这相当于hash * 32. 对于散列生成算法，从移动位的角度来考虑它更容易。

hash = hash & hash看起来是个错误。它将哈希值与自身“和”，并将其分配回自身。将值与自身相加得到原始值，因此它是 nop 的一种形式。

于 2013-09-14T15:57:30.610 回答
0

<< 表示左移操作。此运算符将第一个操作数向左移动指定的位数，例如：

var num = 2; // in binary 10
var shift = 2 << 2;  //shift is 8, in binary 1000

& 运算符表示 AND 逻辑运算，例如：

var num1 = 6; // in binary 110
var num2 = 7; // in binary 111
var result = num1 & num2; // result is 6, in binary 110

有关按位运算符的完整参考，请查看Mozilla javascript 参考。

于 2013-09-14T16:02:31.300 回答