Java集合篇：HashMap原理详解（JDK1.8）
生活随笔
收集整理的這篇文章主要介紹了
Java集合篇：HashMap原理详解（JDK1.8）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
概述
JDK 1.8對HashMap進行了比較大的優化，底層實現由之前的“數組+鏈表”改為“數組+鏈表+紅黑樹”，本文就HashMap的幾個常用的重要方法和JDK 1.8之前的死循環問題展開學習討論。JDK 1.8的HashMap的數據結構如下圖所示，當鏈表節點較少時仍然是以鏈表存在，當鏈表節點較多時（大于8）會轉為紅黑樹。
?
幾個點：
先了解以下幾個點，有利于更好的理解HashMap的源碼和閱讀本文。
?
基本屬性
/*** The default initial capacity - MUST be a power of two.*/ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認容量16/*** The maximum capacity, used if a higher value is implicitly specified* by either of the constructors with arguments.* MUST be a power of two <= 1<<30.*/ static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量/*** The load factor used when none specified in constructor.*/ static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默認負載因子0.75/*** The bin count threshold for using a tree rather than list for a* bin. Bins are converted to trees when adding an element to a* bin with at least this many nodes. The value must be greater* than 2 and should be at least 8 to mesh with assumptions in* tree removal about conversion back to plain bins upon* shrinkage.*/ static final int TREEIFY_THRESHOLD = 8; // 鏈表節點轉換紅黑樹節點的閾值, 8個節點轉/*** The bin count threshold for untreeifying a (split) bin during a* resize operation. Should be less than TREEIFY_THRESHOLD, and at* most 6 to mesh with shrinkage detection under removal.*/ static final int UNTREEIFY_THRESHOLD = 6; // 紅黑樹節點轉換鏈表節點的閾值, 6個節點轉/*** The smallest table capacity for which bins may be treeified.* (Otherwise the table is resized if too many nodes in a bin.)* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts* between resizing and treeification thresholds.*/ static final int MIN_TREEIFY_CAPACITY = 64; // 轉紅黑樹時, table的最小長度/*** Basic hash bin node, used for most entries. (See below for* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)*/ static class Node<K,V> implements Map.Entry<K,V> { // 基本hash節點, 繼承自Entryfinal int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final K getKey() { return key; }public final V getValue() { return value; }public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (o == this)return true;if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;} }/*** Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn* extends Node) so can be used as extension of either regular or* linked node.*/ static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {// 紅黑樹節點TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}// ... }?
?
定位哈希桶數組索引位置
不管增加、刪除、查找鍵值對，定位到哈希桶數組的位置都是很關鍵的第一步。前面說過HashMap的數據結構是“數組+鏈表+紅黑樹”的結合，所以我們當然希望這個HashMap里面的元素位置盡量分布均勻些，盡量使得每個位置上的元素數量只有一個，那么當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，不用遍歷鏈表/紅黑樹，大大優化了查詢的效率。HashMap定位數組索引位置，直接決定了hash方法的離散性能。下面是定位哈希桶數組的源碼：
// 代碼1 static final int hash(Object key) { // 計算key的hash值int h;// 1.先拿到key的hashCode值; 2.將hashCode的高16位參與運算return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 代碼2 int n = tab.length; // 將(tab.length - 1) 與 hash值進行&運算 int index = (n - 1) & hash;整個過程本質上就是三步：
?
方法解讀：
對于任意給定的對象，只要它的hashCode()返回值相同，那么計算得到的hash值總是相同的。我們首先想到的就是把hash值對table長度取模運算，這樣一來，元素的分布相對來說是比較均勻的。
但是模運算消耗還是比較大的，我們知道計算機比較快的運算為位運算，因此JDK團隊對取模運算進行了優化，使用上面代碼2的位與運算來代替模運算。這個方法非常巧妙，它通過 “(table.length -1) &?h” 來得到該對象的索引位置，這個優化是基于以下公式：x mod 2^n = x & (2^n - 1)。我們知道HashMap底層數組的長度總是2的n次方，并且取模運算為“h mod table.length”，對應上面的公式，可以得到該運算等同于“h & (table.length - 1)”。這是HashMap在速度上的優化，因為&比%具有更高的效率。
在JDK1.8的實現中，還優化了高位運算的算法，將hashCode的高16位與hashCode進行異或運算，主要是為了在table的length較小的時候，讓高位也參與運算，并且不會有太大的開銷。
下圖是一個簡單的例子，table長度為16：
?
get方法
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value; }final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// table不為空 && table長度大于0 && table索引位置(根據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; // first的key等于傳入的key則返回first對象if ((e = first.next) != null) { // 向下遍歷if (first instanceof TreeNode) // 判斷是否為TreeNode// 如果是紅黑樹節點，則調用紅黑樹的查找目標節點方法getTreeNodereturn ((TreeNode<K,V>)first).getTreeNode(hash, key);// 走到這代表節點為鏈表節點do { // 向下遍歷鏈表, 直至找到節點的key和傳入的key相等時,返回該節點if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null; // 找不到符合的返回空 }?
代碼塊1：getTreeNode方法
final TreeNode<K,V> getTreeNode(int h, Object k) {// 使用根結點調用find方法return ((parent != null) ? root() : this).find(h, k, null); }?
代碼塊2：find方法
/*** 從調用此方法的結點開始查找, 通過hash值和key找到對應的節點* 此處是紅黑樹的遍歷, 紅黑樹是特殊的自平衡二叉查找樹* 平衡二叉查找樹的特點：左節點<根節點<右節點*/ final TreeNode<K,V> find(int h, Object k, Class<?> kc) { TreeNode<K,V> p = this; // this為調用此方法的節點do {int ph, dir; K pk;TreeNode<K,V> pl = p.left, pr = p.right, q;if ((ph = p.hash) > h) // 傳入的hash值小于p節點的hash值, 則往p節點的左邊遍歷p = pl; // p賦值為p節點的左節點else if (ph < h) // 傳入的hash值大于p節點的hash值, 則往p節點的右邊遍歷p = pr; // p賦值為p節點的右節點// 傳入的hash值和key值等于p節點的hash值和key值,則p節點為目標節點,返回p節點else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p;else if (pl == null) // p節點的左節點為空則將向右遍歷p = pr; else if (pr == null) // p節點的右節點為空則向左遍歷p = pl;else if ((kc != null ||// 如果傳入的key(k)所屬的類實現了Comparable接口,則將傳入的key跟p節點的key比較(kc = comparableClassFor(k)) != null) && // 此行不為空代表k實現了Comparable(dir = compareComparables(kc, k, pk)) != 0)//k<pk則dir<0, k>pk則dir>0p = (dir < 0) ? pl : pr; // k < pk則向左遍歷(p賦值為p的左節點), 否則向右遍歷// 代碼走到此處, 代表key所屬類沒有實現Comparable, 直接指定向p的右邊遍歷else if ((q = pr.find(h, k, kc)) != null) return q;else// 代碼走到此處代表上一個向右遍歷（pr.find(h, k, kc)）為空, 因此直接向左遍歷p = pl; } while (p != null);return null; }?
代碼塊3：comparableClassFor方法
/*** Returns x's Class if it is of the form "class C implements* Comparable<C>", else null.*/ static Class<?> comparableClassFor(Object x) {if (x instanceof Comparable) {Class<?> c; Type[] ts, as; Type t; ParameterizedType p;if ((c = x.getClass()) == String.class) // bypass checksreturn c;if ((ts = c.getGenericInterfaces()) != null) {for (int i = 0; i < ts.length; ++i) {if (((t = ts[i]) instanceof ParameterizedType) &&((p = (ParameterizedType)t).getRawType() ==Comparable.class) &&(as = p.getActualTypeArguments()) != null &&as.length == 1 && as[0] == c) // type arg is creturn c;}}}return null; }如果x實現了Comparable接口，則返回 x的Class。
?
put方法
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;// table是否為空或者length等于0, 如果是則調用resize方法進行初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length; // 通過hash值計算索引位置, 如果table表該索引位置節點為空則新增一個if ((p = tab[i = (n - 1) & hash]) == null)// 將索引位置的頭節點賦值給ptab[i] = newNode(hash, key, value, null);else { // table表該索引位置不為空Node<K,V> e; K k;if (p.hash == hash && // 判斷p節點的hash值和key值是否跟傳入的hash值和key值相等((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果相等, 則p節點即為要查找的目標節點，賦值給e// 判斷p節點是否為TreeNode, 如果是則調用紅黑樹的putTreeVal方法查找目標節點else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else { // 走到這代表p節點為普通鏈表節點for (int binCount = 0; ; ++binCount) { // 遍歷此鏈表, binCount用于統計節點數if ((e = p.next) == null) { // p.next為空代表不存在目標節點則新增一個節點插入鏈表尾部p.next = newNode(hash, key, value, null);// 計算節點是否超過8個, 減一是因為循環是從p節點的下一個節點開始的if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);// 如果超過8個，調用treeifyBin方法將該鏈表轉換為紅黑樹break;}if (e.hash == hash && // e節點的hash值和key值都與傳入的相等, 則e即為目標節點,跳出循環((k = e.key) == key || (key != null && key.equals(k)))) break;p = e; // 將p指向下一個節點}}// e不為空則代表根據傳入的hash值和key值查找到了節點,將該節點的value覆蓋,返回oldValueif (e != null) { V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e); // 用于LinkedHashMapreturn oldValue;}}++modCount;if (++size > threshold) // 插入節點后超過閾值則進行擴容resize();afterNodeInsertion(evict); // 用于LinkedHashMapreturn null; }?
代碼塊4：putTreeVal方法
/*** Tree version of putVal.* 紅黑樹插入會同時維護原來的鏈表屬性, 即原來的next屬性*/ final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {Class<?> kc = null;boolean searched = false;// 查找根節點, 索引位置的頭節點并不一定為紅黑樹的根結點TreeNode<K,V> root = (parent != null) ? root() : this; for (TreeNode<K,V> p = root;;) { // 將根節點賦值給p, 開始遍歷int dir, ph; K pk;if ((ph = p.hash) > h) // 如果傳入的hash值小于p節點的hash值 dir = -1; // 則將dir賦值為-1, 代表向p的左邊查找樹else if (ph < h) // 如果傳入的hash值大于p節點的hash值,dir = 1; // 則將dir賦值為1, 代表向p的右邊查找樹// 如果傳入的hash值和key值等于p節點的hash值和key值, 則p節點即為目標節點, 返回p節點else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p;// 如果k所屬的類沒有實現Comparable接口 或者 k和p節點的key相等else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { // 第一次符合條件, 該方法只有第一次才執行TreeNode<K,V> q, ch;searched = true;// 從p節點的左節點和右節點分別調用find方法進行查找, 如果查找到目標節點則返回if (((ch = p.left) != null &&(q = ch.find(h, k, kc)) != null) ||((ch = p.right) != null &&(q = ch.find(h, k, kc)) != null)) return q;}// 否則使用定義的一套規則來比較k和p節點的key的大小, 用來決定向左還是向右查找dir = tieBreakOrder(k, pk); // dir<0則代表k<pk，則向p左邊查找；反之亦然}TreeNode<K,V> xp = p; // xp賦值為x的父節點,中間變量,用于下面給x的父節點賦值// dir<=0則向p左邊查找,否則向p右邊查找,如果為null,則代表該位置即為x的目標位置if ((p = (dir <= 0) ? p.left : p.right) == null) { // 走進來代表已經找到x的位置，只需將x放到該位置即可Node<K,V> xpn = xp.next; // xp的next節點 // 創建新的節點, 其中x的next節點為xpn, 即將x節點插入xp與xpn之間TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) // 如果時dir <= 0, 則代表x節點為xp的左節點xp.left = x;else // 如果時dir> 0, 則代表x節點為xp的右節點xp.right = x;xp.next = x; // 將xp的next節點設置為xx.parent = x.prev = xp; // 將x的parent和prev節點設置為xp// 如果xpn不為空,則將xpn的prev節點設置為x節點,與上文的x節點的next節點對應if (xpn != null) ((TreeNode<K,V>)xpn).prev = x;moveRootToFront(tab, balanceInsertion(root, x)); // 進行紅黑樹的插入平衡調整return null;}} }?
代碼塊5：tieBreakOrder方法
// 用于不可比較或者hashCode相同時進行比較的方法, 只是一個一致的插入規則，用來維護重定位的等價性。 static int tieBreakOrder(Object a, Object b) { int d;if (a == null || b == null ||(d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1 : 1);return d; }定義一套規則用于極端情況下比較兩個參數的大小。
?
代碼塊6：treeifyBin方法
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// table為空或者table的長度小于64, 進行擴容if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();// 根據hash值計算索引值, 遍歷該索引位置的鏈表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) // tl為空代表為第一次循環hd = p; // 頭結點else {p.prev = tl; // 當前節點的prev屬性設為上一個節點tl.next = p; // 上一個節點的next屬性設置為當前節點}tl = p; // tl賦值為p, 在下一次循環中作為上一個節點} while ((e = e.next) != null); // e指向下一個節點// 將table該索引位置賦值為新轉的TreeNode的頭節點if ((tab[index] = hd) != null) hd.treeify(tab); // 以頭結點為根結點, 構建紅黑樹} }?
代碼塊7：treeify方法
final void treeify(Node<K,V>[] tab) { // 構建紅黑樹TreeNode<K,V> root = null;for (TreeNode<K,V> x = this, next; x != null; x = next) {// this即為調用此方法的TreeNodenext = (TreeNode<K,V>)x.next; // next賦值為x的下個節點x.left = x.right = null; // 將x的左右節點設置為空if (root == null) { // 如果還沒有根結點, 則將x設置為根結點x.parent = null; // 根結點沒有父節點x.red = false; // 根結點必須為黑色root = x; // 將x設置為根結點}else {K k = x.key; // k賦值為x的keyint h = x.hash; // h賦值為x的hash值Class<?> kc = null;// 如果當前節點x不是根結點, 則從根節點開始查找屬于該節點的位置for (TreeNode<K,V> p = root;;) { int dir, ph;K pk = p.key; if ((ph = p.hash) > h) // 如果x節點的hash值小于p節點的hash值dir = -1; // 則將dir賦值為-1, 代表向p的左邊查找else if (ph < h) // 與上面相反, 如果x節點的hash值大于p節點的hash值dir = 1; // 則將dir賦值為1, 代表向p的右邊查找// 走到這代表x的hash值和p的hash值相等，則比較key值else if ((kc == null && // 如果k沒有實現Comparable接口 或者 x節點的key和p節點的key相等(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0)// 使用定義的一套規則來比較x節點和p節點的大小，用來決定向左還是向右查找dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; // xp賦值為x的父節點,中間變量用于下面給x的父節點賦值// dir<=0則向p左邊查找,否則向p右邊查找,如果為null,則代表該位置即為x的目標位置if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; // x的父節點即為最后一次遍歷的p節點if (dir <= 0) // 如果時dir <= 0, 則代表x節點為父節點的左節點xp.left = x;else // 如果時dir > 0, 則代表x節點為父節點的右節點xp.right = x;// 進行紅黑樹的插入平衡(通過左旋、右旋和改變節點顏色來保證當前樹符合紅黑樹的要求)root = balanceInsertion(root, x); break;}}}}moveRootToFront(tab, root); // 如果root節點不在table索引位置的頭結點, 則將其調整為頭結點 }?
代碼塊8：moveRootToFront方法
/*** 如果當前索引位置的頭節點不是root節點, 則將root的上一個節點和下一個節點進行關聯, * 將root放到頭節點的位置, 原頭節點放在root的next節點上*/ static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {int n;if (root != null && tab != null && (n = tab.length) > 0) {int index = (n - 1) & root.hash;TreeNode<K,V> first = (TreeNode<K,V>)tab[index];if (root != first) { // 如果root節點不是該索引位置的頭節點Node<K,V> rn;tab[index] = root; // 將該索引位置的頭節點賦值為root節點TreeNode<K,V> rp = root.prev; // root節點的上一個節點// 如果root節點的下一個節點不為空, // 則將root節點的下一個節點的prev屬性設置為root節點的上一個節點if ((rn = root.next) != null) ((TreeNode<K,V>)rn).prev = rp; // 如果root節點的上一個節點不為空, // 則將root節點的上一個節點的next屬性設置為root節點的下一個節點if (rp != null) rp.next = rn;if (first != null) // 如果原頭節點不為空, 則將原頭節點的prev屬性設置為root節點first.prev = root;root.next = first; // 將root節點的next屬性設置為原頭節點root.prev = null;}assert checkInvariants(root); // 檢查樹是否正常} }?
代碼塊9：checkInvariants方法
/*** Recursive invariant check*/ static <K,V> boolean checkInvariants(TreeNode<K,V> t) { // 一些基本的校驗TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,tb = t.prev, tn = (TreeNode<K,V>)t.next;if (tb != null && tb.next != t)return false;if (tn != null && tn.prev != t)return false;if (tp != null && t != tp.left && t != tp.right)return false;if (tl != null && (tl.parent != t || tl.hash > t.hash))return false;if (tr != null && (tr.parent != t || tr.hash < t.hash))return false;if (t.red && tl != null && tl.red && tr != null && tr.red) // 如果當前節點為紅色, 則該節點的左右節點都不能為紅色return false;if (tl != null && !checkInvariants(tl))return false;if (tr != null && !checkInvariants(tr))return false;return true; }將傳入的節點作為根結點，遍歷所有節點，校驗節點的合法性，主要是保證該樹符合紅黑樹的規則。
?
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) { // 老table不為空if (oldCap >= MAXIMUM_CAPACITY) { // 老table的容量超過最大容量值threshold = Integer.MAX_VALUE; // 設置閾值為Integer.MAX_VALUEreturn oldTab;}// 如果容量*2<最大容量并且>=16, 則將閾值設置為原來的兩倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // 老表的容量為0, 老表的閾值大于0, 是因為初始容量被放入閾值newCap = oldThr; // 則將新表的容量設置為老表的閾值 else { // 老表的容量為0, 老表的閾值為0, 則為空表，設置默認容量和閾值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; // 將當前閾值賦值為剛計算出來的新的閾值@SuppressWarnings({"rawtypes","unchecked"})// 定義新表,容量為剛計算出來的新容量Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab; // 將當前的表賦值為新定義的表if (oldTab != null) { // 如果老表不為空, 則需遍歷將節點賦值給新表for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) { // 將索引值為j的老表頭節點賦值給eoldTab[j] = null; // 將老表的節點設置為空, 以便垃圾收集器回收空間// 如果e.next為空, 則代表老表的該位置只有1個節點, // 通過hash值計算新表的索引位置, 直接將該節點放在該位置if (e.next == null) newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// 調用treeNode的hash分布(跟下面最后一個else的內容幾乎相同)((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve orderNode<K,V> loHead = null, loTail = null; // 存儲跟原索引位置相同的節點Node<K,V> hiHead = null, hiTail = null; // 存儲索引位置為:原索引+oldCap的節點Node<K,V> next;do {next = e.next;//如果e的hash值與老表的容量進行與運算為0,則擴容后的索引位置跟老表的索引位置一樣if ((e.hash & oldCap) == 0) { if (loTail == null) // 如果loTail為空, 代表該節點為第一個節點loHead = e; // 則將loHead賦值為第一個節點else loTail.next = e; // 否則將節點添加在loTail后面loTail = e; // 并將loTail賦值為新增的節點}//如果e的hash值與老表的容量進行與運算為1,則擴容后的索引位置為:老表的索引位置＋oldCapelse { if (hiTail == null) // 如果hiTail為空, 代表該節點為第一個節點hiHead = e; // 則將hiHead賦值為第一個節點elsehiTail.next = e; // 否則將節點添加在hiTail后面hiTail = e; // 并將hiTail賦值為新增的節點}} while ((e = next) != null);if (loTail != null) {loTail.next = null; // 最后一個節點的next設為空newTab[j] = loHead; // 將原索引位置的節點設置為對應的頭結點}if (hiTail != null) {hiTail.next = null; // 最后一個節點的next設為空newTab[j + oldCap] = hiHead; // 將索引位置為原索引+oldCap的節點設置為對應的頭結點}}}}}return newTab; }?
代碼塊10：split方法
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {TreeNode<K,V> b = this; // 拿到調用此方法的節點TreeNode<K,V> loHead = null, loTail = null; // 存儲跟原索引位置相同的節點TreeNode<K,V> hiHead = null, hiTail = null; // 存儲索引位置為:原索引+oldCap的節點int lc = 0, hc = 0;for (TreeNode<K,V> e = b, next; e != null; e = next) { // 從b節點開始遍歷next = (TreeNode<K,V>)e.next; // next賦值為e的下個節點e.next = null; // 同時將老表的節點設置為空，以便垃圾收集器回收//如果e的hash值與老表的容量進行與運算為0,則擴容后的索引位置跟老表的索引位置一樣if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) // 如果loTail為空, 代表該節點為第一個節點loHead = e; // 則將loHead賦值為第一個節點elseloTail.next = e; // 否則將節點添加在loTail后面loTail = e; // 并將loTail賦值為新增的節點++lc; // 統計原索引位置的節點個數}//如果e的hash值與老表的容量進行與運算為1,則擴容后的索引位置為:老表的索引位置＋oldCapelse { if ((e.prev = hiTail) == null) // 如果hiHead為空, 代表該節點為第一個節點hiHead = e; // 則將hiHead賦值為第一個節點elsehiTail.next = e; // 否則將節點添加在hiTail后面hiTail = e; // 并將hiTail賦值為新增的節點++hc; // 統計索引位置為原索引+oldCap的節點個數}}if (loHead != null) { // 原索引位置的節點不為空if (lc <= UNTREEIFY_THRESHOLD) // 節點個數少于6個則將紅黑樹轉為鏈表結構tab[index] = loHead.untreeify(map);else {tab[index] = loHead; // 將原索引位置的節點設置為對應的頭結點// hiHead不為空則代表原來的紅黑樹(老表的紅黑樹由于節點被分到兩個位置)// 已經被改變, 需要重新構建新的紅黑樹if (hiHead != null) loHead.treeify(tab); // 以loHead為根結點, 構建新的紅黑樹}}if (hiHead != null) { // 索引位置為原索引+oldCap的節點不為空if (hc <= UNTREEIFY_THRESHOLD) // 節點個數少于6個則將紅黑樹轉為鏈表結構tab[index + bit] = hiHead.untreeify(map);else {tab[index + bit] = hiHead; // 將索引位置為原索引+oldCap的節點設置為對應的頭結點// loHead不為空則代表原來的紅黑樹(老表的紅黑樹由于節點被分到兩個位置)// 已經被改變, 需要重新構建新的紅黑樹if (loHead != null) hiHead.treeify(tab); // 以hiHead為根結點, 構建新的紅黑樹}} }?
代碼塊11：untreeify方法
// 將紅黑樹節點轉為鏈表節點, 當節點<=6個時會被觸發 final Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; // hd指向頭結點, tl指向尾節點// 從調用該方法的節點, 即鏈表的頭結點開始遍歷, 將所有節點全轉為鏈表節點for (Node<K,V> q = this; q != null; q = q.next) { // 調用replacementNode方法構建鏈表節點Node<K,V> p = map.replacementNode(q, null); // 如果tl為null, 則代表當前節點為第一個節點, 將hd賦值為該節點if (tl == null)hd = p;else // 否則, 將尾節點的next屬性設置為當前節點ptl.next = p;tl = p; // 每次都將tl節點指向當前節點, 即尾節點}return hd; // 返回轉換后的鏈表的頭結點 }?
?
例子1：擴容后，節點重hash為什么只可能分布在原索引位置與原索引+oldCap位置？
擴容代碼中，使用e節點的hash值跟oldCap進行位與運算，以此決定將節點分布到原索引位置或者原索引+oldCap位置上，這是為什么了？
假設老表的容量為16，即oldCap=16，則新表容量為16*2=32，假設節點1的hash值為0000 0000 0000 0000 0000 1111 0000 1010，節點2的hash值為0000 0000 0000 0000 0000 1111 0001 1010，則節點1和節點2在老表的索引位置計算如下圖計算1，由于老表的長度限制，節點1和節點2的索引位置只取決于節點hash值的最后4位。再看計算2，計算2為新表的索引計算，可以知道如果兩個節點在老表的索引位置相同，則新表的索引位置只取決于節點hash值倒數第5位的值，而此位置的值剛好為老表的容量值16，此時節點在新表的索引位置只有兩種情況：原索引位置和原索引+oldCap位置（在此例中即為10和10+16=26）。由于結果只取決于節點hash值的倒數第5位，而此位置的值剛好為老表的容量值16，因此此時新表的索引位置的計算可以替換為計算3，直接使用節點的hash值與老表的容量16進行位于運算，如果結果為0則該節點在新表的索引位置為原索引位置，否則該節點在新表的索引位置為原索引+oldCap位置。
?
remove方法
public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value; }final 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;// 如果table不為空并且根據hash值計算出來的索引位置不為空, 將該位置的節點賦值給pif ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;// 如果p的hash值和key都與入參的相同, 則p即為目標節點, 賦值給nodeif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) { // 否則向下遍歷節點if (p instanceof TreeNode) // 如果p是TreeNode則調用紅黑樹的方法查找節點node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do { // 遍歷鏈表查找符合條件的節點// 當節點的hash值和key與傳入的相同,則該節點即為目標節點if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e; // 賦值給node, 并跳出循環break;}p = e; // p節點賦值為本次結束的e} while ((e = e.next) != null); // 指向像一個節點}}// 如果node不為空(即根據傳入key和hash值查找到目標節點)，則進行移除操作if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) { if (node instanceof TreeNode) // 如果是TreeNode則調用紅黑樹的移除方法((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);// 走到這代表節點是普通鏈表節點// 如果node是該索引位置的頭結點則直接將該索引位置的值賦值為node的next節點else if (node == p)tab[index] = node.next;// 否則將node的上一個節點的next屬性設置為node的next節點, // 即將node節點移除, 將node的上下節點進行關聯(鏈表的移除) else p.next = node.next;++modCount; // 修改次數+1--size; // table的總節點數-1afterNodeRemoval(node); // 供LinkedHashMap使用return node; // 返回被移除的節點}}return null; }?
代碼塊12：removeTreeNode方法
這塊代碼比較長，目的就是移除調用此方法的節點，也就是該方法中的this節點。移除包括鏈表的處理和紅黑樹的處理?？梢越Y合下文的圖解理解。
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable) {// 鏈表的處理startint n;if (tab == null || (n = tab.length) == 0) // table為空或者length為0直接返回return;int index = (n - 1) & hash; // 根據hash計算出索引的位置// 索引位置的頭結點賦值給first和rootTreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; // 該方法被將要被移除的node(TreeNode)調用, 因此此方法的this為要被移除node節點, // 則此處next即為node的next節點, prev即為node的prev節點TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;if (pred == null) // 如果node節點的prev節點為空// 則將table索引位置的值和first節點的值賦值為succ節點(node的next節點)即可tab[index] = first = succ;else// 否則將node的prev節點的next屬性設置為succ節點(node的next節點)(鏈表的移除)pred.next = succ;if (succ != null) // 如果succ節點不為空succ.prev = pred; // 則將succ的prev節點設置為pred, 與上面對應if (first == null) // 如果此處first為空, 則代表該索引位置已經沒有節點則直接返回return;// 如果root的父節點不為空, 則將root賦值為根結點// (root在上面被賦值為索引位置的頭結點, 索引位置的頭節點并不一定為紅黑樹的根結點)if (root.parent != null)root = root.root();// 通過root節點來判斷此紅黑樹是否太小, 如果是則調用untreeify方法轉為鏈表節點并返回// (轉鏈表后就無需再進行下面的紅黑樹處理)if (root == null || root.right == null ||(rl = root.left) == null || rl.left == null) {tab[index] = first.untreeify(map); // too smallreturn;}// 鏈表的處理end// 以下代碼為紅黑樹的處理, 上面的代碼已經將鏈表的部分處理完成// 上面已經說了this為要被移除的node節點,// 將p賦值為node節點,pl賦值為node的左節點,pr賦值為node的右節點TreeNode<K,V> p = this, pl = left, pr = right, replacement;if (pl != null && pr != null) { // node的左節點和右節點都不為空時TreeNode<K,V> s = pr, sl; // s節點賦值為node的右節點while ((sl = s.left) != null)//向左一直查找,直到葉子節點,跳出循環時,s為葉子節點s = sl;boolean c = s.red; s.red = p.red; p.red = c; //交換p節點和s節點(葉子節點)的顏色TreeNode<K,V> sr = s.right; // s的右節點TreeNode<K,V> pp = p.parent; // p的父節點// 第一次調整startif (s == pr) { // 如果p節點的右節點即為葉子節點p.parent = s; // 將p的父節點賦值為ss.right = p; // 將s的右節點賦值為p}else {TreeNode<K,V> sp = s.parent;if ((p.parent = sp) != null) { // 將p的父節點賦值為s的父節點, 如果sp不為空if (s == sp.left) // 如果s節點為左節點sp.left = p; // 則將s的父節點的左節點賦值為p節點else // 如果s節點為右節點sp.right = p; // 則將s的父節點的右節點賦值為p節點}if ((s.right = pr) != null) // s的右節點賦值為p節點的右節點pr.parent = s; // p節點的右節點的父節點賦值為s}// 第二次調整startp.left = null;if ((p.right = sr) != null) // 將p節點的右節點賦值為s的右節點, 如果sr不為空sr.parent = p; // 則將s右節點的父節點賦值為p節點if ((s.left = pl) != null) // 將s節點的左節點賦值為p的左節點, 如果pl不為空pl.parent = s; // 則將p左節點的父節點賦值為s節點if ((s.parent = pp) == null) // 將s的父節點賦值為p的父節點pp, 如果pp為空root = s; // 則p節點為root節點, 此時交換后s成為新的root節點else if (p == pp.left) // 如果p不為root節點, 并且p是父節點的左節點pp.left = s; // 將p父節點的左節點賦值為s節點else // 如果p不為root節點, 并且p是父節點的右節點pp.right = s; // 將p父節點的右節點賦值為s節點if (sr != null)replacement = sr; // 尋找replacement節點(用來替換掉p節點)elsereplacement = p; // 尋找replacement節點}else if (pl != null) // 如果p的左節點不為空,右節點為空,replacement節點為p的左節點replacement = pl;else if (pr != null) // 如果p的右節點不為空,左節點為空,replacement節點為p的右節點replacement = pr;else // 如果p的左右節點都為空, 即p為葉子節點, 替換節點為p節點本身replacement = p;// 第三次調整startif (replacement != p) { // 如果p節點不是葉子節點//將replacement節點的父節點賦值為p節點的父節點, 同時賦值給pp節點TreeNode<K,V> pp = replacement.parent = p.parent;if (pp == null) // 如果p節點沒有父節點, 即p為root節點root = replacement; // 則將root節點賦值為replacement節點即可else if (p == pp.left) // 如果p節點不是root節點, 并且p節點為父節點的左節點pp.left = replacement; // 則將p父節點的左節點賦值為替換節點else // 如果p節點不是root節點, 并且p節點為父節點的右節點pp.right = replacement; // 則將p父節點的右節點賦值為替換節點// p節點的位置已經被完整的替換為替換節點, 將p節點清空, 以便垃圾收集器回收p.left = p.right = p.parent = null;}// 如果p節點不為紅色則進行紅黑樹刪除平衡調整// (如果刪除的節點是紅色則不會破壞紅黑樹的平衡無需調整)TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);if (replacement == p) { // 如果p節點為葉子節點, 則簡單的將p節點去除即可TreeNode<K,V> pp = p.parent; // pp賦值為p節點的父節點p.parent = null; // 將p的parent節點設置為空if (pp != null) { // 如果p的父節點存在if (p == pp.left) // 如果p節點為父節點的左節點pp.left = null; // 則將父節點的左節點賦值為空else if (p == pp.right) // 如果p節點為父節點的右節點pp.right = null; // 則將父節點的右節點賦值為空}}if (movable)moveRootToFront(tab, r); // 將root節點移到索引位置的頭結點 }?
解釋1：為什么sr是replacement的首選，p為備選？
解析：首先我們看sr是什么？從代碼中可以看到sr第一次被賦值時，是在s節點進行了向左窮遍歷結束后，因此此時s節點是沒有左節點的，sr即為s節點的右節點。而從上面的三次調整我們知道，p節點已經跟s節點進行了位置調換，所以此時sr其實是p節點的右節點，并且p節點沒有左節點，因此要移除p節點，只需要將p節點的右節點sr覆蓋掉p節點即可，因此sr是replacement的首選，如果sr為空，則代表p節點為葉子節點，此時將p節點清空即可。
?
圖解1：removeTreeNode圖解
本圖解忽略紅黑樹的顏色，請注意。
下面的圖解是代碼中的最復雜的情況，即流程最長的那個，p節點不為根結點，p節點有左右節點，s節點不為pr節點，s節點有右節點。
?
解釋2：關于紅黑樹的平衡調整？
答：紅黑樹的操作涉及的操作比較復雜，三言兩語無法說清。有興趣的可以去單獨學習，本文由于篇幅關系暫不詳細介紹紅黑樹的具體操作，在這簡單的介紹：紅黑樹是一種自平衡二叉樹，擁有優秀的查詢和插入/刪除性能，廣泛應用于關聯數組。
對比AVL樹，AVL要求每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1，而紅黑樹通過適當的放低該條件（紅黑樹限制從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長，結果是這個樹大致上是平衡的），以此來減少插入/刪除時的平衡調整耗時，從而獲取更好的性能，而這雖然會導致紅黑樹的查詢會比AVL稍慢，但相比插入/刪除時獲取的時間，這個付出在大多數情況下顯然是值得的。
在HashMap中的應用：HashMap在進行插入和刪除時有可能會觸發紅黑樹的插入平衡調整（balanceInsertion方法）或刪除平衡調整（balanceDeletion ）方法，調整的方式主要有以下手段：左旋轉（rotateLeft方法）、右旋轉（rotateRight方法）、改變節點顏色（x.red =?false、x.red = true），進行調整的原因是為了維持紅黑樹的數據結構。
?
死循環問題
在Jdk 1.8以前，Java語言在并發情況下使用HashMap造成Race Condition，從而導致死循環。程序經常占了100%的CPU，查看堆棧，你會發現程序都Hang在了HashMap.get()這個方法上了，重啟程序后問題消失。具體分析可以查看這篇文章：疫苗：JAVA HASHMAP的死循環，有人將這個問題當成一個bug提給了Sun，但是Sun認為這并不是個bug，因為HashMap本來就不保證并發的線程安全性，在并發下，要用ConcurrentHashMap來代替。
那么，在Jdk 1.8的時候，這個問題解決了嗎？
我們知道，Jdk 1.8以前，導致死循環的主要原因是擴容后，節點的順序會反掉，如下圖：擴容前節點A在節點C前面，而擴容后節點C在節點A前面。
?
JDK 1.8擴容過程
JDK1.8?普通鏈表的擴容代碼，如下圖所示，在上文已經分析過了：主要是在一個do/while中處理同一個位置的所有節點。
前提：我們假設有3個節點，節點A，節點B，節點C，并且假設他們的hash值等于key值，則按上圖擴容的過程模擬如下。
先看下老表和新表計算索引位置的過程：（hash計算省略前面28位0，只看最后4位）
?
具體擴容過程：
結果：可以看出，擴容后，節點A和節點C的先后順序跟擴容前是一樣的。因此，即使此時有多個線程并發擴容，也不會出現死循環的情況。當然，這仍然改變不了HashMap仍是非并發安全，在并發下，還是要使用ConcurrentHashMap來代替。
?
?
HashMap和Hashtable的區別：
?
總結：
?
?
原博客地址：https://blog.csdn.net/v123411739/article/details/78996181
總結
以上是生活随笔為你收集整理的Java集合篇：HashMap原理详解（JDK1.8）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Eclipse：Target runti
- 下一篇： MySQL数据库：常见经典SQL语句