扣丁学堂Java视频教程之HashMap原理和底层实现

2018-02-02 11:03:09 854浏览

　　首先java中比较常见的map类型，主要有HashMap,HashTable,LinkedHashMap和concurrentHashMap。这几种map有各自的特性和适用场景。使用方法的话，就不说了，本文重点介绍其原理和底层的实现。文章中的代码来源于jdk1.9版本。

HashMap特点及原理分析

特点

HashMap是java中使用最为频繁的map类型，其读写效率较高，但是因为其是非同步的，即读写等操作都是没有锁保护的，所以在多线程场景下是不安全的，容易出现数据不一致的问题。在单线程场景下非常推荐使用。

原理

HashMap的整体结构，如下图所示：

根据图片可以很直观的看到，HashMap的实现并不难，是由数组和链表两种数据结构组合而成的，其节点类型均为名为Entry的class(后边会对Entry做讲解)。采用这种数据结果，即是综合了两种数据结果的优点，既能便于读取数据，也能方便的进行数据的增删。

每一个哈希表，在进行初始化的时候，都会设置一个容量值(capacity)和加载因子(loadFactor)。容量值指的并不是表的真实长度，而是用户预估的一个值，真实的表长度，是不小于capacity的2的整数次幂。加载因子是为了计算哈希表的扩容门限，如果哈希表保存的节点数量达到了扩容门限，哈希表就会进行扩容的操作，扩容的数量为原表数量的2倍。默认情况下，capacity的值为16，loadFactor的值为0.75(综合考虑效率与空间后的折衷)。

数据写入。以HashMap(String,String)为例，即对于每一个节点，其key值类型为String，value值类型也为String。在向哈希表中插入数据的时候，首先会计算出key值的hashCode，即key.hashCode()。关于hashCode方法的实现，有兴趣的朋友可以看一下jdk的源码(之前看到信息说有一次面试中问到了这个知识点)。该方法会返回一个32位的int类型的值，以inth=key.hashCode()为例。获取到h的值之后，会计算该key对应的哈希表中的数组的位置，计算方法就是取模运算，h%table.length。因为table的长度为2的整数次幂，所以可以用h与table.length-1直接进行位与运算，即是，index=h&(table.length-1)。得到的index就是放置新数据的位置。

如果插入多条数据，则有可能最后计算出来的index是相同的，比如1和17，计算的index均为1。这时候出现了hash冲突。HashMap解决哈希冲突的方式，就是使用链表。每个链表，保存的是index相同的数据。

数据读取。从哈希表中读取数据时候，先定位到对应的index，然后遍历对应位置的链表，找到key值和hashCode相同的节点，获取对应的value值。

数据删除。在hashMap中，数据删除的成本很低，直接定位到对应的index，然后遍历该链表，删除对应的节点。哈希表中数据的分布越均匀，则删除数据的效率越高(考虑到极端场景，数据均保存到了数组中，不存在链表，则复杂度为O(1))。

JDK源码分析

构造方法

/**

*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);

}

从构造方法中可以看到

参数中的initialCapacity并不是哈希表的真实大小。真实的表大小，是不小于initialCapacity的2的整数次幂。

哈希表的大小是存在上限的，就是2的30次幂。当哈希表的大小到达该数值时候，之后就不再进行扩容，只是向链表中插入数据了。

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;

}

可以看到：

给哈希表分配空间的动作，是向表中添加第一个元素触发的，并不是在哈希表初始化的时候进行的。

如果对应index的数组值为null，即插入该index位置的第一个元素，则直接设置tab[i]的值即可。

查看数组中index位置的node是否具有相同的key和hash如果有，则修改对应值即可。

遍历数组中index位置的链表，如果找到了具有相同key和hash的node，跳出循环，进行value更新操作。否则遍历到链表的结尾，并在链表最后添加一个节点，将对应数据添加进去。

方法中涉及到了TreeNode，可以暂时先不关注。

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;

}

代码分析：

先定位到数组中index位置，检查第一个节点是否满足要求

遍历对应该位置的链表，找到满足要求节点进行return

扩容操作

/**

*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，容量到达最大值，则不扩容。容量未到达最大值，则新容量和新门限翻倍。

如果旧门限和旧容量均为0，则相当于初始化，设置对应的容量和门限，分配空间。

旧数据的整理部分，非常非常的巧妙，先膜拜一下众位大神。在外层遍历node数组，对于每一个table[j]，判断该node扩容之后，是属于低位部分(原数组)，还是高位部分(扩容部分数组)。判断的方式就是位与旧数组的长度，如果为0则代表的是地位数组，因为index的值小于旧数组长度，位与的结果就是0;相反，如果不为零，则为高位部分数组。低位数组，添加到以loHead为头的链表中，高位数组添加到以hiHead为头的数组中。链表遍历结束，分别设置新哈希表的index位置和(index+旧表长度)位置的值。非常的巧妙。

注意点

HashMap的操作中未进行锁保护，所以多线程场景下存取数据，很存在数据不一致的问题，不推荐使用

HashMap中key和value可以为null

计算index的运算，h&(length-1)，感觉很巧妙，学习了

哈希表的扩容中的数据整理逻辑，写的非常非常巧妙，大开眼界

以上就是关于扣丁学堂Java视频教程之HashMap原理和底层实现的详细介绍，最后想要学习JavaEE培训课程的小伙伴可以联系我们扣丁学堂的咨询老师，我们这里有配套的JavaEE视频教程课程，在你成为JAVA开发工程师的道路上助你一臂之力，或者直接加入扣丁学堂学习交流群：670348138。

【关注微信公众号获取更多的学习资料】

查看更多关于“Java开发资讯”的相关文章>>