HashMap是由數組加鏈表的結合體。如下圖：

圖中可以看出HashMap底層就是一個數組結構，每個數組中又存儲著鏈表（鏈表的引用）

JDK1.6實現hashmap的方式是采用位桶（數組）+鏈表的方式，即散列鏈表方式。JDK1.8則是采用位桶+鏈表/紅黑樹的方式，即當某個位桶的鏈表長度達到某個閾值（8）的時候，這個鏈表就轉化成紅黑樹，這樣大大減少了查找時間。

存儲查找原理：
- 存儲：首先獲取key的hashcode，然后取模數組的長度，這樣可以快速定位到要存儲到數組中的坐標，然后判斷數組中是否存儲元素，如果沒有存儲則，新構建Node節點，把Node節點存儲到數組中，如果有元素，則迭代鏈表(紅黑二叉樹)，如果存在此key,默認更新value,不存在則把新構建的Node存儲到鏈表的尾部。
- 查找：同上，獲取key的hashcode，通過hashcode取模數組的長度，獲取要定位元素的坐標，然后迭代鏈表，進行每一個元素的key的equals對比，如果相同則返回該元素。

HashMap在相同元素個數時，數組的長度越大，則Hash的碰撞率越低，則讀取的效率就越高，數組長度越小，則碰撞率高，讀取速度就越慢。典型的空間換時間的例子。

下面我們分析HashMap的源碼：

HashMap的結構屬性：

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {//存儲數據的Node數組transient Node<K,V>[] table;//返回Map中所包含的Map.Entry<K,V>的Set視圖。transient Set<Map.Entry<K,V>> entrySet;//當前存儲元素的總個數transient int size;//HashMap內部結構發生變化的次數，主要用于迭代的快速失敗（下面代碼有分析此變量的作用）transient int modCount;//下次擴容的臨界值，size>=threshold就會擴容，threshold等于capacity*load factorint threshold;//裝載因子final float loadFactor;//默認裝載因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//由鏈表轉換成紅黑樹的閾值TREEIFY_THRESHOLDstatic final int TREEIFY_THRESHOLD = 8;//由紅黑樹的閾值轉換鏈表成UNTREEIFY_THRESHOLDstatic final int UNTREEIFY_THRESHOLD = 6;//默認容量（16）static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//數組的最大容量 （1073741824）static final int MAXIMUM_CAPACITY = 1 << 30;//當桶中的bin(鏈表中的元素)被樹化時最小的hash表容量。（如果沒有達到這個閾值，即hash表容量小于MIN_TREEIFY_CAPACITY，當桶中bin的數量太多時會執行resize擴容操作）這個MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。static final int MIN_TREEIFY_CAPACITY = 64;略...

鏈表的結構

static class Node<K,V> implements Map.Entry<K,V> {//hashfinal int hash;final K key;V value;Node<K,V> next;略...

紅黑二叉樹的結構

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // 父節點TreeNode<K,V> left; //左節點TreeNode<K,V> right; //右節點TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;

HashMap.put（key, value）插入方法

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//p：鏈表節點 n:數組長度 i：鏈表所在數組中的索引坐標Node<K,V>[] tab; Node<K,V> p; int n, i;//判斷tab[]數組是否為空或長度等于0，進行初始化擴容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//判斷tab指定索引位置是否有元素，沒有則，直接newNode賦值給tab[i]if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);//如果該數組位置存在Nodeelse {//首先先去查找與待插入鍵值對key相同的Node，存儲在e中，k是那個節點的keyNode<K,V> e; K k;//判斷key是否已經存在(hash和key都相等)if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//如果Node是紅黑二叉樹，則執行樹的插入操作else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//否則執行鏈表的插入操作（說明Hash值碰撞了，把Node加入到鏈表中）else {for (int binCount = 0; ; ++binCount) {//如果該節點是尾節點，則進行添加操作if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//判斷如果鏈表長度，如果鏈表長度大于8則調用treeifyBin方法，判斷是擴容還是把鏈表轉換成紅黑二叉樹if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//如果鍵值存在，則退出循環if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;//把p執行p的子節點，開始下一次循環（p = e = p.next）p = e;}}//在循環中判斷e是否為null，如果為null則表示加了一個新節點，不是null則表示找到了hash、key都一致的Node。if (e != null) { // existing mapping for keyV oldValue = e.value;//判斷是否更新value值。（map提供putIfAbsent方法，如果key存在，不更新value，但是如果value==null任何情況下都更改此值）if (!onlyIfAbsent || oldValue == null)e.value = value;//此方法是空方法，什么都沒實現，用戶可以根據需要進行覆蓋afterNodeAccess(e);return oldValue;}}//只有插入了新節點才進行++modCount；++modCount;//如果size>threshold則開始擴容（每次擴容原來的1倍）if (++size > threshold)resize();//此方法是空方法，什么都沒實現，用戶可以根據需要進行覆蓋afterNodeInsertion(evict);return null;}

1.判斷鍵值對數組tab[i]是否為空或為null，否則執行resize()進行擴容；

2.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接新建節點添加，轉向6，如果table[i]不為空，轉向3；

3.判斷鏈表（或二叉樹）的首個元素是否和key一樣，不一樣轉向④，相同轉向6；

4.判斷鏈表（或二叉樹）的首節點 是否為treeNode，即是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，不是則執行5；

5.遍歷鏈表，判斷鏈表長度是否大于8，大于8的話把鏈表轉換為紅黑樹（還判斷數組長度是否小于64，如果小于只是擴容，不進行轉換二叉樹），在紅黑樹中執行插入操作，否則進行鏈表的插入操作；遍歷過程中若發現key已經存在直接覆蓋value即可；如果調用putIfAbsent方法插入，則不更新值（只更新值為null的元素）。

6.插入成功后，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}}

1、首先判斷數組的長度是否小于64，如果小于64則進行擴容
2、否則把鏈表結構轉換成紅黑二叉樹結構

modCount 變量的作用

public final void forEach(Consumer<? super K> action) {Node<K,V>[] tab;if (action == null)throw new NullPointerException();if (size > 0 && (tab = table) != null) {int mc = modCount;for (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next)action.accept(e.key);}if (modCount != mc)throw new ConcurrentModificationException();}}

從forEach循環中可以發現 modCount 參數的作用。就是在迭代器迭代輸出Map中的元素時，不能編輯（增加，刪除，修改）Map中的元素。如果在迭代時修改，則拋出ConcurrentModificationException異常。

疑問解答：

1、hash取余數，為什么不用取模操作呢，而用tab[i = (n - 1) & hash]？

它通過 (n - 1) & hash來得到該對象的保存位，而HashMap底層數組的長度總是2的n次方，這是HashMap在速度上的優化。當length總是2的n次方時， (n - 1) & hash運算等價于對length取模，也就是h%length，但是&比%具有更高的效率。

2、為什么使用紅黑二叉樹呢？

因為在好的算法，也避免不了hash的碰撞，避免不了鏈表過長的的情況，一旦出現鏈表過長，則嚴重影響到HashMap的性能。JDK8對HashMap做了優化，把鏈表長度超過8個的，則改成紅黑二叉樹，提高訪問的速度。

????本人簡書blog地址：http://www.jianshu.com/u/1f0067e24ff8
????點擊這里快速進入簡書

總結

以上是生活随笔為你收集整理的HashMap 源码解析(JDK1.8)的全部內容，希望文章能夠幫你解決所遇到的問題。

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