轉載自?HashMap 實現原理

HashMap是常考點，而一般不問List的幾個實現類(偏簡單)。以下基于JDK1.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：

1234	static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

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的次冪，所以計算下標的時候，可使用按位與&代替取模%：

1	(n - 1) & hash

設計者認為這方法很容易發生碰撞。為什么這么說呢？不妨思考一下，在n – 1為15(0×1111)時，散列真正生效的只是低4bit的有效位，當然容易碰撞了。

因此，設計者想了一個顧全大局的方法(綜合考慮了速度、作用、質量)，就是把高16bit和低16bit異或了一下。設計者還解釋到因為現在大多數的hashCode的分布已經很不錯了，就算是發生了碰撞也用O(logn)的tree去做了。僅僅異或一下，既減少了系統的開銷，也不會造成因為高位沒有參與下標的計算(table長度比較小)時，引起的碰撞。

但我沒有理解為什么“很”容易發生碰撞。如此設計的話，hash的分布是均勻的，且極其簡單；將高16bit與低16bit異或之后，hash的分布變的復雜一些，更“接近”隨機，但仍然是均勻的。估計作者是從實際使用的角度出發，因為一般情況下，key的分布也符合“局部性原理”，低比特位相同的概率大于異或后仍然相同的概率，從而降低了碰撞的概率。

碰撞

調用put方法時，盡管我們設法避免碰撞以提高HashMap的性能，還是可能發生碰撞。據說碰撞率還挺高，平均加載率到10%時就會開始碰撞。我們使用開放散列法來處理碰撞節點。

將舊entry的引用賦值給新entry的next屬性，改將新entry放在該位置——即在該位置上存儲一個鏈表，沖突節點從鏈表頭部插入，這樣插入新entry時不需要遍歷鏈表，時間復雜度為O(1)。但如果鏈表過長，查詢性能仍將退化到O(n)。Java8中對鏈表長度增加了一個閾值，超過閾值鏈表將轉化為紅黑樹，查詢時間復雜度降為O(logn)，提高了鏈表過長時的性能。

調用get方法時，定位到該位置，再遍歷紅黑樹，比較key值找到所需元素：

12345678910111213141516171819

final Node<K,V> getNode(int hash, Object key) {????Node<K,V>[] tab; Node<K,V> 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<K,V>)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示意圖：

這個設計非常的巧妙，新增的1bit是0還是1可以認為是隨機的，因此resize的過程均勻的把之前的沖突的節點分散到新的bucket中了。

參考：

• Java HashMap工作原理及實現 | Yikun

總結

以上是生活随笔為你收集整理的HashMap 实现原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。