1

特にハッシュテーブルと二次プロービングについて学んでいます。負荷係数が <= 0.5 で、テーブルのサイズが素数の場合、2 次プロービングは常に空のスロットを検出し、複数回アクセスされるキーはないことを読みました。さらに、効率的な挿入を確実にするために、負荷率を常に <= 0.5 に維持する必要があると述べています。これは何を意味するのでしょうか?確かに、アイテムを追加し続けると、必要かどうかに関係なく、負荷率が 1 になるまで増加します。では、私の教科書が小さな負荷率を維持する必要があると言っている場合、それは何を暗示しているのでしょうか?

4

1 に答える 1

3

これは、ある時点 (この場合、負荷係数が 0.5 を超える場合) で、新しいテーブルを割り当てる必要があることを意味します (これは、何らかの係数、おそらく 1.5 または 2 倍大きくなり、切り上げて最も近い素数) を作成し、古いテーブルのすべての要素をそこにコピーします (これは単純なコピーではありません。通常、アイテムの新しい位置は古い位置とは異なります)。

于 2015-05-31T13:02:03.547 に答える