0

再ハッシュについて質問があります。サイズ7のハッシュテーブルがあり、ハッシュ関数は（key％tableSize）であるとします。テーブルに24を挿入すると、24％7 = 3であるため、24はインデックス3になります。次に、要素を追加したとしましょう。次に、再ハッシュします。テーブルサイズは初期テーブルの2倍のサイズになります。つまり、新しいテーブルサイズは14になります。次に、要素を新しいハッシュテーブルにコピーしている間、たとえば要素24をコピーしている間、それはインデックス3に残ります。 、またはインデックス24％14=10になります。つまり、要素をコピーするときに新しいテーブルサイズを使用しますか、それとも要素は初期インデックスに残りますか？ありがとう

4

2 に答える 2

0

それはあなたのハッシュ関数に依存します。あなたの場合、key％size_of_tableを使用する必要があります。そうしないと、7以降のスロットがハッシュ関数によってマップされることはありません。これらのスロットは、衝突に対処するために線形プロービングを選択した場合にのみ占有されます（次の空のスロットを探す場所）。新しいサイズを選択すると、早い段階で衝突を減らすのに役立ちます。そうしないと、テーブルが負荷率に達していないにもかかわらず、多くの衝突に直面している可能性があります。

于 2013-01-11T11:25:47.027 に答える
0

ハッシュテーブルに関する重要なことは、要素の順序が保証されておらず、ハッシュ関数に依存していることです。

例：ハッシュサイズに7を使用してデータを新しいハッシュにコピーすると、新しい配列のインデックス：7、8、9、10、11、12、および13は使用されなくなります。これは、より大きな配列とハッシュ関数は 6 より大きい結果を返すことはできません。これらの未使用のインデックスは単に不要なので悪いことなので、key % 14代わりに使用することをお勧めします。

興味深いことに、内部ハッシュ テーブルの状態は、ハッシュ関数だけでなく、要素が挿入された順序にも依存する可能性があります。たとえば、Xサイズ 4 のハッシュ テーブル (配列と連結リストで実装) があり、要素 2、3、6、10 をこの順序で挿入するとします。

x 
{
    [0] -> []
    [1] -> []
    [2] -> [2,6,10]
    [3] -> [3]
}

ハッシュ関数については、再び使用されkey % sizeます。

ここで、キーを異なる順序 (10、6、3、2) で挿入すると、次のようになります。

x 
{
    [0] -> []
    [1] -> []
    [2] -> [10,6,2]
    [3] -> [3]
}

上記のすべての行を書いたのは、多くの要因により、ハッシュの 2 つのコピーが内部的に異なって見える可能性があることを示すためだけです。それがあなたの質問の考慮事項だったと思います。

于 2013-01-11T11:25:38.020 に答える