xxHash

このページの内容

xxHashは、RAMの速度限界に達するほど高速な非暗号学的ハッシュアルゴリズムです。

3つのファミリーに属する4種類を提供します：

XXH32ファミリー
- 従来型の32ビットハッシュ関数です。単純かつコンパクトで、ほぼすべての32ビット・64ビットシステムで動作します。
XXH64ファミリー
- XXH32を64ビット向けに適応した従来型です。同様に単純で、大部分の64ビットシステムでは良好に動作します（ただし、 32ビットシステムでは良好に動作しない点に注意してください）。
XXH3ファミリー
- 全般に、特に小さなデータで強度と性能を改善した、現代的な64ビット・128ビットハッシュ関数ファミリーです。SIMDや64ビットを必須とはしませんが、それらから大きな利点を得ます。

ベンチマーク

基準システムはIntel i7-9700K CPUを使用し、Ubuntu x64 20.04で動作します。オープンソースのベンチマークプログラムは、clang v10.0で-O3フラグを使ってコンパイルしています。

ハッシュ名	命令セット拡張	ビット幅	大きなデータの速度	小さなデータの効率指標
XXH3_64bits()	AVX2	64	59.4 GB/s	133.1
MeowHash	AES-NI	128	58.2 GB/s	52.5
XXH3_128bits()	AVX2	128	57.9 GB/s	118.1
CLHash	PCLMUL	64	37.1 GB/s	58.1
XXH3_64bits()	SSE2	64	31.5 GB/s	133.1
XXH3_128bits()	SSE2	128	29.6 GB/s	118.1
RAMの逐次読み込み		N/A	28.0 GB/s	N/A
ahash	AES-NI	64	22.5 GB/s	107.2
City64		64	22.0 GB/s	76.6
T1ha2		64	22.0 GB/s	99.0
City128		128	21.7 GB/s	57.7
FarmHash	AES-NI	64	21.3 GB/s	71.9
XXH64()		64	19.4 GB/s	71.0
SpookyHash		64	19.3 GB/s	53.2
Mum		64	18.0 GB/s	67.0
CRC32C	SSE4.2	32	13.0 GB/s	57.9
XXH32()		32	9.7 GB/s	71.9
City32		32	9.1 GB/s	66.0
Blake3*	AVX2	256	4.4 GB/s	8.1
Murmur3		32	3.9 GB/s	56.1
SipHash*		64	3.0 GB/s	43.2
Blake3*	SSE2	256	2.4 GB/s	8.1
HighwayHash		64	1.4 GB/s	6.0
FNV64		64	1.2 GB/s	62.7
Blake2*		256	1.1 GB/s	5.1
SHA1*		160	0.8 GB/s	5.6
MD5*		128	0.6 GB/s	7.8

注記

特定の命令セット拡張が必要なハッシュには、その拡張を記載しています。SSE2はx64では必須ですが、それも記載しています。
アスタリスク付きのハッシュは暗号学的ハッシュです。ただし、現代の基準ではMD5は非暗号学的であることに注意してください。
小さなデータの効率指標は、小さなデータに対するアルゴリズムの効率のおおよその平均です。より正確な情報はwikiを参照してください。
その他のベンチマークや強度試験はwikiにあります： https://github.com/Cyan4973/xxHash/wiki

使い方

xxHashの各種類は似たAPIを使います。アルゴリズムの変更は単純な置き換えで済みます。

事前条件

入力と長さをパラメーターとして受け取る関数は、次の条件を前提とします：

範囲[input, input + length)が、有効で読み取り可能なメモリーであること。
- 唯一の例外は、 length が 0の場合です。この場合、 input は NULLでも構いません。
C++のオブジェクトには、 TriviallyCopyable という性質が必要です。これらの関数は、次の型の配列であるかのようにバイトへ直接アクセスするためです： unsigned char。

ワンショット

これらは状態を持たない関数で、連続したメモリーブロックのハッシュを計算し、すぐに結果を返します。最も簡単で、通常は最も高速な選択肢です。

XXH32(), XXH64(), XXH3_64bits(), XXH3_128bits()

#include <string.h>
#include "xxhash.h"
 
// Example for a function which hashes a null terminated string with XXH32().
XXH32_hash_t hash_string(const char* string, XXH32_hash_t seed)
{
    // NULL pointers are only valid if the length is zero
    size_t length = (string == NULL) ? 0 : strlen(string);
    return XXH32(string, length, seed);
}

ストリーミング

これらの関数群は、サイズが不明な入力を段階的にハッシュ化できます。size_tに収まらない量の入力も扱えます。

XXH32_reset(), XXH64_reset(), XXH3_64bits_reset(), XXH3_128bits_reset()

#include <stdio.h>
#include <assert.h>
#include "xxhash.h"
// Example for a function which hashes a FILE incrementally with XXH3_64bits().
XXH64_hash_t hashFile(FILE* f)
{
    // Allocate a state struct. Do not just use malloc() or new.
    XXH3_state_t* state = XXH3_createState();
    assert(state != NULL && "Out of memory!");
    // Reset the state to start a new hashing session.
    XXH3_64bits_reset(state);
    char buffer[4096];
    size_t count;
    // Read the file in chunks
    while ((count = fread(buffer, 1, sizeof(buffer), f)) != 0) {
        // Run update() as many times as necessary to process the data
        XXH3_64bits_update(state, buffer, count);
    }
    // Retrieve the finalized hash. This will not change the state.
    XXH64_hash_t result = XXH3_64bits_digest(state);
    // Free the state. Do not use free().
    XXH3_freeState(state);
    return result;
}

ストリーミング関数は、段階的な入力からxxHash値を生成します。状態を管理するため、1回の呼び出しで処理する関数より低速です。小さな入力では、 XXH32() と XXH64()の方が適切に最適化されているため、優先してください。

最初にXXHの状態を割り当てるために、 XXH*_createState()を使う必要があります。

新しいハッシュを開始するには、seedを使って状態を初期化します。使用する関数： XXH*_reset()。

次に、ハッシュの状態へ入力を渡すために、 XXH*_update() を必要な回数だけ呼び出します。

この関数はエラーコードを返します。0は正常、それ以外の値はエラーがあることを意味します。

最後に、いつでもハッシュ値を生成できます。使用する関数： XXH*_digest()。この関数はnnビットのハッシュをintまたはlong longとして返します。

digestの後もハッシュの状態へ入力を追加し続け、後から新しいハッシュ値を生成できます。使用する関数： XXH*_digest()。

処理を終えたら、状態を解放します。使用する関数： XXH*_freeState()。

正規形式

XXH関数のデフォルトの戻り値は、符号なし32・64・128ビット整数です。これは、その後の処理に最も単純で高速な形式です。

ただし、リトルエンディアンとビッグエンディアンでは同じ数値を異なる形で格納するため、バイト単位の順序の問題が残ります。

正規形式は、ビッグエンディアンの規則を必須にして、この問題を解決します。これは、人が読む数値と同じ、上位桁を先に置く規則です。

ハッシュ値をストレージへ書き込む、ネットワークで送信する、または表示する場合は、現在と将来のより幅広いシステムでの移植性を確保するため、正規形式を使うことを強く推奨します。

次の関数で、ハッシュ値と正規形式を相互に変換できます。

XXH32_canonicalFromHash(), XXH32_hashFromCanonical(), XXH64_canonicalFromHash(), XXH64_hashFromCanonical(), XXH128_canonicalFromHash(), XXH128_hashFromCanonical(),

#include <stdio.h>
#include "xxhash.h"
 
// Example for a function which prints XXH32_hash_t in human readable format
void printXxh32(XXH32_hash_t hash)
{
    XXH32_canonical_t cano;
    XXH32_canonicalFromHash(&cano, hash);
    size_t i;
    for(i = 0; i < sizeof(cano.digest); ++i) {
        printf("%02x", cano.digest[i]);
    }
    printf("\n");
}
 
// Example for a function which converts XXH32_canonical_t to XXH32_hash_t
XXH32_hash_t convertCanonicalToXxh32(XXH32_canonical_t cano)
{
    XXH32_hash_t hash = XXH32_hashFromCanonical(&cano);
    return hash;
}

コードコメントの日本語訳

コードは原文を保持しています。コメントと診断文字列の意味は次のとおりです。

// Example for a function which hashes a null terminated string with XXH32().：XXH32()でNULL終端文字列のハッシュを計算する関数の例。
// NULL pointers are only valid if the length is zero：NULLポインターが有効なのは長さがゼロの場合だけです。
// Example for a function which hashes a FILE incrementally with XXH3_64bits().：XXH3_64bits()でFILEのハッシュを段階的に計算する関数の例。
// Allocate a state struct. Do not just use malloc() or new.：状態構造体を割り当てます。単にmalloc()やnewを使わないでください。
// Reset the state to start a new hashing session.：新しいハッシュ処理を開始するために状態をリセットします。
// Read the file in chunks：ファイルを小分けに読み込みます。
// Run update() as many times as necessary to process the data：データ処理に必要な回数だけupdate()を実行します。
// Retrieve the finalized hash. This will not change the state.：最終的なハッシュを取得します。状態は変わりません。
// Free the state. Do not use free().：状態を解放します。free()を使わないでください。
// Example for a function which prints XXH32_hash_t in human readable format：XXH32_hash_tを人が読める形式で表示する関数の例。
// Example for a function which converts XXH32_canonical_t to XXH32_hash_t：XXH32_canonical_tをXXH32_hash_tへ変換する関数の例。
Out of memory!：メモリー不足。