1

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

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

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

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

4

1 に答える 1

1

任意の関数で使用するために、テーブル内の要素の数を既に追跡しているはずなsize()ので、要素の数とバケットの数を比較して、テーブルがいっぱいかどうかを確認できます。サイズを追跡していない場合は、挿入操作と削除操作でカウンターをインクリメントおよびデクリメントすることから始めてください。

サイズを追跡することは、size()呼び出しの O(n) コストを回避するために、ほとんどすべてのハッシュ テーブルの実装で行うことです。

上記は、標準のハッシュテーブルに従ってバケットごとに複数の要素を許可していないことを前提としています（説明によるとそうです）。

于 2013-07-24T23:33:19.753 に答える