Implement MurmurHash in Scala

Scala: MurmurHash を実装する

 

Redis の MurmurHash2 実装をそのまま Scala で書いてみる。

• redis/hyperloglog.c at 3.0 · antirez/redis

 

コード

効率よりも分かりやすさを優先。

object MurmurHash {

  private val defaultSeed = 0xadc83b19L

  def murmurHash64A(data: Seq[Byte], seed: Long = defaultSeed): Long = {
    val m = 0xc6a4a7935bd1e995L
    val r = 47

    val f: Long => Long = m.*
    val g: Long => Long = x => x ^ (x >>> r)

    val h = data.grouped(8).foldLeft(seed ^ f(data.length)) { case (y, xs) =>
      val k = xs.foldRight(0L)((b, x) => (x << 8) + (b & 0xff))
      val j: Long => Long = if (xs.length == 8) f compose g compose f else identity
      f(y ^ j(k))
    }
    (g compose f compose g)(h)
  }

}

13行目は、Redis のコードの big endian の場合の分岐に相当。
Byte 型を 0xff と論理積を取れば、非負の Int 値が手に入る。

 

実行例

scala> MurmurHash.murmurHash64A("A".getBytes).toHexString
res1: String = fc089b66b14af040

scala> MurmurHash.murmurHash64A("AB".getBytes).toHexString
res2: String = 24fb508dc42efb7f

scala> MurmurHash.murmurHash64A("ABCDEFGHabcdefgh".getBytes).toHexString
res3: String = 40055074d92b389f

scala> MurmurHash.murmurHash64A(Seq.fill[Byte](100)(-1)).toHexString
res4: String = 78be0c4f11cdc6d5

Redis の HyperLogLog で行われるカウント処理の結果も前回の調査内容と一致した。

scala> def count(x: Long): (Int, Int) = (
     |   (x & ((1L << 14) - 1)).toInt,
     |   (14 until 64).find(i => ((x >>> i) & 1L) != 0L).getOrElse(63) - 13
     | )
count: (x: Long)(Int, Int)

scala> count(MurmurHash.murmurHash64A("A".getBytes))
res7: (Int, Int) = (12352,1)

scala> count(MurmurHash.murmurHash64A("B".getBytes))
res8: (Int, Int) = (12964,3)

scala> count(MurmurHash.murmurHash64A("C".getBytes))
res9: (Int, Int) = (4477,3)

• mog project: HyperLogLog Implementation in Redis, pt.2