6

I have a need to MurmurHash strings in both Python and Scala. However they are giving very different results. Scala's builtin MurmurHash3 library does not seem to give the same results as any of the other libraries I have tried including online ones. The odd thing is it seems to match on a single character but not multiple characters. Here are some examples:

Python:

mmh3.hash('string', 0)
res: -1390314837

Scala:

MurmurHash3.stringHash("string", 0)
res: 379569354

I have tried playing with signed and unsigned ints as I know Java has signed and the C implementation python is wrapping is using unsigned. But even using NumPy to convert to a signed int gives us no help. This website seems to agree with the python implementation:

http://murmurhash.shorelabs.com/

Any ideas on what could be going on here?

patrickbarker
  • 393
  • 1
  • 4
  • 13

2 Answers2

7

This is due to the difference in implementation between Scala's MurmurHash3.stringHash and MurmurHash3.bytesHash

MurmurHash3.bytesHash and python's mmh3.hash pass characters to the hashing mixer in groups of 4, but MurmurHash3.stringHash mixes characters in groups of 2. This means that the two hash functions return completely different outputs:

import scala.util.hashing.MurmurHash3

val testString = "FiddlyString"

MurmurHash3.stringHash(testString)           /* Returns an int */
MurmurHash3.bytesHash(testString.getBytes()) /* Returns a different int */

So if you need the results of python and Scala's MurmurHash3 values to match exactly:

I'd advise the first option, especially if your use-case requires better performance, or you need to hash massive strings

JulianPeach
  • 91
  • 1
  • 3
  • Essentially using the bytesHash method above is the equivalent of calling the mmh3 library in python as follows: mmh3.hash(key = testString, signed = True) – aldudalski Feb 05 '23 at 01:00
4

Scala uses Java strings which are encoded as UTF-16. These are packed two at a time into an Int; Python uses a char* (8 bits), so packs in four characters at a time instead of two.

Edit: Scala also packs the chars in MSB order, i.e. (s.charAt(i) << 16) | (s.charAt(i+1)). You might need to switch to an array of shorts and then swap every pair of them if it's really important to get exactly the same answer. (Or port the Scala code to Python or vice versa.) It also finalizes with the string length; I'm not sure how Python incorporates length data, if it does at all. (This is important so you can distinguish the strings "\u0000" and "\u0000\u0000".)

Rex Kerr
  • 166,841
  • 26
  • 322
  • 407
  • 1
    So, if that was the issue, wouldn't converting 'string' to utf-16 in python return the same result as the Scala? The python being: `'string'.encode('UTF-16')` – patrickbarker Aug 27 '16 at 13:51
  • 1
    @patrickbarker - Only if Python does not pack any other data, and packs the characters (shorts) in MSB order when combining them, since that's what the Scala implementation does. – Rex Kerr Aug 27 '16 at 14:41