Java HashMap配列のサイズ

Question

私はJava 8 HashMapの実装の詳細を読んでいますが、誰も私になぜJava HashMapの初期配列サイズが具体的に16であるかを教えてもらえますか？何が16について特別なのですか？そしてなぜそれは2つの力が常にあるのですか？ありがとう

Answer 1

なぜ2のべき乗が出現するのかという理由は、2の累乗での2進数演算が効率的であるためです。たとえば、2つの数値を掛けることは、バイナリではあまり効率的ではありません.2つの数値にそれぞれ複数の桁を掛けるときに使用するのと同様の方法を使用します。 2の累乗で乗算または除算を行うには、コンピュータが乗算のためにビットを左に移動するか、または分周のためにビットを移動する必要があります。

また、なぜ16のHashMapですか？ 10は、（任意に選択された）動的に成長する構造の一般的なデフォルトであり、16は遠くないが2の累乗である。

2の累乗に対して非常に効率的にモジュラスを行うことができる。n % d = n & (d-1) dがa 2の累乗、およびモジュラスは、アイテムが内部配列内のどのインデックスにマップするかを決定するために使用されます。つまり、Java HashMapで非常に頻繁に発生します。モジュラスは除算を必要とし、bitwise and演算子を使用する場合よりもはるかに効率が悪い。

bitwise andが2の累乗でこのように動作する理由は、2の累乗が1に設定された1ビットで表されるためです。ビットがtであるとしましょう。 2のべき乗から1を減算すると、tより下のすべてのビットを1に設定し、tより上位のすべてのビットを0に設定します。Bitwise andは、したがって、位置nより下のすべてのビットの値を（n残りの部分を0に設定します）。

しかし、それはどのように役立ちますか？ 10の累乗で除算する場合、1に続くゼロの数を数え、残りを見つけるために被除数の最下位から始まるその桁数を取ることを覚えておいてください。例：637989％1000 = 989.同様のプロパティが1に設定された1進数で2進数に適用され、残りは0に設定されます。例：100101％001000 = 000101

Answer 2

hash & (n - 1)moduloとそれは負のハッシュです。 hashcodeはint型ですが、当然負の値になります。負の数のモジュロ（Javaの場合）も負であり、&は負ではありません。

Answer 3

もう1つの理由は、アレイ内のすべてのスロットを同じように使用する可能性が高いことです。 hash（）は32ビットに渡って均等に分散されているため、配列サイズがハッシュ空間に分割されなかった場合、残りの部分があり、インデックスが低くなり、使用される可能性が少し高くなります。理想的には、ハッシュだけでなく、（hash（）％array_size）はランダムで均等に分布しています。

しかし、これは実際には小さなハッシュ範囲（バイトや文字など）のデータにとって重要です。