整数ハッシュキーを受け入れるのに適した整数ハッシュ関数は何ですか? 質問する

Question

次のアルゴリズムは非常に優れた統計的分布を提供することがわかりました。各入力ビットは、約 50% の確率で各出力ビットに影響します。衝突はありません (各入力は異なる出力になります)。CPU に整数乗算ユニットが組み込まれていない場合を除いて、アルゴリズムは高速です。C コードはint32 ビットであると想定しています (Java の場合は>>をに置き換え>>>、を削除しますunsigned)。

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

マジックナンバーは、特別なマルチスレッドテストプログラム数時間にわたって実行されたこのアルゴリズムは、アバランシェ効果（1つの入力ビットが変更された場合に変化する出力ビットの数。平均で約16）、出力ビット変更の独立性（出力ビットは互いに依存しない）、および入力ビットが変更された場合の各出力ビットの変化の確率を計算します。計算された値は、マーマーハッシュ、そして、使用した場合とほぼ同じくらい（完全にではないが）良いですエーエスわずかな利点は、同じ定数が 2 回使用されることです (前回のテストではわずかに高速化されましたが、まだそうであるかどうかはわかりません)。

を0x45d9f3b（0x119de1f3逆数):

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

64ビットの数値の場合、最速ではないかもしれませんが、次のものを使用することをお勧めします。これは、スプリットミックス64これはブログ記事に基づいているようですより良いビットミキシング（ミックス13）。

uint64_t hash(uint64_t x) {
    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
}

この場合、逆転はより複雑になります。

uint64_t unhash(uint64_t x) {
    x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
    x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
    x = x ^ (x >> 30) ^ (x >> 60);
    return x;
}

上記はすべて C 用です。Java の場合は、を使用しlong、をL定数に追加し、>>に置き換えて>>>、を削除しますunsigned。

更新：次の記事もご覧くださいハッシュ関数プロスペクタープロジェクトでは、他の (おそらくより優れた) 定数がリストされています。わずかに優れた 32 ビットハッシュ関数がありますx ^= x >> 16; x *= 0x7feb352d; x ^= x >> 15; x *= 0x846ca68b; x ^= x >> 16; return x;が、2 つの定数を使用します。

Answer 1