5

長い数値 (64 ビット) を取り、10 ビットの結果を生成するハッシュ関数が必要です。そのような目的に最適なハッシュ関数は何ですか。入力は基本的に変数のアドレス (Linux ではアドレスは 64 ビットまたは 8 バイト) であるため、ハッシュ関数はその目的のために最適化する必要があります。

4

3 に答える 3

6

私はこのような何かを言うでしょう：

uint32_t hash(uint64_t x)
{
    x >>= 3;
    return (x ^ (x>>10) ^ (x>>20)) & 0x3FF;
}

ほとんどの変数は4バイトまたは8バイトで整列されているため、最下位の3ビットはあまり役に立ちません。そのため、それらを削除します。次に、次の30ビットを取得し、それぞれ10ビットのブロックに混合（XOR）します。

当然、あなたも取ることができますが(x>>30)^(x>>40)^(x>>50)、それらが実際に何か違いを生むかどうかはわかりません。

于 2012-07-06T09:34:30.070 に答える
2

スタック、データ領域、およびヒープ上の実際のアドレスを確認するおもちゃのプログラムを作成しました。基本的に、4 つのグローバル、4 つのローカルを宣言し、2 を実行しmallocsました。アドレスを印刷するときに、最後の 2 ビットを落としました。実行の 1 つからの出力を次に示します。

 20125e8
 20125e6
 20125e7
 20125e4
3fef2131
3fef2130
3fef212f
3fef212c
 25e4802
 25e4806

これが私に教えてくれること：

  1. この出力の LSB (アドレスの 3 番目のビット) は、頻繁に「オン」と「オフ」になります。したがって、ハッシュを計算するときにそれを削除しません。2 LSB をドロップするだけで十分なようです。
  2. また、下位 8 ～ 10 ビットのエントロピーが大きいこともわかります。ハッシュを計算するときにそれを使用する必要があります。
  3. 64 ビット マシンでは、仮想アドレスの幅が 48 ビットを超えることはありません。

私が次にすること：

/* Drop two LSBs.  */
a >>= 2;

/* Get rid of the MSBs. Keep 46 bits. */
a &= 0x3fffffffffff;

/* Get the 14 MSBs and fold them in to get a 32 bit integer.
The MSBs are mostly 0s anyway, so we don't lose much entropy.  */
msbs = (a >> 32) << 18;
a ^= msbs;

これで、独自の. 「半雪崩」とは、入力の各ビットが同じ位置以上のビットに影響を与える可能性があることを意味します。

uint32_t half_avalanche( uint32_t a)
{
    a = (a+0x479ab41d) + (a<<8);
    a = (a^0xe4aa10ce) ^ (a>>5);
    a = (a+0x9942f0a6) - (a<<14);
    a = (a^0x5aedd67d) ^ (a>>3);
    a = (a+0x17bea992) + (a<<7);
    return a;
}

10 ビット ハッシュの場合、uint32_t返された の上位 10 ビットを使用します。ビット ハッシュの MSB を選択すると、ハッシュ関数は正常に動作し続け、ビットが追加されるたびにバケット カウントが効果的に 2 倍になります。NN

少し退屈だったので、おもちゃのベンチマークを書きました。派手なことは何もありません。ヒープに大量のメモリを割り当て、上で説明したハッシュを試します。ソースはここから入手でき。結果の例:

1024 個のバケット、256 個の値が生成され、29個の衝突
1024 個のバケット、512 個の値が生成され、103個の衝突
1024 個のバケット、1024 個の値が生成され、370 個の衝突

次:ここで回答された他の 2 つのハッシュを試しました。どちらも似たような性能です。次のように見えます：最速のものを選んでください;）

于 2012-07-06T14:54:53.163 に答える
1

ほとんどのディストリビューションでは素数による mod が最適です。1021 は最大の 10 ビット素数です。下位ビットを削除する必要はありません。

static inline int hashaddress(void *v)
{
        return (uintptr_t)v % 1021;
}

パフォーマンスが懸念されると思われる場合は、いくつかの代替品を手元に用意して、実際のプログラムでそれらを競争させてください。マイクロベンチマークは無駄です。数サイクルの違いは、キャッシュ効果によって圧倒されることがほぼ確実であり、サイズが重要です。

于 2012-07-06T11:45:43.923 に答える