5

ハッシュテーブルの負荷率とスペース使用率の違いは何ですか? 誰か説明してください！

4

2 に答える 2

1

負荷率

意味：

Hashtableの負荷係数は、要素とバケットの比率です。負荷係数が小さいほど、メモリ消費量が増加しますが、平均ルックアップ時間が短縮されます。通常、デフォルトの負荷係数 1.0 は、速度とサイズの最適なバランスを提供します。

つまり、小さすぎるload factorと、HashTable の要素へのアクセスが高速になりますが (特定の要素の検索中、または反復中...)、より多くのメモリ使用量が必要になります。

反対に、負荷率が高いと (平均で) 遅くなり、メモリ使用量が少なくなります。

Abucketは一定数のアイテムを保持します。

場合によっては、テーブル内の各場所が固定数のアイテムを保持するバケットであり、そのすべてがこの同じ場所にハッシュされます。おそらく別の場所に行く必要がないため、これによりルックアップが高速化されます。

  • 線形プロービングとダブル ハッシュ : 負荷係数は次のように定義されますn/prime。ここnで、 はテーブル内のアイテムの数、 はテーブルprimeのサイズです。したがって、負荷係数 1 は、テーブルがいっぱいであることを意味します。

これはベンチマークの例です（ここではprime多数の条件で実現されています）：

load        --- successful lookup ---        --- unsuccessful lookup ---
factor         linear       double              linear         double
------------------------------------------------------------------------
0.50           1.50         1.39                2.50           2.00
0.75           2.50         1.85                8.50           4.00
0.90           5.50         2.56               50.50          10.00 
0.95          10.50         3.15              200.50          20.00

テーブルソース。

  • 一部のハッシュ テーブルでは、他の衝突解決スキームが使用されます。 たとえば、同じ場所にハッシュされるアイテムがリンク リストに格納される別の連鎖では、検索時間は、検査する必要があるリスト ノードの数によって測定されます。検索が成功した場合、この数値は です1+lf/2。ここlfで、 は負荷係数です。各テーブルの場所には、多数の項目を含むことができるリンクされたリストが保持されるため、負荷係数は 1 よりも大きくなる可能性がありますが、通常のハッシュ テーブルでは 1 が可能な最大値です。


スペース利用

アイデアは、データのレコードをハッシュ テーブルに格納するというものです。各レコードには、keyフィールドと関連dataフィールドがあります。レコードは、そのキーに基づく場所に格納されます。特定のキーごとにこの位置を生成する関数は、 a と呼ばれますhash function。

各キー フィールドに整数が含まれ、データ フィールドに文字列 (文字列の文字の配列) が含まれているとします。1 つの可能なハッシュ関数はhash(key) = key % prime.

意味：

スペース使用率は、完全に使用されたバケットの数 (負荷係数と比較して) と、ハッシュ テーブルに予約されているバケットの総数との比率になります。

技術的な理由から、素数のバケットの方がうまく機能しますが、これは (完全に使用されたバケットの数をモジュラスとして)メモリの浪費につながる可能性があります。


結論 :線形検索や二分検索を行う必要はなく、通常、ハッシュ テーブルは 1 回の比較だけでルックアップを完了します。ただし、2 つの比較 (またはそれ以上) が必要な場合もあります。したがって、ハッシュ テーブルは (ほぼ) 理想的なルックアップ時間を提供します。トレードオフは、この優れたルックアップ時間を得るために、メモリ スペースが浪費されることです。


ご覧のとおり、私は専門家ではありません。これを書いているときに情報を入手しているので、これをより正確またはより正確にするためにコメントを歓迎します...まあ...間違っています...

         I switched it in Community Wiki mode (Feel free to improve)
于 2013-06-21T06:17:36.820 に答える
0

Load factorは、 の合計数に対して、ハッシュ テーブルがどの程度満たされているかを示す尺度ですbuckets。たとえば、1000 個のバケットがあり、この数の最大 70% のみを保存したいとします。load factor比率がこの最大比率を超える (700 を超える要素が格納されている) 場合、ハッシュ テーブルのサイズを増やしてより多くの要素を効果的に保持できます。

Space utilizationハッシュ テーブル内のバケットの総数に対する、満たされたバケットの数の比率です。

通常、負荷率が増加すると、スペース使用率が増加し、idealハッシュ テーブルでは、負荷率とスペース使用率は相互に直線的に関連する必要があります。ただし、ほとんどの場合、スペース使用率は負荷率のsublinear関数です。これは、負荷率の比率が高い場合に複数の要素を保持するように割り当てられているバケットがあるためです。

理想的なケースに近いハッシュ パフォーマンスを得るには、perfect hashing function.

完全ハッシュ関数は、キーを一意のアドレスにマップします。潜在的なアドレスの範囲がキーの数と同じである場合、関数は最小の (スペース内の) 完全ハッシュ関数です。

于 2013-06-21T06:07:27.267 に答える