HashMap数据结构数组+链表+(红黑树jdk>=8)源码原理分析重要成员变量DEFAULT_INITIAL_CAPACITY=1<<4;Hash表默认初始容量MAXIMUM_CAPACITY=1<<30;最大Hash表容量DEFAULT_LOAD_FACTOR=0.75f；默认加载因子TREEIFY_THRESHOLD=8；链表转红黑树阈值UNTREEIFY_THRESHOLD=6；红黑树转链表阈值MIN_TREEIFY_CAPACITY=64；链表转红黑树时hash表最小容量阈值，达不到优先扩容。内部的执行机制源码HashMap是线程不安全的，不安全的具体原因就是在高并发场景下，扩容可能产生死锁(Jdk1.7存在)以及get操作可能带来的数据丢失。Jdk7-扩容死锁分析死锁问题核心在于下面代码，多线程扩容导致形成的链表环!1voidtransfer(Entry[]newTable,booleanrehash){2intnewCapacity=newTable.length;3for(Entrye:table){4while(null!=e){5Entrynext=e.next;//第一行6if(rehash){7e.hash=null==e.key?0:hash(e.key);8}9inti=indexFor(e.hash,newCapacity);//第二行10e.next=newTable[i];//第三行11newTable[i]=e;//第四行12e=next;//第五行13}14}15}去掉了一些冗余的代码，层次结构更加清晰了。第一行：记录oldhash表中e.next第二行：rehash计算出数组的位置(hash表中桶的位置)第三行：e要插入链表的头部，所以要先将e.next指向newhash表中的第一个元素第四行：将e放入到newhash表的头部第五行：转移e到下一个节点，继续循环下去单线程扩容假设：hash算法就是简单的key与length(数组长度)求余。hash表长度为2，如果不扩容，那么元素key为3,5,7按照计算(key%table.length)的话都应该碰撞到table[1]上。扩容：hash表长度会扩容为4重新hash，key=3会落到table[3]上(3%4=3)，当前e.next为key(7),继续while循环重新hash，key=7会落到table[3]上(7%4=3),产生碰撞，这里采用的是头插入法，所以key=7的Entry会排在key=3前面(这里可以具体看while语句中代码)当前e.next为key(5),继续while循环重新hash，key=5会落到table[1]上(5%4=3)，当前e.next为null,跳出while循环，resize结束。如下图所示多线程扩容下面就是多线程同时put的情况了，然后同时进入transfer方法中：假设这里有两个线程同时执行了put()操作，并进入了transfer()环节1while(null!=e){2Entrynext=e.next;//第一行，线程1执行到此被调度挂起3inti=indexFor(e.hash,newCapacity);//第二行4e.next=newTable[i];//第三行5newTable[i]=e;//第四行6e=next;//第五行7}那么此时状态为：从上面的图我们可以看到，因为线程1的e指向了key(3)，而next指向了key(7)，在线程2rehash后，就指向了线程2rehash后的链表。然后线程1被唤醒了：1.执行e.next=newTable[i]，于是key(3)的next指向了线程1的新Hash表，因为新Hash表为空，所以e.next=null，2.执行newTable[i]=e，所以线程1的新Hash表第一个元素指向了线程2新Hash表的key(3)。好了，e处理完毕。3.执行e=next，将e指向next，所以新的e是key(7)然后该执行key(3)的next节点key(7)了:1.现在的e节点是key(7)，首先执行Entrynext=e.next,那么next就是key(3)了2.执行e.next=newTable[i]，于是key(7)的next就成了key(3)3.执行newTable[i]=e，那么线程1的新Hash表第一个元素变成了key(7)4.执行e=next，将e指向next，所以新的e是key(3)此时状态为：然后又该执行key(7)的next节点key(3)了：1.现在的e节点是key(3)，首先执行Entrynext=e.next,那么next就是null2.执行e.next=newTable[i]，于是key(3)的next就成了key(7)3.执行newTable[i]=e，那么线程1的新Hash表第一个元素变成了key(3)4.执行e=next，将e指向next，所以新的e是key(7)这时候的状态如图所示：很明显，环形链表出现了。Jdk8-扩容Java8HashMap扩容跳过了Jdk7扩容的坑，对源码进行了优化，采用高低位拆分转移方式，避免了链表环的产生。扩容前：扩容后：由于Jdk8引入了新的数据结构，所以put方法过程也有了一定改进，其过程如下图所示。ConcurrentHashMap数据结构ConcurrentHashMap的数据结构与HashMap基本类似，区别在于：1、内部在数据写入时加了同步机制(分段锁)保证线程安全，读操作是无锁操作；2、扩容时老数据的转移是并发执行的，这样扩容的效率更高。并发安全控制Java7ConcurrentHashMap基于ReentrantLock实现分段锁Java8中ConcurrentHashMap基于分段锁+CAS保证线程安全，分段锁基于synchronized关键字实现；源码原理分析重要成员变量ConcurrentHashMap拥有出色的性能,在真正掌握内部结构时,先要掌握比较重要的成员:LOAD_FACTOR:负载因子,默认75%,当table使用率达到75%时,为减少table的hash碰撞,tabel长度将扩容一倍。负载因子计算:元素总个数%table.lenghTREEIFY_THRESHOLD:默认8,当链表长度达到8时,将结构转变为红黑树。UNTREEIFY_THRESHOLD:默认6,红黑树转变为链表的阈值。MIN_TRANSFER_STRIDE:默认16,table扩容时,每个线程最少迁移table的槽位个数。MOVED:值为-1,当Node.hash为MOVED时,代表着table正在扩容TREEBIN,置为-2,代表此元素后接红黑树。nextTable:table迁移过程临时变量,在迁移过程中将元素全部迁移到nextTable上。sizeCtl:用来标志table初始化和扩容的,不同的取值代表着不同的含义:0:table还没有被初始化-1:table正在初始化小于-1:实际值为resizeStamp(n)<1的元素开始迁移,transferIndex代表当前已经迁移的元素下标ForwardingNode:一个特殊的Node节点,其hashcode=MOVED,代表着此时table正在做扩容操作。扩容期间,若table某个元素为null,那么该元素设置为ForwardingNode,当下个线程向这个元素插入数据时,检查hashcode=MOVED,就会帮着扩容。ConcurrentHashMap由三部分构成,table+链表+红黑树,其中table是一个数组,既然是数组,必须要在使用时确定数组的大小,当table存放的元素过多时,就需要扩容,以减少碰撞发生次数,本文就讲解扩容的过程。扩容检查主要发生在插入元素(putVal())的过程:一个线程插完元素后,检查table使用率,若超过阈值,调用transfer进行扩容一个线程插入数据时,发现table对应元素的hash=MOVED,那么调用helpTransfer()协助扩容。协助扩容helpTransfer下面是协助扩容的过程1finalNode[]helpTransfer(Node[]tab,Nodef){//table扩容2Node[]nextTab;intsc;3if(tab!=null&&(finstanceofForwardingNode)&&4(nextTab=((ForwardingNode)f).nextTable)!=null){5//根据length得到一个标识符号6intrs=resizeStamp(tab.length);7while(nextTab==nextTable&&table==tab&&8(sc=sizeCtl)<0){//说明还在扩容9//判断是否标志发生了变化||扩容结束了10if((sc>>>RESIZE_STAMP_SHIFT)!=rs||sc==rs+1||11//达到最大的帮助线程||判断扩容转移下标是否在调整（扩容结束）12sc==rs+MAX_RESIZERS||transferIndex<=0)13break;14//将sizeCtl+1,（表示增加了一个线程帮助其扩容）15if(U.compareAndSwapInt(this,SIZECTL,sc,sc+1)){16transfer(tab,nextTab);17break;18}19}20returnnextTab;21}22returntable;23}主要做了如下事情:检查是否扩容完成对sizeCtrl=sizeCtrl+1,然后调用transfer()进行真正的扩容。扩容transfer扩容的整体步骤就是新建一个nextTab,size是之前的2倍,将table上的非空元素迁移到nextTab上面去。1privatefinalvoidtransfer(Node[]tab,Node[]nextTab){2intn=tab.length,stride;3if((stride=(NCPU>1)?(n>>>3)/NCPU:n)[]nt=(Node[])newNode[n<<1];//扩容2倍11nextTab=nt;12}catch(Throwableex){//trytocopewithOOME13sizeCtl=Integer.MAX_VALUE;14return;15}16nextTable=nextTab;17transferIndex=n;//更新的转移下标，18}19intnextn=nextTab.length;20ForwardingNodefwd=newForwardingNode(nextTab);21//是否能够向前推进到下一个周期22booleanadvance=true;23//toensuresweepbeforecommittingnextTab，完成状态，如果是，则结束此方法24booleanfinishing=false;25for(inti=0,bound=0;;){26Nodef;intfh;27while(advance){//取下一个周期28intnextIndex,nextBound;29//本线程处理的区间范围为[bound,i),范围还没有处理完成，那么就继续处理30if(‐‐i>=bound||finishing)31advance=false;32//目前处理到了这里（从大到小，下线），开始找新的一轮的区间33elseif((nextIndex=transferIndex)<=0){34i=‐1;35advance=false;36}37//这个条件改变的是transferIndex的值，从16变成了138elseif(U.compareAndSwapInt39(this,TRANSFERINDEX,nextIndex,40//nextBound是这次迁移任务的边界，注意，是从后往前41nextBound=(nextIndex>stride?42nextIndex‐stride:0))){43bound=nextBound;//一块区间最小桶的下标44i=nextIndex‐1;//能够处理的最大桶的下标45advance=false;46}47}48if(i<0||i>=n||i+n>=nextn){//每个迁移线程都能达到这里49intsc;50if(finishing){//迁移完成51nextTable=null;52//直接把以前的table丢弃了，上面的MOVE等标志全部丢弃，使用新的53table=nextTab;54sizeCtl=(n<<1)‐(n>>>1);//扩大2n‐0.5n=1.50n,更新新的容量阈值55return;56}57//表示当前线程迁移完成了58if(U.compareAndSwapInt(this,SIZECTL,sc=sizeCtl,sc‐1)){59//注意此时sc的值并不等于sizeCtl，上一步，sizeCtl=sizeCtl‐1了。这两个对象还是分割的60if((sc‐2)!=resizeStamp(n)<ln,hn;//高位桶，地位桶76if(fh>=0){77intrunBit=fh&n;//n为2^n,取余后只能是2^n78NodelastRun=f;79///找到最后一个不和fn相同的节点80for(Nodep=f.next;p!=null;p=p.next){81intb=p.hash&n;82//只要找到这，之后的取值都是一样的，下次循环时，就不用再循环后面的83if(b!=runBit){84runBit=b;85lastRun=p;86}87}88if(runBit==0){89ln=lastRun;90hn=null;91}92else{//比如1，16，32,如果低位%16，那么肯定是0。93hn=lastRun;94ln=null;95}96for(Nodep=f;p!=lastRun;p=p.next){97intph=p.hash;Kpk=p.key;Vpv=p.val;98if((ph&n)==0)99//这样就把相同串的给串起来了100ln=newNode(ph,pk,pv,ln);101else102//这样就把相同串的给串起来了，注意这里ln用法，第一个next为null，烦着串起来了。103hn=newNode(ph,pk,pv,hn);104}105setTabAt(nextTab,i,ln);//反着给串起来了106setTabAt(nextTab,i+n,hn);107setTabAt(tab,i,fwd);108advance=true;109}110elseif(finstanceofTreeBin){//如果是红黑树111TreeBint=(TreeBin)f;112TreeNodelo=null,loTail=null;//也是高低节点113TreeNodehi=null,hiTail=null;//也是高低节点114intlc=0,hc=0;115for(Nodee=t.first;e!=null;e=e.next){//中序遍历红黑树116inth=e.hash;117TreeNodep=newTreeNode118(h,e.key,e.val,null,null);119if((h&n)==0){//0的放低位120//注意这里p.prev=loTail，每一个p都是下一个的prev121if((p.prev=loTail)==null)122lo=p;//把头记住123else124loTail.next=p;//上一次的p的next是这次的p125loTail=p;//把上次p给记住126++lc;127}128else{//高位129if((p.prev=hiTail)==null)130hi=p;//把尾记住elsehiTail.next=p;hiTail=p;134++hc;135}136}ln=(lc<=UNTREEIFY_THRESHOLD)?untreeify(lo):////判断是否需要转化为树(hc!=0)?newTreeBin(lo):t;//如果没有高低的话，则部分为两个树hn=(hc<=UNTREEIFY_THRESHOLD)?untreeify(hi):(lc!=0)?newTreeBin(hi):t;setTabAt(nextTab,i,ln);setTabAt(nextTab,i+n,hn);setTabAt(tab,i,fwd);advance=true;145}146}147}148}149}150}其中有两个变量需要了解下:advance:表示是否可以向下一个轮元素进行迁移。finishing:table所有元素是否迁移完成。大致做了如下事情:确定线程每轮迁移元素的个数stride,比如进来一个线程,确定扩容table下标为(a,b]之间元素,下一个线程扩容(b,c]。这里对b-a或者c-b也是由最小值16限制的。也就是说每个线程最少扩容连续16个table的元素。而标志当前迁移的下标保存在transferIndex里面。检查nextTab是否完成初始化,若没有的话,说明是第一个迁移的线程,先初始化nextTab,size是之前table的2倍。进入while循环查找本轮迁移的table下标元素区间,保存在(bound,i]中,注意这里是半开半闭区间。从i->bound开始遍历table中每个元素,这里是从大到小遍历的:1.若该元素为空,则向该元素标写入ForwardingNode,然后检查下一个元素。当别的线程向这个元素插入数据时,根据这个标志符知道了table正在被别的线程迁移,在putVal中就会调用helpTransfer帮着迁移。2.若该元素的hash=MOVED,代表次table正在处于迁移之中,跳过。按道理不会跑着这里的。3.否则说明该元素跟着的是一个链表或者是个红黑树结构,若hash>0,则说明是个链表,若finstanceofTreeBin,则说明是个红黑树结构。链表迁移原理如下:遍历链表每个节点。若节点的f.hash&n==0成立,则将节点放在i,否则,则将节点放在n+i上面。迁移前,对该元素进行加锁。遍历链表时,这里使用lastRun变量,保留的是上次hash的值,假如整个链表全部节点f.hash&n==0,那么第二次遍历,只要找到lastRun的值,那么认为之后的节点都是相同值,减少了不必要的f.hash&n取值。遍历完所有的节点后,此时形成了两条链表,ln存放的是f.hash&n=0的节点,hn存放的是非0的节点,然后将ln存放在nextTable第i元素的位置,n+i存放在n+i的位置。蓝色节点代表:f.hash&n==0,绿色节点代表f.hash&n!=0。最终蓝色的节点仍在存放在(0,n)范围里,绿的节点存放在(n,2n-1)的范围之内。迁移链表和红黑树的原理是一样的,在红黑树中,我们记录了每个红黑树的first(这个节点不是hash最小的节点)和每个节点的next,根据这两个元素,我们可以访问红黑树所有的元素,红黑树此时也是一个链表,红黑树和链表迁移的过程一样。红黑树根据迁移后拆分成了hn和ln,根据链表长度确定链表是红黑树结构还是退化为了链表。4.如何确定table所有元素迁移完成:1//表示当前线程迁移完成了2if(U.compareAndSwapInt(this,SIZECTL,sc=sizeCtl,sc‐1)){3//注意此时sc的值并不等于sizeCtl，上一步，sizeCtl=sizeCtl‐1了。这两个对象还是分割的4if((sc‐2)!=resizeStamp(n)<resizeStamp(n)<
