關於HashMap的一些疑問

Question

HashMap以非常簡單的方式實現，但它需要一個天才來理解它是如何實現的。所以，我已閱讀了關於java文檔中的HashMap。我有一個關於HashMap一些小問題：

1. 我知道HashMap默認容量爲16。Java文檔，他們給默認的初始容量 - 必須是二的冪。。這背後的任何具體原因？
2. 我知道一點點如何HashMap基於HashCode，Bucket和LinkedList如果我沒有錯。那麼如何增加HashMap的尺寸。我的意思是如何管理桶大小和LinkedList大小。
3. 這可能是個愚蠢的問題。當我們在HashMap中添加新元素時，在HashCode的基礎上，它直接訪問那個特定的存儲桶而不像在LinkedList中那樣旅行。我對嗎？而其他的一點是，它增加了元素而不是尾巴。這是什麼原因。在桶內存在LinkedList的頭部添加新元素以避免尾部遍歷。我的想法是否正確？

Answer 1

1. 使用的兩個大國，簡化實施和提高其性能。
   例如要找到一個哈希碼可以使用哈希&（SIZE -1）水桶代替ABS（散）％SIZE

2. ，直到你知道你將如何HashMap的工作原理完全不能夠回答這個問題。如果地圖的大小超過由負載因子（例如，如果加載因子是.75，它將在填充75％後重新調整地圖大小。與ArrayList等其他集合類相似，Java HashMap通過創建一個尺寸爲前一個大小HashMap的兩倍的新存儲區陣列來重新調整大小，然後開始將每個舊元素放入新的存儲區陣列中。這個過程被稱爲重新哈希，因爲它也應用哈希函數來查找新的存儲桶位置。

3. 我們每一個新的元素存儲在鏈表的頭，以避免尾部橫動，因此在調整中鏈表對象的整個序列時被逆轉，在此期間，有無限循環的機會。

在這裏閱讀更多：

• http://java.dzone.com/articles/hashmap-internal
• http://javarevisited.blogspot.in/2011/02/how-hashmap-works-in-java.html

Answer 2

1. 我會假設，兩個規定的權力是有加快採摘桶。如果你有16個桶和一個578123的索引，你可以使用一個簡單的AND來選擇一個桶，而不必計算578123 mod 16，這是較慢的。

2. HashMap有一個加載因子，默認爲0.75。如果對象的數量>桶的數量*加載因子，HashMap的容量會增加以保持性能。我會認爲它只是將桶的數量加倍並重新分配所有元素。

3. 對不起，我不知道我是否正確理解這個問題。

Answer 3

1. 之所以提出的容量的2的冪是（我認爲）主要是爲了簡化代碼。性能優勢很小，但幾乎可以忽略不計。

2. 它是這樣的：當您嘗試添加新條目

   • 一個HashMap擴大。它發生（粗略地說）當map.size() * load_factor > array.length。 （請參閱代碼以瞭解詳細信息。）

   • 當展開HashMap時，數組的大小加倍。有一個硬限制...由Java中的數組大小所強加。之後，HasMap的數組不會擴展。 （相反，你只是得到更長和更長的哈希鏈......）

   • 沒有做任何事情來管理單個哈希鏈的長度。相反，當HashMap展開時，每個舊鏈中的條目都會移至展開表中的相應鏈中。 （至少在最近實現中，每個鏈節點保持爲條目緩存散列值，所以不需要表膨脹期間重新評估散列函數。）

3. 基本上，是的是。新的條目被添加到每個哈希鏈的開始，因爲這是最有效的（時間和空間）來做到這一點。由於哈希鏈中元素的順序不代表任何內容，所以在鏈的尾部插入新條目沒有意義。這也意味着在典型的HashMap實現中，展開表反轉哈希鏈條目的順序。

---

注意，實際行爲和HashMap實際實施細則對Java的不同版本不同。唯一確定的方法是閱讀您正在使用的Java版本的源代碼。