Implement MurmurHash in Scala

Scala: MurmurHash を実装する

 

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

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

 

コード

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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 値が手に入る。

 

実行例

1 2 3 4 5 6 7 8 9 10 11

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 で行われるカウント処理の結果も前回の調査内容と一致した。

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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