HashMap是常考點，而一般不問List的幾個實現類(偏簡單)。HashMap 的實例有兩個參數影響其性能：初始容量和加載因子。基於哈希表的Map接口的實現。此實現提供所有可選的映射操作，並允許使用null值和null鍵。
以下基於JDK1.8.0_102分析。
JDK版本：oracle java 1.8.0_102
內部存儲
HashMap的內部存儲是一個數組（bucket），數組的元素Node實現了是Map.Entry接口(hash, key, value, next)，next非空時指向定位相同的另一個Entry，如圖：
容量(capacity)和負載因子(loadFactor)
簡單的說，capacity就是bucket的大小，loadFactor就是bucket填滿程度的最大比例。當bucket中的entries的數目(而不是已佔用的位置數)大於capacity*loadFactor時就需要擴容，調整bucket的大小為當前的2倍。同時，初始化容量的大小也是2的次冪（大於等於設定容量的最小次冪），則bucket的大小在擴容前後都將是2的次冪（非常重要，resize時能帶來極大便利）。
Tips:
默認的capacity為16，loadFactor為0.75，但如果需要優化的話，要考量具體的使用場景。
- 如果對迭代性能要求高，不要把capacity設置過大，也不要把loadFactor設置過小，否則會導致bucket中的空位置過多，浪費性能
- 如果對隨機訪問的性能要求很高的話，不要把loadFactor設置的過大，否則會導致訪問時頻繁碰撞，時間複雜度向O(n)退化
- 如果數據增長很快的話，或數據規模可預知，可以在創建HashMap時主動設置capacity
hash與定位
作為API的設計者，不能假定用戶實現了良好的hashCode方法，所以通常會對hashCode再計算一次hash：
<code>static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}/<code>hashCode方法
注意key.hashCode()的多態用法。重點是hash方法。
hash方法的實現和定位
前面已經說過，在get和put計算下標時，先對hashCode進行hash操作，然後再通過hash值進一步計算下標，如下圖所示：
回顧hash方法的源碼可知，hash方法大概的作用就是：高16bit不變，低16bit和高16bit做了一個異或。
javadoc這樣說：
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.
在設計hash函數時，因為目前的table長度n為2的次冪，所以計算下標的時候，可使用按位與&代替取模%：
<code>(n - 1) & hash/<code>
設計者認為這方法很容易發生碰撞。為什麼這麼說呢？不妨思考一下，在n - 1為15(0x1111)時，散列真正生效的只是低4bit的有效位，當然容易碰撞了。
因此，設計者想了一個顧全大局的方法(綜合考慮了速度、作用、質量)，就是把高16bit和低16bit異或了一下。設計者還解釋到因為現在大多數的hashCode的分佈已經很不錯了，就算是發生了碰撞也用O(logn)的tree去做了。僅僅異或一下，既減少了系統的開銷，也不會造成因為高位沒有參與下標的計算(table長度比較小)時，引起的碰撞。
好吧，我還是不理解為什麼“很”容易發生碰撞。難道hash的分佈不是均勻的嗎？
碰撞
調用put方法時，儘管我們設法避免碰撞以提高HashMap的性能，還是可能發生碰撞。據說碰撞率還挺高，平均加載率到10%時就會開始碰撞。我們使用拉鍊法來處理碰撞節點。
將舊entry的引用賦值給新entry的next屬性，改將新entry放在該位置——即在該位置上存儲一個鏈表，衝突節點從鏈表頭部插入，這樣插入新entry時不需要遍歷鏈表，時間複雜度為O(1)。但如果鏈表過長，查詢性能仍將退化到O(n)。Java8中對鏈表長度增加了一個閾值，超過閾值鏈表將轉化為紅黑樹，查詢時間複雜度降為O(logn)，提高了鏈表過長時的性能。
勘誤：網上有朋友聯繫我指出了此處的錯誤，Java8中，發生碰撞時會遍歷到鏈表的最後。
這篇文章寫的時候讀源碼能力比較渣，就基於自己早期對Java7源碼的分析改編，本以為除了紅黑樹部分，大體相同，就直接copy了過來，導致了這個錯誤——當然，現在想來，關於Java7中HashMap的分析也是錯的，最後插入方式沒錯，但是插入前還是要O(n)的時間遍歷一遍。不過其他涉及源碼的文章就都是老老實實追源碼寫出來的，可以放心閱讀。
告誡自己，要堅持踏實，堅持懷疑。以下是改正的分析。從該位置上的entry開始，遍歷到找到相同的key（就替換），或到結尾還是沒有相同的key（就銜接在尾節點的next上）。查詢時過程相同。不考慮任何優化，插入、查詢的性能都是O(n)。Java8中對鏈表長度增加了一個閾值，超過閾值鏈表將轉化為紅黑樹，插入、查詢的時間複雜度降為O(logn)，提高了鏈表過長時的性能。調用get方法時，定位到該位置，再遍歷紅黑樹，比較key值找到所需元素：
<code>final NodegetNode(int hash, Object key) { /<code>
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
判斷元素相等的設計比較經典，利用了bool表達式的短路特性：先比較hash值；如果hash值相等，就通過==比較；如果==不等，再通過equals方法比較。hash是提前計算好的；==直接比較引用值；equals方法最有可能耗費性能，如String的equals方法需要O(n)的時間，n是字符串長度。一定要記住這裡的判斷順序，很能考察對碰撞處理源碼的理解。
針對HashMap的使用，此處要注意覆寫hashCode和equals方法時的兩個重點：
- 覆寫後，一定要保證equals判斷相等的時候，hashCode的返回值也相等。
- 對於選作key的類，要保證調用put與get時hashCode的返回值相等，equals的性質相同。
resize
resize是HashMap中最難理解的部分。
調用put方法時，如果發現目前的bucket佔用程度已經超過了loadFactor，就會發生resize。簡單的說就是把bucket擴充為2倍，之後重新計算index，把節點再放到新的bucket中。
javadoc中這樣說：
Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
即，當超過限制的時候會resize，又因為我們使用的是2次冪的擴展，所以，元素的位置要麼是在原位置，要麼是在原位置再移動2次冪的位置。
怎麼理解呢？例如我們從16擴展為32時，具體的變化如下：
假設bucket大小n=2^k，元素在重新計算hash之後，因為n變為2倍,那麼新的位置就是(2^(k+1)-1)&hash。而2^(k+1)-1=2^k+2^k-1，相當於2^k-1的mask範圍在高位多1bit(紅色)(再次提醒，原來的長度n也是2的次冪)，這1bit非1即0。如圖：
所以，我們在resize的時候，不需要重新定位，只需要看看原來的hash值在新增bit的位置上是1還是0就好了，是0的話位置沒變，是1的話位置變成“原位置+oldCap”。代碼比較長就不貼了，下面為16擴充為32的resize示意圖：
這個設計非常的巧妙，如果認為hash值是隨機的，那麼新增的1bit是0還是1也是隨機的，因此resize的過程隨機的把之前的衝突的節點分散到新的bucket中了。
關注我：轉發+私信回覆“架構資料”獲取往期Java高級架構資料、源碼、筆記、視頻
Dubbo、Redis、設計模式、Netty、zookeeper、Spring cloud、分佈式、微服務
高併發等架構技術
讀者福利
Java高級架構資料
最後的話
為什麼某些人會一直比你優秀，是因為他本身就很優秀還一直在持續努力變得更優秀。而你是不是還在滿足於現狀且內心在竊喜?“對於程序員來說，如果哪一天開始他停止了學習，那麼他的職業生涯便開始宣告消亡。”所以行動起來，學習起來！
關注我：轉發+私信回覆“架構資料”獲取往期Java高級架構資料、源碼、筆記、視頻 Dubbo、Redis、設計模式、Netty、zookeeper、Spring cloud、分佈式、微服務高併發等架構技術。
閱讀更多 Java阿南 的文章
