Scala和Guava的Murmur3算法结果不同

Question

我正在尝试使用Murmur3算法生成哈希值。这些哈希值是一致的，但是Scala和Guava返回的值不同。

class package$Test extends FunSuite {
  test("Generate hashes") {
    println(s"Seed = ${MurmurHash3.stringSeed}")
    val vs = Set("abc", "test", "bucket", 111.toString)
    vs.foreach { x =>
      println(s"[SCALA] Hash for $x = ${MurmurHash3.stringHash(x).abs % 1000}")
      println(s"[GUAVA] Hash for $x = ${Hashing.murmur3_32().hashString(x).asInt().abs % 1000}")
      println(s"[GUAVA with seed] Hash for $x = ${Hashing.murmur3_32(MurmurHash3.stringSeed).hashString(x).asInt().abs % 1000}")
      println()
    }
  }
}


Seed = -137723950
[SCALA] Hash for abc = 174
[GUAVA] Hash for abc = 419
[GUAVA with seed] Hash for abc = 195

[SCALA] Hash for test = 588
[GUAVA] Hash for test = 292
[GUAVA with seed] Hash for test = 714

[SCALA] Hash for bucket = 413
[GUAVA] Hash for bucket = 22
[GUAVA with seed] Hash for bucket = 414

[SCALA] Hash for 111 = 250
[GUAVA] Hash for 111 = 317
[GUAVA with seed] Hash for 111 = 958

我为什么会得到不同的哈希值？

- Saket

Answer 1

我觉得 Scala 中的 hashString 方法和 Guava 中的 hashUnencodedChars 方法处理 UTF-16 char 对转换成 int 的方式不同（在 Scala 中，没有使用 Charset 参数的 hashString 方法改名为这个）。

val data = (str.charAt(i) << 16) + str.charAt(i + 1)

Guava:

int k1 = input.charAt(i - 1) | (input.charAt(i) << 16);

在Guava中，索引处i的char成为int的16个最低有效位，而i+1处的char成为最高的16个有效位。在Scala实现中，它是相反的：索引处i的char是最重要的，而i+1处的char是最不重要的。（我想Scala实现使用+而不是|也可能很重要。）

请注意，Guava实现等价于使用ByteBuffer.putChar(c)两次将两个字符放入小端序的ByteBuffer中，然后使用ByteBuffer.getInt()将int值取回。Guava实现还等价于使用UTF-16LE将字符编码为字节并对这些字节进行哈希。Scala实现不等同于将字符串编码为JVM必须支持的任何标准字符集之一。总的来说，我不确定Scala是否有任何先例可按照其所做的方式执行操作。

另外，Scala实现与Guava实现不同的另一点是：它将哈希的字符数传递给finalizeHash方法，而Guava的实现将字节数传递给等效的fmix方法。

- ColinD

---

谢谢回复！Murmur3是否指定要使用哪些位？我原以为有一种标准的方法来做这个。 - Saket

@Saket：就比特而言，我认为这归结于字节序问题。Guava指定使用murmur3算法的_little-endian_变体，并且它用于组合两个字符的方法相当于将2个连续的char放入LITTLE_ENDIAN ByteBuffer中并获取一个int。与此同时，Scala版本似乎相当于将2个char放入BIG_ENDIAN ByteBuffer中并获取一个int。从我所知道的情况来看，Scala传递给finalizeHash的字符数而不是字节数似乎是错误的。 - ColinD

看一下 MurmurHash3_x86_32 的 C++ 实现（链接：https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp#94），很明显 len 参数是要处理的数据字节数，而在最终化步骤中，正是将 len 与 h1 进行异或运算。 - ColinD

Answer 2

我认为hashString(x, StandardCharsets.UTF_16BE)应该与Scala的行为一致。如果不一致，请告知。

（另外，请升级您的Guava至更新版本！）

- Kevin Bourrillion

---

这实际上不起作用，因为它只改变了每个“char”的字节顺序；它并没有改变这些字符被解释为int的顺序。 - ColinD

哦，我原以为这部分在两者之间是没有区别的。 - Kevin Bourrillion