問題タブ [double-hashing]

ダブル ハッシュの例をたくさん見つけましたが、すべての例で、2 回目のハッシュを行うときに %5 を使用する必要があることがわかりました。

私の質問は、なぜ 5 なのですか? 常に 5 を使用するという契約ですか、それともどのように機能しますか?

一例: https://www.cs.washington.edu/education/courses/326/00wi/handouts/lecture16/sld025.htm

こんにちは、初めてここにいますが、最初に二重ハッシュの理解が正しいかどうかを尋ねることから始めたいと思います。

ダブルハッシュは、最初にハッシュ関数を実装し、次にそのスポットが開いているかどうかを確認することで機能します。現在のスポットが開いていない場合は、2 番目のハッシュ関数を使用して別のスポットを決定し、それを現在の試行で乗算してから、最初のハッシュ アルゴリズムによって決定されたインデックス スポットに追加します。

私が持っている現在のコードは次のとおりです。

2 番目のハッシュ関数が含まれていないことに気付きました

そのようには見えないかもしれませんが、実際には tsize は正しく呼び出されています。

ダブルハッシュを使用する Hashtable を実装しています。ただし、insert(element) メソッドに問題があります。現在、基本的に次のことを行っています。

1. 配列内の計算された位置が空かどうかを確認します。もしそうなら、要素を挿入して終了です
2. 位置が別の要素によってブロックされている場合、新しいハッシュ値を計算し、1 からやり直します (再帰)。

問題は、このアルゴリズムではハッシュテーブルがいっぱいになったことを検出できないことです。訪問した位置の数を追跡し、その数を配列のサイズと比較して、この問題を修正することができました。

ただし、これを行うためのより適切な方法はありますか。同様に、二重ハッシュの深さから、配列が(数学的に)いっぱいでなければならないと推測することは可能ですか?

私は大学でのプロジェクトで問題を抱えていました。ダブル ハッシュされた文字列オブジェクトを返すクラスにダブル ハッシュ メソッドを記述する必要があります。JavaにはhashCode()メソッドが組み込まれているという事実を考えると、これは比較的簡単だと思いましたが、hashCodeを2回繰り返してもまったく同じ値が返されるようです。例えば：

StringHashCode.java:

スペル.java

出力からの抜粋:

dict は単語のリストを含むファイルで、クラスは講師が作成したクラスで、次の文字列を返し、別の単語があるかどうかをチェックします。

二重ハッシュで一次ハッシュ関数と競合する場合は、二次ハッシュ関数を使用します。ただし、それにも衝突がある場合は、再ハッシュする必要があるため、テーブル サイズを 2 倍にして、最も近い素数を新しいテーブル サイズとして選択します。これにより、プライマリ ハッシュ関数も変更されますか? たとえば、プライマリ ハッシュ関数が key mod tableSize で、tableSize が最初は 11 でしたが、現在は 23 になっている場合、それも変更されますか? ハッシュ関数が同じままであれば、同じ場所で衝突が発生するためです。

私は現在ハッシュテーブルに取り組んでおり、二重ハッシュについて少し混乱しています。まず、私が与えられた情報から始めましょう。

最初にすべてのデータを保持する配列を作成し、キーでソートします。式 K % size を使用して、キーが配置される配列内の位置を見つけました。すでにキーがある場所にキーを送信すると、衝突と呼ばれます。ここで double の出番です。式 max(1,(K/size) % size) を使用して、その位置から減少する数値を取得します。

だから私はこれらの機能を思いついた：

そこで、2 つの式を使用してキーを移動します。キーが既に配置されている別の場所にデクリメントして着地するとどうなるか、今、私は混乱しています。場所が見つかるまで、またそれだけ減らさなければならないのでしょうか?

ダブルハッシュで本当に苦労しています。このコードを二重ハッシュに完成させるための助けは素晴らしいでしょう。

ハッシュを二重にしようとしていますが、その方法について混乱しています。私は正しい軌道に乗っていると思いますが、これNullPointerExceptionはtable[index].value=value;.

どんな助けでも素晴らしいでしょう。