3

それぞれサイズ N1 と N2 の 2 つの 32 ビット符号なし整数の並べ替えられていない配列があります。各配列には重複が含まれる場合があります。各キーの頻度を記録するために、各値 (2^32 の可能なキー) をサイズ (N1 + N2) のバイト配列内のスポットにマップしたいと思います。重複するキー値は、この配列内の同じ位置にマップする必要があります。さらに、各整数の頻度が 100 を超えることはありません (これが、スペースを節約するために各キーの頻度を記録するためにバイト配列を選択した理由です)。最大可能周波数がこれを超える場合は、単純にバイト配列を short の配列などに変更します。

最後に、サイズ N1 + N2 の配列が必要です。重複が発生する可能性があるため、必ずしもすべてのエントリが使用されるとは限りません。各一意のキー値の頻度があります。最悪の場合、1 バイトのエントリのみが使用され (たとえば、両方の配列のすべての値が同じ)、((N1 + N2) - 1) 個のエントリが未使用のままになります。最良のシナリオでは、すべてのバイト エントリが使用されます。

私が理解していることから、既知の数の未知のキー (N1 + N2; すべて 0 - 2^32 の範囲) を既知の数のスポット (N1 + N2)にマップするための最小限の完全なハッシュ関数を見つける必要があります。他にもいくつかの投稿を見つけることができましたが、どちらの回答も基本的に gperf を使用すると述べています。

この状況で最小限の完全なハッシュ関数を作成することは可能ですか?

最小限の完全ハッシュ関数

2 つ目 (最小完全ハッシュ関数) は、まさに私がやろうとしていることです。

回答からソースコードを期待するのではなく (ちなみに私は C を使用しています)、 N 個のバケットに対して N 個の可能な正の整数に対して最小限に完全なハッシュ関数を作成する方法について説明したいと思います。未使用のスペースがたくさんある可能性のあるすべての整数の直接マッピングの 4 GB 配列でこれを簡単に行うことができますが、この大量の非効率なスペースを減らしたいと思います。また、主に教育目的でハッシュ自体についてさらに学ぶために、外部ライブラリを使用しないことも望んでいます。

4

2 に答える 2

1

これは明らかに不可能です。N 個の数値がある場合、これらの数値がどのようなものになるかを事前に知っていない限り、それらすべてを範囲 [0, N) の個別の値にハッシュする関数を思い付く方法はありません。それ以外の場合、そのような関数が与えられた場合 (もちろんN < 2^32 で)、それらの整数の両方が同じ値にハッシュされるような整数のペアが少なくとも 1 つあります。どちらも入力に表示されます。

関数をその場で作成できるように条件を緩和すると、これが可能になりますが、それは本当に些細で役に立たない方法でしかありません。つまり、ハッシュ関数は、入力された各数値を記録し、それぞれに対して新しい一意の出力を生成する (たとえば、0 からカウントアップする) ことによって、それ自体を構築できます。しかし、そのような関数は実装の一部としてハッシュ テーブル (または同等のもの) を必要とするため、ハッシュ テーブルの実装にはまったく役に立ちません。

于 2013-11-07T00:42:48.417 に答える
0

Pigeonhole Principleによると、「ハッシュ スロット」が複数の数字で占有されます。つまり、異なる数値が同じ値に「ハッシュ」されます。

さて、 Bloom Filterの恩恵を受けることができるでしょうか。ウィキペディアから:

偽陽性の一致は可能ですが、偽陰性はそうではありません。つまり、クエリは「おそらくセット内」または「間違いなくセット内にない」のいずれかを返します。

何かがキーのセットに「確実に」ない場合は、次に進むことができ (その頻度は 1)、セットにある可能性がある場合は、それをさらに処理して実際の統計を蓄積します。

于 2013-11-07T00:52:39.970 に答える