HashMap的應該是未排序的，但仍然排序根據關鍵

Question

根據這些：

1. http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
2. Difference between HashMap, LinkedHashMap and TreeMap
3. java beginner : How key gets sorted in hashmaps?

在Java的HashMap應該是未排序的，但它正在整理關於Key。

我經歷過這個問題，因爲我需要插入數據。所以，我用LinkedHashMap來代替。但我仍然困惑爲什麼HashMap排序它。

任何人都可以解釋它嗎？

我做了一個簡單的例子來查看排序。

public static void main(String[] args) { 

     HashMap<Integer, String> newHashMap = new HashMap<Integer, String>(); 
     newHashMap.put(2, "First"); 
     newHashMap.put(0, "Second"); 
     newHashMap.put(3, "Third"); 
     newHashMap.put(1, "Fourth"); 

     Iterator<Entry<Integer, String>> iterator = newHashMap.entrySet() 
       .iterator(); 
     while (iterator.hasNext()) { 

      Map.Entry<Integer, String> entry = iterator.next(); 
      System.out.println("Key: " + entry.getKey()); 
      System.out.println("Value: " + entry.getValue()); 
      iterator.remove(); 
     } 

    } 

結果：

Key: 0 
Value: Second 
Key: 1 
Value: Fourth 
Key: 2 
Value: First 
Key: 3 
Value: Third 

編輯：

我試圖插入使用JavaRandom 50張的隨機數，我發現未排序的一些數據。但是，它仍然設法排序大部分整數。

隨機結果：

... 
Key: 36 
Value: random 
Key: 43 
Value: random 
Key: 47 
Value: random 
Key: 44 
Value: random 
Key: 45 
Value: random 
... 

Answer 1

這是一個巧合（不是真的，而它與哈希算法做）。

嘗試增加

newHashMap.put(-5, "Fifth"); 

去年。

輸出將是

Key: 0 
Value: Second 
Key: 1 
Value: Fourth 
Key: 2 
Value: First 
Key: 3 
Value: Third 
Key: -5 
Value: Fifth 

的Javadoc特別說

此類不保證作爲對地圖的順序;特別是，它不能保證訂單會隨着時間的推移保持不變。

Answer 2

您不能對HashMap對象的排序做出假設。他們會根據需要訂購，實施定義。您應該將它們視爲無序的數據結構。

Answer 3

這純粹是巧合。有時出現需要排序，但不斷添加鍵和夢想會粉碎。

我寫了這個小程序：

import java.util.Map; 
import java.util.HashMap; 

class MapTest { 

    public static void main(String[] args){ 
     int count = Integer.parseInt(args[0]); 
     Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
     for (int i = 0; i < count; i++) map.put(i, i); 
     System.out.println(map); 
    } 

} 

當運行java MapTest 20，我得到下面的輸出（線爲了便於閱讀）：

{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9, 10=10, 11=11, 12=12, 13=13, 
14=14, 15=15, 17=17, 16=16, 19=19, 18=18} 

這簡直HashMap執行的財產最初看起來是有序地添加了Integer（從0開始）。

Answer 4

你不應該推斷太多！僅僅因爲三個或四個數字出現排序，並不意味着他們已被排序。

正整數的散列碼通常只是int，所以如果所有的鍵都小於Map維護的內部數組的長度，它們可能會顯示排序。

嘗試使用真正的大值，並且您會看到貼標順序消失。例如，使用

100,200,300,100001，100002，10003，999123456，888777666，......

Answer 5

其實它不能保證的順序。

散列圖使用散列碼來快速散列用於搜索的數據。

你的鑰匙是如此簡單，所以它排序。

Answer 6

你不能認爲它會被排序。在這個簡單的例子中，它顯示排序的原因：一個HashMap是從「Bins」內部構建的。這些箱包含實際的元素。它們基本上都是駐留在數組中的小列表。

[0] -> [ Bin0: ... ] 
[1] -> [ Bin1: ... ] 
[2] -> [ Bin2: ... ] 
[3] -> [ Bin3: ... ] 

當物品插入HashMap中，那麼「賓」，其中它應該被插入是 - 簡化它有點 - 通過使用對象的hashCode()作爲數組索引找到。例如，如果hashCode是2，它將被插入Bin 2中。當這個「index」大於數組大小時，它將被放入Bin（index％arraySize）中 - 也就是說，如果hashCode是5，它將被插入到Bin 1中。

而且由於HashMap最初的內部數組大小爲10，所以在0到9之間插入Integer對象將巧妙地將元素按照正確的順序放入數組中。 （當然，Integer的hashCode只是它的值）。

（注：實際算法和散列函數可能會稍微複雜一些，但是這是基本的想法）

Answer 7

煤礦是一個受過教育的猜測，但其原因很可能是一個事實，即默認的hashCode方法使用內存位置。小Integer s（和您的密鑰自動裝入到Integer）的內存位置很可能是固定的：如果Integer.valueOf(1)在多個調用中返回不同的內存位置將是無稽之談。最後，這些固定內存位置很可能是按升序排列的。這可以解釋這個巧合，但是，我們需要深入Integer和HashMap的實現來證明這一點。

更正：在整數情況下「此對象的哈希碼值，等於此Integer對象表示的基本int值。「（JavaDoc的）。其中，雖然不同的號碼，證實了這個想法。

Answer 8

就像每個人說（和右約）是你應該假設在一個HashMap中的鍵進行排序。 現在他們LOOK整理你的情況兩個簡單的原因：

1 - 您正在使用整數作爲關鍵：本HashMap使用Object類的Java的hashCode()方法查找索引底層數組中，它使用存儲Entry實例（什麼包含您的值和密鑰在HashMap）。它恰好發生了的哈希碼3210是它自己的價值。

2 - 您沒有設置HashMap的初始大小，因此正在使用其默認初始大小（即16）。因此，直到您添加一個低於0或高於16（包括）的密鑰，您將看到按順序存儲的密鑰。由於HashMap做

int index = newKey.hashCode() % this.capacity; 

後來HashMap如果插入了很多鍵值對（當它決定這樣做，這是非常有趣的，如果你是如何和可能增加其底層陣列的容量得到指數進入算法和數據結構研究），所以你最終可能會遇到你的Integer鍵可能會重新排序的情況，但實際上它們並不是有意排序的。

順便說一句，如果你的鍵將是整數，你可以估計你將有的最大鍵值，我建議直接使用一個數組。訪問速度更快，使用的內存將相同或略少。

Answer 9

既然沒有答案真的用於查看Java源代碼，我會這麼做！ :)

當您調用put()函數時，內部哈希函數使用該對象的hashCode來生成哈希索引。 [put() source]

hash()函數簡單地確保hashCodes在每個比特位置上僅以恆定倍數差異的碰撞數量有限[使用Google來查明原因是什麼]。

事情只是巧合在這裏工作。就是這樣。