Zero-allocation Hashingのハッシュ関数（MurmurHash／FarmHash／CityHash／xxHash）で遊ぶ

Javaでの高速なハッシュ関数についてのこちらの資料に以前から興味があって、そのうちちょっと気になったライブラリで
遊んでみましたという話。

#JJUG - Java で最速のハッシュアルゴリズムを求めて

対象のライブラリは、Zero-allocation Hashing。

Zero-allocation Hashing？

GitHub - OpenHFT/Zero-Allocation-Hashing: Zero-allocation hashing for Java

OpenHFTが提供する、ハッシュ関数の実装です。

このZero-allocation Hashingには、

MurmurHash3
FarmHash（na／uo）
CityHash
xxHash

のハッシュが提供されています。

現時点のバージョンは0.8で、ソースコードもハッシュに特化した内容のようです。
https://github.com/OpenHFT/Zero-Allocation-Hashing/tree/zero-allocation-hashing-0.8/src/main/java/net/openhft/hashing

※）
なお、これらのハッシュ関数はセキュリティ（メッセージダイジェストなど）関連で使用するものとは用途が違うので、そういう時は
SHA-256とかを使うことになるでしょう（これらに比べると、速度は出ませんが）。

参考）
高速ハッシュアルゴリズム | YOSBITS

特徴としては、

高速
バイトシーケンスや"フラットな"オブジェクトをハッシュするのに使う

といったところで、

POJOのような複雑なデータ構造を直接ハッシュに変換する
あらかじめ長さのわかっているデータでないとハッシュにできない（Iteratorなど）
戻ってくるのはlong値固定

あたりが注意点です。

内部的には、sun.misc.Unsafeがかなり使われています。
https://github.com/OpenHFT/Zero-Allocation-Hashing/blob/zero-allocation-hashing-0.8/src/main/java/net/openhft/hashing/UnsafeAccess.java

処理によっては、特化した実装が使われたりもしますが。
https://github.com/OpenHFT/Zero-Allocation-Hashing/blob/zero-allocation-hashing-0.8/src/main/java/net/openhft/hashing/ByteBufferAccess.java
https://github.com/OpenHFT/Zero-Allocation-Hashing/blob/zero-allocation-hashing-0.8/src/main/java/net/openhft/hashing/CharSequenceAccess.java

では、なにはともあれ、使っていってみましょう。

準備

Maven依存関係は、このように定義。

        <dependency>
            <groupId>net.openhft</groupId>
            <artifactId>zero-allocation-hashing</artifactId>
            <version>0.8</version>
        </dependency>

あとは、テスト用にJUnit 5とAssertJを使用します。

        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-api</artifactId>
            <version>5.0.1</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.assertj</groupId>
            <artifactId>assertj-core</artifactId>
            <version>3.8.0</version>
            <scope>test</scope>
        </dependency>

    <build>
        <plugins>
            <plugin>
                <artifactId>maven-surefire-plugin</artifactId>
                <version>2.19</version>
                <dependencies>
                    <dependency>
                        <groupId>org.junit.platform</groupId>
                        <artifactId>junit-platform-surefire-provider</artifactId>
                        <version>1.0.1</version>
                    </dependency>
                    <dependency>
                        <groupId>org.junit.jupiter</groupId>
                        <artifactId>junit-jupiter-engine</artifactId>
                        <version>5.0.1</version>
                    </dependency>
                </dependencies>
            </plugin>
        </plugins>
    </build>

はい。

では、QuickStartに沿って使っていってみます。

Zero-allocation Hashing / QuickStart

Javadocは、こちら。

Zero-allocation Hashing 0.8-SNAPSHOT API

テストコードの雛形は、このように。
※Guavaが入っているのは、あとで補足します。
src/test/java/org/littlewings/zeroallocationhasing/HashFunctionTest.java

package org.littlewings.zeroallocationhasing;

import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import javax.xml.bind.DatatypeConverter;

import com.google.common.hash.Hashing;
import net.openhft.hashing.LongHashFunction;
import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;

public class HashFunctionTest {
    // ここに、テストを書く！！
}

MurmurHash3

まずは、MurmurHash3から。

MurmurHash3 · aappleby/smhasher Wiki · GitHub

分散系のミドルウェアなどで、よく名前を見るハッシュ関数…。

サンプルコードは、こちら。

    @Test
    public void murmur3Hash() {
        LongHashFunction function = LongHashFunction.murmur_3();

        assertThat(function.hashBytes("Hello Hash Function!!".getBytes(StandardCharsets.UTF_8)))
                .isEqualTo(-7409062315873329197L);
        assertThat(DatatypeConverter.printHexBinary(ByteBuffer.allocate(Long.BYTES).putLong(-7409062315873329197L).array()))
                .isEqualTo("992DB9141FA31FD3");
    }

基本的な使い方として、LongHashFunctionから目的のハッシュアルゴリズムを取得するためのファクトリメソッドを呼び出すスタイルのようです。

        LongHashFunction function = LongHashFunction.murmur_3();

対応する、LongHashFunctionの実装のインスタンスが返ってきます。

あとは、LongHashFunction#hashXXXという各種シグニチャのメソッドを呼び出せばよいのですが

        assertThat(function.hashBytes("Hello Hash Function!!".getBytes(StandardCharsets.UTF_8)))
                .isEqualTo(-7409062315873329197L);

個人的には、LongHashFunction#hashBytesでよいかなと。

他には、

boolean
byte
bytes（Array）
char
chars（Array）
String／StringBuilder
int
ints（Array）
long
longs（Array）
short
shorts（Array）

といった型を入力に取ることができます。

ただ、戻り値はすべてlongになります。

byte配列にしたいなどあれば、自分で変換しましょう。

        assertThat(DatatypeConverter.printHexBinary(ByteBuffer.allocate(Long.BYTES).putLong(-7409062315873329197L).array()))
                .isEqualTo("992DB9141FA31FD3");

つまり、64bitのハッシュ関数となります。

これに対して、Google Guavaを使用した場合は、long以外にもbyte配列として結果を取得することができるので、128bitのMurmurHash3が使えることになります。

    @Test
    public void murmur3HashAsGuava() {
        assertThat(Hashing.murmur3_128().hashBytes("Hello Hash Function!!".getBytes(StandardCharsets.UTF_8)).asLong())
                .isEqualTo(-7409062315873329197L);
        assertThat(Hashing.murmur3_128().hashString("Hello Hash Function!!", StandardCharsets.UTF_8).asLong())
                .isEqualTo(-7409062315873329197L);

        assertThat(DatatypeConverter.printHexBinary(
                ByteBuffer.allocate(Long.BYTES).putLong(
                        Hashing.murmur3_128().hashBytes("Hello Hash Function!!".getBytes(StandardCharsets.UTF_8)).asLong()
                ).array())).isEqualTo("992DB9141FA31FD3");
        assertThat(DatatypeConverter.printHexBinary(
                Hashing.murmur3_128().hashBytes("Hello Hash Function!!".getBytes(StandardCharsets.UTF_8)).asBytes()
        )).isEqualTo("D31FA31F14B92D99293948B3A8F7C00B");
    }

HashingExplained · google/guava Wiki · GitHub

依存関係は、こちら。

        <dependency>
          <groupId>com.google.guava</groupId>
          <artifactId>guava</artifactId>
          <version>23.4-jre</version>
        </dependency>

ところで、Zero-allocation HashingでのLongHashFunctionのインスタンスの取得方法なのですが、次のように引数なしのものと

        LongHashFunction function = LongHashFunction.murmur_3();

シードを引数に取るものの2種類があります。シードは、longです。

        LongHashFunction function = LongHashFunction.murmur_3(seed);

シードを指定しない場合は、内部的にはシングルトンのインスタンスが使いまわされ、シードと指定した場合は（当たり前ですが）シードをもとにした
インスタンスが構築・返却されます。

FarmHash（na／uo）

次は、FarmHash。後述の、CityHashの後継です。

GitHub - google/farmhash: Automatically exported from code.google.com/p/farmhash

GoogleがFarmHashを公開，文字列ハッシュ関数のニューファミリー

FarmHash 1.0から使えるfarmhashnaと、FarmHash 1.1から使えるfarmhashuoをそれぞれ利用することができます。

使い方は、LongHashFunctionから使いたい方に合わせてfarmNaまたはfarmUoメソッドを呼び出し、LongHashFunctionのインスタンスを取得すればOKです。

    @Test
    public void farmHashNa() {
        LongHashFunction function = LongHashFunction.farmNa();

        assertThat(function.hashBytes("Hello Hash Function!!".getBytes(StandardCharsets.UTF_8)))
                .isEqualTo(750635406093098467L);
        assertThat(DatatypeConverter.printHexBinary(ByteBuffer.allocate(Long.BYTES).putLong(750635406093098467L).array()))
                .isEqualTo("0A6ACAECC0029DE3");
    }

    @Test
    public void farmHashUo() {
        LongHashFunction function = LongHashFunction.farmUo();

        assertThat(function.hashBytes("Hello Hash Function!!".getBytes(StandardCharsets.UTF_8)))
                .isEqualTo(750635406093098467L);
        assertThat(DatatypeConverter.printHexBinary(ByteBuffer.allocate(Long.BYTES).putLong(750635406093098467L).array()))
                .isEqualTo("0A6ACAECC0029DE3");
    }

使い方自体は、MurmurHash3の時と同じです。

CityHash

CityHash。

GitHub - google/cityhash: Automatically exported from code.google.com/p/cityhash

http://www.ctrlshift.net/blog/?id=20110415_city_hash

CityHashを使う場合は、LongHashFunction#city_1_1からLongHashFunctionのインスタンスを取得します。

    @Test
    public void cityHash() {
        LongHashFunction function = LongHashFunction.city_1_1();

        assertThat(function.hashBytes("Hello Hash Function!!".getBytes(StandardCharsets.UTF_8)))
                .isEqualTo(750635406093098467L);
        assertThat(DatatypeConverter.printHexBinary(ByteBuffer.allocate(Long.BYTES).putLong(750635406093098467L).array()))
                .isEqualTo("0A6ACAECC0029DE3");
    }

xxHash

最後は、xxHash。圧縮アルゴリズム、LZ4で使われているそうな。

GitHub - Cyan4973/xxHash: Extremely fast non-cryptographic hash algorithm

とても高速なハッシュ関数だそうです。

xxHashを使用する場合は、LongHashFunction#xxからLongHashFunctionのインスタンスを取得します。

    @Test
    public void xxHash() {
        LongHashFunction function = LongHashFunction.xx();

        assertThat(function.hashBytes("Hello Hash Function!!".getBytes(StandardCharsets.UTF_8)))
                .isEqualTo(571581975522999203L);
        assertThat(DatatypeConverter.printHexBinary(ByteBuffer.allocate(Long.BYTES).putLong(571581975522999203L).array()))
                .isEqualTo("07EEAAC743107BA3");
    }

使い方は、だいたい分かった感じですね。覚えておきましょう。

CLOVER🍀

That was when it all began.