3

できれば手っ取り早い方法。ケースはN = 2^bとても簡単です。そのために、最初に、選択したタイプのビット数を把握します。

typedef unsigned int type;
size_t size = sizeof(type) * 8;

次に、適切なビット数だけ右シフトを実行して、上位bビットのハッシュキーを生成します。

type input = 0x657;
unsigned char b = 4;
unsigned char hash = input >> (size - b);

しかし、私が欲しかったらどうしN = 3ますか？または他の2の累乗ではありませんか？N私が常に（最大で256になる）の中に収まると仮定すると、いくつかunsigned charをハッシュする最も速い方法は何でしょうかinput？input上記の関数のように、バケットの範囲の差を+/- 1以下に保ち、の上位ビットの順序も維持します。

4

1 に答える 1

3

32 ビット値の場合は、64 ビットの乗算をN行い、上位 32 ビットを保持します。(他のサイズについても同様ですが、64 ビット値の場合、乗算はより複雑になります。)

これが基本的な証明の概要です。

このマッピングが順序を保持していることは明らかです。唯一の問題は、各バケットにいくつの値が入るかです。ここで、いくつかのバケットを検討し、そのバケットにマップされるj最小のものを見つけます。バケツに入るということは、どこにあることを意味しますが、 がそのiような最小の値である場合、. (そうしないと、bucket にも分類されます。)ijNi − j×232 = m0 ≤ m < 232i0 ≤ m < Ni−1j

では、 を定義します。これは、 と言うのと同じです。これら 2 つの式を足し合わせると、次のことがわかります。単純化すると、 と が得られます。つまり、またはが (が負かどうかに応じて) にマップされる最小値であることを意味します。つまり、またはにマップされる値が存在することを意味します。これはどの にも当てはまるため、バケット サイズは 2 つしかなく、そのうちの 1 つが であると断言できます。他の可能なバケット サイズは.w = ⌊232∕N⌋Nw − 232 = −m' where 0 ≤ m' < NNi + Nw - j×232 - 232 = m−m'N(i+w)-(j+1)×232 = m−m'−N < m−m' < Ni + wi + w + 1j + 1m − m'ww + 1jj⌊232∕N⌋⌈232∕N⌉

上記の証明には何も魔法はありません。任意の値を使用できました。しかし、それでは凝縮された証明がさらに読みにくくなってしまうでしょう。232M

于 2012-12-18T18:08:52.547 に答える