次のアルゴリズムが非常に優れた統計分布を提供することがわかりました。各入力ビットは、約 50% の確率で各出力ビットに影響します。衝突はありません (各入力は異なる出力になります)。 CPU に整数乗算ユニットが組み込まれていない場合を除いて、アルゴリズムは高速です。 int を想定した C コード 32 ビットです (Java の場合、>> を置き換えます) >>> で unsigned を削除します ):
unsigned int hash(unsigned int x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
return x;
}
マジック ナンバーは、雪崩効果 (単一の入力ビットが変更された場合に変更される出力ビットの数。平均でほぼ 16 になるはずです) を計算する、何時間にもわたって実行される特別なマルチスレッド テスト プログラムを使用して計算されました。出力ビットの変化 (出力ビットは互いに依存してはならない)、および入力ビットが変更された場合の各出力ビットの変化の確率。計算された値は、MurmurHash で使用される 32 ビットのファイナライザーよりも優れており、AES を使用した場合とほぼ同じ (完全ではない) です。わずかな利点は、同じ定数が 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 ビットの数値の場合は、最速ではないかもしれませんが、以下を使用することをお勧めします。これは、ブログ記事 Better Bit Mixing (mix 13) に基づいていると思われる splitmix64 に基づいています。
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;
}
Java の場合、long を使用します 、 L を追加 >> を定数に置き換えます。 >>> で unsigned を削除します .この場合、反転はより複雑になります:
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;
}
更新:Hash Function Prospector プロジェクトを参照することもできます。ここには、他の (おそらくより良い) 定数がリストされています。
クヌースの乗法:
hash(i)=i*2654435761 mod 2^32
一般に、ハッシュ サイズ (2^32) のオーダーの乗数を選択する必要があります。 例では）、それとの共通因数はありません。このようにして、ハッシュ関数はすべてのハッシュ スペースを均一にカバーします。
編集:このハッシュ関数の最大の欠点は、割り切れる可能性を保持することです。そのため、整数がすべて 2 または 4 で割り切れる場合 (これは珍しいことではありません)、それらのハッシュも割り切れます。これはハッシュ テーブルの問題です。最終的に、使用されるバケットの 1/2 または 1/4 だけになる可能性があります。
データの配布方法によって異なります。単純なカウンターの場合、最も単純な関数
f(i) = i
(私は最適だと思うが、それを証明することはできない).