??HashMap是基于Map接口实现的，元素以key-value的方式存储在map在中，此实现提供所有可选的映射操作，并允许null的key和null的value。HashMap类与Hashtable类大致等效，不同之处在于它不是线程安全的，并且允许为null。HashMap的UML图如下图所示：
1.2构造方法??HashMap一共有4个构造方法，如下图所示：
/***构造一个空的HashMap，默认容量为16，负载因子为0.75*/publicHashMap(){this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR);}
/***构造一个空的HashMap，容量为指定的initialCapacity，负载因子默认为0.75*/publicHashMap(intinitialCapacity){this(initialCapacity,DEFAULT_LOAD_FACTOR);}
/***构造一个空的HashMap，具有指定初始值容量和负载因子的HashMap*/publicHashMap(intinitialCapacity,floatloadFactor){//判断传入的初始容量是否大于0，如果小于0，则抛出相应异常信息。if(initialCapacity0)thrownewIllegalArgumentException("Illegalinitialcapacity:"+initialCapacity);//判断传入的初始容量是否大于最大容量，如果大于最大容量，则将initialCapacity赋值为最大容量MAXIMUM_CAPACITY，，1左移30位if(initialCapacityMAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;//如果负载因子loadFactor小于0或者如果指定的数字不是一个数字(NaN)，返回{true，否则返回falseif(loadFactor=0
Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegalloadfactor:"+loadFactor);this.loadFactor=loadFactor;threshold=initialCapacity;init();}1.3基本属性
常量：
staticfinalintDEFAULT_INITIAL_CAPACITY：默认初始容量，14，1左移4位，默认大小为16。
staticfinalintMAXIMUM_CAPACITY：最大容量，如果任何一个带参数的构造函数隐式指定了较大的值，则使用。
staticfinalfloatDEFAULT_LOAD_FACTOR：默认负载因子,值为0.75f。
成员变量：
transientintsize：map中存储key-value的个数
transientEntryK,V[]table：entry数组，长度必须是2的幂。
intthreshold：扩容的阈值(capacity*loadfactor),如果table==EMPTY_TABLE，那么这个值为map初始容量大小。
finalfloatloadFactor：哈希表中的负载因子
2、数据结构??HashMap由数组和链表来实现对数据的存储。HashMap采用Entry数组来存储key-value键值对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。??HashMap中实现了一个静态内部类Entry，其重要的属性有hash，key，value，next。如下图所示：JDK1.7数据结构如下图所示：
3、源码解析3.1put过程分析??put(Kkey,Vvalue)方法
publicVput(Kkey,Vvalue){//判断table数组是否为空，如果为空，则初始化数组if(table==EMPTY_TABLE){inflateTable(threshold);}//如果key为空，调用putForNullKey方法put数据，最终会将元素存储在table[0]中if(key==null)returnputForNullKey(value);//计算key的哈希值inthash=hash(key);//根据哈希值和table数组长度计算数据存储在table中的索引下标inti=indexFor(hash,table.length);//取出table数组中索引i位置处的Entrye，如果e不为空，循环遍历Entry链表，判断是否有重复的key存在，如果有替换掉key的值for(EntryK,Ve=table[i];e!=null;e=e.next){Objectk;//如果当前节点e的哈希值、key与要put元素的哈希值、key相等if(e.hash==hash((k=e.key)==key
key.equals(k))){VoldValue=e.value;//使用新值替换掉旧值e.value=value;//每当对HashMap中已经存在的键k的put(k,v)调用覆盖条目中的值时，就会调用recordAccess方法。e.recordAccess(this);//返回旧值returnoldValue;}}//记录修改次数，结构修改是指那些改变HashMap中映射数量或修改其内部结构的修改(例如，重新哈希)。modCount++;//如果不存在重复的key，将当前元素添加到Entry链表中，后面会详细介绍此逻辑addEntry(hash,key,value,i);returnnull;}
??put方法中的初始化数组inflateTable(inttoSize)方法
//put方法中的初始化数组inflateTable(inttoSize)方法privatevoidinflateTable(inttoSize){//roundUpToPowerOf2方法的目的就是根据传入toSize计算出一个合理的初始容量，保证数组大小始终为2的n次方。//比如在newHashMap(17),通过此方法计算后得出初始化数组的大小为32，也就是最终的capacity要大于等于离toSize最近的2的n次方的数intcapacity=roundUpToPowerOf2(toSize);//计算扩容的阈值：capacity*loadFactorthreshold=(int)Math.min(capacity*loadFactor,MAXIMUM_CAPACITY+1);//new一个初始数组，大小为capacitytable=newEntry[capacity];initHashSeedAsNeeded(capacity);}
??putForNullKey(Vvalue)方法：当元素的key为null时，调用putForNullKey(Vvalue)方法存储元素数据,实际上当key为null时，数据是存储在table[0]的位置
privateVputForNullKey(Vvalue){//获取table[0]位置的数据，如果e不为null，遍历循环链表for(EntryK,Ve=table[0];e!=null;e=e.next){//如果e元素的key为null，使用新值替换掉旧值，并返回旧值。if(e.key==null){VoldValue=e.value;e.value=value;e.recordAccess(this);returnoldValue;}}modCount++;//如果table[0]位置没有元素的key为null,则将元素添加到table[0]的链表中addEntry(0,null,value,0);returnnull;}
??将元素添加到Entry链表中，调用addEntry(inthash,Kkey,Vvalue,intbucketIndex)方法。将具有指定键、值和散列码的元素添加到指定bucket位置。此方法负责在适当的情况下对table数组进行扩容处理
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){//如果map中的元素个数size=扩容阈值threshold，并且在table的bucketIndex索引下标处有值，需要进一步扩容操作if((size=threshold)(null!=table[bucketIndex])){//扩容操作，数组大小扩容为原来数组大小的2倍。resize(2*table.length);//扩容以后重新计算hash值，如果key为null，hash值为0。hash=(null!=key)?hash(key):0;//扩容后重新计算下标bucketIndex=indexFor(hash,table.length);}//根据元素hash、key、value值创建一个Entry，赋值到table的bucketIndex位置createEntry(hash,key,value,bucketIndex);}
//将新值放到链表的表头，size++voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){//获取table数组中bucketIndex位置的值EntryK,Ve=table[bucketIndex];//new一个Entry,将新加入的元素放在链表的表头table[bucketIndex]=newEntry(hash,key,value,e);//put中元素个数加1size++;}
??扩容过程：将此map中的数据重新散列到具有更大容量的新数组中。当此map中的键数达到其阈值时，将自动调用此方法。如果当前容量是MAXIMUM_CAPACITY，此方法不会调整map的大小，而是将阈值设置为Integer.MAX_VALUE。这具有防止以后调用的作用。
voidresize(intnewCapacity){//旧数组entryEntry[]oldTable=table;//旧数组大小intoldCapacity=oldTable.length;//如果旧数组大小等于最大容量值，则将扩容的阈值设置为Integer.MAX_VALUE，作用是防止以后再调用。if(oldCapacity==MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;return;}//创建一个新的tableEntry[]newTable=newEntry[newCapacity];//将所有entry从当前table转移到newTabletransfer(newTable,initHashSeedAsNeeded(newCapacity));//重新将table数据赋值为newTabletable=newTable;//计算下一次扩容的阈值threshold=(int)Math.min(newCapacity*loadFactor,MAXIMUM_CAPACITY+1);}
??将所有entry从当前table转移到newTable。
voidtransfer(Entry[]newTable,booleanrehash){//获取新table容量大小intnewCapacity=newTable.length;//循环遍历旧的table数据for(EntryK,Ve:table){//当entry不为nullwhile(null!=e){//获取链表entry的下一个元素EntryK,Vnext=e.next;//如果需要重新计算哈希值if(rehash){e.hash=null==e.key?0:hash(e.key);}//重新计算下标inti=indexFor(e.hash,newCapacity);//当前entry元素的下一个元素为新的table数组中的值（也就是头插法）e.next=newTable[i];//将entry值赋值到新table的索引i位置newTable[i]=e;//保证旧table的entry在下一次while循环使用e=next;}}}3.2get过程分析
??get过程相对put过程来说简单得很多，首先根据key计算hash值，再通过位运算（h(length-1)）找到数组索引下标，最后遍历数组下标位置处的Entry链表，找到对应的值即返回。返回指定key的值，如果map中不包含指定key的值，则返回null。
publicVget(Objectkey){//如果key为null，调用getForNullKey()方法，从table的0下标处取值if(key==null)returngetForNullKey();//返回HashMap中指定的key相关联的entry。如果HashMap不包含key的映射，则返回null。EntryK,Ventry=getEntry(key);//返回具体指returnnull==entry?null:entry.getValue();}
??getEntry(Objectkey)方法
//返回指定key的值，如果map中不包含指定key的值，则返回null。finalEntryK,VgetEntry(Objectkey){//如果map中没有数据，则返回null。if(size==0){returnnull;}//计算hash值inthash=(key==null)?0:hash(key);//获取索引位置处的Entry,循环遍历Entryfor(EntryK,Ve=table[indexFor(hash,table.length)];e!=null;e=e.next){Objectk;//如果entry的hash值与传入的key对应的hash值相等，且key也相等，则返回entryif(e.hash==hash((k=e.key)==key
(key!=nullkey.equals(k))))returne;}//未找到对应数据，返回null。returnnull;}3.3remove过程分析
??remove过程也是非常多简单，大概思路就是根据指定的key计算出hash值和table的索引值，循环遍历链表找到对应的entry删除即可。
//删除并返回与HashMap中指定key相关联的entry。如果HashMap不包含此key的map，则返回null。publicVremove(Objectkey){EntryK,Ve=removeEntryForKey(key);return(e==null?null:e.value);}
finalEntryK,VremoveEntryForKey(Objectkey){//如果map中没有数据，则返回null。if(size==0){returnnull;}//计算hash值inthash=(key==null)?0:hash(key);//计算数组索引下标inti=indexFor(hash,table.length);//获取索引处的entry值，前驱entryEntryK,Vprev=table[i];//当前entryEntryK,Ve=prev;while(e!=null){//当前entry的下一个entryEntryK,Vnext=e.next;Objectk;//如果当前entry的hash等于需要删除key对应的hash值，且key不为null，相等if(e.hash==hash((k=e.key)==key
(key!=nullkey.equals(k)))){//记录修改次数modCount++;//map中元素个数-1size--;//删除的是链表中第一个entry，断开当前entrye,table中i索引处的赋值为nextif(prev==e)table[i]=next;elseprev.next=next;//断开当前entrye,前驱entry的下一个entry为nexte.recordRemoval(this);//返回删除的entry信息returne;}//未找到删除的元素，重新给前驱prev赋值为e，当前e赋值为nextprev=e;e=next;}returne;}二、ConcurrentHashMap详解1、基本介绍1.1概述
??在Java1.5中，并发编程大师DougLea给我们带来了concurrent包，而该包中提供的ConcurrentHashMap是线程安全并且高效的HashMap。在并发编程中使用HashMap可能会导致死循环，而使用线程安全的HashTable效率又低下。HashMap之所以在并发下的扩容造成死循环，是因为多个线程并发进行时，因为一个线程先期完成了扩容，将原Map的链表重新散列到自己的表中，并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序链表。于是形成了一个环形链表，当get表中不存在的元素时，造成死循环。于是在多线程并发处理下，ConcurrentHashMap解决了HashMap在扩容到时候造成链表形成环形结构的问题。ConcurrentHashMapUML图如下图所示：
1.2构造方法??ConcurrentHashMap一共有5个构造方法，如下图所示：??ConcurrentHashMap初始化方法是通过initialCapacity、loadFactor和concurrencyLevel(参数concurrencyLevel是用户估计的并发级别，就是说你觉得最多有多少线程共同修改这个map，根据这个来确定Segment数组的大小concurrencyLevel默认是DEFAULT_CONCURRENCY_LEVEL=16;)等几个参数来初始化segment数组、段偏移量segmentShift、段掩码segmentMask和每个segment里的HashEntry数组来实现的。??并发级别可以理解为程序运行时能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数，实际上就是ConcurrentHashMap中的分段锁个数，即Segment[]的数组长度。ConcurrentHashMap默认的并发度为16，但用户也可以在构造函数中设置并发度。当用户设置并发度时，ConcurrentHashMap会使用大于等于该值的最小2幂指数作为实际并发度（假如用户设置并发度为17，实际并发度则为32）。??如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPUcache命中率会下降，从而引起程序性能下降。??segments数组的长度ssize是通过concurrencyLevel计算得出的。为了能通过按位与的散列算法来定位segments数组的索引，必须保证segments数组的长度是2的N次方（power-of-twosize），所以必须计算出一个大于或等于concurrencyLevel的最小的2的N次方值来作为segments数组的长度。假如concurrencyLevel等于14、15或16，ssize都会等于16，即容器里锁的个数也是16。
/***创建一个空的map，默认初始容量(16)、负载因子(0.75)和concurrencyLevel(16)。*/publicConcurrentHashMap(){this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR,DEFAULT_CONCURRENCY_LEVEL);}
/***创建一个空的map，指定初始容量，且默认负载因子(0.75)和concurrencyLevel(16)。*/publicConcurrentHashMap(intinitialCapacity){this(initialCapacity,DEFAULT_LOAD_FACTOR,DEFAULT_CONCURRENCY_LEVEL);}
/***创建一个空的map，指定初始容量和负载因子，且默认concurrencyLevel(16)。*/publicConcurrentHashMap(intinitialCapacity,floatloadFactor){this(initialCapacity,loadFactor,DEFAULT_CONCURRENCY_LEVEL);}
/***创建一个空的map，指定初始容量、负载因子和concurrencyLevel。*/publicConcurrentHashMap(intinitialCapacity,floatloadFactor,intconcurrencyLevel){//验证参数合法性if(!(loadFactor0)
initialCapacity0
concurrencyLevel=0)thrownewIllegalArgumentException();//如果并发级别concurrencyLevel大于允许的最大值MAX_SEGMENTS=，则concurrencyLevel等于最大值if(concurrencyLevelMAX_SEGMENTS)concurrencyLevel=MAX_SEGMENTS;//Findpower-of-twosizesbestmatchingargumentsintsshift=0;//segment数组的大小，根据并发级别来计算的。//以必须计算出一个大于或等concurrencyLevel的最小的2的N次方值来作为segments数组的长度。//假如concurrencyLevel等于14、15或16，ssize都会等于16，即容器里锁的个数也是16。intssize=1;while(ssizeconcurrencyLevel){++sshift;
ssize=1;
}//如果使用默认的concurrencyLevel16，那么计算出来的ssize为16，sshift为4，segmentShift为28，segmentMask为15//段偏移量this.segmentShift=32-sshift;//段掩码this.segmentMask=ssize-1;//如果指定的初始容量大于最大容量，则initialCapacity为最大容量值if(initialCapacityMAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;intc=initialCapacity/ssize;if(c*ssizeinitialCapacity)++c;//segment里HashEntry数组的长度，默认最小值为2，因为这样的话，对于具体的segment，在插入第一个元素的时候不会扩容，插入第二个是时候才会扩容intcap=MIN_SEGMENT_TABLE_CAPACITY;while(capc)cap=1;//创建一个segment数组，只初始化segments[0]位置处的HashEntrySegmentK,Vs0=newSegmentK,V(loadFactor,(int)(cap*loadFactor),(HashEntryK,V[])newHashEntry[cap]);SegmentK,V[]ss=(SegmentK,V[])newSegment[ssize];//将segments[0]写入数组中UNSAFE.putOrderedObject(ss,SBASE,s0);//orderedwriteofsegments[0]this.segments=ss;}1.3基本属性ConcurrentHashMap中的常量
staticfinalintDEFAULT_INITIAL_CAPACITY：table的默认初始容量，在构造函数中未指定时使用，默认大小为16。
staticfinalfloatDEFAULT_LOAD_FACTOR：table的默认负载因子，在构造函数中未指定时使用，默认大小为0.75f。
staticfinalintDEFAULT_CONCURRENCY_LEVEL：table的默认并发级别，在构造函数中未指定时使用，默认大小为16。
staticfinalintMAXIMUM_CAPACITY：table的最大容量，如果任何一个带参数的构造函数指定了较大的值，则使用。大小为，也就是1*2的30次方。
staticfinalintMIN_SEGMENT_TABLE_CAPACITY：每个segment中HashEntry的table最小容量。必须是2的n次方，默认为2。
staticfinalintMAX_SEGMENTS：最大segment容量，值为。
ConcurrentHashMap中的成员变量
finalSegmentK,V[]segments：segment，每个segment都是一个专用的hashtable。
Segment中的常量
staticfinalintMAX_SCAN_RETRIES：单核CPU的值为1，多核CPU的值为16。
Segment中的成员变量
transientvolatileHashEntryK,V[]table：每个segment中的table
transientintcount：元素个数
transientintmodCount：segment中mutativeoperations总数
transientintthreshold：扩容的阈值
finalfloatloadFactor：负载因子
Segment内的构造函数：
Segment(floatlf,intthreshold,HashEntryK,V[]tab){this.loadFactor=lf;this.threshold=threshold;this.table=tab;}2、数据结构
??ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁（ReentrantLock），在ConcurrentHashMap里扮演锁的角色；HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组。Segment的结构和HashMap类似，是一种数组和链表结构。一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得与它对应的Segment锁。如下图所示：
JDK1.7数据结构如下图所示：
3、源码解析3.1put过程源码解析??put(Kkey,Vvalue)方法：将指定的key-value存储到map中，且key-value都不能为空。可以通过调用get方法来获取相应值。首先我们来看一下ConcurrentHashMap中的put方法，在此方法中主要是确定新值要插入到哪一个segment中，而真正put数据的操作是在Segment类中的put方法。
publicVput(Kkey,Vvalue){SegmentK,Vs;//判断参数是否为空if(value==null)thrownewNullPointerException();//计算key的hash值，如果key为空，则报空指针异常inthash=hash(key);//根据hash值找到Segment数组中的位置j//hash是32位，无符号右移segmentShift(28)位，剩下低4位//再和segmentMask(15)做一次与操作，也就是说j是hash值的最后4位，也就是segment的数组下标intj=(hashsegmentShift)segmentMask;//在初始化的时候只初始化了segment[0]，但是其他位置还是null，ensureSegment(j)对segment[j]进行初始化if((s=(SegmentK,V)UNSAFE.getObject//nonvolatile;recheck(segments,(jSSHIFT)+SBASE))==null)//inensureSegments=ensureSegment(j);//插入新值到segment中returns.put(key,hash,value,false);}
??segment中的put方法，由数组+链表组成，这个HashMap数据结构一样。
//segment中的put方法，由数组+链表组成，这个HashMap数据结构一样。finalVput(Kkey,inthash,Vvalue,booleanonlyIfAbsent){//在往该segment写入前，需要先获取该segment的独占锁//put方法会通过tryLock()方法尝试获得锁，获得了锁，node为null进入try语句块，//没有获得锁，调用scanAndLockForPut方法自旋等待获得锁。HashEntryK,Vnode=tryLock()?null:scanAndLockForPut(key,hash,value);VoldValue;try{//segment中的HashEntry数组tableHashEntryK,V[]tab=table;//根据hash值和tab长度计算索引下标intindex=(tab.length-1)hash;//获取索引index处的HashEntry值，first是tab了数组该位置处的链表的表头HashEntryK,Vfirst=entryAt(tab,index);//for循环遍历first，两种情况，一种是index处有元素，另一种是index处没有元素。for(HashEntryK,Ve=first;;){//如果e不为空if(e!=null){Kk;//如果HashEntry中的key等于新值key或者HashEntry中的hash等于新值hash，且key相等if((k=e.key)==key
(e.hash==hashkey.equals(k))){oldValue=e.value;//判断是否替换旧值if(!onlyIfAbsent){e.value=value;++modCount;}break;}//继续执行链表下一个HashEntrye=e.next;}else{//node不为null，那就直接将它设置为链表表头if(node!=null)node.setNext(first);else//node为null，初始化并设置为链表表头node=newHashEntryK,V(hash,key,value,first);intc=count+1;//当table数组的大小超过阈值时，将对其进行重新散列、扩容操作。if(cthresholdtab.lengthMAXIMUM_CAPACITY)rehash(node);else//没有达到阈值，将node放到数组tab的index位置，也就是将新的节点设置成原链表的表头setEntryAt(tab,index,node);++modCount;count=c;oldValue=null;break;}}}finally{//释放锁unlock();}returnoldValue;}
??ensureSegment(intk)方法：ConcurrentHashMap初始化的时候会初始化第一个槽segment[0]，对于其他槽，在插入第一个值的时候再进行初始化。ensureSegment方法考虑了并发情况，多个线程同时进入初始化同一个槽segment[k]，但只要有一个成功就可以了。
//初始化segment：返回给定索引的segment，创建它并(通过CAS)记录在segmetntable中(如果还没有)。privateSegmentK,VensureSegment(intk){finalSegmentK,V[]ss=this.segments;longu=(kSSHIFT)+SBASE;//rawoffsetSegmentK,Vseg;if((seg=(SegmentK,V)UNSAFE.getObjectVolatile(ss,u))==null){//这里看到为什么之前要初始化segment[0]了，//使用当前segment[0]处的数组长度和负载因子来初始化segment[k]//为什么要用“当前”，因为segment[0]可能早就扩容过了SegmentK,Vproto=ss[0];//usesegment0asprototype，使用segment[0]作为原型，这也就是为什么要初始化segment[0]的原因intcap=proto.table.length;//segment[0]中table数组的长度floatlf=proto.loadFactor;//segment[0]中负载因子intthreshold=(int)(cap*lf);//计算下次扩容的阈值//创建一个HashEntry数组，容量为cap，也就是segment[k]内部的数组HashEntryK,V[]tab=(HashEntryK,V[])newHashEntry[cap];if((seg=(SegmentK,V)UNSAFE.getObjectVolatile(ss,u))==null){//recheck，再次检查一遍该segment[k]是否被其他线程初始化了。//创建一个segmentSegmentK,Vs=newSegmentK,V(lf,threshold,tab);//while循环CAS操作，保证多线程下只有一个线程可以成功while((seg=(SegmentK,V)UNSAFE.getObjectVolatile(ss,u))==null){//使用CAS操作，当前线程成功设值或其他线程成功设值后，退出if(UNSAFE.