1.8
https://processon.com/view/60cc62685653bb3c31f06a22
jdk 1.7中是基于segment数组然后通过ReentrantLock对每一个segment元素加锁，来保证每一个segment内线程操作的安全性，从而保证了所有线程的操作安全；
其中：默认的segment数组长度是16，也就是说concurrenthashmap1.7默认的并发度是16；
1.8中直接取消segment数组，采用和hashmap相同的结构 ：Node数组+链表+红黑树；每一次增加操作是锁住一个Node元素，相对于1.7中是锁住一个segment，1.8的锁粒度要小一些(因为segment中是hashentry数组)；引入红黑树的原因与hashmap的原因一样，当每一个Node下面有很多元素，链表过长的时候，访问的效率会变低，引入红黑树来使其查询操作的复杂度为logN；
现在开始看源码，我们看jdk1.8的；put方法，首先看整体逻辑：
put
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();//从这就可以看出concurrenthashmap不允许插入null
int hash = spread(key.hashCode());//计算key的hash
int binCount = 0;//记录链表长度，判断是否需要扩容
for (Node<K,V>[] tab = table;;) {//可以看到是一个死循环，多线程的时候就不断循环
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)//数组为空就初始化
tab = initTable();
//获取对应下标上的元素，如果为空
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //该下标元素为空就直接把节点放入(cas)
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}//如果当前节点正在扩容，就并发扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {//正常情况
V oldVal = null;
synchronized (f) {//syn，处理多线程(给头节点加锁)
if (tabAt(tab, i) == f) {//再次判断，和单例那里一样
if (fh >= 0) {//说明这个下标的是链表
binCount = 1;//后面就和hashmap里面的判断差不多了
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}//如果是树型节点，就用树的方式来插入
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {//插入之后判断
//如果数组长度小于64则先扩容到64；然后链表长度再大于8就变为红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//最后把总元素个数+1
addCount(1L, binCount);
return null;
}
runBit
runBit的作用是目的是尽量重用 Node 链表尾部的一部分
大家可以看到，16 位的结果到 32 位的结果，正好增加了 16.
比如 20 & 15=4 、20 & 31=20 ； 4-20 =16
比如 60 & 15=12 、60 & 31=28； 12-28=16
initTable()
初始化数组。sizeCtl的含义：private transient volatile int sizeCtl;
- -1：正在初始化
- -n：代表有n-1个线程在扩容
- 0：表示数组还没有被初始化
- .>0：表示下一次扩容需要的元素个数
transient volatile Node<K,V>[] table;
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)//有线程在初始化了，则其他初始化线程等待
Thread.yield(); // lost initialization race; just spin
//cas操作将sizeCtl设置为-1，cas成功由该线程去初始化
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
//默认大小是16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;//赋值给全局变量
sc = n - (n >>> 2);//计算下次扩容的变量
}
} finally {
sizeCtl = sc;//重新赋值
}
break;
}
}
return tab;
}
tabAt
getObjectVolatile，volatile，虽然table也是volatile修饰的，但是可见的是数组的引用，对于具体的元素调用这个方法就可以让对应下标的修改马上可见。
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
helpTransfer
这个方法就是用来并发转移数组的。
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
//进来先判断下是否还需要帮住扩容
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
//这个判断和addcount里面的判断差不多：表示扩容结束
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {//在低16位上增加正在口容的线程数
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;//返回新数组
}
addCount
调用源：addCount(1L, binCount);//check就是链表上的个数
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
//首先判断counterCells是否位空，为空就去cas设置basecount(同时表示没有线程竞争)
//cas失败就会执行下面的代码，通过并发去计算
(增加元素) if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
//计数表或者某一下标为空就直接调用fullAddCount
//或者cas修改a下标处
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
//主要用来初始化CounterCell，并记录元素个数（包含扩容，初始化等操作）
fullAddCount(x, uncontended);
return;
}
if (check <= 1)//链表个数小于1，返回
return;
s = sumCount();//统计
}
//如果链表上的个数大于等于0，则需要检查扩容
(扩容判断)if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
//s 标识集合大小，如果集合大小大于或等于扩容阈值（默认值的 0.75）
//并且 table 不为空并且 table 的长度小于最大容量
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);//生成扩容戳
//说明有其他线程正在扩容
if (sc < 0) {
//满足下面任一一个就说明不能帮住扩容，然后退出循环
//sc=rs+1 表示扩容结束
//sc >>> RESIZE_STAMP_SHIFT!=rs 表示比较高 RESIZE_STAMP_BITS 位生成戳和 rs 是否相等，相同
//sc==rs+MAX_RESIZERS 表示帮助线程线程已经达到最大值了
//(nt = nextTable) == null表示扩容已经结束了
//transferIndex <= 0表示没有多余的空间来让更多线程来扩容了
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
//当前没有线程在扩容
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))//+2表示现在在扩容的线程有一个
transfer(tab, null);
s = sumCount();
}
}
}
resizeStamp
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
Integer.numberOfLeadingZeros 这个方法是返回无符号整数 n 最高位非 0 位前面的 0 的个数
接着再来看,当第一个线程尝试进行扩容的时候，会执行下面这段代码
U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)
因为 1 表示初始化，2 表示一个线程在执行扩容，而且对 sizeCtl 的操作都是基于位运算的，所以不会关心它本身的数值是多少，只关心它在二进制上的数值，而 sc + 1 会在低 16 位上加 1。
transfer
任务：扩大数组长度；数据迁移；
第一个扩容的线程，执行 transfer 方法之前，会设置 sizeCtl =
(resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2)
后续帮其扩容的线程，执行 transfer 方法之前，会设置 sizeCtl = sizeCtl+1
每一个退出 transfer 的方法的线程，退出之前，会设置 sizeCtl = sizeCtl-1
每个线程的负责范围：（bound,i） =(16,31) 从 31 的位置往前推动。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;//表示每个线程要处理的桶的大小
//n/8/cpu核心数，如果得到的结果小于16，那么让每个线程处理16个桶
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];//n*2，扩大两倍
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {//向前推移
int nextIndex, nextBound;
//--i 表示下一个待处理的 bucket，如果它>=bound,表示当前线程已经分配过bucket 区域
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//cas去修改边界，也就是给当前线程分配区间，当运行到这里的时候nextIndex的值是数组长度，32；stride感觉就是步长了；“TRANSFERINDEX”就是transferIndex
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
//第一次：bound=32-16=16;i=31;然后当前线程分配完毕
//第二个线程：bound=0;i=15;
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
//表示当前线程负责的桶已经处理完了
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {//如果d完成了扩容，善后工作
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {//给总线程个数-1
//如果当前线程是最后一个线程
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
//加锁，转移元素
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
//区别高低位的重点
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
fullAddCount
主要用来初始化CounterCell，并记录元素个数（包含扩容，初始化等操作）
private final void fullAddCount(long x, boolean wasUncontended ){
int h;//调用了就有冲突wasUncontended=true
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;// 由于重新生成了 probe，未冲突标志位设置为 true
}
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
//说明 counterCells 已经被其他线程初始化过了
if ((as = counterCells) != null && (n = as.length) > 0) {
//counterCells已经被初始化过了，但是a下标处为空
if ((a = as[(n - 1) & h]) == null) {
//cellsBusy=0 表示 counterCells 不在初始化或者扩容状态下
if (cellsBusy == 0) { // Try to attach new Cell
CounterCell r = new CounterCell(x); // Optimistic create
//防止其他线程并发修改countercells
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
rs[j] = r;
created = true;
}
} finally {
cellsBusy = 0;
}
if (created)
break;
//说明rs[j = (m - 1) & h] == null处不为空
continue; // Slot is now non-empty
}
}
collide = false;
}
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
//到这就是指定位置不为空，就通过cas增加
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;
//有其他线程建立了新的counterCells或者并发数大于cpu核数
else if (counterCells != as || n >= NCPU)
collide = false; //表示当前线程不进行扩容，退出循环 // At max size or stale
else if (!collide)
collide = true;//标记下次循环会进行扩容
//说明线程数过多，需要创建更多的counterCells，同时标记正在扩容，下面就是扩容的流程
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
if (counterCells == as) {// Expand table unless stale
CounterCell[] rs = new CounterCell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
counterCells = rs;
}
} finally {
cellsBusy = 0;
}
collide = false;
continue; // Retry with expanded table
}
h = ThreadLocalRandom.advanceProbe(h);
}
//(第一次进入也会到这)
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0;
}
if (init)
break;
}
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
tryPresize
尝试扩容；
size number of elements (doesn't need to be perfectly accurate)
/*官方注释：因为后面会对这个参数进行修正*/
private final void tryPresize(int size) {
//对 size 进行修复,主要目的是防止传入的值不是一个 2 次幂的整数，然后通过tableSizeFor 来讲入参转化为离该整数最近的 2 次幂
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
jdk1.7
1.7中的结构：数组+链表+reentrantlock+
构造函数
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
int sshift = 0;
int ssize = 1;
//依据给定的concurrencyLevel并行度，找到最适合的segments数组的长度，
// 为上文默认并行度参数说明的大于concurrencyLevel的最小的2的n次方
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;//2
while (cap < c)
cap <<= 1;
// create segments and segments[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
put
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//先尝试对segment加锁，如果直接加锁成功，那么node=null；如果加锁失败，则会调用scanAndLockForPut方法去获取锁，
//在这个方法中，获取锁后会返回对应HashEntry（要么原来就有要么新建一个）
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
//获取对应索引下的头节点
HashEntry<K,V> first = entryAt(tab, index);
//开始遍历first为头结点的链表
for (HashEntry<K,V> e = first;;) {
if (e != null) {//<1>
//e不为空，说明当前键值对需要存储的位置有hash冲突，直接遍历当前链表，如果链表中找到一个节点对应的key相同，
//依据onlyIfAbsent来判断是否覆盖已有的value值。
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
//进入这个条件内说明需要put的<k,y>对应的key节点已经存在，直接判断是否更新并最后break退出循环。
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;//未进入上面的if条件中，说明当前e节点对应的key不是需要的，直接遍历下一个节点。
}
else {//<2>
//进入到这个else分支，说明e为空，对应有两种情况下e可能会为空，即：
// 1>. 遍历到了链表的表尾仍然没有满足条件的节点。
// 2>. e=first一开始就是null（可以理解为即一开始就遍历到了尾节点）
if (node != null) //这里有可能获取到锁是通过scanAndLockForPut方法内自旋获取到的，这种情况下依据找好或者说是新建好了对应节点，node不为空
node.setNext(first);
else// 当然也有可能是这里直接第一次tryLock就获取到了锁，从而node没有分配对应节点，即需要给依据插入的k,v来创建一个新节点
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1; //总数+1 在这里依据获取到了锁，即是线程安全的！对应了上述对count变量的使用规范说明。
//判断是否需要进行扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
//扩容是直接重新new一个新的HashEntry数组，这个数组的容量是老数组的两倍，
rehash(node);
else
//数组无需扩容，那么就直接插入node到指定index位置，这个方法里用的是UNSAFE.putOrderedObject
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
scanAndLockForPut
获取锁失败后，不想它白白阻塞在这，就让
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
int retries = -1; // negative while locating node
//如果尝试加锁失败，那么就对segment[hash]对应的链表进行遍历找到需要put的这个entry所在的链表中的位置，
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
//获取锁失败，初始时retries=-1必然开始先进入第一个if
if (retries < 0) {//<1>
if (e == null) { //<1.1>
//e=null代表两种意思，第一种就是遍历链表到了最后，仍然没有发现指定key的entry；
//第二种情况是刚开始时确实太过entryForHash找到的HashEntry就是空的，即通过hash找到的table中对应位置链表为空
//当然这里之所以还需要对node==null进行判断，是因为有可能在第一次给node赋值完毕后，然后预热准备工作已经搞定，
//然后进行循环尝试获取锁，在循环次数还未达到<2>以前，某一次在条件<3>判断时发现有其它线程对这个segment进行了修改，
//那么retries被重置为-1，从而再一次进入到<1>条件内，此时如果再次遍历到链表最后时，因为上一次遍历时已经给node赋值过了，
//所以这里判断node是否为空，从而避免第二次创建对象给node重复赋值。
if (node == null) // speculatively create node
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
else if (key.equals(e.key))//<1.2> 遍历过程发现链表中找到了我们需要的key的坑位
retries = 0;
else//<1.3> 当前位置对应的key不是我们需要的，遍历下一个
e = e.next;
}
else if (++retries > MAX_SCAN_RETRIES) {//<2>
lock();
break;
}
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {//<3>
// 遍历过程中，有可能其它线程改变了遍历的链表，这时就需要重新进行遍历了。
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
return node;
}
rehash
/**
* Doubles size of table and repacks entries, also adding the
* given node to new table
* 对数组进行扩容，由于扩容过程需要将老的链表中的节点适用到新数组中，所以为了优化效率，可以对已有链表进行遍历，
* 对于老的oldTable中的每个HashEntry，从头结点开始遍历，找到第一个后续所有节点在新table中index保持不变的节点fv，
* 假设这个节点新的index为newIndex，那么直接newTable[newIndex]=fv，即可以直接将这个节点以及它后续的链表中内容全部直接复用copy到newTable中
* 这样最好的情况是所有oldTable中对应头结点后跟随的节点在newTable中的新的index均和头结点一致，那么就不需要创建新节点，直接复用即可。
* 最坏情况当然就是所有节点的新的index全部发生了变化，那么就全部需要重新依据k,v创建新对象插入到newTable中。
*/
@SuppressWarnings("unchecked")
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
int newCapacity = oldCapacity << 1;
threshold = (int)(newCapacity * loadFactor);
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
int sizeMask = newCapacity - 1;
for (int i = 0; i < oldCapacity ; i++) {
HashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
int idx = e.hash & sizeMask;
if (next == null) // Single node on list 只有单个节点
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
HashEntry<K,V> lastRun = e;
int lastIdx = idx;
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}//这个for循环就是找到第一个后续节点新的index不变的节点。
newTable[lastIdx] = lastRun;
// Clone remaining nodes
//第一个后续节点新index不变节点前所有节点均需要重新创建分配。
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, p.value, n);
}
}
}
}
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}//这个for循环就是找到第一个后续节点新的index不变的节点。
newTable[lastIdx] = lastRun;
// Clone remaining nodes
//第一个后续节点新index不变节点前所有节点均需要重新创建分配。
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, p.value, n);
}
}
}
}
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}