HashMap解析put的過程

首先，用代碼運(yùn)行下，來體會(huì)下：

代碼實(shí)現(xiàn)：

@Test
	public void test1() {
		//創(chuàng)建了一個(gè)HashMap
		Map<String,Object>map = new HashMap<>();

		//使用put方法保存數(shù)據(jù)
		map.put("age", 12);
		map.put("name", "gaga");
		
		System.out.println(map);
		}

運(yùn)行結(jié)果：

首先經(jīng)過了hash之后的key，是一個(gè)整型的hashcode，其次是我們傳入的key和value。

首先一進(jìn)入putVal就會(huì)聲明存放數(shù)據(jù)的table，如果這個(gè)HashMap是首次設(shè)置值，就會(huì)被初始化一個(gè)默認(rèn)size的table，且所有元素的初始值都是NULL。

默認(rèn)值為啥是16

通過源碼解析，在注釋中會(huì)得到“The default initial capacity - MUST be a power of two.”意思是：默認(rèn)初始容量-必須是2的冪。

自動(dòng)擴(kuò)容

除了size，初始化的時(shí)候還會(huì)設(shè)定一個(gè)閾值，值為12，newThr = 12，這里需要提到一個(gè)概念負(fù)載因子，HashMap的實(shí)現(xiàn)里默認(rèn)給的是0.75。

負(fù)載因子是用來干嘛的呢？當(dāng)我們不停的往map里存數(shù)據(jù)的時(shí)候，總會(huì)存滿，當(dāng)元素快存滿的時(shí)候，我們就需要擴(kuò)大map的容量，來容納更多的元素，這就需要一個(gè)自動(dòng)擴(kuò)容的機(jī)制了。

在當(dāng)數(shù)據(jù)量大于超過設(shè)定的閾值的時(shí)候（容量*負(fù)載因子），自動(dòng)對(duì)map進(jìn)行擴(kuò)容，以存放更多的數(shù)據(jù)。

自動(dòng)擴(kuò)容做了什么事情呢？

• 1、創(chuàng)建新的數(shù)組，大小是原來數(shù)組的一倍。
• 2、將元素rehash到新的數(shù)組

為什么要rehash呢？上面我們提到過了，當(dāng)元素被放進(jìn)map時(shí)，確認(rèn)下標(biāo)的方法是table的長(zhǎng)度-1和hash值做與運(yùn)算，現(xiàn)在table的長(zhǎng)度發(fā)生了變化，那么自然而然，元素獲取下標(biāo)的運(yùn)算結(jié)果也就跟之前的不一樣了， 所以需要將老的map中的元素再按照新的table長(zhǎng)度rehash到擴(kuò)容后的table中。

put的過程

了解了底層數(shù)據(jù)結(jié)構(gòu)和自動(dòng)擴(kuò)容機(jī)制，接下來我們來看一下put過程中究竟發(fā)生了什么。

我們上面說過了，會(huì)通過數(shù)組的長(zhǎng)度-1和hash值與運(yùn)算得到一個(gè)數(shù)組下標(biāo)。

如果該位置沒有元素，那么就很簡(jiǎn)單，直接新建一個(gè)節(jié)點(diǎn)即可然后放置在數(shù)據(jù)的具體位置即可。

tab[i] = this.newNode(hash, key, value, (HashMap.Node)null);

但是如果該下標(biāo)已經(jīng)有元素了，這種情況HashMap是怎么處理的呢？這也要看情況。

如果是跟當(dāng)前槽位相同的key，就直接覆蓋。這就是我們修改某個(gè)key的值會(huì)發(fā)生的情況。

那HashMap怎么來判斷是不是同一個(gè)key呢？

就像下面這樣。p就是當(dāng)前槽位上已經(jīng)有的元素，如果新、老元素的key的hashCode和值都相同且key不為空，那么就能證明這兩個(gè)key是相同的，那么此時(shí)只需要覆蓋即可。

p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

而如果p是TreeNode的實(shí)例，那么就代表當(dāng)前槽位已經(jīng)是一個(gè)紅黑樹了，此時(shí)只需要往這個(gè)樹里putTreeVal即可。

至于為什么是紅黑樹，哪兒來的紅黑樹，下面馬上就要講到了。

最后一種情況就是，既不是已經(jīng)存在的元素也不是TreeNode的實(shí)例，也不是紅黑樹。這種情況下，它就是一個(gè)普通的Node。

你可以理解為鏈表，如果hash沖突了，就把這個(gè)Node放到該位置的鏈表末尾。

當(dāng)該位置的鏈表中的元素超過了TREEIFY_THRESHOLD所設(shè)置的數(shù)量時(shí)，就會(huì)觸發(fā)樹化，將其轉(zhuǎn)化為紅黑樹。Java8里給的默認(rèn)值是8。

為啥要轉(zhuǎn)化成紅黑樹？

首先我們要知道為什么要樹化。

當(dāng)大量的數(shù)據(jù)放入Map中，Hash沖突會(huì)越來越多，某些位置就會(huì)出現(xiàn)一個(gè)很長(zhǎng)的鏈表的情況。

這種情況下，查詢時(shí)間復(fù)雜度是O(n) ，刪除的時(shí)間復(fù)雜度也是O(n)，查詢、刪除的效率會(huì)大大降低。

而同樣的數(shù)據(jù)情況下，平衡二叉樹的時(shí)間復(fù)雜度都是O(logn)。

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論