爲什麼HashMap調整大小在發生衝突或最壞情況下

我只問java版本的問題，直到1.7。我正在使用反射來查找HashMap的當前容量。在下面的程序中，將12個獨特的人放入一個HashMap桶中（使用相同的哈希碼）。然後，我將第13個唯一的人放在同一個或不同的存儲桶中（使用相同或不同的哈希碼）。在添加第13個元素後的兩種情況下，HashMap調整爲32個桶。我明白，由於負載因素.75和初始容量16 HashMap調整到它是第13個元素的雙倍。但是仍然有空的桶可用，並且這些第13個元素僅使用2個桶。爲什麼HashMap調整大小在發生衝突或最壞情況下

我的問題是：

1）我的理解是否正確。我沒有犯任何錯誤。這是HashMap的預期行爲。 2）如果所有這些都是正確的，那麼即使有12個或11個空閒桶，爲什麼在這種情況下需要使用第13個元素來加倍HashMap。調整HashMap的大小不是額外的開銷或昂貴的代價。在這種情況下需要將HashMap加倍，而根據哈希碼可以將第13個放入任何可用的桶中。

public class HashMapTest { 
    public static void main(String[] args) throws NoSuchFieldException, 
      SecurityException, IllegalArgumentException, IllegalAccessException { 
     HashMap<Person, String> hm = new HashMap<Person, String>(); 
     for (int i = 1; i <= 12; i++) { 
      // 12 Entry in same bucket(linkedlist) 
      hm.put(new Person(), "1"); 
     } 
     System.out.println("Number of Buckets in HashMap : "+bucketCount(hm)); 
     System.out.println("Number of Entry in HashMap : " + hm.size()); 
     System.out.println("**********************************"); 
     // 13th element in different bucket 
     hm.put(new Person(2), "2"); 
     System.out.println("Number of Buckets in HashMap : "+bucketCount(hm)); 
     System.out.println("Number of Entry in HashMap : " + hm.size()); 
    } 
    public static int bucketCount(HashMap<Person, String> h) 
      throws NoSuchFieldException, SecurityException, 
      IllegalArgumentException, IllegalAccessException { 
     Field tableField = HashMap.class.getDeclaredField("table"); 
     tableField.setAccessible(true); 
     Object[] table = (Object[]) tableField.get(h); 
     return table == null ? 0 : table.length; 
    } 
} 

class Person { 
    int age = 0; 
    Person() { 
    } 
    Person(int a) { 
     age = a; 
    } 
    @Override 
    public boolean equals(Object obj) { 
     return false; 
    } 
    @Override 
    public int hashCode() { 
     if (age != 0) { 
      return 1; 
     } else { 
      return age; 
     } 
    } 
}

輸出

Number of Buckets in HashMap : 16 
Number of Entry in HashMap : 12 
********************************** 
Number of Buckets in HashMap : 32 
Number of Entry in HashMap : 13

來源

2017-06-25 Pradeep Singh

@Am_I_Helpful對於第二個答案，加載因子適用於輸入計數。爲什麼它看不到已經存在的桶。爲什麼它會調整性能。 –

是的，這是預期的行爲。
HashMap不關心使用了多少桶。它只知道負載因子已經達到，因此碰撞的可能性變得過大，因此地圖應該調整大小。即使已經發生了許多碰撞，調整地圖大小實際上可以解決這個問題。不是你的情況，因爲你有目的地選擇了相同的hashCode，但在更現實的情況下，hashCodes應該有更好的分佈。如果你故意選擇錯誤的hashCode，HashMap不能做任何事情來提高它的效率，並且增加處理極端情況的複雜性是沒有任何意義的，而這絕不應該發生，並且HashMap將無法修復。

來源

2017-06-25 11:22:06

嗨JB！我注意到1件事。由於負載因素0.75，第13個元素的容量變爲32。現在，如果我從HashMap中刪除元素1。容量不會回到16.甚至HashMap現在只包含7個條目。容量仍然是32.如果條目數量下降，是否不需要爲HashMap減少容量？ –

不，HashMap根據需要展開，但永遠不會縮回。 –

哦好吧謝謝JB :) –

是的，你觀察到的行爲是預期的行爲。

執行HashMap期望您使用合理的hashCode作爲密鑰。它假定您的hashCode將盡可能均勻地在可用桶中分配密鑰。如果你不這樣做（就像你在你的例子中所做的那樣 - 所有的鍵都有相同的hashCode），你將會得到不好的表現。

在均勻分佈的假設下，一旦通過加載因子，HashMap的大小加倍是有道理的。它不檢查有多少桶實際上是空的（因爲它無法知道是否將新條目分配給空桶或被佔用的桶）。它只是檢查每個桶的平均入口數量。一旦該數字超過負載因數，桶的數量就會增加一倍。

來源

2017-06-25 11:21:20 Eran

Ean根據你的答案，你說**，因爲它無法知道新的條目將被分配給空桶或被佔用的桶**。現在問題1。特定的桶如何鏈接到HashCode。我認爲第一個HasCode是計算出來的，然後這是連接到空桶。如果我錯了，請糾正我。問題2。我認爲一個新的條目肯定會分配給空的存儲桶或已經佔用的存儲桶。現在在這兩種情況下，加倍hashmap的大小並不需要。我錯了嗎？是的，如果所有的桶都滿了，那麼把HashMap加倍是有意義的 –

@PradeepSingh根據hashCode的值（通過HashMap實現來轉換HashMap實現以改善分配）和當前的數字，將hashCode映射到一個桶的水桶。水桶是否已經被佔用沒有區別。 – Eran

@PradeepSingh至於你的第二個問題，當具有不同散列碼的密鑰映射到同一個存儲桶時，將HashMap加倍會有所幫助。當地圖加倍時，這樣的密鑰可以分成不同的桶，從而減少了那些桶中的搜索時間，因爲新的桶將比原桶更少地進入。 – Eran

這裏還有一個細微的方面;當你調整內部數組的大小時（從16到32），你也「觸摸」了所有的條目。讓我解釋一下：

當有16個桶（內部數組的大小爲16）時，只有last 4 bits決定該入口的位置;認爲%，但其內部其實(n - 1) & hash，其中n是桶的數量。

當內部陣列增長時，再考慮一點來決定入口的位置：曾經有4 bits，現在有5 bits;這意味着所有條目都是重新散列並且它們可能現在可能會移動到不同的桶中;這就是調整大小的原因，以分散條目。

如果你真的想填補所有的「空白」，你指定load_factor的1;而不是默認的0.75;但是這在HashMap構造函數中有記載。

來源

2017-06-25 13:04:59 Eugene

爲什麼HashMap調整大小在發生衝突或最壞情況下

回答

相關問題