HahsMap實現了Map接口。其繼承關系如下圖： 
HashMap有兩個影響性能的重要參數：初始容量和加載因子。容量是Hash表中桶的個數，當HashMap初始化時，容量就是初始容量。加載因子是衡量hash表多滿的一個指標，用來判斷是否需要增加容量。當HashMap需要增加容量時，將會導致rehash操作。 默認情況下，0.75的加載因子在時間和空間方面提供了很好的平衡。加載因子越大，增加了空間利用率但是也增加了查詢的時間。
在JDK1.7之前，HashMap采用的是數組+鏈表的結構，其結構圖如下： 
左邊部分代表Hash表，數組的每一個元素都是一個單鏈表的頭節點，鏈表是用來解決沖突的，如果不同的key映射到了數組的同一位置處，就將其放入單鏈表中。
JDK1.8之前的HashMap都采用上圖的結構，都是基于一個數組和多個單鏈表，hash值沖突的時候，就將對應節點以鏈表形式存儲。如果在一個鏈表中查找一個節點時，將會花費O(n)的查找時間，會有很大的性能損失。到了JDK1.8，當同一個Hash值的節點數不小于8時，不再采用單鏈表形式存儲，而是采用紅黑樹，如下圖所示： 
HashMap中有幾個重要的字段，如下：
//Hash表結構 transient Node<K,V>[] table; //元素個數 transient int size; //確保fail-fast機制 transient int modCount; //下一次增容前的閾值 int threshold; //加載因子 final float loadFactor; //默認初始容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //加載因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //鏈表轉紅黑樹的閾值 static final int TREEIFY_THRESHOLD = 8;HashMap一共有4個構造方法，主要的工作就是完成容量和加載因子的賦值。Hash表都是采用的懶加載方式，當第一次插入數據時才會創建。
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }HashMap允許K和V為null，添加一個鍵值對時使用put方法，如果之前已經存在K的鍵值，那么舊值將會被新值替換。實現如下：
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) { Node<K,V>[] tab; Node<K,V> p; int n, i; //如果哈希表為空或長度為0，調用resize()方法創建哈希表 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果哈希表中K對應的桶為空，那么該K，V對將成為該桶的頭節點 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //該桶處已有節點，即發生了哈希沖突 else { Node<K,V> e; K k; //如果添加的值與頭節點相同，將e指向p if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果與頭節點不同，并且該桶目前已經是紅黑樹狀態，調用putTreeVal()方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //桶中仍是鏈表階段 else { //遍歷，要比較是否與已有節點相同 for (int binCount = 0; ; ++binCount) { //將e指向下一個節點，如果是null，說明鏈表中沒有相同節點，添加到鏈表尾部即可 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果此時鏈表個數達到了8，那么需要將該桶處鏈表轉換成紅黑樹，treeifyBin()方法將hash處的桶轉成紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //如果與已有節點相同，跳出循環 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //如果有重復節點，那么需要返回舊值 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //子類實現 afterNodeaccess(e); return oldValue; } } //是一個全新節點，那么size需要+1 ++modCount; //如果超過了閾值，那么需要resize()擴大容量 if (++size > threshold) resize(); //子類實現 afterNodeInsertion(evict); return null; }從上面代碼可以看到putVal()方法的流程： 1. 判斷哈希表是否為空，如果為空，調用resize()方法進行創建哈希表 2. 根據hash值得到哈希表中桶的頭節點，如果為null，說明是第一個節點，直接調用newNode()方法添加節點即可 3. 如果發生了哈希沖突，那么首先會得到頭節點，比較是否相同，如果相同，則進行節點值的替換返回 4. 如果頭節點不相同，但是頭節點已經是TreeNode了，說明該桶處已經是紅黑樹了，那么調用putTreeVal()方法將該結點加入到紅黑樹中 5. 如果頭節點不是TreeNode，說明仍然是鏈表階段，那么就需要從頭開始遍歷，一旦找到了相同的節點就跳出循環或者直到了鏈表尾部，那么將該節點插入到鏈表尾部 6. 如果插入到鏈表尾部后，鏈表個數達到了閾值8，那么將會將該鏈表轉換成紅黑樹，調用treeifyBin()方法 7. 如果是新加一個數據，那么將size+1，此時如果size超過了閾值，那么需要調用resize()方法進行擴容
下面我們一個一個分析上面提到的方法。首先是resize()方法，resize()在哈希表為null時將會初始化，但是在已經初始化后就會進行容量擴展。下面是resize()的具體實現：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length;//舊表容量 int oldThr = threshold;//舊表與之 int newCap, newThr = 0; //舊表存在 if (oldCap > 0) { //舊表已經達到了最大容量，不能再大，直接返回舊表 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //否則，新容量為舊容量2倍，新閾值為舊閾值2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //如果就閾值>0，說明構造方法中指定了容量 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //初始化時沒有指定閾值和容量，使用默認的容量16和閾值16*0.75=12 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //更新閾值 threshold = newThr; //創建表,初始化或更新表 @Sup從上面可以看到，resize()首先獲取新容量以及新閾值，然后根據新容量創建新表。如果是擴容操作，則需要進行rehash操作，通過e.hash&oldCap將鏈表分為兩列，更好地均勻分布在新表中。 當頭節點是TreeNode時，將調用TreeNode的split方法將紅黑樹復制到新表中，代碼實現如下： final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this;//就是上面的頭結點e // Relink into lo and hi lists, preserving order //與鏈表rehash時類似，將紅黑樹分為兩部分 TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; //遍歷 for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next; e.next = null; //分散規則與rehash中相同 if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } //如果存在低端 if (loHead != null) { //如果分散后的紅黑樹節點小于等于6，將紅黑樹節點轉換成鏈表節點 if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; //將鏈表轉換成紅黑樹 if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } //如果存在高端 if (hiHead != null) { //如果分散后的紅黑樹節點小于等于6，將紅黑樹節點轉換成鏈表節點 if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; //將鏈表轉換成紅黑樹節點 if (loHead != null) hiHead.treeify(tab); } } }TreeNode的split方法首先將頭節點從頭開始遍歷，區分出兩條單鏈表，再根據如果節點數小于等于6，那么將單鏈表的每個TreeNode轉換成Node節點；否則將單鏈表轉換成紅黑樹結構。 至此，resize()方法結束。需要注意的是rehash時，由于容量擴大一倍，本來一條鏈表有可能會分成兩條鏈表，而如果將紅黑樹結構復制到新表時，有可能需要完成紅黑樹到單鏈表的轉換。
treeifyBin()方法將表中某一個桶處的單鏈表結果轉換成紅黑樹結構，其實現如下：
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //如果哈希表不存在，或者哈希表尺寸小于64，進行resize()擴容 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); //如果桶處頭節點不為null else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //將單鏈表節點轉換成TreeNode結構的單鏈表 do { //將Node轉換成TreeNode 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); //調用treeify將該TreeNode結構的單鏈表轉換成紅黑樹 if ((tab[index] = hd) != null) hd.treeify(tab); } }當調用put插入一個鍵值對時，在表為空時，會創建表。如果桶為空時，直接插入節點，如果桶不為空時，則需要對當前桶中包含的結構做判斷，如果已是紅黑樹結構，那么需要使用紅黑樹的插入方法；如果不是紅黑樹結構，則需要遍歷鏈表，如果添加到鏈表后端，如果該條鏈表達到了8，那么需要將該鏈表轉換成紅黑樹，從treeifyBin方法可以看到，當容量小于64時，不會進行紅黑樹轉換，只會擴容。當成功新加一個桶，那么需要將尺寸和閾值進行判斷，是否需要進行resize()操作。
get(K k)根據鍵得到值，如果值不存在，那么返回null。其實現如下：
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }//根據鍵的hash值和鍵得到對應節點final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //可以從桶中得到對應hash值的第一個節點 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) { //如果首節點是紅黑樹節點，調用getTreeNode()方法 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; }從上面代碼可以看到getNode()方法中有多種情況： 1. 表為空或表的長度為0或表中不存在key對應的hash值桶，那么返回null 2. 如果表中有key對應hash值的桶，得到首節點，如果首節點匹配，那么直接返回； 3. 如果首節點不匹配，并且沒有后續節點，那么返回null 4. 如果首節點有后續節點并且首節點是TreeNode,調用getTreeNode方法尋找節點 5. 如果首節點有后續節點并且是鏈表結構，那么從前往后遍歷，一旦找到則返回節點，否則返回null
remove(K k)用于根據鍵值刪除鍵值對，如果哈希表中存在該鍵，那么返回鍵對應的值，否則返回null。其實現如下：
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }//按照hash和key刪除節點，如果不存在節點，則返回nullfinal Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; //如果哈希表不為空并且存在桶與hash值匹配,p為桶中的頭節點 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; //case 1：如果頭節點匹配 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { //case2：如果頭節點不匹配，且頭節點是TreeNode，即桶中的結構為紅黑樹結構 if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { //case 3:如果頭節點不匹配，且頭節點是Node，即桶中的結構為鏈表結構，遍歷鏈表 do { //一旦匹配，跳出循環 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } //如果存在待刪除節點節點 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { //如果節點是TreeNode，使用紅黑樹的方法 if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); //如果待刪除節點是頭節點，更改桶中的頭節點即可 else if (node == p) tab[index] = node.next; //在鏈表遍歷過程中，p代表node節點的前驅節點 else p.next = node.next; ++modCount; --size; //子類實現 afterNodeRemoval(node); return node; } } return null; }從上面的代碼可以看出，removeNode()方法首先是找到待刪除的節點，如果存在待刪除節點，接下來再執行刪除操作。查詢時流程與getNode()方法的流程類似，只不過多了在遍歷鏈表時還需要保存前驅節點，因為后面刪除時要用到（單鏈表結構）。刪除節點時就比較簡單了，三種情況三種處理方式,分別是： 1. 如果待刪除節點是TreeNode，那么調用removeTreeNode()方法 2. 如果待刪除節點是Node，并且待刪除節點就是頭節點，那么將頭節點更改為原有節點的下一個節點就可以了 3. 如果待刪除節點是Node且待刪除節點不是頭節點，那么將遍歷過程中保存的前驅節點p的后繼節點設為node的后繼節點就可以了
至此，我們分析完了HashMap的主要方法：構造器、put、get和remove。只需要明白JDK1.8的HashMap底層結構，那么就很好理解了。需要注意的是什么時候應該將鏈表結構轉換成紅黑樹結構，什么時候又應該將紅黑樹結構重新轉換成鏈表結構，本文沒有具體解釋有關紅黑樹的結構，但是這并不影響理解HashMap的基本原理。 另外需要注意的是，本文的源碼是基于JDK1.8的。
新聞熱點
疑難解答
