HashSetの塗りつぶし率または荷重係数の概念とは何か

Question

HashSetクラスを勉強したように、塗りつぶし率という概念を使用しています。これは、HashSetがこの限界までいっぱいになるとHashSetが大きくなり、それに。なぜ、HashSetにオブジェクトがいっぱいになってから、新しいHashSetを作成させるのはなぜですか？なぜ新しい概念がHashSetのために派生したのですか？

Answer 1

ArrayListとVectorの両方が位置インデックスでアクセスされるため、競合はなく、アクセスは常にO（1）です。

ハッシュベースのデータ構造はハッシュ値によってアクセスされます。ハッシュ値は、第2レベルの「オーバーフロー」データ構造（リストまたはツリー）へのアクセスに衝突し、劣化する可能性があります。そのような衝突がない場合、アクセスはO（1）ですが、多くの衝突があると、それはかなり悪化する可能性があります。より多くのメモリを割り当てることで、これを少し制御することができます（バケットがたくさんあり、衝突が少なくなるように）。

結果として、すべての要素を格納するのに必要な容量以上にArrayListを拡張する必要はありませんが、HashSetの場合にはビット（またはロット）を「無駄にする」のは意味があります。このパラメータは、プログラマが自分のアプリケーションに最適なものを選択できるように公開されています。

Answer 2

Jonny Henlyが説明しました。データが格納される方法が原因です。

ArrayListは線形データ構造ですが、HashSetはそうではありません。 HashSetでは、データはハッシュコードに基づいて基本配列に格納されます。ある意味では、HashSetのパフォーマンスは、いくつのバケットが満たされているか、これらのバケット間でどのくらいデータが分散しているかに関係しています。このデータの分布が一定レベル（負荷率と呼ばれる）を超えると、再ハッシングが行われます。

Answer 3

HashSetは、HashSetに格納されているエントリの数に関係なく、一定の時間内に基本的な操作（追加、フェッチ、変更、削除など）を確実に実行するために主に使用されます。

よく設計されたハッシュ関数ではこれを達成できますが、設計には時間がかかることがあります。したがって、パフォーマンスがアプリケーションの重要な要件である場合、負荷係数を使用して、一定の時間内で操作が確実に実行されるようにすることができます。私は、これらの両方をお互いに冗長なもの（負荷要因とハッシュ関数）と呼ぶことができると思います。

私はこれが完璧な説明ではないことに同意しますが、それはその主題についていくらか明確にすることを望みます。