面試官再問你 HashMap 底層原理,就把這篇文章甩給他看

前言

HashMap 源碼和底層原理在現在面試中是必問的。因此,我們非常有必要搞清楚它的底層實現和思想,才能在面試中對答如流,跟面試官大戰三百回合。文章較長,介紹了很多原理性的問題,希望對你有所幫助~

目錄

本篇文章主要包括以下內容:

  • HashMap 的存儲結構
  • 常用變量說明,如加載因子等
  • HashMap 的四個構造函數
  • tableSizeFor()方法及作用
  • put()方法詳解
  • hash()方法,以及避免哈希碰撞的原理
  • resize()擴容機制及原理
  • get()方法
  • 為什么HashMap鏈表會形成死循環,JDK1.8做了哪些優化

正文

說明:本篇主要以JDK1.8的源碼來分析,順帶講下和JDK1.7的一些區別。

HashMap存儲結構

這里需要區分一下,JDK1.7和 JDK1.8之后的 HashMap 存儲結構。在JDK1.7及之前,是用數組加鏈表的方式存儲的。

但是,眾所周知,當鏈表的長度特別長的時候,查詢效率將直線下降,查詢的時間復雜度為 O(n)。因此,JDK1.8 把它設計為達到一個特定的閾值之后,就將鏈表轉化為紅黑樹。

這里簡單說下紅黑樹的特點:

  1. 每個節點只有兩種顏色:紅色或者黑色
  2. 根節點必須是黑色
  3. 每個葉子節點(NIL)都是黑色的空節點
  4. 從根節點到葉子節點,不能出現兩個連續的紅色節點
  5. 從任一節點出發,到它下邊的子節點的路徑包含的黑色節點數目都相同

由于紅黑樹,是一個自平衡的二叉搜索樹,因此可以使查詢的時間復雜度降為O(logn)。(紅黑樹不是本文重點,不了解的童鞋可自行查閱相關資料哈)

HashMap 結構示意圖:

常用的變量

在 HashMap源碼中,比較重要的常用變量,主要有以下這些。還有兩個內部類來表示普通鏈表的節點和紅黑樹節點。


//默認的初始化容量為16,必須是2的n次冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//最大容量為 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

//默認的加載因子0.75,乘以數組容量得到的值,用來表示元素個數達到多少時,需要擴容。
//為什么設置 0.75 這個值呢,簡單來說就是時間和空間的權衡。
//若小于0.75如0.5,則數組長度達到一半大小就需要擴容,空間使用率大大降低,
//若大于0.75如0.8,則會增大hash沖突的概率,影響查詢效率。
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//剛才提到了當鏈表長度過長時,會有一個閾值,超過這個閾值8就會轉化為紅黑樹
static final int TREEIFY_THRESHOLD = 8;

//當紅黑樹上的元素個數,減少到6個時,就退化為鏈表
static final int UNTREEIFY_THRESHOLD = 6;

//鏈表轉化為紅黑樹,除了有閾值的限制,還有另外一個限制,需要數組容量至少達到64,才會樹化。
//這是為了避免,數組擴容和樹化閾值之間的沖突。
static final int MIN_TREEIFY_CAPACITY = 64;

//存放所有Node節點的數組
transient Node<K,V>[] table;

//存放所有的鍵值對
transient Set<Map.Entry<K,V>> entrySet;

//map中的實際鍵值對個數,即數組中元素個數
transient int size;

//每次結構改變時,都會自增,fail-fast機制,這是一種錯誤檢測機制。
//當迭代集合的時候,如果結構發生改變,則會發生 fail-fast,拋出異常。
transient int modCount;

//數組擴容閾值
int threshold;

//加載因子
final float loadFactor;					

//普通單向鏈表節點類
static class Node<K,V> implements Map.Entry<K,V> {
	//key的hash值,put和get的時候都需要用到它來確定元素在數組中的位置
	final 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;
	}
}

//轉化為紅黑樹的節點類
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 deletion
	//當前節點是紅色或者黑色的標識
	boolean red;
	TreeNode(int hash, K key, V val, Node<K,V> next) {
		super(hash, key, val, next);
	}
}	

HashMap 構造函數

HashMap有四個構造函數可供我們使用,一起來看下:

//默認無參構造,指定一個默認的加載因子
public HashMap() {
	this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

//可指定容量的有參構造,但是需要注意當前我們指定的容量并不一定就是實際的容量,下面會說
public HashMap(int initialCapacity) {
	//同樣使用默認加載因子
	this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//可指定容量和加載因子,但是筆者不建議自己手動指定非0.75的加載因子
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;
	//這里就是把我們指定的容量改為一個大于它的的最小的2次冪值,如傳過來的容量是14,則返回16
	//注意這里,按理說返回的值應該賦值給 capacity,即保證數組容量總是2的n次冪,為什么這里賦值給了 threshold 呢?
	//先賣個關子,等到 resize 的時候再說
	this.threshold = tableSizeFor(initialCapacity);
}

//可傳入一個已有的map
public HashMap(Map<? extends K, ? extends V> m) {
	this.loadFactor = DEFAULT_LOAD_FACTOR;
	putMapEntries(m, false);
}

//把傳入的map里邊的元素都加載到當前map
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
	int s = m.size();
	if (s > 0) {
		if (table == null) { // pre-size
			float ft = ((float)s / loadFactor) + 1.0F;
			int t = ((ft < (float)MAXIMUM_CAPACITY) ?
					 (int)ft : MAXIMUM_CAPACITY);
			if (t > threshold)
				threshold = tableSizeFor(t);
		}
		else if (s > threshold)
			resize();
		for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
			K key = e.getKey();
			V value = e.getValue();
			//put方法的具體實現,后邊講
			putVal(hash(key), key, value, false, evict);
		}
	}
}

tableSizeFor()

上邊的第三個構造函數中,調用了 tableSizeFor 方法,這個方法是怎么實現的呢?

static final int tableSizeFor(int cap) {
	int n = cap - 1;
	n |= n >>> 1;
	n |= n >>> 2;
	n |= n >>> 4;
	n |= n >>> 8;
	n |= n >>> 16;
	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

我們以傳入參數為14 來舉例,計算這個過程。

首先,14傳進去之后先減1,n此時為13。然后是一系列的無符號右移運算。

//13的二進制
0000 0000 0000 0000 0000 0000 0000 1101 
//無右移1位,高位補0
0000 0000 0000 0000 0000 0000 0000 0110 
//然后把它和原來的13做或運算得到,此時的n值
0000 0000 0000 0000 0000 0000 0000 1111 
//再以上邊的值,右移2位
0000 0000 0000 0000 0000 0000 0000 0011
//然后和第一次或運算之后的 n 值再做或運算,此時得到的n值
0000 0000 0000 0000 0000 0000 0000 1111
...
//我們會發現,再執行右移 4,8,16位,同樣n的值不變
//當n小于0時,返回1,否則判斷是否大于最大容量,是的話返回最大容量,否則返回 n+1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
//很明顯我們這里返回的是 n+1 的值,
0000 0000 0000 0000 0000 0000 0000 1111
+                                     1
0000 0000 0000 0000 0000 0000 0001 0000

將它轉為十進制,就是 2^4 = 16 。我們會發現一個規律,以上的右移運算,最終會把最低位的值都轉化為 1111 這樣的結構,然后再加1,就是1 0000 這樣的結構,它一定是 2的n次冪。因此,這個方法返回的就是大于當前傳入值的最小(最接近當前值)的一個2的n次冪的值。

put()方法詳解

//put方法,會先調用一個hash()方法,得到當前key的一個hash值,
//用于確定當前key應該存放在數組的哪個下標位置
//這里的 hash方法,我們姑且先認為是key.hashCode(),其實不是的,一會兒細講
public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

//把hash值和當前的key,value傳入進來
//這里onlyIfAbsent如果為true,表明不能修改已經存在的值,因此我們傳入false
//evict只有在方法 afterNodeInsertion(boolean evict) { }用到,可以看到它是一個空實現,因此不用關注這個參數
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是否為空,如果空的話,會先調用resize擴容
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	//根據當前key的hash值找到它在數組中的下標,判斷當前下標位置是否已經存在元素,
	//若沒有,則把key、value包裝成Node節點,直接添加到此位置。
	// i = (n - 1) & hash 是計算下標位置的,為什么這樣算,后邊講
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	else { 
		//如果當前位置已經有元素了,分為三種情況。
		Node<K,V> e; K k;
		//1.當前位置元素的hash值等于傳過來的hash,并且他們的key值也相等,
		//則把p賦值給e,跳轉到①處,后續需要做值的覆蓋處理
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		//2.如果當前是紅黑樹結構,則把它加入到紅黑樹 
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		else {
		//3.說明此位置已存在元素,并且是普通鏈表結構,則采用尾插法,把新節點加入到鏈表尾部
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {
					//如果頭結點的下一個節點為空,則插入新節點
					p.next = newNode(hash, key, value, null);
					//如果在插入的過程中,鏈表長度超過了8,則轉化為紅黑樹
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					//插入成功之后,跳出循環,跳轉到①處
					break;
				}
				//若在鏈表中找到了相同key的話,直接退出循環,跳轉到①處
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		//① 
		//說明發生了碰撞,e代表的是舊值,因此節點位置不變,但是需要替換為新值
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			//用新值替換舊值,并返回舊值
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			//看方法名字即可知,這是在node被訪問之后需要做的操作。其實此處是一個空實現,
			//只有在 LinkedHashMap才會實現,用于實現根據訪問先后順序對元素進行排序,hashmap不提供排序功能
			// Callbacks to allow LinkedHashMap post-actions
			//void afterNodeAccess(Node<K,V> p) { }
			afterNodeAccess(e);
			return oldValue;
		}
	}
	//fail-fast機制
	++modCount;
	//如果當前數組中的元素個數超過閾值,則擴容
	if (++size > threshold)
		resize();
	//同樣的空實現
	afterNodeInsertion(evict);
	return null;
}

hash()計算原理

前面 put 方法中說到,需要先把當前key進行哈希處理,我們看下這個方法是怎么實現的。

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

這里,會先判斷key是否為空,若為空則返回0。這也說明了hashMap是支持key傳 null 的。若非空,則先計算key的hashCode值,賦值給h,然后把h右移16位,并與原來的h進行異或處理。為什么要這樣做,這樣做有什么好處呢?

我們知道,hashCode()方法繼承自父類Object,它返回的是一個 int 類型的數值,可以保證同一個應用單次執行的每次調用,返回結果都是相同的(這個說明可以在hashCode源碼上找到),這就保證了hash的確定性。在此基礎上,再進行某些固定的運算,肯定結果也是可以確定的。

我隨便運行一段程序,把它的 hashCode的二進制打印出來,如下。

public static void main(String[] args) {
    Object o = new Object();
    int hash = o.hashCode();
    System.out.println(hash);
    System.out.println(Integer.toBinaryString(hash));

}
//1836019240
//1101101011011110110111000101000

然后,進行 (h = key.hashCode()) ^ (h >>> 16) 這一段運算。

//h原來的值
0110 1101 0110 1111 0110 1110 0010 1000
//無符號右移16位,其實相當于把低位16位舍去,只保留高16位
0000 0000 0000 0000 0110 1101 0110 1111
//然后高16位和原 h進行異或運算
0110 1101 0110 1111 0110 1110 0010 1000
^
0000 0000 0000 0000 0110 1101 0110 1111
=
0110 1101 0110 1111 0000 0011 0100 0111

可以看到,其實相當于,我們把高16位值和當前h的低16位進行了混合,這樣可以盡量保留高16位的特征,從而降低哈希碰撞的概率。

思考一下,為什么這樣做,就可以降低哈希碰撞的概率呢?先別著急,我們需要結合 i = (n - 1) & hash 這一段運算來理解。

** (n-1) & hash 作用**

//②
//這是 put 方法中用來根據hash()值尋找在數組中的下標的邏輯,
//n為數組長度, hash為調用 hash()方法混合處理之后的hash值。
i = (n - 1) & hash

我們知道,如果給定某個數值,去找它在某個數組中的下標位置時,直接用模運算就可以了(假設數組值從0開始遞增)。如,我找 14 在數組長度為16的數組中的下標,即為 14 % 16,等于14 。 18的位置即為 18%16,等于2。

而②中,就是取模運算的位運算形式。以18%16為例

//18的二進制
0001 0010
//16 -1 即 15的二進制
0000 1111
//與運算之后的結果為
0000 0010
// 可以看到,上邊的結果轉化為十進制就是 2 。
//其實我們會發現一個規律,因為n是2的n次冪,因此它的二進制表現形式肯定是類似于
0001 0000
//這樣的形式,只有一個位是1,其他位都是0。而它減 1 之后的形式就是類似于
0000 1111 
//這樣的形式,高位都是0,低位都是1,因此它和任意值進行與運算,結果值肯定在這個區間內
0000 0000  ~  0000 1111
//也就是0到15之間,(以n為16為例)
//因此,這個運算就可以實現取模運算,而且位運算還有個好處,就是速度比較快。

為什么高低位異或運算可以減少哈希碰撞

我們想象一下,假如用 key 原來的hashCode值,直接和 (n-1) 進行與運算來求數組下標,而不進行高低位混合運算,會產生什么樣的結果。

//例如我有另外一個h2,和原來的 h相比較,高16位有很大的不同,但是低16位相似度很高,甚至相同的話。
//原h值
0110 1101 0110 1111 0110 1110 0010 1000
//另外一個h2值
0100 0101 1110 1011 0110 0110 0010 1000
// n -1 ,即 15 的二進制
0000 0000 0000 0000 0000 0000 0000 1111
//可以發現 h2 和 h 的高位不相同,但是低位相似度非常高。
//他們分別和 n -1 進行與運算時,得到的結果卻是相同的。(此處n假設為16)
//因為 n-1 的高16位都是0,不管 h 的高 16 位是什么,與運算之后,都不影響最終結果,高位一定全是 0
//因此,哈希碰撞的概率就大大增加了,并且 h 的高16 位特征全都丟失了。

愛思考的同學可能就會有疑問了,我進行高低16位混合運算,是可以的,這樣可以保證盡量減少高區位的特征。那么,為什么選擇用異或運算呢,我用與、或、非運算不行嗎?

這是有一定的道理的。我們看一個表格,就能明白了。

可以看到兩個值進行與運算,結果會趨向于0;或運算,結果會趨向于1;而只有異或運算,0和1的比例可以達到1:1的平衡狀態。(非呢?別扯犢子了,兩個值怎么做非運算。。。)

所以,異或運算之后,可以讓結果的隨機性更大,而隨機性大了之后,哈希碰撞的概率當然就更小了。

以上,就是為什么要對一個hash值進行高低位混合,并且選擇異或運算來混合的原因。

resize() 擴容機制

在上邊 put 方法中,我們會發現,當數組為空的時候,會調用 resize 方法,當數組的 size 大于閾值的時候,也會調用 resize方法。 那么看下 resize 方法都做了哪些事情吧。

final Node<K,V>[] resize() {
	//舊數組
	Node<K,V>[] oldTab = table;
	//舊數組的容量
	int oldCap = (oldTab == null) ? 0 : oldTab.length;
	//舊數組的擴容閾值,注意看,這里取的是當前對象的 threshold 值,下邊的第2種情況會用到。
	int oldThr = threshold;
	//初始化新數組的容量和閾值,分三種情況討論。
	int newCap, newThr = 0;
	//1.當舊數組的容量大于0時,說明在這之前肯定調用過 resize擴容過一次,才會導致舊容量不為0。
	//為什么這樣說呢,之前我在 tableSizeFor 賣了個關子,需要注意的是,它返回的值是賦給了 threshold 而不是 capacity。
	//我們在這之前,壓根就沒有在任何地方看到過,它給 capacity 賦初始值。
	if (oldCap > 0) {
		//容量達到了最大值
		if (oldCap >= MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return oldTab;
		}
		//新數組的容量和閾值都擴大原來的2倍
		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
				 oldCap >= DEFAULT_INITIAL_CAPACITY)
			newThr = oldThr << 1; // double threshold
	}
	//2.到這里,說明 oldCap <= 0,并且 oldThr(threshold) > 0,這就是 map 初始化的時候,第一次調用 resize的情況
	//而 oldThr的值等于 threshold,此時的 threshold 是通過 tableSizeFor 方法得到的一個2的n次冪的值(我們以16為例)。
	//因此,需要把 oldThr 的值,也就是 threshold ,賦值給新數組的容量 newCap,以保證數組的容量是2的n次冪。
	//所以我們可以得出結論,當map第一次 put 元素的時候,就會走到這個分支,把數組的容量設置為正確的值(2的n次冪)
	//但是,此時 threshold 的值也是2的n次冪,這不對啊,它應該是數組的容量乘以加載因子才對。別著急,這個會在③處理。
	else if (oldThr > 0) // initial capacity was placed in threshold
		newCap = oldThr;
	//3.到這里,說明 oldCap 和 oldThr 都是小于等于0的。也說明我們的map是通過默認無參構造來創建的,
	//于是,數組的容量和閾值都取默認值就可以了,即 16 和 12。
	else {               // zero initial threshold signifies using defaults
		newCap = DEFAULT_INITIAL_CAPACITY;
		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
	//③ 這里就是處理第2種情況,因為只有這種情況 newThr 才為0,
	//因此計算 newThr(用 newCap即16 乘以加載因子 0.75,得到 12) ,并把它賦值給 threshold
	if (newThr == 0) {
		float ft = (float)newCap * loadFactor;
		newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
				  (int)ft : Integer.MAX_VALUE);
	}
	//賦予 threshold 正確的值,表示數組下次需要擴容的閾值(此時就把原來的 16 修正為了 12)。
	threshold = newThr;
	@SuppressWarnings({"rawtypes","unchecked"})
		Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
	table = newTab;
	//如果原來的數組不為空,那么我們就需要把原來數組中的元素重新分配到新的數組中
	//如果是第2種情況,由于是第一次調用resize,此時數組肯定是空的,因此也就不需要重新分配元素。
	if (oldTab != null) {
		//遍歷舊數組
		for (int j = 0; j < oldCap; ++j) {
			Node<K,V> e;
			//取到當前下標的第一個元素,如果存在,則分三種情況重新分配位置
			if ((e = oldTab[j]) != null) {
				oldTab[j] = null;
				//1.如果當前元素的下一個元素為空,則說明此處只有一個元素
				//則直接用它的hash()值和新數組的容量取模就可以了,得到新的下標位置。
				if (e.next == null)
					newTab[e.hash & (newCap - 1)] = e;
				//2.如果是紅黑樹結構,則拆分紅黑樹,必要時有可能退化為鏈表
				else if (e instanceof TreeNode)
					((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
				//3.到這里說明,這是一個長度大于 1 的普通鏈表,則需要計算并
				//判斷當前位置的鏈表是否需要移動到新的位置
				else { // preserve order
					// loHead 和 loTail 分別代表鏈表舊位置的頭尾節點
					Node<K,V> loHead = null, loTail = null;
					// hiHead 和 hiTail 分別代表鏈表移動到新位置的頭尾節點
					Node<K,V> hiHead = null, hiTail = null;
					Node<K,V> next;
					do {
						next = e.next;
						//如果當前元素的hash值和oldCap做與運算為0,則原位置不變
						if ((e.hash & oldCap) == 0) {
							if (loTail == null)
								loHead = e;
							else
								loTail.next = e;
							loTail = e;
						}
						//否則,需要移動到新的位置
						else {
							if (hiTail == null)
								hiHead = e;
							else
								hiTail.next = e;
							hiTail = e;
						}
					} while ((e = next) != null);
					//原位置不變的一條鏈表,數組下標不變
					if (loTail != null) {
						loTail.next = null;
						newTab[j] = loHead;
					}
					//移動到新位置的一條鏈表,數組下標為原下標加上舊數組的容量
					if (hiTail != null) {
						hiTail.next = null;
						newTab[j + oldCap] = hiHead;
					}
				}
			}
		}
	}
	return newTab;
}

上邊還有一個非常重要的運算,我們沒有講解。就是下邊這個判斷,它用于把原來的普通鏈表拆分為兩條鏈表,位置不變或者放在新的位置。

if ((e.hash & oldCap) == 0) {} else {}

我們以原數組容量16為例,擴容之后容量為32。說明下為什么這樣計算。

還是用之前的hash值舉例。

//e.hash值
0110 1101 0110 1111 0110 1110 0010 1000
//oldCap值,即16
0000 0000 0000 0000 0000 0000 0001 0000 
//做與運算,我們會發現結果不是0就是非0,
//而且它取決于 e.hash 二進制位的倒數第五位是 0 還是 1,
//若倒數第五位為0,則結果為0,若倒數第五位為1,則結果為非0。
//那這個和新數組有什么關系呢?
//別著急,我們看下新數組的容量是32,如果求當前hash值在新數組中的下標,則為
// e.hash &( 32 - 1) 這樣的運算 ,即 hash 與 31 進行與運算,
0110 1101 0110 1111 0110 1110 0010 1000 
&
0000 0000 0000 0000 0000 0000 0001 1111 
=
0000 0000 0000 0000 0000 0000 0000 1000
//接下來,我們對比原來的下標計算結果和新的下標結果,看圖

看下面的圖,我們觀察,hash值和舊數組進行與運算的結果 ,跟新數組的與運算結果有什么不同。

會發現一個規律:

若hash值的倒數第五位是0,則新下標與舊下標結果相同,都為 0000 1000

若hash值的倒數第五位是1,則新下標(0001 1000)與舊下標(0000 1000)結果值相差了 16 。

因此,我們就可以根據 (e.hash & oldCap == 0) 這個判斷的真假來決定,當前元素應該在原來的位置不變,還是在新的位置(原位置 + 16)。

如果,上邊的推理還是不明白的話,我再舉個簡單的例子。

18%16=2     18%32=18
34%16=2     34%32=2
50%16=2     50%32=18

怎么樣,發現規律沒,有沒有那個感覺了?

計算中的18,34 ,50 其實就相當于 e.hash 值,和新舊數組做取模運算,得到的結果,要么就是原來的位置不變,要么就是原來的位置加上舊數組的長度。

get()方法

有了前面的基礎,get方法就比較簡單了。

public V get(Object key) {
	Node<K,V> e;
	//如果節點為空,則返回null,否則返回節點的value。這也說明,hashMap是支持value為null的。
	//因此,我們就明白了,為什么hashMap支持Key和value都為null
	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;
	//首先要確保數組不能為空,然后取到當前hash值計算出來的下標位置的第一個元素
	if ((tab = table) != null && (n = tab.length) > 0 &&
		(first = tab[(n - 1) & hash]) != null) {
		//若hash值和key都相等,則說明我們要找的就是第一個元素,直接返回
		if (first.hash == hash && // always check first node
			((k = first.key) == key || (key != null && key.equals(k))))
			return first;
		//如果不是的話,就遍歷當前鏈表(或紅黑樹)
		if ((e = first.next) != null) {
			//如果是紅黑樹結構,則找到當前key所在的節點位置
			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);
		}
	}
	//否則,說明沒有找到,返回null
	return null;
}

為什么HashMap鏈表會形成死循環

準確的講應該是 JDK1.7 的 HashMap 鏈表會有死循環的可能,因為JDK1.7是采用的頭插法,在多線程環境下有可能會使鏈表形成環狀,從而導致死循環。JDK1.8做了改進,用的是尾插法,不會產生死循環。

那么,鏈表是怎么形成環狀的呢?

關于這一點的解釋,我發現網上文章抄來抄去的,而且都來自左耳朵耗子,更驚奇的是,連配圖都是一模一樣的。(別問我為什么知道,因為我也看過耗子叔的文章,哈哈。然而,菜雞的我,那篇文章,并沒有看懂。。。)

我實在看不下去了,于是一怒之下,就有了這篇文章。我會照著源碼一步一步的分析變量之間的關系怎么變化的,并有配圖哦。

我們從 put()方法開始,最終找到線程不安全的那個方法。這里省略中間不重要的過程,我只把方法的跳轉流程貼出來:

//添加元素方法 -> 添加新節點方法 -> 擴容方法 -> 把原數組元素重新分配到新數組中
put()  --> addEntry()  --> resize() -->  transfer()

問題就發生在 transfer 這個方法中。

圖1

我們假設,原數組容量只有2,其中一條鏈表上有兩個元素 A,B,如下圖

現在,有兩個線程都執行 transfer 方法。每個線程都會在它們自己的工作內存生成一個newTable 的數組,用于存儲變化后的鏈表,它們互不影響(這里互不影響,指的是兩個新數組本身互不影響)。但是,需要注意的是,它們操作的數據卻是同一份。

因為,真正的數組中的內容在堆中存儲,它們指向的是同一份數據內容。就相當于,有兩個不同的引用 X,Y,但是它們都指向同一個對象 Z。這里 X、Y就是兩個線程不同的新數組,Z就是堆中的A,B 等元素對象。

假設線程一執行到了上圖1中所指的代碼①處,恰好 CPU 時間片到了,線程被掛起,不能繼續執行了。 記住此時,線程一中記錄的 e = A , e.next = B。

然后線程二正常執行,擴容后的數組長度為 4, 假設 A,B兩個元素又碰撞到了同一個桶中。然后,通過幾次 while 循環后,采用頭插法,最終呈現的結構如下:

此時,線程一解掛,繼續往下執行。注意,此時線程一,記錄的還是 e = A,e.next = B,因為它還未感知到最新的變化。

我們主要關注圖1中標注的①②③④處的變量變化:

/**
* next = e.next
* e.next = newTable[i]
* newTable[i] = e;
* e = next;
*/

//第一次循環,(偽代碼)
e=A;next=B;
e.next=null //此時線程一的新數組剛初始化完成,還沒有元素
newTab[i] = A->null //把A節點頭插到新數組中
e=B; //下次循環的e值

第一次循環結束后,線程一新數組的結構如下圖:

然后,由于 e=B,不為空,進入第二次循環。

//第二次循環
e=B;next=A;  //此時A,B的內容已經被線程二修改為 B->A->null,然后被線程一讀到,所以B的下一個節點指向A
e.next=A->null  // A->null 為第一次循環后線程一新數組的結構
newTab[i] = B->A->null //新節點B插入之后,線程一新數組的結構
e=A;  //下次循環的 e 值

第二次循環結束后,線程一新數組的結構如下圖:

此時,由于 e=A,不為空,繼續循環。

//第三次循環
e=A;next=null;  // A節點后邊已經沒有節點了
e.next= B->A->null  // B->A->null 為第二次循環后線程一新數組的結構
//我們把A插入后,抽象的表達為 A->B->A->null,但是,A只能是一個,不能分身啊
//因此實際上是 e(A).next指向發生了變化,A的 next 由指向 null 改為指向了 B,
//而 B 本身又指向A,因此A和B互相指向,成環
newTab[i] = A->B 且 B->A 
e=next=null; //e此時為空,結束循環

第三次循環結束后,看下圖,A的指向由 null ,改為指向為 B,因此 A 和 B 之間成環。

這時,有的同學可能就會問了,就算他們成環了,又怎樣,跟死循環有什么關系?

我們看下 get() 方法(最終調用 getEntry 方法),

可以看到查找元素時,只要 e 不為空,就會一直循環查找下去。若有某個元素 C 的 hash 值也落在了和 A,B元素同一個桶中,則會由于, A,B互相指向,e.next 永遠不為空,就會形成死循環。

結語

如果本文對你有用,歡迎關注我哦~

posted @ 2020-04-13 10:13  煙雨星空  閱讀(2446)  評論(23編輯  收藏
最新chease0ldman老人|无码亚洲人妻下载|大香蕉在线看好吊妞视频这里有精品www|亚洲色情综合网