JavaScript哈希算法

Question

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的含义。谢谢您的回复。

- Tenescu Andrei

你在哪里找到那段代码的？我认为它并不是一个很好的示例。特别是 hash = hash & hash 这一步看起来是多余的。我猜它可能是为了保持值在整数范围内。 - Pointy

我不太记得了。当时我在谷歌上搜索，然后就看到了这个。最近我想起来了，因为我并不是很理解它的工作原理，所以我就在这里发帖问了一下。 - Tenescu Andrei

你能否提供一个更好的例子？ - user3376708

5个回答

2

一种常见的哈希技术是从0开始。然后，您将现有的哈希值乘以一个质数，最后再加上新元素。

在这种情况下：

((hash << 5) - hash)

实际上，“hash * 31”相当于应用左移操作符“<<”5次，就像将数字乘以2，5次。或者乘以2^5，即32。然后它们再减去一次，得到31。

“hash & hash”实际上是一个“什么也不做”的操作，在一个数字上执行逻辑与（“&”）会返回相同的数字，它不会“做任何事情”，但它可以用来强制转换数字并确保它保持为整数。可能有一些JS机制涉及到数字的表示，这就是第二行存在的原因。

如果这只是原始的C代码，那么它将简单地是“hash = hash * 31 + char”。

- Will Hartung

2

“<<” 和 “&” 是位运算符。一个是将位向左移动，另一个是对它们进行与运算。

例如，“0010 << 2” 变成 “1000”，因为所有的位都向左移动了。

再例如，“0101 & 1110” 变成 “0100”，因为只有在两个值的特定位上都为 1 时，结果才为 1。

@Pointy 的答案解释了 “hash = hash & hash”（& 同一值）的作用，我不确定它是什么。

参见：

- Bjorn

它是否总是自动将哈希转换为二进制数，还是在代码中有某个地方需要告诉它要转换为二进制数？ - user3376708

每种类型的数据都已经表示为位。如果您尝试在非数字类型的JavaScript上使用位运算符，JavaScript将首先尝试将其转换为数字。 - Bjorn

0

hash << 5 是将哈希值向左移动5位。这相当于 hash * 32。对于哈希生成算法来说，更容易从位移的角度来思考。

hash = hash & hash 看起来像是一个错误。它将哈希值与自身进行“与”操作，并将结果赋回给自己。将值与自身进行“与”操作会得到原始值，因此它是一种无操作形式。

- ash

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 参考文档。

- Alberto

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pointy · Accepted Answer

步骤

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

实际上的意思是：

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

然后，

  hash = hash & hash;

如果数字已经超过了整型范围（32位，或者可能是31位），这个语句才会改变数值。（我不会这么写，但这只是个人风格的问题。）

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

var hash = 0, i, char;