0

Hashtableクラスに関するJavaのドキュメントから、それは言う

原則として、デフォルトの負荷係数 (.75) は、時間とスペースのコストの適切なトレードオフを提供します。

したがって、Hashtable の負荷係数は 0.75 です。つまり、N 個のキーがある場合、Hashtable は M = N/0.75 のスペースを使用してそれらを格納します。

CLRS ブックでは、ロード ファクター アルファも紹介されています。

しかし、私の理解では、CLRS はアルファを 1 よりも大きく設定することを意図しています。つまり、M = N/アルファ < N です。これは、ハッシュテーブルが M < N の場合に M スロットを使用できることを意味し、未使用のキーからストレージを節約できます。

通常、N の正確な値がわからないため、M < N はストレージを節約できると言いますが、キーのセットはわかっており、N を使用して可能なキーの数を表します。キーのセットは非常に大きいかもしれませんが、実際に使用されるキーの数は非常に少ないです。したがって、M を N より小さく設定すると、ストレージを節約できます。また、これが通常、Hashtable がすべての {key, value} を 1:1 でマップするために直接配列を使用しない理由です。

しかし、Java の Hashtable は N を超えるストレージを使用します。これは CLRS の設計と一致していないと思いますよね?

私は正しいですか？

ありがとう

4

2 に答える 2

2

まあ、負荷率は追加された要素よりも大きくする必要があります。1 未満の数で除算すると、最初の数よりも大きな数になります。

100 個の要素を追加すると仮定すると、次のいずれかを記述できます。

AllocationSize = 100 / 0.75; // Your formula: M = N/0.75

また

AllocationSize = 100 * 1.33333333; // M = N / X -> M = N * (1/X)

どちらの結果も133.333333->になり133ます。

JavaDoc 全体:

Hashtable のインスタンスには、パフォーマンスに影響を与える 2 つのパラメーターがあります。それは、初期容量と負荷係数です。容量はハッシュ テーブル内のバケットの数であり、初期容量は単にハッシュ テーブルが作成された時点の容量です。ハッシュ テーブルが開いていることに注意してください。「ハッシュの衝突」が発生した場合、1 つのバケットに複数のエントリが格納され、これらを順番に検索する必要があります。負荷率は、容量が自動的に増加する前に、ハッシュ テーブルがどれだけいっぱいになることができるかの尺度です。ハッシュテーブルのエントリ数が負荷率と現在の容量の積を超えた場合、rehash メソッドを呼び出して容量を増やします。

一般に、デフォルトの負荷係数 (.75) は、時間とスペースのコストの間の適切なトレードオフを提供します。値を大きくすると、領域のオーバーヘッドが減少しますが、エントリを検索するための時間コストが増加します (これは、get や put を含むほとんどの Hashtable 操作に反映されます)。

初期容量は、無駄なスペースと時間のかかる再ハッシュ操作の必要性との間のトレードオフを制御します。初期容量が、ハッシュテーブルに含まれるエントリの最大数を負荷係数で割った値よりも大きい場合、再ハッシュ操作は発生しません。ただし、初期容量の設定が高すぎると、スペースが無駄になる可能性があります。

Hashtable に多くのエントリを作成する場合、必要に応じて自動的に再ハッシュを実行してテーブルを大きくするよりも、十分な容量で作成した方が効率的にエントリを挿入できる場合があります。

于 2012-02-18T09:15:35.690 に答える
0

CLRS の本のことは聞いたことがありませんが、約 0.75 を超える負荷係数を使用すると (一部のハッシュ マップの設計ではさらに低い)、かなりの数の衝突が発生することはわかります。

HashMap または Hashtable が自然に大きくなるようにすると、その容量はエントリの数に比例します。これらの参照はエントリ オブジェクトのサイズ (通常は 16 ～ 24 バイト) に比べて小さい (通常は 4 バイト) ため、関心のあるハッシュ インデックス テーブルは、キーは言うまでもなく、常にエントリ オブジェクトのサイズより数倍小さくなります。と値。

于 2012-02-18T09:16:37.243 に答える