なぜHashMapが自然な順序で印刷されるのですか

Question

私はJavaでハッシュマップを導入しようとしていましたが、ハッシュマップは順序付けされていないと分類されていませんでした。したがって、System.out.println(HM)を使用して印刷するときは、キーの任意の順序でマッピングを取得する必要があります。例えば、次のコードのキーの明らかにランダムな順序で

HashMap<Integer,String> HM = new HashMap<>(); 
HM.put(16,"hello16"); 
HM.put(6, "hello6"); 
HM.put(1, "hello1"); 

プリント{16=hello16, 1=hello1, 6=hello6}。

{1=hello1, 6=hello6, 15=hello15} 

私は友人を尋ねたし、彼はそれが初期容量に関係だと言った（= 16）の：私はHM.put(15,"hello15");とHM.put(16,"hello16");を交換する場合でも、それはキーの自然順序でマッピング、is surprising and seems unlikely by chanceを印刷しますHashMapだが彼はそれをはっきりと説明できなかった。誰でもこの特定の例で出力のこの違いを説明できますか？

Answer 1

IntegerのhashCodeが値そのものです。あなたのHashMapは、あなたの鍵は、15の範囲0である場合は0から15

に数である、値が割り当てられているバケットがkey % 16であることを意味し、16個のバケツを持って、その後バケット番号ですキー。キー> 15または< 0を使用すると、物事が乱雑になります。

HashMapを印刷すると、エントリはバケット順に表示されます。つまり、バケット0のキーがある場合は最初に印刷されます。バケツ1のキーなどがあります。 HashMapの場合、すべてのキーの値が0〜15の場合は、キーの順序とまったく同じです。

Answer 2

HashMapは、キーのハッシュコードを使用して、インデックス付きバケットの配列にマップエントリをスローします。検索順序は多かれ少なかれ恣意的です。同じ長さの文字列として、最後の文字が異なるだけで、一般にX +最後の文字に等しいハッシュコードがあります。その中には順序があります。クラスのTreeMapを実装

他の地図はのSortedMapで、キーの順序でエントリを保持します。

さらに別のマップの実装は、LinkedHashMapです。ここでは、順序はマップにエントリを入れる順序です。

Answer 3

コードキー

任意現れ得るためのランダムな順序でプリント{16=hello16, 1=hello1, 6=hello6}、それは決定論的です。順序を決定する（キーのハッシュコードの

• 値、
• ハッシュテーブルのバケットの数、及び
• キーが挿入されている順序：順序は、三つの要因に基づいています

ハッシュテーブルエントリの列挙は、ハッシュバケットによって行われます。ハッシュバケットの数は可能なハッシュコードの範囲よりも小さいので、ハッシュコードの値はハッシュバケットのインデックスに間接的に変換されます。 Java implementationは、ハッシュキーの上に補足的なハッシュ関数を適用して、実際のインデックスを取得するためにビット単位&を使用しています。

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); 
} 
... 
static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

あなたがそれだ（lengthは2の累乗であることが予想されていることをindexForコードから見ることができますなぜ% length式の代わりに& (length-1)を使用できるのか）。あなたの場合、整数のハッシュコードは対応する整数の値と一致するので、これは重要です。 16バケットの容量を仮定すると、16はバケットゼロに変換され、15はバケット15に変換されます（バケットは0から番号付けされます）。

これは、15の値があなたの例の前から後に移動する理由です。