Отличные результаты Murmur3 от Scala и Guava

Я пытаюсь сгенерировать хэши, используя алгоритм 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

Почему я получаю разные хэши?


scala guava consistent-hashing murmurhash
person Saket    schedule 12.05.2015    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Мне кажется, что hashString в Scala преобразует пары UTF-16 char в int не так, как hashUnencodedChars в Guava (hashString без Charset было переименовано в это).

Скала:

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

Гуава:

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

В Guava char в индексе i становится 16 младшими битами int, а char в i + 1 становится старшими 16 битами. В реализации Scala все наоборот: char в i является самым значащим, а char в i + 1 является наименее значимым. (Я полагаю, что тот факт, что реализация Scala использует +, а не |, также может иметь значение.)

Обратите внимание, что реализация Guava эквивалентна двукратному использованию ByteBuffer.putChar(c) для помещения двух символов в ByteBuffer с прямым порядком байтов, а затем использованию ByteBuffer.getInt() для получения обратно значения int. Реализация Guava также эквивалентна кодированию символов в байты с использованием UTF-16LE и хэшированию этих байтов. Реализация Scala не эквивалентна кодированию строки в любой из стандартных кодировок, которые должны поддерживать JVM. В общем, я не уверен, есть ли у Scala прецедент (если он есть) для того, чтобы сделать это так, как он делает.

Изменить:

Реализация Scala делает еще одну вещь, отличную от реализации Guava: она передает количество хэшируемых символов в метод finalizeHash, тогда как реализация Guava передает количество байтов в метод finalizeHash. эквивалентный fmix метод.

person ColinD    schedule 12.05.2015
comment
Спасибо за ответ! Разве Murmur3 не указывает, какие биты использовать? Я ожидал стандартного способа сделать это. - person Saket; 13.05.2015
comment
@Saket: Что касается деталей, я думаю, что это сводится к порядку байтов. Guava указывает, что он использует вариант little-endian алгоритма murmur3, а метод, который он использует для объединения двух символов, эквивалентен помещению двух последовательных char в LITTLE_ENDIAN ByteBuffer и получению int на выходе. Между тем версия Scala кажется эквивалентной помещению 2 char в BIG_ENDIAN ByteBuffer и получению int. Проблема с тем, что Scala передает количество chars в finalizeHash, а не количество байтов, кажется просто неправильной, насколько я могу судить. - person ColinD; 13.05.2015
comment
(Глядя на C++ реализация MurmurHash3_x86_32 , кажется очевидным, что параметр len представляет собой количество байтов, которые должны быть обработаны в данных, и именно этот параметр len подвергается операции xor с h1 как часть шага финализации.) - person ColinD; 13.05.2015

arrow_upward
-1
arrow_downward

Я считаю, что hashString(x, StandardCharsets.UTF_16BE) должно соответствовать поведению Scala. Дайте нам знать.

(Кроме того, пожалуйста, обновите свою гуаву до чего-то более нового!)

person Kevin Bourrillion    schedule 12.05.2015
comment
На самом деле это не работает, поскольку он только меняет порядок байтов для каждого char; он не меняет порядок, в котором эти символы интерпретируются как int. - person ColinD; 12.05.2015
comment
Хм, я думал, что эта часть не отличается между ними. - person Kevin Bourrillion; 12.05.2015