ハッシュ関数の設計と均一性（非暗号学的）

非暗号ハッシュは何のためにあるのか

ハッシュ関数と聞くとSHA-256のような暗号学的ハッシュを思い浮かべがちですが、ハッシュテーブルの添字計算、チェックサム、データ重複排除、ロードバランサのシャーディングなどで毎秒何億回も呼ばれるのは、もっと軽量な非暗号学的ハッシュです。これらに求められるのは「衝突を予測されない暗号的強度」ではなく、出力がよく散ることととにかく速いこと。設計の力点が暗号ハッシュとはまるで違います。

非暗号ハッシュの設計目標は次の三つに集約されます。(1) 分布の均一性 — 入力の偏りに関わらず出力値が出力空間に一様に散ること。(2) 雪崩効果（avalanche） — 入力の1ビットを変えると出力ビットの約半数が反転すること。(3) 速度 — 1バイトあたりのコストが小さく、現代CPUのパイプラインやSIMDに乗ること。この三つはしばしば緊張関係にあり、どこで折り合うかが各アルゴリズムの個性になります。

良いハッシュの内部部品 — 乗算・XOR・回転

非暗号ハッシュはたいてい少数の整数演算の組み合わせで撹拌（mixing）を行います。中核となる部品はおおむね三つです。乗算は1ビットの違いを上位ビットへ大きく波及させる主力で、奇数（特に大きな素数や慎重に選ばれた定数）を掛けると周期が長く全ビットへ影響が及びます。XORは値を混ぜ合わせて情報を打ち消さずに重ねます。ビット回転（rotate）やシフトは、乗算で上位に溜まった撹拌結果を下位へ戻し、ビット位置の偏りをならします。

剰余で添字に畳み込む際、mod m のmが2のべき乗だと下位ビットしか効きません。乗算結果は上位ビットほどよく混ざるため、h ^ (h >>> r) のように上位を下位へXORで折り返す**ファイナライズ（finalization）**処理が均一性の決め手になります。MurmurHash3の最終段にある以下のような撹拌は、まさにこの目的の典型です。

// MurmurHash3 の fmix32（ファイナライザ）
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;

FNV — 単純さの極北

**FNV（Fowler–Noll–Vo）**は最も単純な実用ハッシュの一つです。よく使われるFNV-1aは、初期値（オフセット基底）から始め、1バイトごとに「XORしてから素数を掛ける」だけを繰り返します。

uint64_t fnv1a(const uint8_t *data, size_t n) {
    uint64_t h = 0xcbf29ce484222325ULL;   // offset basis
    for (size_t i = 0; i < n; i++) {
        h ^= data[i];
        h *= 0x100000001b3ULL;             // FNV prime
    }
    return h;
}

実装が数行で済み分岐もないため短い文字列キーでは十分高速ですが、設計は古く弱点もあります。1バイトずつの逐次処理なので長いデータでは伸びが鈍く、雪崩効果も完全ではありません。とりわけ末尾バイトの影響が上位ビットへ十分波及しないため、低位ビットだけを添字に使う実装では分布が偏ることがあります。それでも、依存ライブラリ不要で誰でも書ける明快さから、いまも広く生き残っています。

MurmurHash と xxHash — ブロック処理で速度を稼ぐ

より大きなデータを高速に捌くために、現代の非暗号ハッシュは入力を4〜32バイトのブロック単位で処理します。MurmurHash3は各ブロックに対し「乗算 → 回転 → 乗算 → XORで蓄積」を施し、最後に前述のfmixでファイナライズします。バイト単位のFNVに比べ、ブロックごとにまとめて撹拌するため雪崩効果が強く、スループットも大きく上がります。

xxHash（特にXXH3）はこの方向をさらに推し進め、複数の独立した内部状態（アキュムレータ）を並行更新します。各アキュムレータが別のデータ部分を担当することでCPUの命令レベル並列性を引き出し、SIMD（AVX2/SSE2/NEON）で一度に複数レーンを処理できます。結果として、メモリ帯域に律速されるほどの数GB/sに達し、現在のデータ処理基盤で広く採用されています。

均一性の検証には、出力ビットの独立性を測るSMHasherのような検定スイートが使われます。雪崩バイアス（1入力ビットが各出力ビットを反転させる確率の0.5からのずれ）や分布の偏り、特定パターンでの衝突を網羅的に調べ、新しいハッシュ関数はこの試験を通って初めて実用に値すると見なされます。

ハッシュフラッディング攻撃とSipHash

ここまでの非暗号ハッシュには共通の急所があります。アルゴリズムが公開されていて鍵を持たないため、攻撃者が同じ添字に落ちるキー列を事前計算できる点です。Webサーバーがリクエストのパラメータ名をハッシュテーブルに入れる場面で、すべて同一バケットへ衝突するキーを大量に送りつけると、本来O(1)の挿入・検索が計算量O(n)へ劣化し、1リクエストでCPUを飽和させられます。これがハッシュフラッディング（HashDoS）攻撃で、2011年に多数のWebフレームワークが同時に影響を受けたことで広く知られるようになりました。

そこで設計されたのがSipHashです。SipHashは128ビットの秘密鍵を取り、ARX（加算・回転・XOR）演算を規定回数（SipHash-2-4なら圧縮2ラウンド・最終4ラウンド）繰り返す、軽量な擬似ランダム関数です。鍵を知らない攻撃者は、ある入力が生むハッシュ値を現実的な計算量で予測できないため、特定バケットへ衝突を集中させる攻撃が成立しません。速度はxxHash等に劣りますが、それでも暗号ハッシュよりは十分軽く、短い入力をハッシュテーブルの鍵にする用途に最適化されています。

まとめ

非暗号ハッシュの設計は、均一性・雪崩効果・速度という三目標のバランス取りです。乗算で違いを上位へ波及させ、回転とシフトで全ビットへならし、ファイナライズで折り返すという部品構成は共通で、違いは処理粒度に現れます。1バイト逐次のFNVは単純さで、ブロック処理のMurmurHashは強い撹拌で、SIMD並列のxxHashは最速クラスのスループットで、それぞれの居場所を持ちます。ただし、これらは鍵を持たないがゆえにハッシュフラッディングに弱く、外部入力をキーにする場面では鍵付きPRFであるSipHashが必要になります。「速さのためのハッシュ」と「予測されないためのハッシュ」を切り分けて選ぶことが、性能と安全の両立に効きます。なお出力をいったんキャッシュに載せて再利用するか、毎回計算するかも実測コストを左右する設計判断です。