なぜJavaで</p> <p>現在、HashMapの::私は私の心に疑いを持っている

Question

代わりに満たされたバケットの合計サイズに基づいてサイズを変更するハッシュマップ、totalSize(no of elements inserted) > arrayLength * loadFactor

は、それがテーブルを倍増し、すべてのキーと値をリハッシュときリサイズします。

しかし、Keyクラスのハッシュコードがハードコーディングされているとしましょう.1とすると、毎回要素がリンクリスト形式でインデックス1に挿入されます。しかし、私たちのbucketarrayは、合計サイズに合わせてサイズ変更する必要はありません。したがって、要素はそのようなハッシュコードの実装で同じバケットに入る間、それは増加するbucketarrayのサイズを維持します。

私は質問がありますが、サイズの合計ではなく、埋められたバケットのサイズを確認してください。

私はそのようなハッシュコードがパフォーマンスを妨げることがわかります。私はこれを論理的な質問として求めています。

Answer 1

HashMapには、悪い点を改善しようとするコードがいくつかありますが、常に同じ値を返す恐ろしいhashCode()の実装を改善するために何もできません。

このようなhashCode()は、HashMapのサイズを変更するかどうかに関係なく、パフォーマンスが低下します。したがって、このような悪い使用法HashMapは、あなたが示唆するように特別なロジックを追加することを正当化するものではありません。

hashCode()のキーの実装では、HashMapビンの間でキーを可能な限り一様に近いところに配布することが前提です。したがって、バケット内のエントリの平均数（エントリの総数をバケットの数で割ったもの）は、HashMapのサイズを変更する必要があり、個々のバケットのサイズをチェックする必要はありません。

Answer 2

hashcode場合は、常にそれが悪い実装、行われるべきではありませんどのような支援の無いロジックで同じ値に

1. を返します。

2. hashcode定数関数ではないかもしれない、ハッシュマップは、ハッシュ関数は、型の定数であるかどうか突然hashcode非定数関数は、次に、サイズ変更が生じることになった場合のように、hashmapのサイズを変更するのが賢明であるかどうかを知る方法がありませんより良い値の分布で。

Answer 3

サイズ12のハッシュマップとその中の9個のアイテムを想像してください。偶然にも、#hashCode()は3の倍数しか返しません - それでも欠陥のあるハッシュコードですが、それは一定のハッシュコード1などのような人為的なエッジケースではありません。つまり、この場合、4つのバケット（0,3 、6、および9）は、1つまたは2つの要素で満たされます。

あなたのアプローチでは、このハッシュマップは決してリサイズされず、衝突リストは永遠に成長し、パフォーマンスは低下します。ただし、合計サイズに基づいてサイズを変更し、負荷係数を75％（つまり10番目の要素を追加する場合）にすると、24個のバケットのあるマップが作成されます。そのうちの8個が埋められます。

合計サイズに基づいて成長すると、実際の不完全なハッシュ関数を持つ合理的なサイズの衝突リストが保持されます。これは、すべてのハッシュ関数が少なくともハッシュコードを配布するのに最善の努力を払うと考えているからです。ハッシュマップを大きくすると、クラスタや空のバケットがまだ残っていても、以前よりも完全なバケットが得られることを意味します。

基本的には、エッジの場合のメモリ使用を最適化し、アクセスパフォーマンス（マップの主目的）を最適化しないようにすることをお勧めします。