参数及其含义存储对象的数组。volatile用于保证table变化后可以立刻被看到。transientvolatileNodeK,V[]table;用于table中元素计数。volatile关键字用于保证可见性。同时为避免数据不一致使用cas操作进行修改。privatetransientvolatilelongbaseCount;用于table中每个单元中节点个数的计数。大小是2的倍数privatetransientvolatileCounterCell[]counterCells;节点用于存储每个keyvalue的类。其中key和hash在赋值后不允许修改。value和next指针修改后需要立即可见。staticclassNodeK,VimplementsMap.EntryK,V{finalinthash;finalKkey;volatileVval;volatileNodeK,Vnext;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;}publicfinalVsetValue(Vvalue){thrownewUnsupportedOperationException();}publicfinalbooleanequals(Objecto){Objectk,v,u;Map.Entry?,?e;return((oinstanceofMap.Entry)(k(e(Map.Entry?,?)o).getKey())!null(ve.getValue())!null(kkey||k.equals(key))(v(uval)||v.equals(u)));}/** * Virtualized support for map.get(); overridden in subclasses. */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;}}节点特殊状态的hash值。staticfinalintMOVED-1;// hash for forwarding nodesstaticfinalintTREEBIN-2;// hash for roots of treesstaticfinalintRESERVED-3;// hash for transient reservations进行resize控制。用于表的初始化和resize控制。如果是负数说明table正在被初始化或者resize-1表示初始化否则-1正在resize的线程数。否则当表为空的时候默认值为0。在初始化之后保存下一个计数值用于resize控制。privatetransientvolatileintsizeCtl;常用方法size()方法publicintsize(){longnsumCount();return((n0L)?0:(n(long)Integer.MAX_VALUE)?Integer.MAX_VALUE:(int)n);}如果n的范围在0到Integer.MAX_VALUE之间返回n。如果小于0返回0如果大于Integer.MAX_VALUE返回Integer.MAX_VALUE。finallongsumCount(){CounterCell[]ascounterCells;CounterCella;longsumbaseCount;if(as!null){for(inti0;ias.length;i){if((aas[i])!null)suma.value;}}returnsum;}sumCount统计所有元素的个数。首先sum赋值baseCount获取数组中元素个数然后遍历counterCells统计冲突的元素个数。get()方法publicVget(Objectkey){NodeK,V[]tab;NodeK,Ve,p;intn,eh;Kek;inthspread(key.hashCode());if((tabtable)!null(ntab.length)0(etabAt(tab,(n-1)h))!null){if((ehe.hash)h){if((eke.key)key||(ek!nullkey.equals(ek)))returne.val;}elseif(eh0)return(pe.find(h,key))!null?p.val:null;while((ee.next)!null){if(e.hashh((eke.key)key||(ek!nullkey.equals(ek))))returne.val;}}returnnull;}NodeK,V[] tab;用来对数组进行操作。NodeK,V e指向当前key在数组中对应的对象。NodeK,V p用于表示在链表中查找的对象。int n用于表示在数组的长度。eh用于表示在key对应对象的哈希值。ek用于表示在key对应对象的key。如果数组不为空且key在数组中对应的对象的key和hash值相等则返回对象的值。否则说明存在冲突。如果eh小于0。条件成立即hash小于0分2种情况是树或者正在扩容,需要借助find方法寻找元素find的寻找方式依据Node的不同子类有不同的实现方式:情况一eh-1 是fwd结点 - 说明当前table正在扩容且当前查询的这个桶位的数据已经被迁移走了需要借助fwd结点的内部方法find去查询情况二eh-2 是TreeBin节点 - 需要使用TreeBin 提供的find方法查询否则说明是链表。遍历链表判断数据是否是要获取的数据。put方法putVal方法finalVputVal(Kkey,Vvalue,booleanonlyIfAbsent){if(keynull||valuenull)thrownewNullPointerException();inthashspread(key.hashCode());intbinCount0;for(NodeK,V[]tabtable;;){NodeK,Vf;intn,i,fh;if(tabnull||(ntab.length)0)tabinitTable();elseif((ftabAt(tab,i(n-1)hash))null){if(casTabAt(tab,i,null,newNodeK,V(hash,key,value,null)))break;// no lock when adding to empty bin}elseif((fhf.hash)MOVED)tabhelpTransfer(tab,f);else{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;}}}}if(binCount!0){if(binCountTREEIFY_THRESHOLD)treeifyBin(tab,i);if(oldVal!null)returnoldVal;break;}}}addCount(1L,binCount);returnnull;}如果key为空或者val为空就抛出异常。if (tab null || (n tab.length) 0) tab initTable();如果数组为空或者数组长度为0就初始化table。else if ((f tabAt(tab, i (n - 1) hash)) null)获取数组中i下标的数据是否为空。为空就进行修改。if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null)))casTabAt方法判断tab中i指向的对象是否为空为空就将new的Node更新到当前位置。(fh f.hash) MOVED当前key对应的节点被移动了。调用helpTransfer(tab, f);方法协助进行扩容。否则存在多个key的hash值相同的情况。synchronized (f)对对象f加锁if (tabAt(tab, i) f) { if (fh 0) {判断tab是否发生变化了即tab中索引i对应的对象是否还为f。如果tab没有变化并且fh0说明节点不是fwd结点、TreeBin节点是链表。遍历链表节点如果key存在则覆盖原值如果key不存在在尾部添加节点。如果f节点是TreeBin节点在树中插入节点。if (binCount ! 0)说明存在插入的位置是链表或者是树if (binCount TREEIFY_THRESHOLD)说明是链表需要转树结构。if (oldVal ! null)说明原来的key已经存在了。返回原来的值。addCount(1L, binCount);走到这里说明执行了插入。binCount对应计数加一。initTable方法privatefinalNodeK,V[]initTable(){NodeK,V[]tab;intsc;while((tabtable)null||tab.length0){if((scsizeCtl)0)Thread.yield();// lost initialization race; just spinelseif(U.compareAndSwapInt(this,SIZECTL,sc,-1)){try{if((tabtable)null||tab.length0){intn(sc0)?sc:DEFAULT_CAPACITY;SuppressWarnings(unchecked)NodeK,V[]nt(NodeK,V[])newNode?,?[n];tabletabnt;scn-(n2);}}finally{sizeCtlsc;}break;}}returntab;}while ((tab table) null || tab.length 0)如果table是空说明需要执行resize流程。if ((sc sizeCtl) 0)说明有线程正在初始化或者进行resize。if (U.compareAndSwapInt(this, SIZECTL, sc, -1))对sizectl减一表明在初始化过程中了。把变量赋值给SIZECTL。if ((tab table) null || tab.length 0)表为空或者长度为0需要进行初始化。int n (sc 0) ? sc : DEFAULT_CAPACITY;如果sc大于0说明创建map对象时传递了初始化容量的参数。否则sc0就给n赋默认值。NodeK,V[] nt (NodeK,V[])new Node?,?[n];创建长度为n的临时table。table tab nt;table赋值。sc n - (n 2);等价于数组容量*阈值即数组中存储的元素个数。n2是n右移两位相当于除以4。n-n2相当于n*0.75。finally中sizeCtl赋值。最后返回初始化的表table。
ConcurrentHashMap源码学习
参数及其含义存储对象的数组。volatile用于保证table变化后可以立刻被看到。transientvolatileNodeK,V[]table;用于table中元素计数。volatile关键字用于保证可见性。同时为避免数据不一致使用cas操作进行修改。privatetransientvolatilelongbaseCount;用于table中每个单元中节点个数的计数。大小是2的倍数privatetransientvolatileCounterCell[]counterCells;节点用于存储每个keyvalue的类。其中key和hash在赋值后不允许修改。value和next指针修改后需要立即可见。staticclassNodeK,VimplementsMap.EntryK,V{finalinthash;finalKkey;volatileVval;volatileNodeK,Vnext;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;}publicfinalVsetValue(Vvalue){thrownewUnsupportedOperationException();}publicfinalbooleanequals(Objecto){Objectk,v,u;Map.Entry?,?e;return((oinstanceofMap.Entry)(k(e(Map.Entry?,?)o).getKey())!null(ve.getValue())!null(kkey||k.equals(key))(v(uval)||v.equals(u)));}/** * Virtualized support for map.get(); overridden in subclasses. */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;}}节点特殊状态的hash值。staticfinalintMOVED-1;// hash for forwarding nodesstaticfinalintTREEBIN-2;// hash for roots of treesstaticfinalintRESERVED-3;// hash for transient reservations进行resize控制。用于表的初始化和resize控制。如果是负数说明table正在被初始化或者resize-1表示初始化否则-1正在resize的线程数。否则当表为空的时候默认值为0。在初始化之后保存下一个计数值用于resize控制。privatetransientvolatileintsizeCtl;常用方法size()方法publicintsize(){longnsumCount();return((n0L)?0:(n(long)Integer.MAX_VALUE)?Integer.MAX_VALUE:(int)n);}如果n的范围在0到Integer.MAX_VALUE之间返回n。如果小于0返回0如果大于Integer.MAX_VALUE返回Integer.MAX_VALUE。finallongsumCount(){CounterCell[]ascounterCells;CounterCella;longsumbaseCount;if(as!null){for(inti0;ias.length;i){if((aas[i])!null)suma.value;}}returnsum;}sumCount统计所有元素的个数。首先sum赋值baseCount获取数组中元素个数然后遍历counterCells统计冲突的元素个数。get()方法publicVget(Objectkey){NodeK,V[]tab;NodeK,Ve,p;intn,eh;Kek;inthspread(key.hashCode());if((tabtable)!null(ntab.length)0(etabAt(tab,(n-1)h))!null){if((ehe.hash)h){if((eke.key)key||(ek!nullkey.equals(ek)))returne.val;}elseif(eh0)return(pe.find(h,key))!null?p.val:null;while((ee.next)!null){if(e.hashh((eke.key)key||(ek!nullkey.equals(ek))))returne.val;}}returnnull;}NodeK,V[] tab;用来对数组进行操作。NodeK,V e指向当前key在数组中对应的对象。NodeK,V p用于表示在链表中查找的对象。int n用于表示在数组的长度。eh用于表示在key对应对象的哈希值。ek用于表示在key对应对象的key。如果数组不为空且key在数组中对应的对象的key和hash值相等则返回对象的值。否则说明存在冲突。如果eh小于0。条件成立即hash小于0分2种情况是树或者正在扩容,需要借助find方法寻找元素find的寻找方式依据Node的不同子类有不同的实现方式:情况一eh-1 是fwd结点 - 说明当前table正在扩容且当前查询的这个桶位的数据已经被迁移走了需要借助fwd结点的内部方法find去查询情况二eh-2 是TreeBin节点 - 需要使用TreeBin 提供的find方法查询否则说明是链表。遍历链表判断数据是否是要获取的数据。put方法putVal方法finalVputVal(Kkey,Vvalue,booleanonlyIfAbsent){if(keynull||valuenull)thrownewNullPointerException();inthashspread(key.hashCode());intbinCount0;for(NodeK,V[]tabtable;;){NodeK,Vf;intn,i,fh;if(tabnull||(ntab.length)0)tabinitTable();elseif((ftabAt(tab,i(n-1)hash))null){if(casTabAt(tab,i,null,newNodeK,V(hash,key,value,null)))break;// no lock when adding to empty bin}elseif((fhf.hash)MOVED)tabhelpTransfer(tab,f);else{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;}}}}if(binCount!0){if(binCountTREEIFY_THRESHOLD)treeifyBin(tab,i);if(oldVal!null)returnoldVal;break;}}}addCount(1L,binCount);returnnull;}如果key为空或者val为空就抛出异常。if (tab null || (n tab.length) 0) tab initTable();如果数组为空或者数组长度为0就初始化table。else if ((f tabAt(tab, i (n - 1) hash)) null)获取数组中i下标的数据是否为空。为空就进行修改。if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null)))casTabAt方法判断tab中i指向的对象是否为空为空就将new的Node更新到当前位置。(fh f.hash) MOVED当前key对应的节点被移动了。调用helpTransfer(tab, f);方法协助进行扩容。否则存在多个key的hash值相同的情况。synchronized (f)对对象f加锁if (tabAt(tab, i) f) { if (fh 0) {判断tab是否发生变化了即tab中索引i对应的对象是否还为f。如果tab没有变化并且fh0说明节点不是fwd结点、TreeBin节点是链表。遍历链表节点如果key存在则覆盖原值如果key不存在在尾部添加节点。如果f节点是TreeBin节点在树中插入节点。if (binCount ! 0)说明存在插入的位置是链表或者是树if (binCount TREEIFY_THRESHOLD)说明是链表需要转树结构。if (oldVal ! null)说明原来的key已经存在了。返回原来的值。addCount(1L, binCount);走到这里说明执行了插入。binCount对应计数加一。initTable方法privatefinalNodeK,V[]initTable(){NodeK,V[]tab;intsc;while((tabtable)null||tab.length0){if((scsizeCtl)0)Thread.yield();// lost initialization race; just spinelseif(U.compareAndSwapInt(this,SIZECTL,sc,-1)){try{if((tabtable)null||tab.length0){intn(sc0)?sc:DEFAULT_CAPACITY;SuppressWarnings(unchecked)NodeK,V[]nt(NodeK,V[])newNode?,?[n];tabletabnt;scn-(n2);}}finally{sizeCtlsc;}break;}}returntab;}while ((tab table) null || tab.length 0)如果table是空说明需要执行resize流程。if ((sc sizeCtl) 0)说明有线程正在初始化或者进行resize。if (U.compareAndSwapInt(this, SIZECTL, sc, -1))对sizectl减一表明在初始化过程中了。把变量赋值给SIZECTL。if ((tab table) null || tab.length 0)表为空或者长度为0需要进行初始化。int n (sc 0) ? sc : DEFAULT_CAPACITY;如果sc大于0说明创建map对象时传递了初始化容量的参数。否则sc0就给n赋默认值。NodeK,V[] nt (NodeK,V[])new Node?,?[n];创建长度为n的临时table。table tab nt;table赋值。sc n - (n 2);等价于数组容量*阈值即数组中存储的元素个数。n2是n右移两位相当于除以4。n-n2相当于n*0.75。finally中sizeCtl赋值。最后返回初始化的表table。
