2

目的: 2 つの整数キー (unsigned int キャストを使用して整数に変換されたポインター、はい、これは機能します) を取り、それを単一の値にマップするハッシュ マップを作成します。

試みられた解決策：だから私はすでに単一のキーを取り、それを値にうまくマップするハッシュマップを持っています。「ペアリング機能」を使用して2つのキーを取るように拡張しました。そこで、2 つのキーを取得し、Cantor ペアリング関数を使用してそれらをペアにし、この結合されたキーをハッシュします。

ボトルネック:したがって、2 つのキーの問題は、cantor ペアリング関数が整数オーバーフローを引き起こす乗算を実行するため、数学的に想定されているように、一意の出力が得られないことです。

質問:

  1. 多くのハッシュ関数が乗算を行うことがわかります。整数オーバーフローはハッシュの通常のことですか、それともこれは悪いことですか?
  2. また、あるキーを別のキーに追加して、新しい 64 ビット整数にすることも考えています。aaaaaaaabbbbbbbbb のようにして、それをハッシュ マップに渡します。しかし、これにより、浮動小数点表現が原因で NaN などの異常な数値が発生する可能性があり、これが悪い可能性があるのではないかと心配しています。
  3. より良いアイデアは大歓迎です。

不明な部分があれば教えてください。

4

2 に答える 2

3

boost::hash_combineをご覧になることをお勧めします

于 2012-11-05T07:05:23.957 に答える
1

  1. 整数オーバーフローはそれほど悪くありません。確かに衝突が発生する可能性がありますが、ハッシュマップ用のハッシュでまれに衝突が発生しても問題ありません。

  2. おそらく悪い考えです。衝突が多すぎる可能性があります。

  3. 入力がNビット幅の場合、出力は少なくとも2Nビット幅でなければなりません。したがって、入力に対応するには、サイズuintの出力が必要です。ulong入力がそれよりも高い場合、オーバーフローが発生します。出力がそれより小さい場合、衝突/重複が発生します。

2Nしかし、実際にはサイズに収まる機能は多くありません。あなたは試すことができます

a * uint.MaxValue + b

またはこれ

a >= b ? a * a + a + b : a + b * b

どちらも unsigned long になります。これらの 2 つは、取得できるスペース効率が最も高くなります。

さらに、一意かつ決定論的な方法で、2 つの整数を 1 つにマッピングするを参照してください。

于 2012-12-27T09:22:16.930 に答える