JavaでMessageDigestにないハッシュ関数を使う

ユーザーの入力値から適当な文字列を生成する要件があった。

Javaで標準的に使えるハッシュ関数だとMD5SHA1,2,3あたりになるが、計算速度は早いほうがいいということで、高速なハッシュ関数が使えないか調べてみたのでメモ。

環境

OpenJDK 11 11.0.12.7

Javaで標準的に使えるハッシュ関数

MessageDigestJavadocにリンクのある、Javaセキュリティ標準アルゴリズム名#MessageDigestアルゴリズムに記載がある。

Java11の時点で、MD2, MD5, SHA-1, SHA-2, SHA-3が使える。

JVM実装に依存するため、実際に指定できるアルゴリズムを確認するには、 java.security.Security.getAlgorithms("MessageDigest") を使用すればいい。

System.out.println(new TreeSet(Security.getAlgorithms("MessageDigest")));

OpenJDK 11だと、[MD2, MD5, SHA, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256, SHA3-224, SHA3-256, SHA3-384, SHA3-512] となった。「Javaセキュリティ標準アルゴリズム名」のページ記載とは多少差異があるが、別名で設定されているのだろう。

標準外のハッシュ関数

これら以外に利用できるハッシュ関数がないか調べたところ、GuavaApache Commons Codecにいくつか実装を見つけた。

Guava

com.google.common.hash.Hashingにて、ハッシュ関数を返すstaticメソッドが用意されている。

MD5やSHA系の MessageDigest で使用可能なハッシュ関数以外に、以下のハッシュ関数がある。

  • CRC32 (32bit)
  • CRC32C (32bit)
  • FarmHash Fingerprint64 (64bit)
  • MurmurHash3 (32bit, 128bit)
    • Guava v31.0にて、BMP(基本多言語面)に含まれない文字が文字列に含まれている場合、生成されるハッシュ値が不正ということで、 Hashing#murmur3_x_fixed が追加された。
  • SipHash 2-4 (64bit)

速度優先のハッシュ関数を返す、 Hashing.html#goodFastHash メソッドなんてのもあった。

Commons Codec

org.apache.commons.codec.digestパッケージに、ハッシュや暗号化関連のクラスが用意されている。

ハッシュだと以下。

  • CRC32
  • CRC32C
  • MurmurHash2
  • MurmurHash3
  • xxHash32

Guavaと同様、 MessageDigest で利用可能なアルゴリズムを返す DigestUtils も用意されている。

その他

FNV実装もいくつか見つけたが、MurmurHashやSipHashがあれば不要と判断し、調査せず。

振り返り

思ったよりもたくさん見つかった。

実際のハッシュ生成には、内部的にしか使わず、衝突しても問題なしという要件だったため、GuavaのMurmurHash3 32bitを利用。

参考資料

プログラミング言語内でのハッシュ関数としては、SipHashが広く使われている。その経緯は以下に詳しい。

kazu-yamamoto.hatenablog.jp

PythonでFNVからSipHashに切り替える際のPEP 456に、それぞれの比較結果が載っている。

SipHashも、当初のSipHash24から、ラウンド数を減らしても安全ということで、SipHash13への置き換えが進んでいるとのこと。

methane.hatenablog.jp