Java HashMapの実装について

Question

なぜ容量は倍数または2でなければなりませんか？ indexFor関数で "&"を使用する理由は？ キーのハッシュコードを直接使用するのではなく、ハッシュ関数でハッシュを再計算するのはなぜですか？

この実装と「アルゴリズムの紹介」の説明との間には、いくつかの重要な違いがあると思います。

「>>>」とはどういう意味ですか？

static int hash(int h) { 
     // This function ensures that hashCodes that differ only by 
     // constant multiples at each bit position have a bounded 
     // number of collisions (approximately 8 at default load factor). 
     h ^= (h >>> 20)^(h >>> 12); 
     return h^(h >>> 7)^(h >>> 4); 
} 

誰でも教えていただけますか？私はいくつかのハッシュアルゴリズムを説明することができれば感謝します。 ありがとう！

Answer 1

これはパフォーマンスの最適化です。テーブルインデックスにハッシュコードをマッピングするための通常の方法は

table_index = hash_code % table_length; 

%オペレータが高価です。 table_lengthが2のべき乗である場合には、計算：

table_index = hash_code & (table_length - 1); 

は（かなり）より高価な剰余演算に相当します。

Answer 2

カーテンの後ろの男には注意を払わないでください。

実際のアルゴリズムは、開発者にとっての「気分が良い」、縮退したいくつかの奇妙なケースの修正、単純な伝統（ユーザーがしばしばあいまいな依存関係を生む）の組み合わせであることは間違いありません。

そして、この点に注意してください。

* Applies a supplemental hash function to a given hashCode, which 
* defends against poor quality hash functions. This is critical 
* because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0. 

をネット：それが動作する限り、パフォーマンスが良いですが、あなたは気にしないでください。