非暗号学的ハッシュ関数まとめ

この記事について

連想配列の実装などで利用される非暗号学的ハッシュ関数をまとめます。

非暗号学的ハッシュ関数は「分布の均一性」と「計算効率」を重視しており、衝突や逆算の困難性は求められません。そのためセキュリティ用途には不向きですが、プログラミング言語の内部などで利用されます。

代表的なハッシュ関数

黄金比ハッシュ

背景
Donald E. Knuth が「The Art of Computer Programming」で提唱。ビットパターンをうまく分散させる乗算ハッシュとして、初期のハッシュテーブル設計で利用されていました。

用途

• 固定幅整数のハッシュ化

実装

uint32_t knuth_hash(uint32_t x) {
    return x * 2654435761u;  // 32bitの場合の定数
}

平均性能

実装	Throughput
Knuth (x * 2654435761)	≈ 430 Mops/s

※opsはoperetion per seconds

FNV-1a

背景
1990年年代にFowler・Noll・Vo により小型・高速なネットワークハッシュとして提唱。乗算とXORのみで十分な分散を得ることができます。

用途

• ファイルハッシュ（チェックサム代替）
• 軽量ハッシュテーブル

実装

uint32_t fnv1a(const char *key) {
    uint32_t hash = 2166136261u;
    while (*key)
        hash = (hash ^ *key++) * 16777619u;
    return hash;
}

平均性能（バイト列）

入力サイズ	Throughput (MiB/s)
64B	1100
1KiB	970
16KiB	850
64KiB	800

Jenkins One-at-a-Time Hash

背景
1997年にBob Jenkins により提唱されたハッシュ関数。シンプルな構造で十分な雪崩効果（アバランシェ効果）を得ることができるように設計されています。

用途

• 文字列キー用ハッシュテーブル（組込み系）
• ハッシュ衝突を避ける用途
• 古典的、教育用途

実装

uint32_t jenkins(const char *key) {
    uint32_t hash = 0;
    while (*key) {
        hash += *key++;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

平均性能

サイズ	Throughput (MiB/s)
64B	1000
1KiB	870
64KiB	780

DJB2

背景
1990年代にDaniel J. Bernstein が提案。単純な式で文字列の分散性を確保できるように設計されています。DJB2 はシンプルながら衝突も多く、近年の実装では教育・参考用途が主です。'Aa' と 'BB' などの衝突例が知られています。

用途

• ハッシュテーブル（初期のUNIXツールなど）
• 古典的、教育用途

実装

unsigned long djb2(const char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++))
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    return hash;
}

性能

サイズ	Throughput (MiB/s)
64B	1050
1KiB	950
64KiB	820

Wang Integer Hash

背景
Thomas Wang により、整数を均等に分散させる目的で開発されたハッシュ関数。ビットの偏りを消すための XOR・加算・乗算の組み合わせで設計されています。

用途

• ビットボードや整数ベースのキャッシュキー
• 擬似乱数生成の初期化

実装

uint32_t wang_hash(uint32_t key) {
    key = ~key + (key << 15);
    key = key ^ (key >> 12);
    key = key + (key << 2);
    key = key ^ (key >> 4);
    key = key * 0x27d4eb2d;
    key = key ^ (key >> 16);
    return key;
}

平均性能

実装	Throughput
Wang Integer Hash	≈ 380 Mops/s

MurmurHash3 Finalizer

背景
Austin Appleby により2011年に開発されたハッシュ関数。高速・良分布・非暗号用途に十分な雪崩効果を得られるように設計されています。

用途

• Redis / Cassandra などで採用
• Bloom Filter / MapReduce 等の分散処理

実装（finalizer部のみ）

uint32_t murmur_mix(uint32_t h) {
    h ^= h >> 16;
    h *= 0x7feb352d;
    h ^= h >> 15;
    h *= 0x846ca68b;
    h ^= h >> 16;
    return h;
}

平均性能

サイズ	Throughput (MiB/s)
64B	980
1KiB	910
64KiB	860

BuzHash（回転XOR）

背景
1990年代にローリングハッシュの高速化を目的に開発されたハッシュ関数。

用途

• ストリーム中の重複検出
• Rabin fingerprint のローリング版

実装

static const uint32_t table[256] = { /* 固定ランダム値 */ };
uint32_t buzhash(const char *data, size_t len) {
    uint32_t hash = 0;
    for (size_t i = 0; i < len; i++)
        hash = ((hash << 1) | (hash >> 31)) ^ table[(uint8_t)data[i]];
    return hash;
}

平均性能

サイズ	Throughput (MiB/s)
64B	900
1KiB	850
64KiB	780

xxHash / CityHash / MetroHash

背景

• xxHash: Cyan4973 により設計、圧縮処理での超高速ハッシュとして誕生
• CityHash: Google が Web 検索用キャッシュで開発
• MetroHash/FarmHash: SIMD・マルチスレッド環境向け最適化

用途

• 高速ファイル検査、キャッシュキー、データ指紋

性能（参考）

• xxHash: 約 6〜8 GiB/s (SIMD最適化で8 GiB/s超)
• CityHash: 約 5 GiB/s
• MurmurHashよりも 3〜5倍高速

SpookyHash

背景
Bob Jenkins による 128bit 非暗号ハッシュ関数。2012年に V2 が公開。64bit環境で極めて高速かつ高品質なアバランシェ性を持ち、Jenkins の lookup3 の後継として設計されました。128bit 出力が標準で、64/32bit も下位ビット切り出しで利用可能です。

用途

• 分散処理やログフットプリント
• BloomFilter

SipHash（セキュア軽量ハッシュ）

背景
Jean-Philippe Aumasson と Daniel J. Bernstein によって 2012 年に提案。Hash DoS（攻撃者が衝突キーを大量送信してハッシュテーブルを破壊する攻撃）対策として誕生。キー（秘密値）を用いた MAC（Message Authentication Code）方式で、攻撃者に予測されないハッシュ処理を実行できます。

用途

• Python, Ruby, Rust の標準ハッシュ関数
• ネットワークプロトコルや短いメッセージの認証

実装抜粋（2round部分）

def siphash24(v0, v1, v2, v3, m):
    v3 ^= m
    for _ in range(2):
        v0 += v1; v1 = (v1 << 13) | (v1 >> 19); v1 ^= v0
        v2 += v3; v3 = (v3 << 16) | (v3 >> 16); v3 ^= v2
        v0 += v3; v3 = (v3 << 21) | (v3 >> 11); v3 ^= v0
        v2 += v1; v1 = (v1 << 17) | (v1 >> 15); v1 ^= v2
    v0 ^= m

特徴

• 4×64bit状態でラウンド処理
• 加算＋XOR＋ローテートでAvalanche効果
• 衝突攻撃に強い（DoS耐性）

性能（参考）
Python版：約 150 MiB/s
C版： 1 GiB/s

性能まとめ

Byte-wise 系

Hash	64B	1KiB	64KiB	特徴
FNV-1a	1100	970	800	軽量・単純
DJB2	1050	950	820	教育用
Jenkins OAAT	1000	870	780	分布良好
BuzHash	900	850	780	ローリング向け
Murmur3 mix	980	910	860	実用定番
SHA-256	340	330	320	暗号用途（参考)

Integer 系

Hash	Throughput (Mops/s)	特徴
Knuth (×2654435761)	430	テーブルインデックス
Wang Integer	380	均等分布・整数キー
Murmur3 Finalizer	350	分散処理・BloomFilter

参考

• MurmurHash3 (Austin Appleby)
• FNV Spec
• SipHash Paper
• xxHash Official Site
• Google FarmHash
• Bob Jenkins hashes