xxHash
xxHashは、Yann Colletが設計した極めて高速な非暗号学的ハッシュで、現代のCPUでメモリ帯域の限界に迫り、LZ4/Zstd圧縮と組み合わせて使われる。
目的
RAM帯域級の超高速な非暗号学的ハッシュを提供し、高性能チェックサムとシャーディングに使う。
メカニズム
XXH32/XXH64は4つのアキュムレータを維持し、16バイトごとに1ラウンド処理する。acc = acc ⊕ (input × prime)、acc = rotl(acc, 13) × prime。アキュムレータは最後にマージされアバランチされる。XXH3はAESハードウェアアクセラレーションでさらに高速である。
ユースケース
- Zstd/LZ4の圧縮検証
- RustのxxHashクレート
- 高頻度のハッシュテーブル
- ゲームエンジンの内部
例
- 入力
helloOutput0x391c7cb6XXH32
よくあるエラー
- Using xxHash for cryptographic authentication
- xxHash is not cryptographic; use HMAC
関連用語
MurmurHash
MurmurHashはAustin Applebyが設計した非暗号学的ハッシュで、乗算と回転（rotate）操作により優れた分布と高速性を実現する。 用語集
FNV
FNV（Fowler-Noll-Vo）は XOR と素数乗算で高速に計算される単純な非暗号ハッシュであり、ハッシュテーブルやフィンガープリントに使われる。 用語集
CRC32
CRC32 は GF(2) 上の多項式除算に基づく 32 ビットの巡回冗長検査であり、伝送エラーの検出に使われる。暗号学的ハッシュではない。 用語集
BLAKE3
BLAKE3 は BLAKE2 を二分ツリー並列化でさらに最適化したハッシュ関数であり、BLAKE2 よりはるかに高速で、XOF と MAC モードもサポートする。 用語集