万字解析ConcurrentHashMap源码

　　ConcurrentHashMap
　　在多线程环境下，使用HashMap进行put操作时存在丢失数据的情况，为了避免这种bug的隐患，强烈建议使用ConcurrentHashMap代替HashMap1。ConcurrentHashMap的结构
　　和HashMap一样是一个散列链表，数据存储在hash桶中。2。源码解析2。1属性及构造
　　属性privatestaticfinalintMAXIMUMCAPACITY130；privatestaticfinalintDEFAULTCAPACITY16；staticfinalintMAXARRAYSIZEInteger。MAXVALUE8；privatestaticfinalintDEFAULTCONCURRENCYLEVEL16；privatestaticfinalfloatLOADFACTOR0。75f；privatestaticfinalintMINTRANSFERSTRIDE16；privatestaticintRESIZESTAMPBITS16；privatestaticfinalintMAXRESIZERS（1（32RESIZESTAMPBITS））1；privatestaticfinalintRESIZESTAMPSHIFT32RESIZESTAMPBITS；staticfinalintTREEIFYTHRESHOLD8；staticfinalintUNTREEIFYTHRESHOLD6；staticfinalintMINTREEIFYCAPACITY64；privatestaticfinalsun。misc。UnsafeU；privatestaticfinallongSIZECTL；privatestaticfinallongTRANSFERINDEX；privatestaticfinallongBASECOUNT；privatestaticfinallongCELLSBUSY；privatestaticfinallongCELLVALUE；privatestaticfinallongABASE；privatestaticfinalintASHIFT；staticfinalintMOVED1；hashforforwardingnodesstaticfinalintTREEBIN2；hashforrootsoftreesstaticfinalintRESERVED3；hashfortransientreservationsstaticfinalintHASHBITS0x7fffffff；usablebitsofnormalnodehashstaticfinalintNCPURuntime。getRuntime（）。availableProcessors（）；volatile修饰的table，表示table数组在内存中对所有线程都及时可见，如果一个线程修改了table数组的值，其他线程中如果自己的线程栈中有table的副本，就会把table缓存行设置为失效，强制从内存中读取table数组的值。当然下面使用了volatile修饰的也是一样的transientvolatileNodeK，V〔〕table；一个过渡的table表只有在扩容的时候才会使用privatetransientvolatileNodeK，V〔〕nextTable；privatetransientvolatilelongbaseCount；Tableinitializationandresizingcontrol。Whennegative，thetableisbeinginitializedorresized：1forinitialization，else（1thenumberofactiveresizingthreads）。Otherwise，whentableisnull，holdstheinitialtablesizetouseuponcreation，or0fordefault。Afterinitialization，holdsthenextelementcountvalueuponwhichtoresizethetable。hash表初始化或扩容时的一个控制位标识量。负数代表正在进行初始化或扩容操作1代表正在初始化N表示有N1个线程正在进行扩容操作正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小privatetransientvolatileintsizeCtl；privatetransientvolatileinttransferIndex；privatetransientvolatileintcellsBusy；privatetransientvolatileCounterCell〔〕counterCells；viewsprivatetransientKeySetViewK，VkeySet；privatetransientValuesViewK，Vvalues；privatetransientEntrySetViewK，VentrySet；
　　构造Createsanew，emptymapwiththedefaultinitialtablesize（16）。publicConcurrentHashMap（）｛｝publicConcurrentHashMap（intinitialCapacity）｛if（initialCapacity0）thrownewIllegalArgumentException（）；intcap（（initialCapacity（MAXIMUMCAPACITY1））？MAXIMUMCAPACITY：tableSizeFor（initialCapacity（initialCapacity1）1））；this。sizeCtlcap；｝publicConcurrentHashMap（intinitialCapacity，floatloadFactor）｛this（initialCapacity，loadFactor，1）；｝publicConcurrentHashMap（intinitialCapacity，floatloadFactor，intconcurrencyLevel）｛if（！（loadFactor0。0f）initialCapacity0concurrencyLevel0）thrownewIllegalArgumentException（）；if（initialCapacityconcurrencyLevel）UseatleastasmanybinsinitialCapacityconcurrencyLevel；asestimatedthreadslongsize（long）（1。0（long）initialCapacityloadFactor）；intcap（size（long）MAXIMUMCAPACITY）？MAXIMUMCAPACITY：tableSizeFor（（int）size）；this。sizeCtlcap；｝publicConcurrentHashMap（Maplt；？extendsK，？extendsVm）｛this。sizeCtlDEFAULTCAPACITY；putAll（m）；｝2。2重点解析publicvoidputAll（Maplt；？extendsK，？extendsVm）｛tryPresize（m。size（））；for（Map。Entrylt；？extendsK，？extendsVe：m。entrySet（））putVal（e。getKey（），e。getValue（），false）；｝hash方法staticfinalintspread（inth）｛return（h（h16））HASHBITS；｝2。2。1putValfinalVputVal（Kkey，Vvalue，booleanonlyIfAbsent）｛keyvalue都不能为空if（keynullvaluenull）thrownewNullPointerException（）；concurrentHashMap的hash方法inthashspread（key。hashCode（））；intbinCount0；for（NodeK，V〔〕tabtable；；）｛NodeK，Vf；intn，i，fh；如果table是空，那么调用初始化若不空则根据hash寻找，若没有找到则插入。if（tabnull（ntab。length）0）tabinitTable（）；elseif（（ftabAt（tab，i（n1）hash））null）｛if（casTabAt（tab，i，null，newNodeK，V（hash，key，value，null）））break；nolockwhenaddingtoemptybin｝staticfinalintMOVED1；如果当前位置的hashcodeMOVED1，map正在扩容，其他线程帮助扩容，也就是多线程扩容。elseif（（fhf。hash）MOVED）tabhelpTransfer（tab，f）；else｛利用synchronized锁写入数据fh〉0说明这个节点是一个链表的节点不是树的节点。如果是红黑树，照树的方式插入值内置锁synchronized锁住了f，因为f是指定特定的tab〔i〕的。所以就锁住了整行链表，这个设计跟分段锁有异曲同工之妙，只是其他读取操作需要用cas来保证VoldValnull；synchronized（f）｛if（tabAt（tab，i）f）｛if（fh0）｛binCount1；for（NodeK，Vef；；binCount）｛Kek；if（e。hashhash（（eke。key）key（ek！nullkey。equals（ek））））｛oldVale。val；if（！onlyIfAbsent）e。valvalue；break；｝NodeK，Vprede；if（（ee。next）null）｛pred。nextnewNodeK，V（hash，key，value，null）；break；｝｝｝elseif（finstanceofTreeBin）｛NodeK，Vp；binCount2；if（（p（（TreeBinK，V）f）。putTreeVal（hash，key，value））！null）｛oldValp。val；if（！onlyIfAbsent）p。valvalue；｝｝｝｝当链表长度大于8时，将链表转换为红黑树if（binCount！0）｛if（binCountTREEIFYTHRESHOLD）treeifyBin（tab，i）；if（oldVal！null）returnoldVal；break；｝｝｝addCount（1L，binCount）；returnnull；｝
　　下面这段内容是搬运最开始的资料中putVal（Kkey，Vvalue，booleanonlyIfAbsent，booleanevict）大体流程如下：1、检查keyvalue是否为null，如果为null，则抛异常，否则进行22、进入for死循环，进行33、检查table是否初始化了，如果没有，则调用initTable（）进行初始化然后进行2，否则进行44、根据key的hash值计算出其应该在table中储存的位置i（根据key的hashcode计算出Hash值，在将Hash值与length1进行按位与，length是2的整数次幂，减1后的二进制与Hash值进行按位与相当于取余运算，但取余的位运算次数肯定不止1次，而这里一次位运算就得出结果，效率更高），取出table〔i〕的节点用f表示。根据f的不同有如下三种情况：
　　1）如果table〔i〕null（即该位置的节点为空，没有发生碰撞），则利用CAS操作直接存储在该位置，如果CAS操作成功则退出死循环。
　　2）如果table〔i〕！null（即该位置已经有其它节点，发生碰撞），碰撞处理也有两种情况2。1）检查table〔i〕的节点的hash是否等于MOVED（1），如果等于，则检测到正在扩容，则帮助其扩容2。2）说明table〔i〕的节点的hash值不等于MOVED，synchronized锁住头结点table〔i〕，进行插入操作；
　　如果table〔i〕为链表节点，则将此节点插入链表末尾中即可；
　　如果table〔i〕为树节点，则将此节点插入树中即可；
　　插入成功后，进行5
　　5、如果table〔i〕的节点是链表节点，则检查table的第i个位置的链表的元素个数是否大于了8，大于8就需要转化为树，如果需要则调用treeifyBin函数进行转化。链表转树：将数组tab的第index位置的链表转化为红黑树。6、插入成功后，如果key已经存在，返回oldValue；key开始不存在，返回null。上面第4点中的2）中的2。1）帮助扩容：如果当前正在扩容，则尝试协助其扩容，死循环再次发挥了重试的作用，有趣的是ConcurrentHashMap是可以多线程同时扩容的。
　　这里说协助的原因在于，对于数组扩容，一般分为两步：1。新建一个更大的数组；2。将原数组数据（重新散列Hash值）copy到新数组中。
　　对于第一步，ConcurrentHashMap通过CAS来控制一个int变量保证新建数组这一步建一个更大的数组只会执行一次；
　　对于第二步，ConcurrentHashMap采用CASsynchronized移动后标记的方式来达到多线程扩容的目的。
　　感兴趣可以查看transfer函数。
　　目前的猜想多线程扩容可能是：多线程操作不同的table位置的链表或红黑树，将元素重新散列到新的table数组中。2。2。2initTableInitializestable，usingthesizerecordedinsizeCtl。privatefinalNodeK，V〔〕initTable（）｛NodeK，V〔〕tab；intsc；while（（tabtable）nulltab。length0）｛初始化的功劳被其他线程抢去了if（（scsizeCtl）0）Thread。yield（）；lostinitializationrace；justspinCAS一下，将sizeCtl设置为1，代表抢到了锁elseif（U。compareAndSwapInt（this，SIZECTL，sc，1））｛try｛if（（tabtable）nulltab。length0）｛intn（sc0）？sc：DEFAULTCAPACITY；SuppressWarnings（unchecked）NodeK，V〔〕nt（NodeK，V〔〕）newNodelt；？，？〔n〕；tabletabnt；scn（n2）；｝｝finally｛sizeCtlsc；｝break；｝｝returntab；｝2。2。3addCount从putVal传入的参数是1，binCount，binCount默认是0，只有hash冲突了才会大于1。且他的大小是链表的长度（如果不是红黑数结构的话）。privatefinalvoidaddCount（longx，intcheck）｛CounterCell〔〕as；longb，s；如果计数盒子不是空或者修改baseCount失败if（（ascounterCells）！null！U。compareAndSwapLong（this，BASECOUNT，bbaseCount，sbx））｛CounterCella；longv；intm；booleanuncontendedtrue；如果计数盒子是空（尚未出现并发）如果随机取余一个数组位置为空或者修改这个槽位的变量失败（出现并发了）执行fullAddCount方法。并结束if（asnull（mas。length1）0（aas〔ThreadLocalRandom。getProbe（）m〕）null！（uncontendedU。compareAndSwapLong（a，CELLVALUE，va。value，vx）））｛fullAddCount（x，uncontended）；return；｝if（check1）return；ssumCount（）；｝if（check0）｛NodeK，V〔〕tab，nt；intn，sc；当条件满足开始扩容while（s（long）（scsizeCtl）（tabtable）！null（ntab。length）MAXIMUMCAPACITY）｛intrsresizeStamp（n）；如果小于0说明已经有线程在进行扩容操作了已经有在扩容或者多线程进行了扩容，则break不要进入扩容操作if（sc0）｛if（（scRESIZESTAMPSHIFT）！rsscrs1scrsMAXRESIZERS（ntnextTable）nulltransferIndex0）break；if（U。compareAndSwapInt（this，SIZECTL，sc，sc1））transfer（tab，nt）；｝这个时候sizeCtl已经等于（rsRESIZESTAMPSHIFT）2等于一个大的负数，这边加上2很巧妙，因为transfer后面对sizeCtl操作的时候，最多只能减两次就结束elseif（U。compareAndSwapInt（this，SIZECTL，sc，（rsRESIZESTAMPSHIFT）2））transfer（tab，null）；ssumCount（）；｝｝｝CounterCell中volatilevaluesun。misc。ContendedstaticfinalclassCounterCell｛volatilelongvalue；CounterCell（longx）｛valuex；｝｝x参数表示的此次需要对表中元素的个数加几。check参数表示是否需要进行扩容检查，大于等于0需要进行检查，而我们的putVal方法的binCount参数最小也是0，因此，每次添加元素都会进行检查。（除非是覆盖操作）
　　判断计数盒子属性是否是空，如果是空，就尝试修改baseCount变量，对该变量进行加X。
　　如果计数盒子不是空，或者修改baseCount变量失败了，则放弃对baseCount进行操作。
　　如果计数盒子是null或者计数盒子的length是0，或者随机取一个位置取于数组长度是null，那么就对刚刚的元素进行CAS赋值。
　　如果赋值失败，或者满足上面的条件，则调用fullAddCount方法重新死循环插入。
　　这里如果操作baseCount失败了（或者计数盒子不是Null），且对计数盒子赋值成功，那么就检查check变量，如果该变量小于等于1。直接结束。否则，计算一下count变量。
　　如果check大于等于0，说明需要对是否扩容进行检查。
　　如果map的size大于sizeCtl（扩容阈值），且table的长度小于130，那么就进行扩容。
　　根据length得到一个标识符，然后，判断sizeCtl状态，如果小于0，说明要么在初始化，要么在扩容。
　　如果正在扩容，那么就校验一下数据是否变化了（具体可以看上面代码的注释）。如果检验数据不通过，break。
　　如果校验数据通过了，那么将sizeCtl加一，表示多了一个线程帮助扩容。然后进行扩容。
　　如果没有在扩容，但是需要扩容。那么就将sizeCtl更新，赋值为标识符左移16位一个负数。然后加2。表示，已经有一个线程开始扩容了。然后进行扩容。然后再次更新count，看看是否还需要扩容。
　　addCount方法做了2件事情
　　对table的长度加一。无论是通过修改baseCount，还是通过使用CounterCell。当CounterCell被初始化了，就优先使用他，不再使用baseCount。
　　检查是否需要扩容，或者是否正在扩容。如果需要扩容，就调用扩容方法，如果正在扩容，就帮助其扩容。2。2。4helpTransferHelpstransferifaresizeisinprogress。如果线程进入到这边说明已经有其他线程正在做扩容操作，这个是一个辅助方法finalNodeK，V〔〕helpTransfer（NodeK，V〔〕tab，NodeK，Vf）｛NodeK，V〔〕nextTab；intsc；if（tab！null（finstanceofForwardingNode）（nextTab（（ForwardingNodeK，V）f）。nextTable）！null）｛intrsresizeStamp（tab。length）；while（nextTabnextTabletabletab（scsizeCtl）0）｛if（（scRESIZESTAMPSHIFT）！rsscrs1scrsMAXRESIZERStransferIndex0）break；if（U。compareAndSwapInt（this，SIZECTL，sc，sc1））｛transfer（tab，nextTab）；break；｝｝returnnextTab；｝returntable；｝2。2。5transferMovesandorcopiesthenodesineachbintonewtable。Seeaboveforexplanation。privatefinalvoidtransfer（NodeK，V〔〕tab，NodeK，V〔〕nextTab）｛intntab。length，stride；if（（stride（NCPU1）？（n3）NCPU：n）MINTRANSFERSTRIDE）单个线程允许处理的最少table桶首节点个数，即每个线程的处理任务量strideMINTRANSFERSTRIDE；subpiderangeif（nextTabnull）｛initiatingtry｛SuppressWarnings（unchecked）构造一个nextTable对象它的容量是原来的两倍NodeK，V〔〕nt（NodeK，V〔〕）newNodelt；？，？〔n1〕；nextTabnt；｝catch（Throwableex）｛trytocopewithOOMEsizeCtlInteger。MAXVALUE；return；｝nextTablenextTab；transferIndex为扩容复制过程中的桶首节点遍历索引，所以从n开始，表示从后向前遍历transferIndexn；｝intnextnnextTab。length；调用内部类ForwardingNode的构造，将扩容后的table放在fwd节点后面ForwardingNodeK，VfwdnewForwardingNodeK，V（nextTab）；booleanadvancetrue；booleanfinishingfalse；toensuresweepbeforecommittingnextTabfor（inti0，bound0；；）｛NodeK，Vf；intfh；while（advance）｛intnextIndex，nextBound；if（iboundfinishing）advancefalse；transferIndex0表示table中所有数组元素都已经有其他线程负责扩容elseif（（nextIndextransferIndex）0）｛i1；advancefalse；｝尝试更新transferIndex，获取当前线程执行扩容复制的索引区间，更新成功，则当前线程负责完成索引为（nextBound，nextIndex）之间的桶首节点扩容elseif（U。compareAndSwapInt（this，TRANSFERINDEX，nextIndex，nextBound（nextIndexstride？nextIndexstride：0）））｛boundnextBound；inextIndex1；advancefalse；｝｝if（i0ininnextn）｛intsc；if（finishing）｛nextTablenull；tablenextTab；扩容成功，设置新sizeCtl，仍然为总大小的0。75sizeCtl（n1）（n1）；return；｝利用CAS方法更新这个扩容阈值，在这里面sizectl值减一，说明新加入一个线程参与到扩容操作if（U。compareAndSwapInt（this，SIZECTL，scsizeCtl，sc1））｛if（（sc2）！resizeStamp（n）RESIZESTAMPSHIFT）return；finishingadvancetrue；in；recheckbeforecommit｝｝当前table节点为空，不需要复制，直接放入ForwardingNodeelseif（（ftabAt（tab，i））null）advancecasTabAt（tab，i，null，fwd）；当前table节点已经是ForwardingNode，表示已经被其他线程处理了，则直接往前遍历，通过CAS读写ForwardingNode节点状态，达到多线程互斥处理elseif（（fhf。hash）MOVED）advancetrue；alreadyprocessedelse｛锁住当前桶首节点synchronized（f）｛if（tabAt（tab，i）f）｛NodeK，Vln，hn；if（fh0）｛intrunBitfhn；NodeK，VlastRunf；for（NodeK，Vpf。next；p！null；pp。next）｛intbp。hashn；if（b！runBit）｛runBitb；lastRunp；｝｝if（runBit0）｛lnlastRun；hnnull；｝else｛hnlastRun；lnnull；｝for（NodeK，Vpf；p！lastRun；pp。next）｛intphp。hash；Kpkp。key；Vpvp。val；if（（phn）0）lnnewNodeK，V（ph，pk，pv，ln）；elsehnnewNodeK，V（ph，pk，pv，hn）；｝setTabAt（nextTab，i，ln）；setTabAt（nextTab，in，hn）；setTabAt（tab，i，fwd）；advancetrue；｝elseif（finstanceofTreeBin）｛TreeBinK，Vt（TreeBinK，V）f；TreeNodeK，Vlonull，loTailnull；TreeNodeK，Vhinull，hiTailnull；intlc0，hc0；for（NodeK，Vet。first；e！null；ee。next）｛inthe。hash；TreeNodeK，VpnewTreeNodeK，V（h，e。key，e。val，null，null）；if（（hn）0）｛if（（p。prevloTail）null）lop；elseloTail。nextp；loTailp；lc；｝else｛if（（p。prevhiTail）null）hip；elsehiTail。nextp；hiTailp；hc；｝｝ln（lcUNTREEIFYTHRESHOLD）？untreeify（lo）：（hc！0）？newTreeBinK，V（lo）：t；hn（hcUNTREEIFYTHRESHOLD）？untreeify（hi）：（lc！0）？newTreeBinK，V（hi）：t；setTabAt（nextTab，i，ln）；setTabAt（nextTab，in，hn）；setTabAt（tab，i，fwd）；advancetrue；｝｝｝｝｝｝涉及的内部类ForwardingNodeAnodeinsertedatheadofbinsduringtransferoperations。staticfinalclassForwardingNodeK，VextendsNodeK，V｛finalNodeK，V〔〕nextTable；ForwardingNode（NodeK，V〔〕tab）｛super（MOVED，null，null，null）；this。nextTabletab；｝NodeK，Vfind（inth，Objectk）｛looptoavoidarbitrarilydeeprecursiononforwardingnodesouter：for（NodeK，V〔〕tabnextTable；；）｛NodeK，Ve；intn；if（knulltabnull（ntab。length）0（etabAt（tab，（n1）h））null）returnnull；for（；；）｛inteh；Kek；if（（ehe。hash）h（（eke。key）k（ek！nullk。equals（ek））））returne；if（eh0）｛if（einstanceofForwardingNode）｛tab（（ForwardingNodeK，V）e）。nextTable；continueouter；｝elsereturne。find（h，k）；｝if（（ee。next）null）returnnull；｝｝｝｝
　　下面内容搬运自链接https：blog。csdn。netzguoshuaiiiiarticledetails78495332整个扩容操作分为两个部分
　　第一部分是构建一个nextTable，它的容量是原来的两倍，这个操作是单线程完成的。这个单线程的保证是通过RESIZESTAMPSHIFT这个常量经过一次运算来保证的，这个地方在后面会有提到；
　　第二个部分就是将原来table中的元素复制到nextTable中，这里允许多线程进行操作。
　　先来看一下单线程是如何完成的：
　　它的大体思想就是遍历、复制的过程。首先根据运算得到需要遍历的次数i，然后利用tabAt方法获得i位置的元素：
　　如果这个位置为空，就在原table中的i位置放入forwardNode节点，这个也是触发并发扩容的关键点；
　　如果这个位置是Node节点（fh0），如果它是一个链表的头节点，就构造一个反序链表，把他们分别放在nextTable的i和in的位置上
　　如果这个位置是TreeBin节点（fh0），也做一个反序处理，并且判断是否需要untreefi，把处理的结果分别放在nextTable的i和in的位置上
　　遍历过所有的节点以后就完成了复制工作，这时让nextTable作为新的table，并且更新sizeCtl为新容量的0。75倍，完成扩容。
　　看一下多线程是如何完成的：在扩容部分代码中有一个判断，如果遍历到的节点是forward节点，就向后继续遍历，再加上给节点上锁的机制，就完成了多线程的控制。多线程遍历节点，处理了一个节点，就把对应点的值set为forward，另一个线程看到forward，就向后遍历。这样交叉就完成了复制工作。而且还很好的解决了线程安全的问题。
　　2。2。6getpublicVget（Objectkey）｛NodeK，V〔〕tab；NodeK，Ve，p；intn，eh；Kek；inthspread（key。hashCode（））；if（（tabtable）！null（ntab。length）0（etabAt（tab，（n1）h））！null）｛判断是否就是桶首节点if（（ehe。hash）h）｛if（（eke。key）key（ek！nullkey。equals（ek）））returne。val；｝hash为负表示是扩容中的ForwardingNode节点，直接调用ForwardingNode的find方法（可以是代理到扩容中的nextTable）elseif（eh0）return（pe。find（h，key））！null？p。val：null；通过next指针，逐一查找while（（ee。next）！null）｛if（e。hashh（（eke。key）key（ek！nullkey。equals（ek））））returne。val；｝｝returnnull；｝2。2。7removepublicVremove（Objectkey）｛returnreplaceNode（key，null，null）；｝finalVreplaceNode（Objectkey，Vvalue，Objectcv）｛inthashspread（key。hashCode（））；for（NodeK，V〔〕tabtable；；）｛NodeK，Vf；intn，i，fh；if（tabnull（ntab。length）0每次循环都会重新计算槽的位置，因为在扩容完成后会使用新表槽的位置可能会发生改变（ftabAt（tab，i（n1）hash））null）break；如果有线程正在扩容，先帮助它一起扩容，然后在新表中进行put操作elseif（（fhf。hash）MOVED）tabhelpTransfer（tab，f）；else｛VoldValnull；booleanvalidatedfalse；加锁操作，防止其它线程对此桶同时进行put，remove，transfer操作synchronized（f）｛if（tabAt（tab，i）f）｛if（fh0）｛validatedtrue；for（NodeK，Vef，prednull；；）｛Kek；if（e。hashhash（（eke。key）key（ek！nullkey。equals（ek））））｛Veve。val；if（cvnullcvev（ev！nullcv。equals（ev）））｛oldValev；if（value！null）e。valvalue；elseif（pred！null）pred。nexte。next；elsesetTabAt（tab，i，e。next）；｝break；｝prede；if（（ee。next）null）break；｝｝elseif（finstanceofTreeBin）｛validatedtrue；TreeBinK，Vt（TreeBinK，V）f；TreeNodeK，Vr，p；if（（rt。root）！null（pr。findTreeNode（hash，key，null））！null）｛Vpvp。val；if（cvnullcvpv（pv！nullcv。equals（pv）））｛oldValpv；if（value！null）p。valvalue；elseif（t。removeTreeNode（p））setTabAt（tab，i，untreeify（t。first））；｝｝｝｝｝if（validated）｛if（oldVal！null）｛if（valuenull）addCount（1L，1）；returnoldVal；｝break；｝｝｝returnnull；｝2。2。8ConcurrentHashMap实现高效的并发操作的三个函数
　　得益于ConcurrentHashMap中的如下三个函数（sun。misc。UnsafeU）：3个用的比较多的CAS操作SuppressWarnings（unchecked）ASHIFT等均为privatestaticfinalstaticfinalK，VNodeK，VtabAt（NodeK，V〔〕tab，inti）｛获取索引i处Nodereturn（NodeK，V）U。getObjectVolatile（tab，（（long）iASHIFT）ABASE）；｝利用CAS算法设置i位置上的Node节点（将c和table〔i〕比较，相同则插入v）。但是这边为什么i要等于（（long）iASHIFT）ABASE呢，计算偏移量ASHIFT是指tab〔i〕中第i个元素在相对于数组第一个元素的偏移量，而ABASE就算第一数组的内存素的偏移地址所以呢，（（long）iASHIFT）ABASE就算i最后的地址那么compareAndSwapObject的作用就算tab〔i〕和c比较，如果相等就tab〔i〕v否则tab〔i〕c；staticfinalK，VbooleancasTabAt（NodeK，V〔〕tab，inti，NodeK，Vc，NodeK，Vv）｛returnU。compareAndSwapObject（tab，（（long）iASHIFT）ABASE，c，v）；｝在链表转树时用到了这个方法；设置节点位置的值，仅在上锁区被调用staticfinalK，VvoidsetTabAt（NodeK，V〔〕tab，inti，NodeK，Vv）｛U。putObjectVolatile（tab，（（long）iASHIFT）ABASE，v）；｝2。2。9keySet、valuespublicCollectionVvalues（）｛ValuesViewK，Vvs；return（vsvalues）！null？vs：（valuesnewValuesViewK，V（this））；｝publicKeySetViewK，VkeySet（VmappedValue）｛if（mappedValuenull）thrownewNullPointerException（）；returnnewKeySetViewK，V（this，mappedValue）；｝
　　同HashMap，ConcurrentHashMap也是实现自己的内部迭代器来实现迭代，以KeySe为例，可以看到返回的是一个内部类KeySetView，这个类里面重点属性是一个构造器对应类型是另一个内部类KeyIterator，KeyIterator类继承至BaseIterator类，而BaseIterator又继承至Traverser。KeyIterator调用next方法时，最终会调用Traverser的advance方法。这个方法源码如下：TraverserstaticclassTraverserK，V｛NodeK，V〔〕tab；currenttable；updatedifresizedNodeK，Vnext；thenextentrytouseTableStackK，Vstack，spare；tosaverestoreonForwardingNodesintindex；indexofbintousenextintbaseIndex；currentindexofinitialtableintbaseLimit；indexboundforinitialtablefinalintbaseSize；initialtablesizeTraverser（NodeK，V〔〕tab，intsize，intindex，intlimit）｛this。tabtab；this。baseSizesize；this。baseIndexthis。indexindex；this。baseLimitlimit；this。nextnull；｝Advancesifpossible，returningnextvalidnode，ornullifnone。如果有可能，返回下一个有效节点，否则返回null。finalNodeK，Vadvance（）｛NodeK，Ve；获取Node链表的下一个元素eif（（enext）！null）ee。next；for（；；）｛NodeK，V〔〕t；inti，n；mustuselocalsinchecksif（e！null）returnnexte；e为空，说明此链表已经遍历完成，准备遍历下一个hash桶if（baseIndexbaseLimit（ttab）null（nt。length）（iindex）i0）returnnextnull；获取下一个hash桶对应的node链表的头节点if（（etabAt（t，i））！nulle。hash0）｛if（einstanceofForwardingNode）｛tab（（ForwardingNodeK，V）e）。nextTable；enull；pushState（t，i，n）；continue；｝elseif（einstanceofTreeBin）e（（TreeBinK，V）e）。first；elseenull；｝if（stack！null）recoverState（n）；elseif（（indexibaseSize）n）indexbaseIndex；visitupperslotsifpresent｝｝｝2。3内部类2。3。1Node
　　Node是最核心的内部类，它包装了keyvalue键值对，与HashMap中的定义很相似，但是它对value和next属性设置了volatile同步锁，它不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map。get（）方法。staticclassNodeK，VimplementsMap。EntryK，V｛finalinthash；finalKkey；volatileVval；带有同步锁的valuevolatileNodeK，Vnext；带有同步锁的next指针Node（inthash，Kkey，Vval，NodeK，Vnext）｛this。hashhash；this。keykey；this。valval；this。nextnext；｝publicfinalKgetKey（）｛returnkey；｝publicfinalVgetValue（）｛returnval；｝publicfinalinthashCode（）｛returnkey。hashCode（）val。hashCode（）；｝publicfinalStringtoString（）｛returnkeyval；｝不允许直接改变value的值publicfinalVsetValue（Vvalue）｛thrownewUnsupportedOperationException（）；｝publicfinalbooleanequals（Objecto）｛Objectk，v，u；Map。Entrylt；？，？e；return（（oinstanceofMap。Entry）（k（e（Map。Entrylt；？，？）o）。getKey（））！null（ve。getValue（））！null（kkeyk。equals（key））（v（uval）v。equals（u）））；｝Virtualizedsupportformap。get（）；overriddeninsubclasses。NodeK，Vfind（inth，Objectk）｛NodeK，Vethis；if（k！null）｛do｛Kek；if（e。hashh（（eke。key）k（ek！nullk。equals（ek））））returne；｝while（（ee。next）！null）；｝returnnull；｝｝2。3。2TreeNode
　　树节点类，另外一个核心的数据结构。当链表长度过长的时候，会转换为TreeNode。但是与HashMap不相同的是，它并不是直接转换为红黑树，而是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。而且TreeNode在ConcurrentHashMap集成自Node类，而并非HashMap中的集成自LinkedHashMap。EntryK，V类，也就是说TreeNode带有next指针，这样做的目的是方便基于TreeBin的访问。2。3。3TreeBin
　　包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap数组中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。另外这个类还带有了读写锁。Createsbinwithinitialsetofnodesheadedbyb。TreeBin（TreeNodeK，Vb）｛super（TREEBIN，null，null，null）；this。firstb；TreeNodeK，Vrnull；for（TreeNodeK，Vxb，next；x！null；xnext）｛next（TreeNodeK，V）x。next；x。leftx。rightnull；if（rnull）｛x。parentnull；x。redfalse；rx；｝else｛Kkx。key；inthx。hash；Classlt；？kcnull；for（TreeNodeK，Vpr；；）｛intdir，ph；Kpkp。key；if（（php。hash）h）dir1；elseif（phh）dir1；elseif（（kcnull（kccomparableClassFor（k））null）（dircompareComparables（kc，k，pk））0）dirtieBreakOrder（k，pk）；TreeNodeK，Vxpp；if（（p（dir0）？p。left：p。right）null）｛x。parentxp；if（dir0）xp。leftx；elsexp。rightx；rbalanceInsertion（r，x）；break；｝｝｝｝this。rootr；assertcheckInvariants（root）；｝2。3。4ForwardingNode
　　这个内部类在2。3。5中可以看到源码
　　其实是一个包含一个nextTable指针，用于指向下一张表。而且这个节点的keyvaluenext指针全部为null，它的hash值为1。这里面定义的find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找2。3。5ValuesView、ValueIterator、KeySetView、KeyIterator
　　在2。2。9中已经查看。此处不赘述3、Unsafe与CAS
　　unsafe代码块控制了一些属性的修改工作，比如最常用的SIZECTL。在这一版本的concurrentHashMap中，大量应用来的CAS方法进行变量、属性的修改工作。利用CAS进行无锁操作，可以大大提高性能。privatestaticfinalsun。misc。UnsafeU；privatestaticfinallongSIZECTL；privatestaticfinallongTRANSFERINDEX；privatestaticfinallongBASECOUNT；privatestaticfinallongCELLSBUSY；privatestaticfinallongCELLVALUE；privatestaticfinallongABASE；privatestaticfinalintASHIFT；static｛try｛Usun。misc。Unsafe。getUnsafe（）；Classlt；？kConcurrentHashMap。class；SIZECTLU。objectFieldOffset（k。getDeclaredField（sizeCtl））；TRANSFERINDEXU。objectFieldOffset（k。getDeclaredField（transferIndex））；BASECOUNTU。objectFieldOffset（k。getDeclaredField（baseCount））；CELLSBUSYU。objectFieldOffset（k。getDeclaredField（cellsBusy））；Classlt；？ckCounterCell。class；CELLVALUEU。objectFieldOffset（ck。getDeclaredField（value））；Classlt；？akNode〔〕。class；ABASEU。arrayBaseOffset（ak）；intscaleU。arrayIndexScale（ak）；if（（scale（scale1））！0）thrownewError（datatypescalenotapoweroftwo）；ASHIFT31Integer。numberOfLeadingZeros（scale）；｝catch（Exceptione）｛thrownewError（e）；｝｝
　　CAS会单独写文章来进行分析这个理论4、常见QA
　　Tip：本文分析的1。8的源码，没有看1。7源码，因此涉及1。7部分的回答都是网上摘抄，可自行求证4。1ConcurrentHashMap有哪些构造函数？无参构造
　　初始容器大小的构造函数
　　传入Map的构造
　　设置阈值和初始容量
　　初始容量和阈值和并发级别4。2ConcurrentHashMap使用什么技术来保证线程安全？jdk1。7：SegmentHashEntry来进行实现的；
　　jdk1。8：放弃了Segment臃肿的设计，采用NodeCASSynchronized来保证线程安全；4。3ConcurrentHashMap的get方法是否要加锁，为什么？
　　不需要，get方法采用了unsafe方法，来保证线程安全。4。4ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？弱一致性，hashmap强一直性。
　　ConcurrentHashMap可以支持在迭代过程中，向map添加新元素，而HashMap则抛出了ConcurrentModificationException，
　　因为HashMap包含一个修改计数器，当你调用他的next（）方法来获取下一个元素时，迭代器将会用到这个计数器。4。5ConcurrentHashMap1。7和1。8的区别；jdk1。8的实现降低锁的粒度，jdk1。7锁的粒度是基于Segment的，包含多个HashEntry，而jdk1。8锁的粒度就是Node
　　数据结构：jdk1。7SegmentHashEntry；jdk1。8数组链表红黑树CASsynchronized4。6ConcurrentHashMap中变量使用final和volatile修饰有什么用呢？其中链表是final的next属性，那么发生删除某个元素，如何实现的？使用final来实现不变模式（immutable），他是多线程安全里最简单的一种保障方式。因为你拿他没有办法，想改变它也没有机会。不变模式主要通过final关键字来限定的。在JMM中final关键字还有特殊的语义。Final域使得确保初始化安全性（initializationsafety）成为可能，初始化安全性让不可变形对象不需要同步就能自由地被访问和共享。
　　使用volatile来保证某个变量内存的改变对其他线程即时可见，在配合CAS可以实现不加锁对并发操作的支持
　　remove执行的开始就将table赋给一个局部变量tab，将tab依次复制出来，最后直到该删除位置，将指针指向下一个变量。5、总结
　　总结只针对1。8版本。至于1。7版本若有时间在进行解析源码（1。8对这个类做了很大的变动）
　　数据结构和HashMap类似，大部分属性都加上了final或者volidate关键字来确保线程安全。在做新增操作的时候采用了CAS（比较和交换ConmpareAndSwap）的思路来处理线程的问题（这个思想中主要使用了关键字volidate）。另外在更新或者扩容等操作的时候使用了Synchronized来锁住hash桶的头节点来保证每个节点只能同时有一个线程来操作。jdk1。8的线程颗粒度相比1。7更细。
　　迭代器的弱一致性、强一致。强一致要求在迭代过程中不能对数据进行修改，一旦修改就迭代器会抛出异常。
　　弱一致则没有此要求。ConcurrentHashMap实现弱一致性其实就时通过不断循环进行寻找对应元素。