アルゴリズムクラスのハッシュテーブルについて勉強していて、負荷率に戸惑いました。「n」が要素の数で「m」がテーブル スロットの数である場合、負荷係数 n/m が重要なのはなぜですか? また、すべての要素が 1 つのスロットに格納されている場合、この負荷係数がハッシュ テーブルのスロット j にあるリンク リストである n(j) の予想される長さに等しいのはなぜですか?
1427 次
2 に答える
3
ハッシュ テーブルの重要な特性は、要素を検索するのにかかる予想一定時間です。*
これを実現するために、ハッシュ テーブルの実装者は、ハッシュ テーブルへのすべてのクエリが一定量以下のステップを返すことを確認する必要があります。
バケットを持つハッシュ テーブルがあり、m要素を無制限に追加する場合 (n>>mつまりますます増加するリンク リストをトラバースする必要がある実行時間は、バケットのルックアップを上回ります)。
では、リストが増えないようにするにはどうすればよいでしょうか。さて、リストの長さが固定定数によって制限されていることを確認する必要があります - どうやってそれを行うのでしょうか? さて、バケットを追加する必要があります。
ハッシュ テーブルが適切に実装されている場合、要素をバケットにマップするために使用されるハッシュ関数は、要素をバケット全体に均等に分散する必要があります。ハッシュ関数がこれを行う場合、リストの長さはほぼ同じになります。
要素が均等に分散されている場合、リストの 1 つはどのくらいの長さですか? 明らかに、要素の総数をバケットの数で割った値、つまり負荷係数 n/m(バケットあたりの要素の数= 各リストの予想される長さ/平均の長さ) が得られます。
したがって、一定時間のルックアップを確実にするために、負荷係数 (リストの予想長さ) を追跡する必要があります。これにより、一定の定数を超えた場合にバケットを追加できます。
もちろん、すでに保存されている要素を再配布する方法や、バケットをいくつ追加する必要があるかなど、さらに多くの問題が発生します。
取り上げるべき重要なメッセージは、ハッシュ テーブルにバケットを追加するタイミングを決定するために負荷係数が必要であるということです。
もちろん、すべての要素を同じバケットにマップすると、各リストの平均の長さはあまり価値がありません。これらすべては、バケット全体に均等に分散する場合にのみ意味があります。
*予想されることに注意してください-これを十分に強調することはできません. 「ハッシュテーブルには一定のルックアップ時間がある」と聞くのは典型的なことです。彼らはしない！最悪の場合は常に O(n) であり、それをなくすことはできません。
于 2015-10-15T13:17:10.110 に答える
0
既存の回答に追加して、簡単な派生を入れましょう。
テーブル内で任意に選択されたバケットを考えてみましょう。要素がこの要素に挿入された場合とそうでない場合に等しいインジケータ確率X_i変数とします。1ith0
見つけたいE[X_1 + X_2 + ... + X_n].
期待値の線形性により、これは次のようになりますE[X_1] + E[X_2] + ... E[X_n]
E[X_i].これは単純に(1/m) 1 + (1 - (1/m) 0) = 1/m期待値の定義によるものです。したがって、すべての値を合計すると、時間i'sが得られ1/m + 1/m + 1/m nます。これは次のようになります。ランダム バケットに挿入される要素n/m.の予想数がわかりました。これが負荷係数です。
于 2015-10-16T09:49:20.383 に答える