問題タブ [double-hashing]

vb.netでダブルハッシュハッシュテーブルを作成しようとしていますが、解決方法がわからないエラーがいくつか発生しています。うまくいけば、皆さんが私を助けてくれます。私が抱えている問題は、私が dbnull.value または mod= を持っているところならどこでもあります。エディターでエラーが発生し、それらを修正する方法がわかりません。このコードをvbに入れて、私が何を意味するかを確認してください。コードは次のとおりです。

クラス終了

ダブルハッシュによるオープンアドレス指定を使用して、C++ で HashTable を実装しています。

ダブルハッシュの背後にある基本原則は次のとおりであることを理解しています。

私はこの部分を正しく実装したと思います。これは宿題のためであり、特定のコードについてアドバイスを求めることはできないというのがクラスのポリシーであるため、その部分については私を信頼する必要があります。

私の問題を引き起こしているように見えるのは、2番目のハッシュ関数の対象となるときに、一部のキーが（素数の）テーブルサイズの倍数である値を返すことがあるということです。これらの場合、プローブ シーケンス内のすべてのインデックスは同じです。たとえば、次の場合です。

プロービング シーケンスは次のとおりです。

等々。

私は何が欠けていますか？

ダブルハッシュを使用して文字列キーをハッシュテーブルにハッシュしようとしています。私は次のようなことをしました：

主要部分は、後の最初の3行doです。ダブルハッシュを使用すると、衝突の可能性がなくなるはずだと言えますか？sizeハッシュテーブルの一意キーの可能な合計値です

これは質問です：

ダブル ハッシュによるオープン アドレスを使用し、主なハッシュ関数はhi(x) = (hash(x) + f(i)) mod M、 where hash(x) = x mod M、f(i) = i ∗ hash2(x)およびhash2(x) = 13 − (x mod 7)です。

キー 27、22、16、26、47、12、42、3 を (この順序で) 挿入する必要があります。セットのサイズは10個

26 の挿入は二重衝突であるため、混乱しています....その方法と何が起こっているのか、誰か説明できますか?

一連のキーとそのハッシュ値が与えられた場合、ダブル ハッシュ関数を決定するにはどうすればよいですか?

アップデート

おもうh(x) = k % 13 + 1

現在、アルゴリズムクラスの最終試験を検討していますが、模擬試験でよくわからない質問がいくつかありました。どんな助けでもいただければ幸いです！

ダブルハッシュを実装するためのプローブシーケンスについて正しくないのは次のうちどれですか？

A.2つのキーが同じプローブシーケンスを持つ可能性があります

B.ハッシュテーブルのすべてのスロットが各プローブシーケンスに表示されます

C.プローブシーケンスの要素は、ハッシュテーブルの可能なキーです。

D.キーのプローブシーケンスは変更できません

A、B、Dは正しいと思うので、Cが正解だと思います。

ダブルハッシュの最悪のケースは次のとおりです。

A.保存されているすべてのキーのh1は同じです。

B.保存されているすべてのキーのh2は同じです。

C.保存されているすべてのキーのh1とh2は同じです。

D.各キーを挿入するには、以前に挿入したすべてのキーのスロットをプローブする必要があります

この答えはCだと思います。これについては完全にはわかりませんので、説明があればいいでしょう。

Consider inserting the keys 10, 22, 31, 9 , 15, 28, 62, 88 in to a hash table of length m = 11 using open addressing with the hash function h(k) = k mod m. Illustrate the result of inserting these keys using double hashing with h2(k) = 1 + (k mod(m-1)).

Following is my approach.

Ok the problem comes when try to put the key 9 in to the hash table.

h(9) = 9 mod 11, which is 9. I can't put 9 since 9 already gone. Then I try for the double hash function given h2(9) = 1 + (9 mod (11-1)) , which is 10 and it's gone again. So still I can't put 9 in to the hash table. What should I do in such scenarios.

素数に基づくオープン アドレス ハッシュで、ハッシュ テーブル内のすべてのエントリをダブル ハッシュで埋めることができますか?

配列として実装されたサイズ 11 のハッシュ テーブルがあります。ダブル ハッシュ手法を使用しようとしています。私はすでに私の数のほとんどをやった。私のハッシュ関数は次のとおりです。

これによりh(k,i) = k mod 11 + i(k * 3 mod 4)、i = 0、1、2、3、...

すでにスロット 0、1、4、8、9、および 10 が埋められています。19 を挿入しようとしています。これは、19 をハッシュした結果です。

私は何をすべきか？

また、「テーブルに 11 個のスロットを持たせてください」と言うとき、それはハッシュ テーブルに 0 から 10 までの使用可能なスロットがあるということですか?

チェーンとダブルプローブを比較しようとしています。40 個の整数をテーブル サイズ 100 に挿入する必要があります。ナノタイム (Java で) を使用して時間を測定すると、Double の方が高速であることがわかります。それは Chaining の Insert 方式で、毎回 LinkedListEntry を作成し、それが add 時間だからです。Chaining が Double probing よりも速いのはどうしてでしょうか? （それは私がウィキペディアで読んだものです）

ありがとう！！

これは連鎖のコードです：

これは、二重プローブからの関連コードです。

このように、Double での挿入は連鎖よりも高速です。どうすれば修正できますか？