問題タブ [universal-hashing]

衝突を軽減/回避するために再ハッシュを使用しHashtableていると言われています。.NET

すなわち。「再ハッシュは次のように機能します。ハッシュの異なる関数 H1 ... Hn のセットがあると仮定します。ハッシュ テーブルからアイテムを挿入または取得するとき、最初に H1 ハッシュ関数が使用されます。これが衝突につながる場合は、代わりに H2 が試行され、Hashtable での衝突を回避するために Hn まで試行されます。」</p>

仮定: 漸近的な時間の複雑さが o(1) である n (n < Infinity) 要素を持つハッシュテーブルがあります。私たち (CLR) は、いくつかのハッシュ関数 (n>1 の Hn-1 ハッシュ関数) を適用しながらこれを達成しました。

質問: (異なるハッシュ関数が使用されている場合) 任意の要素をシーク (取得) するときに、CLR が Key をハッシュ コードにマップする方法を誰か説明してもらえますか? CLR はどのようにライブ オブジェクト (ハッシュ テーブル) のハッシュ関数を (もしあれば) 追跡しますか?

前もって感謝します

こんにちは私はCLRSのユニバーサルハッシュに関する章を読んでいます。

234ページ

系11.4

ユニバーサルハッシュとmスロットのテーブルをチェーンすることによる衝突解決を使用すると、O（m）INSERT操作を含むn個のINSERT、SEARCH、およびDELETE操作のシーケンスを処理するのにTheta（n）に予想時間がかかります。

ちょっとわかりましたが、この英語の文章を理解するのに苦労しています。「O（m）INSERT操作を含む」という終わりはどういう意味ですか？

n = O（m）の挿入がすでに実行されているという意味ですか。じゃあ……わかりません。この文を解析できません。1番目のINSERTと2番目のINSERTの違いは何ですか？

ご意見をお聞かせください。

ありがとう！

私の現在の理解では、ユニバーサルハッシングは、あらゆる種類の入力に対して妥当なパフォーマンスを保証するために、実行時にハッシュ関数がランダムに選択される方法です。

誰かが悪意のある入力を意図的に選択することによる操作を防ぐためにこれを行う可能性があることを理解しています (決定論的ハッシュ関数の可能性はわかっています)。

私の質問は次のとおりです。キーをハッシュするたびに、キーが同じアドレスにマップされることを保証する必要があるというのは本当ですか? たとえば、情報を取得したいが、ハッシュ関数がランダムに選択されている場合、データを取得できることをどのように保証しますか?

特異値を a のキーとしてハッシュできることを知っていますdict。たとえば5、 のキーの 1 つとしてハッシュできますdict。

現在、値の範囲をハッシュする必要があるという問題に直面しています。

基本的に、これを行うにはより高速な方法が必要です。

ここで、xはfloat任意精度のパラメータです。

私が考えることができる最速の方法はハッシュですが、ここに問題があります:(0.1, 0.2)キーとして使用できますが、それでも O(n) ランタイムがかかり、最終的にはelifs のスルーよりも良くありません (私はキーを反復し、確認するかどうかを確認しますkey[0] <= x <= key[1])。

ハッシュテーブルをチェックして取得できるように、値の範囲をハッシュする方法はあり0.15ます#execute Bか?

そのようなハッシュが不可能な場合、これの実行時間を改善するにはどうすればよいでしょうか? 線形ランタイムが十分に速くないほど大きなデータセットを扱っています。

編集:チーケンの答えに応えて、間隔が規則的であると想定できないことに注意する必要があります。実際のところ、そうではないことはほぼ保証できます。

コメントでのリクエストに応えて、遺伝的アルゴリズムでフィットネスベースの選択を実装しようとしてこれを行っていることを言及する必要があります。アルゴリズム自体は宿題ですが、具体的な実装は実験データを生成するための実行時間を改善することだけです。

ブルームフィルターを使用して、セットの交差近似をシミュレートしています。値をフィルターにハッシュするために、多くの単純なハッシュ関数を試しました。しかし、衝突を避けるのは苦手です。そのため、誰かがユニバ​​ーサル ハッシュ関数を提案しました。しかし、それがどのように機能するかわかりません。私のプログラムはキーだけをハッシュ関数に渡すように設計されており、ハッシュ関数はハッシュを返します。誰でもコードを手伝ってもらえますか? ありがとう

2つの要素を挿入した後に衝突が発生しない確率を計算するにはどうすればよいですか。答えは4/9ですが、4/9の様子がわかりません

ユニバーサル ハッシュを実装し、次のユニバーサル ハッシュ関数を使用しています。

h(k)=((A*k)mod 2^64) rsh 64-r

ここで、A は次の間の乱数です。

2^61 と 2^62。

C++のrand()関数は戻り値の型が整数であり、その大きな数値を生成できません。では、この範囲で乱数を生成するにはどうすればよいですか? (数字は非常にランダムである必要があります。つまり、すべての数字が選択される確率が等しい必要があります)

ノート：

によって返される数値randはintであるため、機能しません。

ユニバーサルハッシュに関連するこのビデオレクチャーを読んでいました。IP アドレスのハッシュ化の例を示します。各 IP アドレスは、4 つの 32 ビット整数 (x1、x2、x3、x4) で構成され、xi の最大値は 255 です。

チュートリアルでは、ハッシュ テーブルのサイズは 255 または任意の xis よりも大きくする必要があると述べています。なぜそうなのですか？

私が知っていることは次のとおりです。

• コンシステント ハッシュ: 均一な分散ストレージ システム
• コーン ハッシング: 不均一な分散ストレージ システム

私は知りたいです：

• 使い方？
• それの用途は何ですか？
• この 2 種類のハッシュの違いは何ですか?

この2つの違いを理解できません。誰かこれで私を助けてください！