リストがいっぱいになると乗算されますが、ハッシュマップ/ハッシュテーブルはロードファクターに達すると乗算されます。なぜ、ハッシュマップがいっぱいになるまでサイズ変更を待つことができないのですか?
質問する
149 次
3 に答える
5
array-list と hash-map には大きな違いがあります。前者は各エントリを個別のスロットに格納しますが、後者はエントリのハッシュが一致する場合に複数のエントリをスロットに入れることができます。つまり、すべてのスロットが使用されるずっと前にハッシュマップの速度が低下し始める可能性があり、実際、スロットで倍増する前にすべてのスロットを一度だけ満たすことはほとんどありません。
ハッシュできる固定セットがある場合、ハッシュを作成し、そこからその固定セットのみを効率的に格納するハッシュマップを作成できます。その結果は完全ハッシュと呼ばれます。 .
于 2012-07-17T14:55:11.697 に答える
3
ハッシュの衝突の可能性は、容量の終わりに向かって劇的に上昇するためです (空のバケットが十分ではありません)。同じバケットに入るエントリが増えると、クエリの有効性は、満杯になるずっと前に低下します。ハッシュ アルゴリズムによっては、最適な負荷率が異なる場合があります。
配列に対するクエリの有効性は、その負荷係数の影響を受けません。そのため、サイズを早く変更しても意味がありません。
于 2012-07-17T14:57:16.617 に答える
1
arraylist は常に次の空きスロットに新しい要素を配置します。将来時間を節約したい場合を除き、そのスロットが使用されるまで展開する必要はありません。その場合は を使用できますensureCapacity。
一方、ハッシュマップは、入れた各オブジェクトの整数値を計算します。この値に基づいて、オブジェクトは特定のバケットに格納されます。これは、高速なルックアップをサポートするために行われます。ただし、計算された値は必ずしも一意であるとは限りません。たとえそれが 2 つの異なる値であったとしても、同じバケットを指している可能性があります。これは、バケットの量が少ない場合に特に一般的であり、バケットがほぼ満杯の場合に発生する可能性が非常に高くなります。
誕生日に基づいてバケットに人を格納するハッシュマップを考えてみましょう。バケットが 365 個あっても、10 人で衝突する可能性は約 10% です。23 の場合、50%の可能性があります (詳細はこちら)。
現在、単一の衝突は大したことではありませんが、ハッシュマップを使用する場合は通常、高速な検索のために行います。複数のアイテムが同じバケットにある場合、ルックアップの実行にかかる時間はますます長くなります。したがって、パフォーマンス上の理由から、要素の密度を下げるためにバケットの数を増やす必要があります。
于 2012-07-17T15:05:15.017 に答える