EEPW论坛

　　首先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开发工程师的道路上助你一臂之力，或者直接加入扣丁学堂学习交流群：850353792。