java - サイズがしきい値に達するたびに、すべての辞書のようなデータ構造を再ハッシュする必要がありますか?

Question

辞書のようなデータ構造 (Hashtable、HashMap、LinkedHashMap、TreeMap、ConncurrentHashMap、SortedMap など) は、サイズがしきい値に達したときに再ハッシュ操作を行う必要があるのでしょうか? テーブルのサイズを変更するたびに非常にコストがかかるため、テーブルのサイズを変更するときに再ハッシュを必要としないものや、そのような操作のパフォーマンスを向上させる方法は他にあるのでしょうか?

Answer 1

SortedMap (TreeMap) は再ハッシュする必要はありません。赤黒ツリーとして設計されているため、自己バランスがとれています。

クローズドハッシュ関連の構造は、パフォーマンスを向上させるために再ハッシュする必要があるかもしれませんが、それはトレードオフです。

そのため、再ハッシュせずに実装できます。これが、負荷係数パラメーターが導入された理由です。

Answer 2

パフォーマンスを向上させるには、アプリケーションに基づいて概算の初期容量を見積もり、データ構造にメモリを割り当てるときに適切な負荷係数を選択します。

独自の HashMap を実装しない限り、再ハッシュから逃れることはできません。

その他のいくつかの事実: 再ハッシュは HashRelated データ構造、つまり HashMap、HashTable などでのみ発生します。したがって、treemap、sortedmap などのすべての非ハッシュ データ構造 (これはインターフェイスであるため、これを図から外すことができます) は、制限に達しても再ハッシュされません。

サイズ変更は、ArrayList がしきい値に達すると常に発生します。したがって、データ構造の間に多くの挿入と削除がある場合は、リンクされたリストを使用してください。