java中對HashMap的put過程解讀
HashMap解析put的過程
首先,用代碼運行下,來體會下:
代碼實現(xiàn):
@Test public void test1() { //創(chuàng)建了一個HashMap Map<String,Object>map = new HashMap<>(); //使用put方法保存數(shù)據(jù) map.put("age", 12); map.put("name", "gaga"); System.out.println(map); }
運行結(jié)果:
首先經(jīng)過了hash之后的key,是一個整型的hashcode,其次是我們傳入的key和value。
首先一進入putVal就會聲明存放數(shù)據(jù)的table,如果這個HashMap是首次設(shè)置值,就會被初始化一個默認size的table,且所有元素的初始值都是NULL。
默認值為啥是16
通過源碼解析,在注釋中會得到“The default initial capacity - MUST be a power of two.”意思是:默認初始容量-必須是2的冪。
自動擴容
除了size,初始化的時候還會設(shè)定一個閾值,值為12,newThr = 12,這里需要提到一個概念負載因子,HashMap的實現(xiàn)里默認給的是0.75。
負載因子是用來干嘛的呢?當(dāng)我們不停的往map里存數(shù)據(jù)的時候,總會存滿,當(dāng)元素快存滿的時候,我們就需要擴大map的容量,來容納更多的元素,這就需要一個自動擴容的機制了。
在當(dāng)數(shù)據(jù)量大于超過設(shè)定的閾值的時候(容量*負載因子),自動對map進行擴容,以存放更多的數(shù)據(jù)。
自動擴容做了什么事情呢?
- 1、創(chuàng)建新的數(shù)組,大小是原來數(shù)組的一倍。
- 2、將元素rehash到新的數(shù)組
為什么要rehash呢?上面我們提到過了,當(dāng)元素被放進map時,確認下標(biāo)的方法是table的長度-1和hash值做與運算,現(xiàn)在table的長度發(fā)生了變化,那么自然而然,元素獲取下標(biāo)的運算結(jié)果也就跟之前的不一樣了, 所以需要將老的map中的元素再按照新的table長度rehash到擴容后的table中。
put的過程
了解了底層數(shù)據(jù)結(jié)構(gòu)和自動擴容機制,接下來我們來看一下put過程中究竟發(fā)生了什么。
我們上面說過了,會通過數(shù)組的長度-1和hash值與運算得到一個數(shù)組下標(biāo)。
如果該位置沒有元素,那么就很簡單,直接新建一個節(jié)點即可然后放置在數(shù)據(jù)的具體位置即可。
tab[i] = this.newNode(hash, key, value, (HashMap.Node)null);
但是如果該下標(biāo)已經(jīng)有元素了,這種情況HashMap是怎么處理的呢?這也要看情況。
如果是跟當(dāng)前槽位相同的key,就直接覆蓋。這就是我們修改某個key的值會發(fā)生的情況。
那HashMap怎么來判斷是不是同一個key呢?
就像下面這樣。p就是當(dāng)前槽位上已經(jīng)有的元素,如果新、老元素的key的hashCode和值都相同且key不為空,那么就能證明這兩個key是相同的,那么此時只需要覆蓋即可。
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
而如果p是TreeNode的實例,那么就代表當(dāng)前槽位已經(jīng)是一個紅黑樹了,此時只需要往這個樹里putTreeVal即可。
至于為什么是紅黑樹,哪兒來的紅黑樹,下面馬上就要講到了。
最后一種情況就是,既不是已經(jīng)存在的元素也不是TreeNode的實例,也不是紅黑樹。這種情況下,它就是一個普通的Node。
你可以理解為鏈表,如果hash沖突了,就把這個Node放到該位置的鏈表末尾。
當(dāng)該位置的鏈表中的元素超過了TREEIFY_THRESHOLD所設(shè)置的數(shù)量時,就會觸發(fā)樹化,將其轉(zhuǎn)化為紅黑樹。Java8里給的默認值是8。
為啥要轉(zhuǎn)化成紅黑樹?
首先我們要知道為什么要樹化。
當(dāng)大量的數(shù)據(jù)放入Map中,Hash沖突會越來越多,某些位置就會出現(xiàn)一個很長的鏈表的情況。
這種情況下,查詢時間復(fù)雜度是O(n) ,刪除的時間復(fù)雜度也是O(n),查詢、刪除的效率會大大降低。
而同樣的數(shù)據(jù)情況下,平衡二叉樹的時間復(fù)雜度都是O(logn)。
總結(jié)
以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關(guān)文章
SpringBoot全局配置long轉(zhuǎn)String丟失精度問題解決方案
這篇文章主要介紹了SpringBoot全局配置long轉(zhuǎn)String丟失精度問題解決方案,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08spring?boot自動裝配之@ComponentScan注解用法詳解
@ComponentScan的作用就是根據(jù)定義的掃描路徑,把符合掃描規(guī)則的類裝配到spring容器中,下面這篇文章主要給大家介紹了關(guān)于spring?boot自動裝配之@ComponentScan注解用法的相關(guān)資料,需要的朋友可以參考下2023-04-04IKAnalyzer結(jié)合Lucene實現(xiàn)中文分詞(示例講解)
下面小編就為大家?guī)硪黄狪KAnalyzer結(jié)合Lucene實現(xiàn)中文分詞(示例講解)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-10-10經(jīng)典的Java面試題及回答集錦(基礎(chǔ)篇)
本文給大家收藏整理了java面試題及回答,非常不錯,具有參考借鑒價值,需要的朋友參考下吧2018-03-03