扣丁學(xué)堂Java視頻教程之HashMap原理和底層實(shí)現(xiàn)
2018-02-02 11:03:09
1830瀏覽
首先java中比較常見(jiàn)的map類(lèi)型，主要有HashMap,HashTable,LinkedHashMap和concurrentHashMap。這幾種map有各自的特性和適用場(chǎng)景。使用方法的話，就不說(shuō)了，本文重點(diǎn)介紹其原理和底層的實(shí)現(xiàn)。文章中的代碼來(lái)源于jdk1.9版本。
HashMap特點(diǎn)及原理分析
特點(diǎn)
HashMap是java中使用最為頻繁的map類(lèi)型，其讀寫(xiě)效率較高，但是因?yàn)槠涫欠峭降?，即讀寫(xiě)等操作都是沒(méi)有鎖保護(hù)的，所以在多線程場(chǎng)景下是不安全的，容易出現(xiàn)數(shù)據(jù)不一致的問(wèn)題。在單線程場(chǎng)景下非常推薦使用。
原理
HashMap的整體結(jié)構(gòu)，如下圖所示：
根據(jù)圖片可以很直觀的看到，HashMap的實(shí)現(xiàn)并不難，是由數(shù)組和鏈表兩種數(shù)據(jù)結(jié)構(gòu)組合而成的，其節(jié)點(diǎn)類(lèi)型均為名為Entry的class(后邊會(huì)對(duì)Entry做講解)。采用這種數(shù)據(jù)結(jié)果，即是綜合了兩種數(shù)據(jù)結(jié)果的優(yōu)點(diǎn)，既能便于讀取數(shù)據(jù)，也能方便的進(jìn)行數(shù)據(jù)的增刪。
每一個(gè)哈希表，在進(jìn)行初始化的時(shí)候，都會(huì)設(shè)置一個(gè)容量值(capacity)和加載因子(loadFactor)。容量值指的并不是表的真實(shí)長(zhǎng)度，而是用戶(hù)預(yù)估的一個(gè)值，真實(shí)的表長(zhǎng)度，是不小于capacity的2的整數(shù)次冪。加載因子是為了計(jì)算哈希表的擴(kuò)容門(mén)限，如果哈希表保存的節(jié)點(diǎn)數(shù)量達(dá)到了擴(kuò)容門(mén)限，哈希表就會(huì)進(jìn)行擴(kuò)容的操作，擴(kuò)容的數(shù)量為原表數(shù)量的2倍。默認(rèn)情況下，capacity的值為16，loadFactor的值為0.75(綜合考慮效率與空間后的折衷)。
數(shù)據(jù)寫(xiě)入。以HashMap(String,String)為例，即對(duì)于每一個(gè)節(jié)點(diǎn)，其key值類(lèi)型為String，value值類(lèi)型也為String。在向哈希表中插入數(shù)據(jù)的時(shí)候，首先會(huì)計(jì)算出key值的hashCode，即key.hashCode()。關(guān)于hashCode方法的實(shí)現(xiàn)，有興趣的朋友可以看一下jdk的源碼(之前看到信息說(shuō)有一次面試中問(wèn)到了這個(gè)知識(shí)點(diǎn))。該方法會(huì)返回一個(gè)32位的int類(lèi)型的值，以inth=key.hashCode()為例。獲取到h的值之后，會(huì)計(jì)算該key對(duì)應(yīng)的哈希表中的數(shù)組的位置，計(jì)算方法就是取模運(yùn)算，h%table.length。因?yàn)閠able的長(zhǎng)度為2的整數(shù)次冪，所以可以用h與table.length-1直接進(jìn)行位與運(yùn)算，即是，index=h&(table.length-1)。得到的index就是放置新數(shù)據(jù)的位置。
如果插入多條數(shù)據(jù)，則有可能最后計(jì)算出來(lái)的index是相同的，比如1和17，計(jì)算的index均為1。這時(shí)候出現(xiàn)了hash沖突。HashMap解決哈希沖突的方式，就是使用鏈表。每個(gè)鏈表，保存的是index相同的數(shù)據(jù)。
數(shù)據(jù)讀取。從哈希表中讀取數(shù)據(jù)時(shí)候，先定位到對(duì)應(yīng)的index，然后遍歷對(duì)應(yīng)位置的鏈表，找到key值和hashCode相同的節(jié)點(diǎn)，獲取對(duì)應(yīng)的value值。
數(shù)據(jù)刪除。在hashMap中，數(shù)據(jù)刪除的成本很低，直接定位到對(duì)應(yīng)的index，然后遍歷該鏈表，刪除對(duì)應(yīng)的節(jié)點(diǎn)。哈希表中數(shù)據(jù)的分布越均勻，則刪除數(shù)據(jù)的效率越高(考慮到極端場(chǎng)景，數(shù)據(jù)均保存到了數(shù)組中，不存在鏈表，則復(fù)雜度為O(1))。
JDK源碼分析
構(gòu)造方法
/**
*Constructsanempty{@codeHashMap}withthespecifiedinitial
*capacityandloadfactor.
*
*@paraminitialCapacitytheinitialcapacity
*@paramloadFactortheloadfactor
*@throwsIllegalArgumentExceptioniftheinitialcapacityisnegative
*ortheloadfactorisnonpositive
*/
publicHashMap(intinitialCapacity,floatloadFactor){
if(initialCapacity<0)
thrownewIllegalArgumentException("Illegalinitialcapacity:"+
initialCapacity);
if(initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
if(loadFactor<=0||Float.isNaN(loadFactor))
thrownewIllegalArgumentException("Illegalloadfactor:"+
loadFactor);
this.loadFactor=loadFactor;
this.threshold=tableSizeFor(initialCapacity);
}
從構(gòu)造方法中可以看到
參數(shù)中的initialCapacity并不是哈希表的真實(shí)大小。真實(shí)的表大小，是不小于initialCapacity的2的整數(shù)次冪。
哈希表的大小是存在上限的，就是2的30次冪。當(dāng)哈希表的大小到達(dá)該數(shù)值時(shí)候，之后就不再進(jìn)行擴(kuò)容，只是向鏈表中插入數(shù)據(jù)了。
PUT方法
/**
*Associatesthespecifiedvaluewiththespecifiedkeyinthismap.
*Ifthemappreviouslycontainedamappingforthekey,theold
*valueisreplaced.
*
*@paramkeykeywithwhichthespecifiedvalueistobeassociated
*@paramvaluevaluetobeassociatedwiththespecifiedkey
*@returnthepreviousvalueassociatedwith{@codekey},or
*{@codenull}iftherewasnomappingfor{@codekey}.
*(A{@codenull}returncanalsoindicatethatthemap
*previouslyassociated{@codenull}with{@codekey}.)
*/
publicVput(Kkey,Vvalue){
returnputVal(hash(key),key,value,false,true);
}
/**
*ImplementsMap.putandrelatedmethods
*
*@paramhashhashforkey
*@paramkeythekey
*@paramvaluethevaluetoput
*@paramonlyIfAbsentiftrue,don'tchangeexistingvalue
*@paramevictiffalse,thetableisincreationmode.
*@returnpreviousvalue,ornullifnone
*/
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,
booleanevict){
Node[]tab;Nodep;intn,i;
if((tab=table)==null||(n=tab.length)==0)
n=(tab=resize()).length;
if((p=tab[i=(n-1)&hash])==null)
tab[i]=newNode(hash,key,value,null);
else{
Nodee;Kk;
if(p.hash==hash&&
((k=p.key)==key||(key!=null&&key.equals(k))))
e=p;
elseif(pinstanceofTreeNode)
e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);
else{
for(intbinCount=0;;++binCount){
if((e=p.next)==null){
p.next=newNode(hash,key,value,null);
if(binCount>=TREEIFY_THRESHOLD-1)//-1for1st
treeifyBin(tab,hash);
break;
}
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
break;
p=e;
}
}
if(e!=null){//existingmappingforkey
VoldValue=e.value;
if(!onlyIfAbsent||oldValue==null)
e.value=value;
afterNodeAccess(e);
returnoldValue;
}
}
++modCount;
if(++size>threshold)
resize();
afterNodeInsertion(evict);
returnnull;
}
可以看到：
給哈希表分配空間的動(dòng)作，是向表中添加第一個(gè)元素觸發(fā)的，并不是在哈希表初始化的時(shí)候進(jìn)行的。
如果對(duì)應(yīng)index的數(shù)組值為null，即插入該index位置的第一個(gè)元素，則直接設(shè)置tab[i]的值即可。
查看數(shù)組中index位置的node是否具有相同的key和hash如果有，則修改對(duì)應(yīng)值即可。
遍歷數(shù)組中index位置的鏈表，如果找到了具有相同key和hash的node，跳出循環(huán)，進(jìn)行value更新操作。否則遍歷到鏈表的結(jié)尾，并在鏈表最后添加一個(gè)節(jié)點(diǎn)，將對(duì)應(yīng)數(shù)據(jù)添加進(jìn)去。
方法中涉及到了TreeNode，可以暫時(shí)先不關(guān)注。
GET方法
/**
*Returnsthevaluetowhichthespecifiedkeyismapped,
*or{@codenull}ifthismapcontainsnomappingforthekey.
*
*
Moreformally,ifthismapcontainsamappingfromakey
*{@codek}toavalue{@codev}suchthat{@code(key==null?k==null:
*key.equals(k))},thenthismethodreturns{@codev};otherwise
*itreturns{@codenull}.(Therecanbeatmostonesuchmapping.)
*
*
Areturnvalueof{@codenull}doesnotnecessarily
*indicatethatthemapcontainsnomappingforthekey;it'salso
*possiblethatthemapexplicitlymapsthekeyto{@codenull}.
*The{@link#containsKeycontainsKey}operationmaybeusedto
*distinguishthesetwocases.
*
*@see#put(Object,Object)
*/
publicVget(Objectkey){
Nodee;
return(e=getNode(hash(key),key))==null?null:e.value;
}
/**
*ImplementsMap.getandrelatedmethods
*
*@paramhashhashforkey
*@paramkeythekey
*@returnthenode,ornullifnone
*/
finalNodegetNode(inthash,Objectkey){
Node[]tab;Nodefirst,e;intn;Kk;
if((tab=table)!=null&&(n=tab.length)>0&&
(first=tab[(n-1)&hash])!=null){
if(first.hash==hash&&//alwayscheckfirstnode
((k=first.key)==key||(key!=null&&key.equals(k))))
returnfirst;
if((e=first.next)!=null){
if(firstinstanceofTreeNode)
return((TreeNode)first).getTreeNode(hash,key);
do{
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
returne;
}while((e=e.next)!=null);
}
}
returnnull;
}
代碼分析：
先定位到數(shù)組中index位置，檢查第一個(gè)節(jié)點(diǎn)是否滿(mǎn)足要求
遍歷對(duì)應(yīng)該位置的鏈表，找到滿(mǎn)足要求節(jié)點(diǎn)進(jìn)行return
擴(kuò)容操作
/**
*Initializesordoublestablesize.Ifnull,allocatesin
*accordwithinitialcapacitytargetheldinfieldthreshold.
*Otherwise,becauseweareusingpower-of-twoexpansion,the
*elementsfromeachbinmusteitherstayatsameindex,ormove
*withapoweroftwooffsetinthenewtable.
*
*@returnthetable
*/
finalNode[]resize(){
Node[]oldTab=table;
intoldCap=(oldTab==null)?0:oldTab.length;
intoldThr=threshold;
intnewCap,newThr=0;
if(oldCap>0){
if(oldCap>=MAXIMUM_CAPACITY){
threshold=Integer.MAX_VALUE;
returnoldTab;
}
elseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&
oldCap>=DEFAULT_INITIAL_CAPACITY)
newThr=oldThr<<1;//doublethreshold
}
elseif(oldThr>0)//initialcapacitywasplacedinthreshold
newCap=oldThr;
else{//zeroinitialthresholdsignifiesusingdefaults
newCap=DEFAULT_INITIAL_CAPACITY;
newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);
}
if(newThr==0){
floatft=(float)newCap*loadFactor;
newThr=(newCap<MAXIMUM_CAPACITY&&ft<(float)MAXIMUM_CAPACITY?
(int)ft:Integer.MAX_VALUE);
}
threshold=newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[]newTab=(Node[])newNode[newCap];
table=newTab;
if(oldTab!=null){
for(intj=0;j<oldCap;++j){
Nodee;
if((e=oldTab[j])!=null){
oldTab[j]=null;
if(e.next==null)
newTab[e.hash&(newCap-1)]=e;
elseif(einstanceofTreeNode)
((TreeNode)e).split(this,newTab,j,oldCap);
else{//preserveorder
NodeloHead=null,loTail=null;
NodehiHead=null,hiTail=null;
Nodenext;
do{
next=e.next;
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;
}
}
}
}
}
returnnewTab;
}
代碼分析：
如果就容量大于0，容量到達(dá)最大值，則不擴(kuò)容。容量未到達(dá)最大值，則新容量和新門(mén)限翻倍。
如果舊門(mén)限和舊容量均為0，則相當(dāng)于初始化，設(shè)置對(duì)應(yīng)的容量和門(mén)限，分配空間。
舊數(shù)據(jù)的整理部分，非常非常的巧妙，先膜拜一下眾位大神。在外層遍歷node數(shù)組，對(duì)于每一個(gè)table[j]，判斷該node擴(kuò)容之后，是屬于低位部分(原數(shù)組)，還是高位部分(擴(kuò)容部分?jǐn)?shù)組)。判斷的方式就是位與舊數(shù)組的長(zhǎng)度，如果為0則代表的是地位數(shù)組，因?yàn)閕ndex的值小于舊數(shù)組長(zhǎng)度，位與的結(jié)果就是0;相反，如果不為零，則為高位部分?jǐn)?shù)組。低位數(shù)組，添加到以loHead為頭的鏈表中，高位數(shù)組添加到以hiHead為頭的數(shù)組中。鏈表遍歷結(jié)束，分別設(shè)置新哈希表的index位置和(index+舊表長(zhǎng)度)位置的值。非常的巧妙。
注意點(diǎn)
HashMap的操作中未進(jìn)行鎖保護(hù)，所以多線程場(chǎng)景下存取數(shù)據(jù)，很存在數(shù)據(jù)不一致的問(wèn)題，不推薦使用
HashMap中key和value可以為null
計(jì)算index的運(yùn)算，h&(length-1)，感覺(jué)很巧妙，學(xué)習(xí)了
哈希表的擴(kuò)容中的數(shù)據(jù)整理邏輯，寫(xiě)的非常非常巧妙，大開(kāi)眼界
以上就是關(guān)于扣丁學(xué)堂Java視頻教程之HashMap原理和底層實(shí)現(xiàn)的詳細(xì)介紹，最后想要學(xué)習(xí)JavaEE培訓(xùn)課程的小伙伴可以聯(lián)系我們扣丁學(xué)堂的咨詢(xún)老師，我們這里有配套的JavaEE視頻教程課程，在你成為JAVA開(kāi)發(fā)工程師的道路上助你一臂之力，或者直接加入扣丁學(xué)堂學(xué)習(xí)交流群：670348138。
【關(guān)注微信公眾號(hào)獲取更多的學(xué)習(xí)資料】
查看更多關(guān)于“Java開(kāi)發(fā)資訊”的相關(guān)文章>>
標(biāo)簽:
JavaEE視頻教程
JavaEE培訓(xùn)
JavaEE開(kāi)發(fā)工程師
Java培訓(xùn)
Java開(kāi)發(fā)程序員
HashMap
返回頂部