java - 削除時にハッシュ可能な再ハッシュ

Question

hashtableのjavajdk実装が削除時にテーブルを再ハッシュしない理由を誰かが知っていますか？

スペース使用量が少なすぎる場合はどうなりますか？サイズを小さくして再ハッシュする理由ではありませんか？

プット時に再ハッシュをトリガーする負荷率0.75と同様に、テーブルの密度に0.25のような下限を設定し（もちろん、ここで最適な値で分析を実行できます）、テーブルのサイズに応じて再ハッシュを再度トリガーできます。 initialCapacityよりも大きいです。

Answer 1

再ハッシュはコストのかかる操作であり、Javaハッシュベースのデータ構造はそれを回避しようとします。ルックアップのパフォーマンスが悪い場合にのみ、再ハッシュを実行します。これが、このタイプのデータ構造の目的であるルックアップパフォーマンスです。

HashMapjavaドキュメントからの引用は次のとおりです。

再ハッシュ操作の数を最小限に抑えるために、初期容量を設定するときに、マップ内の予想されるエントリ数とその負荷率を考慮する必要があります。初期容量が最大エントリ数を負荷率で割った値よりも大きい場合、再ハッシュ操作は発生しません。

多くのマッピングをHashMapインスタンスに格納する場合は、十分な容量でマッピングを作成すると、テーブルを拡張するために必要に応じて自動再ハッシュを実行するよりも効率的にマッピングを格納できます。

この議論に加えて、Java作成者は、ハッシュテーブルに非常に多くの要素がある場合、それらを再び持つ可能性は非常に高いため、テーブルを2回再ハッシュする必要はないと考えたかもしれません。

Answer 2

サイズを小さくするためのしきい値がない理由を知るために、Sun/Oracleのエンジニアに尋ねる必要があります。

これが私の2セントです：

• テーブルの再ハッシュには時間がかかります
• すべての削除操作のチェックには時間がかかります

一方で：

• おそらく、多くのメモリを節約することはありません（テーブル内のオブジェクトとノードははるかに多くのスペースを使用します）
• 最初に（いくつかの）非常に大きなハッシュテーブルを作成し、次にそれらを空にして未使用のスペースを切望するシナリオは多くないかもしれません。
• あなたはその振る舞いを含む一般的な実装を知っています（テーブルサイズを減らす）

人生のようにプログラミングでは、行われるかもしれないことがたくさんあります。いくつかは非常に特定の場合にのみ価値があります。痛みにまったく値しないものもあります。