[JDK源码]-J.U.C-ConcurrentHashMap

**由于作者水平有限，如有什么错误点，多谢指出。 **

ConcurrentHashMap

publicclassConcurrentHashMap<K,V>extendsAbstractMap<K,V>implementsConcurrentMap<K,V>,Serializable{//保存K-V 节点staticclassNode<K,V>implementsMap.Entry<K,V>{finalint hash;finalK key;volatileV val;volatileNode<K,V> next;}//链表Node 转为 TreeNode 节点，继承了Node节点staticfinalclassTreeNode<K,V>extendsNode<K,V>{TreeNode<K,V> parent;// red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;boolean red;}//链表Node转为红黑树，放在 数组位置上的头节点，本身不保存数据staticfinalclassTreeBin<K,V>extendsNode<K,V>{TreeNode<K,V> root;volatileTreeNode<K,V> first;volatileThread waiter;//等待线程volatileint lockState;//锁状态staticfinalint WRITER =1;// 写锁staticfinalint WAITER =2;// 等待写锁staticfinalint READER =4;// 读锁}//保存数据的数组 2的倍数transientvolatileNode<K,V>[] table;/*扩容时候生成的下一个数组   */privatetransientvolatileNode<K,V>[] nextTable;/*计数器     */privatetransientvolatilelong baseCount;/*用于控制hash表的初始化和扩容，-1：hash初始化，-1+参与扩容操作的线程数：用于扩容操作，正数：hash表的容量   */privatetransientvolatileint sizeCtl;/*在扩容时，多线程竞争转移 槽 区间时使用     */privatetransientvolatileint transferIndex;/*在扩容时自旋锁使用    */privatetransientvolatileint cellsBusy;/* CounterCell hash表，如果不为空，那么肯定是2的倍数   */privatetransientvolatileCounterCell[] counterCells;// 通过迭代器遍历时候 的 几种视图privatetransientKeySetView<K,V> keySet;privatetransientValuesView<K,V> values;privatetransientEntrySetView<K,V> entrySet;staticfinalint MOVED     =-1;// resize时 forwarding 节点 的hash值staticfinalint TREEBIN   =-2;// 红黑树根节点的hash值staticfinalint RESERVED  =-3;// 创建 reservationNode 节点的hash值staticfinalint HASH_BITS =0x7fffffff;// 正常hash用的位数staticfinalclassReservationNode<K,V>extendsNode<K,V>{ReservationNode(){super(RESERVED,null,null,null);}}//创建初始容量的publicConcurrentHashMap(int initialCapacity){if(initialCapacity <0)thrownewIllegalArgumentException();//最大容量  MAXIMUM_CAPACITY = 1<<30 int cap =((initialCapacity >=(MAXIMUM_CAPACITY >>>1))?
                   MAXIMUM_CAPACITY :tableSizeFor(initialCapacity +(initialCapacity >>>1)+1));//此时保存 hash表的最大容量this.sizeCtl = cap;}//转移操作时，如果slot没有节点可以转移或已经转移成功，将在相应的slot放上这个类的对象staticfinalclassForwardingNode<K,V>extendsNode<K,V>{finalNode<K,V>[] nextTable;ForwardingNode(Node<K,V>[] tab){super(MOVED,null,null,null);this.nextTable = tab;}}//减少hash冲突，异或的结果继续和HASH_BITS 与运算staticfinalintspread(int h){return(h ^(h >>>16))& HASH_BITS;//0x7fffffff}}

put

publicVput(K key,V value){returnputVal(key, value,false);}finalVputVal(K key,V value,boolean onlyIfAbsent){if(key ==null|| value ==null)thrownewNullPointerException();//不允许放入空值int hash =spread(key.hashCode());//计算 hashint binCount =0;//记录元素个数for(Node<K,V>[] tab = table;;){//循环直到 插入成功Node<K,V> f;int n, i, fh;if(tab ==null||(n = tab.length)==0)//为空 初始化 hash表
            tab =initTable();elseif((f =tabAt(tab, i =(n -1)& hash))==null){//根据hash值找到应该保存的数组的位置，如果没放入，通过CAS，封装成 Node对象放入索引位 i的位置if(casTabAt(tab, i,null,newNode<K,V>(hash, key, value,null)))break;}//这里，f就是找到下标位i的node元素，这时根据MOVED标志看看是数组正在扩容还是数据迁移，如果迁移，那么调用helpTransfer方法帮助完成迁移elseif((fh = f.hash)== MOVED)
            tab =helpTransfer(tab, f);else{V oldVal =null;synchronized(f){//对f上锁if(tabAt(tab, i)== f){//索引下标 i 处节点没有被更改if(fh >=0){//链表
                        binCount =1;for(Node<K,V> e = f;;++binCount){//遍历链表K ek;//当前与 要放入的 hash 相同if(e.hash == hash &&((ek = e.key)== key ||//比较 地址//比较 equals (ek !=null&& key.equals(ek)))){
                                oldVal = e.val;//保存找到的旧值if(!onlyIfAbsent)//如果没有设置 onlyIfAbsent ，覆盖旧值
                                    e.val = value;break;}//遍历到结尾 说明没有当前节点Node<K,V> pred = e;if((e = e.next)==null){
                                pred.next =newNode<K,V>(hash, key,
                                                          value,null);break;}}}//红黑树操作elseif(f instanceofTreeBin){//红黑树，在 slot中放置了一个 TreeBin对象 ，然后才是根节点 所以直接设置2Node<K,V> p;
                        binCount =2;//插入红黑树，如果返回值不为空，说明红黑树包含了K，根据onlyIfAbsent 来决定是否覆盖原来的值if((p =((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value))!=null){
                            oldVal = p.val;if(!onlyIfAbsent)
                                p.val = value;}}}}if(binCount !=0){//节点超过 TREEIFY_THRESHOLD = 8if(binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);//转换为红黑树if(oldVal !=null)//如果发生了冲突，替换原来的值，则返回return oldVal;break;}}}addCount(1L, binCount);//增加一个节点计数，看看是否需要扩容returnnull;}

initTable初始化过程

privatefinalNode<K,V>[]initTable(){Node<K,V>[] tab;int sc;while((tab = table)==null|| tab.length ==0){//循环直到成功if((sc = sizeCtl)<0)Thread.yield();elseif(U.compareAndSwapInt(this, SIZECTL, sc,-1)){try{//双重判断，避免CAS成功，但后面释放了sc后 又有线程进入if((tab = table)==null|| tab.length ==0){int n =(sc >0)? sc : DEFAULT_CAPACITY;//默认16@SuppressWarnings("unchecked")Node<K,V>[] nt =(Node<K,V>[])newNode<?,?>[n];//创建数组
                    table = tab = nt;//sc保存最大的数量，这个n是 0.75
                    sc = n -(n >>>2);}}finally{
                sizeCtl = sc;}break;}}return tab;}

addCount

privatefinalvoidaddCount(long x,int check){CounterCell[] as;long b, s;if((as = counterCells)!=null||//已经创建//直接在baseCount 变量上计数。如果失败进入初始化 as，!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)){CounterCell a;long v;int m;boolean uncontended =true;//初始化asif(as ==null||(m = as.length -1)<0||(a = as[ThreadLocalRandom.getProbe()& m])==null||!(uncontended =U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))){fullAddCount(x, uncontended);//创建as或者添加计数器return;}if(check <=1)//如果check<= 1 直接退出return;
        s =sumCount();//获取当前hash表的数据量}if(check >=0){//检查表的大小，要不要扩容Node<K,V>[] tab, nt;int n, sc;//s是当前数据量，大于等于 当前容量  && 数组不为空 && 数组小于最大容量while(s >=(long)(sc = sizeCtl)&&(tab = table)!=null&&(n = tab.length)< MAXIMUM_CAPACITY){int rs =resizeStamp(n);//计算扩容时 使用的stampif(sc <0){//如果sc小于0，表明已经开始扩容//stamp 已经改变  || 达到最大帮助resize的线程数      MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;//nextTable 为空，扩容完毕 if((sc >>> RESIZE_STAMP_SHIFT)!= rs || sc == rs +1||
                    sc == rs + MAX_RESIZERS ||(nt = nextTable)==null||
                    transferIndex <=0)break;//增加帮助 resize 的线程数if(U.compareAndSwapInt(this, SIZECTL, sc, sc +1))transfer(tab, nt);//如果成功 开始扩容}//将 sc设置为  (rs << RESIZE_STAMP_SHIFT) + 2)elseif(U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT)+2))transfer(tab,null);//开始扩容
            s =sumCount();//重新计算 数据量}}}

transfer扩容

privatefinalvoidtransfer(Node<K,V>[] tab,Node<K,V>[] nextTab){int n = tab.length, stride;//计算每个线程负责的区间，单核就单线程//否则(n >>> 3) / NCPU。   最小值MIN_TRANSFER_STRIDE = 16if((stride =(NCPU >1)?(n >>>3)/ NCPU : n)< MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE;if(nextTab ==null){// 初始化目标数组try{@SuppressWarnings("unchecked")Node<K,V>[] nt =(Node<K,V>[])newNode<?,?>[n <<1];//2倍扩容
            nextTab = nt;}catch(Throwable ex){// OOM异常，设置 sizeCtl 返回
            sizeCtl =Integer.MAX_VALUE;return;}
        nextTable = nextTab;
        transferIndex = n;//设置 原来数组的长度}int nextn = nextTab.length;//目标数组长度ForwardingNode<K,V> fwd =newForwardingNode<K,V>(nextTab);//创建转移节点boolean advance =true;boolean finishing =false;for(int i =0, bound =0;;){//循环直到扩容成功Node<K,V> f;int fh;while(advance){int nextIndex, nextBound;//如果 寻找的区间 还没有完成if(--i >= bound || finishing)//如果完成迁移 那么不需要继续前进
                advance =false;elseif((nextIndex = transferIndex)<=0){//没有可分的区间了，也不需要前进
                i =-1;            
                advance =false;}//原子分割区间 ：通过操作  transferIndex 变量elseif(U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,//如果可以继续分，获取区间的长度，否则设置0
                      nextBound =(nextIndex > stride ?
                                   nextIndex - stride :0))){
                bound = nextBound;//获得的区间
                i = nextIndex -1;//设置开始转移的下标i为nextIndex - 1（
                advance =false;}}//没有可分的区间 || i>=数组长度  || 开始下标+n >= 扩容后的数组长度if(i <0|| i >= n || i + n >= nextn){int sc;if(finishing){//扩容完成
                nextTable =null;
                table = nextTab;
                sizeCtl =(n <<1)-(n >>>1);//重新设置sizeCtl return;}//帮助线程数 - 1if(U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc -1)){//如果 resizeStamp 改变 直接退出if((sc -2)!=resizeStamp(n)<< RESIZE_STAMP_SHIFT)return;
                finishing = advance =true;
                i = n;// 开始下标设置为 数组大小}}//如果当前索引下标 i 处没有存放元素，那么将其设置为 fwd = ForwardingNode elseif((f =tabAt(tab, i))==null)
            advance =casTabAt(tab, i,null, fwd);elseif((fh = f.hash)== MOVED)//节点的 hash 值为 MOVED，表示当前节点已经删除
            advance =true;else{//对 头节点上锁 避免别的线程在转移期间进行插入操作synchronized(f){if(tabAt(tab, i)== f){//如果头节点没有发生变化  进行转移，否则重试Node<K,V> ln, hn;if(fh >=0){//当前节点为链表结构int runBit = fh & n;//获取当前头节点 对原数组长度对应 的 runBitNode<K,V> lastRun = f;// lastRun 节点//遍历链表 for(Node<K,V> p = f.next; p !=null; p = p.next){int b = p.hash & n;//当前节点hash & 数组长度 //如果当前节点的b和上一个b不同，将当前节点的b位设置位新的runBit，并且将当前节点p设置为lastRunif(b != runBit){
                                runBit = b;
                                lastRun = p;}}//runBit = 0，将 lastRun保存 lnif(runBit ==0){
                            ln = lastRun;
                            hn =null;}else{//到否则保存 hn
                            hn = lastRun;
                            ln =null;}//从头节点开始遍历，直到 找到 lastRun节点for(Node<K,V> p = f; p != lastRun; p = p.next){//当前节点的 hash  key valint ph = p.hash;K pk = p.key;V pv = p.val;if((ph & n)==0)//如果 为0 ，那么连接到 ln中
                                ln =newNode<K,V>(ph, pk, pv, ln);else//否则 hn中
                                hn =newNode<K,V>(ph, pk, pv, hn);}//ln放入 nextTab 的原理index位置setTabAt(nextTab, i, ln);//hn放入 i + n setTabAt(nextTab, i + n, hn);//链表已转移 用 fwd 来补填原来的位置setTabAt(tab, i, fwd);
                        advance =true;}elseif(f instanceofTreeBin){//红黑树的情况TreeBin<K,V> t =(TreeBin<K,V>)f;TreeNode<K,V> lo =null, loTail =null;//lo 头节点和 loTail尾节点TreeNode<K,V> hi =null, hiTail =null;//h 的int lc =0, hc =0;//从第一个节点开始遍历    生成 lo  ho 两个链表for(Node<K,V> e = t.first; e !=null; e = e.next){int h = e.hash;//当前节点的 hash值TreeNode<K,V> p =newTreeNode<K,V>(h, e.key, e.val,null,null);if((h & n)==0){// 为0 的情况 lo链表//将loTail赋值给 prev，如果当前为null，将当前p节点作为lo头节点if((p.prev = loTail)==null)
                                    lo = p;else// 否则通过 next 变量来构造双向链表
                                    loTail.next = p;
                                loTail = p;++lc;}else{//hi 链表if((p.prev = hiTail)==null)
                                    hi = p;else
                                    hiTail.next = p;
                                hiTail = p;++hc;}}//类似于链表  多了判断是否  要不要转回链表
                        ln =(lc <= UNTREEIFY_THRESHOLD)?untreeify(lo):(hc !=0)?newTreeBin<K,V>(lo): t;
                        hn =(hc <= UNTREEIFY_THRESHOLD)?untreeify(hi):(lc !=0)?newTreeBin<K,V>(hi): t;setTabAt(nextTab, i, ln);setTabAt(nextTab, i + n, hn);setTabAt(tab, i, fwd);
                        advance =true;}}}}}}

helpTransfer方法

多线程帮助resize

finalNode<K,V>[]helpTransfer(Node<K,V>[] tab,Node<K,V> f){Node<K,V>[] nextTab;int sc;//数组不为空 && f  ForwardingNode && nextTab不为空 if(tab !=null&&(f instanceofForwardingNode)&&(nextTab =((ForwardingNode<K,V>)f).nextTable)!=null){int rs =resizeStamp(tab.length);// 保存  rs//在转移过程中 && 原数组未 改变 && 仍在进行转移 while(nextTab == nextTable && table == tab &&(sc = sizeCtl)<0){//如果 sc 已经改变   帮助转移线程已达最大   没有可以获取的帮助区间   拜拜 if((sc >>> RESIZE_STAMP_SHIFT)!= rs || sc == rs +1||
                sc == rs + MAX_RESIZERS || transferIndex <=0)break;//CAS 增加帮助线程数量   开始帮助if(U.compareAndSwapInt(this, SIZECTL, sc, sc +1)){transfer(tab, nextTab);break;}}return nextTab;}return table;}

treeifyBin

privatefinalvoidtreeifyBin(Node<K,V>[] tab,int index){Node<K,V> b;int n, sc;//数组长度 <64 的时候 resize if(tab !=null){if((n = tab.length)< MIN_TREEIFY_CAPACITY)tryPresize(n <<1);elseif((b =tabAt(tab, index))!=null&& b.hash >=0){// 尝试将链表转化为红黑树synchronized(b){//上锁if(tabAt(tab, index)== b){//当前slot 节点仍未改变TreeNode<K,V> hd =null, tl =null;//遍历整个链表 生成TreeNode for(Node<K,V> e = b; e !=null; e = e.next){TreeNode<K,V> p =newTreeNode<K,V>(e.hash, e.key, e.val,null,null);if((p.prev = tl)==null)
                            hd = p;else
                            tl.next = p;
                        tl = p;}// 创建红黑树 并将TreeBin节点放到 数组上setTabAt(tab, index,newTreeBin<K,V>(hd));}}}}}

remove删除

publicVremove(Object key){returnreplaceNode(key,null,null);}// 将节点值替换为v，如果cv非空，则将cv匹配为条件。 如果结果值为空，则删除。      finalVreplaceNode(Object key,V value,Object cv){int hash =spread(key.hashCode());//计算hashfor(Node<K,V>[] tab = table;;){//循环Node<K,V> f;int n, i, fh;if(tab ==null||(n = tab.length)==0||//数组长度(f =tabAt(tab, i =(n -1)& hash))==null)//要删除的 k 存在不存在break;elseif((fh = f.hash)== MOVED)//如果正在扩容迁移数组，那么帮助
            tab =helpTransfer(tab, f);else{V oldVal =null;boolean validated =false;synchronized(f){if(tabAt(tab, i)== f){//查找下标 i处节点有没有发生变化if(fh >=0){//链表结构
                        validated =true;//遍历链表for(Node<K,V> e = f, pred =null;;){K ek;if(e.hash == hash &&//当前节点的hash值 与 要删除的 相同((ek = e.key)== key ||//地址相同或者 equals 判断相同(ek !=null&& key.equals(ek)))){V ev = e.val;//cv 为空  比较值 和当前 地址相同  再通过equals方法判断if(cv ==null|| cv == ev ||(ev !=null&& cv.equals(ev))){
                                    oldVal = ev;//保存替换掉的值if(value !=null)//替换原来的 V 为空不替换
                                        e.val = value;elseif(pred !=null)//删除时 前一个节点是不是根节点
                                        pred.next = e.next;else//前一个节点为头节点  直接替换原来的头节点setTabAt(tab, i, e.next);}break;}
                            pred = e;if((e = e.next)==null)break;}}elseif(f instanceofTreeBin){//红黑树结构
                        validated =true;TreeBin<K,V> t =(TreeBin<K,V>)f;//转为 TreeBinTreeNode<K,V> r, p;//根节点     找到要删除节点if((r = t.root)!=null&&(p = r.findTreeNode(hash, key,null))!=null){V pv = p.val;//获取 val//如果 cv 为空    如上述一样if(cv ==null|| cv == pv ||(pv !=null&& cv.equals(pv))){
                                oldVal = pv;if(value !=null)
                                    p.val = value;elseif(t.removeTreeNode(p))//要不要转换成 链表setTabAt(tab, i,untreeify(t.first));}}}}}//如果替换或删除的K在hash表中存在if(validated){if(oldVal !=null){//如果找到了替换掉的值if(value ==null)//删除节点addCount(-1L,-1);//减少节点计数return oldVal;}break;}}}returnnull;}

get

publicVget(Object key){Node<K,V>[] tab;Node<K,V> e, p;int n, eh;K ek;int h =spread(key.hashCode());//计算hash//数组检查if((tab = table)!=null&&(n = tab.length)>0&&(e =tabAt(tab,(n -1)& h))!=null){//通过hash 比较if((eh = e.hash)== h){//通过地址和 equals 比较if((ek = e.key)== key ||(ek !=null&& key.equals(ek)))return e.val;//找到返回它}elseif(eh <0)// 调用 find 查找return(p = e.find(h, key))!=null? p.val :null;while((e = e.next)!=null){//遍历链表查找if(e.hash == h &&((ek = e.key)== key ||(ek !=null&& key.equals(ek))))return e.val;}}returnnull;}