1

ハッシュテーブルに挿入するのに本当に助けが必要です。私は今それを完全に理解しているわけではありません。誰かが二次および線形プロービングを素人の言葉で説明できますか？

public void insert(String key)
{
    int homeLocation = 0;
    int location = 0;
    int count = 0;

    if (find(key).getLocation() == -1)  // make sure key is not already in the table
    {
       //****** ADD YOUR CODE HERE FOR QUADRATIC PROBING  ********
    }
}

これは私が取り組んでいるコードです。私は誰かにそれをするように頼んでいません、私は本当に全体の概念を学ぶのを手伝う必要があります

どんな助けでも大歓迎です。

4

1 に答える 1

3

まず、オープン アドレッシング(またはクローズド ハッシング) アプローチについて説明します。前のハッシュコードが別のハッシュコードによって既に使用されている場合は、新しいハッシュコードを計算する衝突を処理する必要があります。これは、ハッシュマップのすべてのバケットに最大 1 つの要素を含めることができるためです。

したがって、2 つのパラメーターを持つハッシュ関数があります。

  • v、ハッシュコードの計算に使用されるオブジェクトの値。
  • t、それはstepsizeと呼ばれるi*f場所で、衝突が発生した場合にハッシュ関数に毎回追加するものであり、これまでに到達した衝突の数です。if

これから開始すると、2 つの可能な機能があります。

H(v, t) = (H(v) + t) % n
H(v, t) = (H(v) + c*t + d*t*t) % n

最初のものは線形関数であり、2番目のものは二次関数です（ここにこ​​のテクニックの名前があります）..何が何で% nあるかを知っておく必要がcありd、より良いハッシュ関数を持つために定数が選択されます..

線形プロービングについて実際に言えば：

  • あなたが計算するH(x, 0)
    • セルが空いている場合は、そこに要素を配置します
    • セルが占有されている場合は計算しますH(x, i)
      • セルが空いている場合、要素を新しいアドレスに配置します
      • セルが占有されている場合は計算しますH(x, i+i)
        • 空のセルが見つかるまで続行します

二次プロービングの場合は同じです。 から開始しH(x,0)、次にH(x,i)、H(x,i+i)異なるのは、ステップサイズに異なる重みを与える関連するハッシュ関数です。

于 2010-04-10T12:46:32.187 に答える