9

HashMapのドキュメントには、次のように記載されています。

  • 初期容量は、ハッシュテーブルが作成されたときの容量です。
  • 容量は、ハッシュテーブル内のバケットの数です。

ここで、初期容量が16（デフォルト）であり、100個の番号に要素を追加し続けると、ハッシュマップの容量は100*loadfactorになります。

ハッシュバケットの数は100または16ですか？

編集：
私が読んだ解決策から：バケットは追加された要素以上のものです。これを視点としてとると、文字列をキーとして追加すると、1つの要素/バケットが取得され、多くのスペース消費/複雑さが発生します。私の理解は正しいですか？

4

5 に答える 5

10

100バケットでも16バケットでもありません。ほとんどの場合、256個のバケットがありますが、これはドキュメントによって保証されていません。

更新されたドキュメントリンクから：

負荷率は、容量が自動的に増加する前にハッシュテーブルがどれだけいっぱいになるかを示す尺度です。ハッシュテーブルのエントリ数が負荷率と現在の容量の積を超えると、ハッシュテーブルのバケット数が約2倍になるように、ハッシュテーブルが再ハッシュされます（つまり、内部データ構造が再構築されます） 。

（強調鉱山）

したがって、上記の「ほぼ」という単語を無視すると、ハッシュテーブルが75％いっぱいになると（またはコンストラクターで指定した負荷率）、ハッシュバケットの数が2倍になると判断されます。つまり、12番目、24番目、48番目、および96番目の要素を挿入すると、バケットの数が2倍になり、合計256個のバケットが残ります。

ただし、ドキュメントスニペットで強調したように、この数は前のサイズの約2倍であるため、正確に256ではない可能性があります。実際、最後から2番目の倍増をわずかに大きい増加に置き換えると、最後の倍増が発生する可能性があります。決して起こらないので、最終的なハッシュテーブルは134バケットほど小さい場合もあれば、256要素より大きい場合もあります。

NNB私は134の数に到達しました。これは、のような最小の整数だから0.75 * N > 100です。

于 2012-04-30T06:41:00.113 に答える
3

のソースコードHashMapを見ると、次のことがわかります。

threshold = capacity * loadfactor
size = number of elements in the map

if( size >= threshold ) {
  double capacity
}

したがって、初期容量が16で、負荷率が0.75（デフォルト）の場合、初期しきい値は12になります。12番目の要素を追加すると、容量は32に増加し、しきい値は24になります。次のステップは容量です。 64およびしきい値48など。

したがって、100個の要素を使用すると、容量は256、しきい値は192になります。

これは標準値にのみ適用されることに注意してください。マップに含まれる要素のおおよその数がわかっている場合は、容量が増加したときにコピーされないように、十分に高い初期容量でマップを作成する必要があります。

更新：

容量に関する一言：異なる初期容量を定義した場合でも、常に2の累乗になります。次に、ハッシュマップは、容量を、提供された初期容量以上の最小の2乗に設定します。

于 2012-04-30T06:43:28.147 に答える
1

ドキュメント内 

When the number of entries in the hash table exceeds the product of the 
load factor and the current capacity, the capacity is roughly doubled by 
calling the rehash method.

threshold=product of the  load factor and the current capacity

試してみましょう。ハッシュマップの初期サイズは16
で、デフォルトの負荷率は最初の0.75 しきい値が12なので、12要素の次の容量を追加すると次のようになります。（16 * 2）= 32
2番目のしきい値は24なので、24番目の要素を追加すると次の容量は次のようになります。 （32 * 2）= 64

等々..

于 2012-04-30T06:53:48.473 に答える
1

あなたのリンクから：

ハッシュテーブルのエントリ数が負荷率と現在の容量の積を超える場合、rehashメソッドを呼び出すことで容量が約2倍になります。

つまり、初期容量が16で、それを超えると、容量が32増加し、次回は64増加します。

あなたの場合、100個の番号を追加しています。したがって、16番目の数値になると、サイズが32増加するため、合計サイズは48になります。48番目の数値になるまで追加を続けると、サイズは64増加します。したがって、この場合、バケットの合計サイズは112になります。

于 2012-04-30T06:41:19.873 に答える
0

実際のアイテムごとに少なくとも1つのバケットが必要です。16を超えるアイテムを追加する場合は、テーブルのサイズを変更して再ハッシュする必要があります。

ここで、初期容量が16（デフォルト）であり、100個の番号に要素を追加し続けると、ハッシュマップの容量は100*loadfactorになります。

実際にそれは言う：

初期容量が最大エントリ数を負荷率で割った値よりも大きい場合、再ハッシュ操作は発生しません。

つまり、最大100個のアイテムがあり、容量が100 / 0.75 = 133の場合、再ハッシュは発生しません。これは、テーブルがいっぱいでなくても、いっぱいに近づいたときに再ハッシュする必要がある可能性があることを意味していることに注意してください。したがって、デフォルトの負荷率を使用して設定する理想的な初期容量は、100未満のアイテムが予想される場合、約135以上です。

于 2012-04-30T06:42:57.773 に答える