一、结构介绍
HashMap和ConcurrentHashMap的存储结构是一致的。ConcurrentHashMap是线程安全的。
ConcurrentHashMap底层存储结构：
关于put和putIfAbsent的区别 ：
// put和putIfAbsent都是想ConcurrentHashMap中存储值。
// 如果出现key一致的，将新数据覆盖老数据，并且返回老数据
public V put(K key, V value) {
return putVal(key, value, false);
}
// 如果出现key一致的，什么都不做，返回老数据。 最只有key不存在时，才会正常的添加数据
public V putIfAbsent(K key, V value) {
return putVal(key, value, true);
}二、源码剖析
2.1 构造方法
/**
* 默认的构造方法为空，不做任何操作，数组长度默认是16
*/
public ConcurrentHashMap() {
}
/**
* 传递初始化容量的构造方法，传递进来一个初始容量，
* ConcurrentHashMap会基于这个值计算一个比这个值大的2的幂次方数作为初始容量
* 与其他版本不同，例如：传递 16 作为参数，它会计算得到 32 作为初始化容量，而不是 16
*/
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}2.2 putVal源码剖析
在此之前我们先介绍一下sizeCtl属性不同值代表的不同含义，方便后续观看源码去印证：
1.sizeCtl为0，代表数组未初始化， 且数组的初始容量为16
2.sizeCtl为正数，如果数组未初始化，那么其记录的是数组的初始容量，如果数组已经初始化，那么其记录的是数组的扩容阈值
3.sizeCtl为-1，表示数组正在进行初始化
4.sizeCtl小于0，并且不是-1，表示数组正在扩容， -(1+n)，表示此时有n个线程正在共同完成数组的扩容操作
由于putVal代码太多长，后续分析这个方法源码以分段形式来展开分析各个方法的作用。
2.2.1 散列算法
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 判断key与value不能为空，这与hashmap不同
if (key == null || value == null) throw new NullPointerException();
// 通过散列算法获取对应的hash
int hash = spread(key.hashCode());
int binCount = 0;
}
// 通过散列算法获取对应的hash值，我们举个例子看一下下面这个算法做了哪些事情
// HASH_BITS为十六进制：0x7fffffff换算成二进制如下：
// 0111 1111 1111 1111 1111 1111 1111 1111
// 比如我现在的key计算出来的hash值如下：
// 00001001 10001010 00000000 01100101
// 首先h >>> 16，就是左移16位，那结果就是：
// 00000000 00000000 00001001 10001010
// 然后跟原hash值做异或[相同为0，不同为1]：
// 00000000 00000000 00001001 10001010
// 异或
// 00001001 10001010 00000000 01100101
// 结果为：
// 00001001 10001010 00001001 11101111
// 然后在跟 0111 1111 1111 1111 1111 1111 1111 1111
// 最后结果为: 00001001 10001010 00001001 11101111
// 其实这样子的算法可以看得出来就是为了能够让高16位的hash值也能够参与进来运算，减少hash冲突
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
2.2.2 初始化数组
初始化数组，ConrrentHashMap在new时，不会创建数组，在使用时才会创建。
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 判断key与value不能为空，这与hashmap不同
if (key == null || value == null) throw new NullPointerException();
// 通过散列算法获取对应的hash
int hash = spread(key.hashCode());
int binCount = 0;
// tab是ConrrentHashMap的数组
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// tab为空，代表当前数组没有初始化
if (tab == null || (n = tab.length) == 0)
// 初始化数组，ConrrentHashMap在new时，不会创建数组，在使用时才会创建
tab = initTable();
}
return null;
}
// 初始化数组
private final Node<K,V>[] initTable() {
// 声明tab：临时存数组。 sc：临时存sizeCtl
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，表示数组正在初始化
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// DCL，再次判断数组是否已经初始化
if ((tab = table) == null || tab.length == 0) {
// 如果sc大于等于0，没人在执行初始化操作。
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;
}2.2.3 添加数据-数组
添加数据到数组上，如果没有存在冲突。
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 判断key与value不能为空，这与hashmap不同
if (key == null || value == null) throw new NullPointerException();
// 通过散列算法获取对应的hash
int hash = spread(key.hashCode());
int binCount = 0;
// tab是ConrrentHashMap的数组
for (Node<K,V>[] tab = table;;) {
n:数组长度 i:索引位置 f:i位置所在的数据 fh:是f的hash值
Node<K,V> f; int n, i, fh;
// tab为空，代表当前数组没有初始化
if (tab == null || (n = tab.length) == 0)
// 初始化数组，ConrrentHashMap在new时，不会创建数组，在使用时才会创建
tab = initTable();
// tabAt（数组，索引位置）= 拿到数组指定索引位置的数据
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 通过CAS的方式，将数据放到tab的i位置上，将key，hash封装成了一个node对象
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);
}
return null;
}2.2.4 添加数据-链表
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 判断key与value不能为空，这与hashmap不同
if (key == null || value == null) throw new NullPointerException();
// 通过散列算法获取对应的hash
int hash = spread(key.hashCode());
int binCount = 0;
// tab是ConrrentHashMap的数组
for (Node<K,V>[] tab = table;;) {
n:数组长度 i:索引位置 f:i位置所在的数据 fh:是f的hash值
Node<K,V> f; int n, i, fh;
// tab为空，代表当前数组没有初始化
if (tab == null || (n = tab.length) == 0)
// 初始化数组，ConrrentHashMap在new时，不会创建数组，在使用时才会创建
tab = initTable();
// tabAt（数组，索引位置）= 拿到数组指定索引位置的数据
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 通过CAS的方式，将数据放到tab的i位置上，将key，hash封装成了一个node对象
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 {
// 代码执行到了执行说明就存在了hash冲突
V oldVal = null;
// 以桶的位置为锁
synchronized (f) {
// dcl，再一次判断数据是否发生了变化
if (tabAt(tab, i) == f) {
// fh 大于0则说明是链表
if (fh >= 0) {
// 赋值为1，记录的是链表node的节点数量
binCount = 1;
//e为当前桶的第一个位置
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;
// 如果是putIfAbsent，进去不if逻辑
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
// e指向下一个节点，并且如果e == null，说明下面没节点了
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;
}
}
}
}
// 判断当前链表的长度是否大于8，如果是则进去转红黑树操作
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
// 判断是否需要返回值操作
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
return null;
}2.2.5 扩容操作
可以看到在putVal之后会通过binCount判断当前链表是否要转红黑树，在treeifyBin方法中会判断是否转红黑树和是否需要扩容操作。
// 判断是否需要转红黑树或者扩容
private final void treeifyBin(Node<K,V>[] tab, int index) {
// n：数组长度 sc：sizeCtl
Node<K,V> b; int n, sc;
if (tab != null) {
// 判断当前数组长度 小于64，则不转红黑树，先进行扩容(意思是更想把数据放到数组上)
// 只有数组长度大于等于64并且链表长度达到8，才会转为红黑树
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
// 转红黑树操作
// 将单向链表转成TreeNode对象，在通过TreeBin方法转成红黑树
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}2.2.6 HashMap扩容
在了解ConrrentHashMap的扩容操作之前最好先了解一下hashmap的扩容，高低位链表，因为我们扩容都是两倍扩容，而且我们取数组的下标都是拿hash值与上数组长度，那么决定元素在新数组的高位还是低位，取决于当前hash值高一位的值，如下图：
2.2.7 ConrrentHashMap扩容操作
private final void tryPresize(int size) {
// 这个判断是给putALL留的，要计算当前数组的长度
// 如果这个size大于最大长度/2,直接将数组长度设置为最大值
// c就是初始化的长度
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
// sizeCtl
// -1:正在做初始化 小于-1 正在扩容 0：代表还没初始化 大于0 可能初始化了，也可能没有初始化[初始化的长度]
int sc;
while ((sc = sizeCtl) >= 0) {
// 代表没有正在初始化，也没有正在扩容
// tab：数组 n：数组长度
Node<K,V>[] tab = table; int n;
// 判断数组是不是还没开始初始化
if (tab == null || (n = tab.length) == 0) {
// 初始化数组和initTable一样的代码
// 在sc跟c中取最大的值
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) {
// 计算出来扩容标识戳【基于老数组长度计算扩容标识戳，因为ConcurrentHashMap允许多线程迁移数据】
int rs = resizeStamp(n);
// 这里是一个BUG，当前sc在while循环中，除了初始化没有额外赋值的前提下，这个sc < 0 永远进不来。
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || // 判断协助扩容线程的标识戳是否一致，BUG之一,在判断扩容操作是否已经到了最后的检查阶段
sc == rs + MAX_RESIZERS || (nt = nextTable) == null || // BUG之一，判断扩容线程是否已经达到最大值
transferIndex <= 0)// transferIndex为线程领取任务的最大节点，如果为0，代表所有老数据迁移任务都没领干净了
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// 还没有进行扩容，当前线程可能是第一个进来执行扩容的线程
// 基于CAS的方式，将sizeCtl将原值改为扩容标识戳左移16位
// 10000000 00011010 00000000 00000010 一定是< -1的负数，可以代表当前[可以先看resizeStamp]
// 为什么低位+2，代表1个线程扩容，低位为5，代表4个线程正在扩容
// 扩容分为两个部分： 创建新数组，迁移数据
// 当最后一个线程迁移完毕之后，对低位-1，最终结果低位还是1，需要对整个老数组再次检查，数据是否已经迁移干净
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// 开始扩容操作，传入老数组
transfer(tab, null);
}
}
}
// 扩容标识戳，比如现在由 32-64
// 00000000 00000000 00000000 00011010 -->32
// numberOfLeadingZeros计算n在二进制表示时，前面有多少个0
// 前面的操作是基于数组长度等到一个标识，方便其他线程参与扩容
// (1 << (RESIZE_STAMP_BITS - 1))后面的值是为了保证当前扩容戳左移16位之后，一定是一个负数
// 后续左移16位就是表示：高16位用来表示一个扩容标识戳，低16位用来表示正在扩容的线程数 -1
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
2.2.8 transfer方法
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 这里是为了能够最大程度使用计算机CPU
// - 比如n为：左移3位：1024 512 256 128 / 4 = 32 那么步长就是32
// 就是每次线程迁移的最小数据就是32
// 这个操作就是为了能够充分发挥CPU的性能，因为迁移数据是CPU密集型，尽量让并发扩容线程数量不要太大，从而造成CPU的性能都消耗在了线程切换上面，从而导致扩容效率低
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];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
// transferIndex 设置为老数组长度
transferIndex = n;
}
// 以下我们示例比如是由：32 -> 64 那么以上属性值为：
// stride 步长 16
// n:老数组长度 32
// nextTable，nextTab：新数组
// nextn ：新数组长度64
// transferIndex ：线程领取任务时的核心属性 32
int nextn = nextTab.length;
// 声明fwd节点，在老数组浅灰数据完成之后，将fwd赋值上去
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;
// 第一个判断是为了迁移下一个索引位置，暂时不用管
if (--i >= bound || finishing)
advance = false;
// 说明没有任务需要迁移了
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// transferIndex：16
// stride：16，nextIndex：32，nextBound：16
// bound:16 ，i：31
// 开始领取任务，如果CAS成功，代表当前线程领取了32-16这个范围数据的迁移
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
// 迁移最后一个的线程活干完了，或者其他线程没有任务可以领取了
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
// 判断结束了没，第一次肯定是进不来的
if (finishing) {
// 置为空
nextTable = null;
table = nextTab;
// 将sizeCtl赋值为下一次扩容的值
sizeCtl = (n << 1) - (n >>> 1);
// 扩容结束
return;
}
// 到这里说明当前线程已经没有任务可以领取了
// 基于CAS的方式，将低位-1，代表当前线程退出了扩容操作
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 判断我是否是最后一个线程完成迁移数据的，如果不是直接return结束
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// 到这里说明是最后一个线程结束迁移任务
// finishing 结束表示和advance领取任务的标记全部设置为true
finishing = advance = true;
// i设置为老数组长度，从头到尾再检查一次整个老数组
i = n; // recheck before commit
//额外分析：当前线程完成领取的迁移任务后，再次进入while循环，查看是否有任务可以领取如果transferIndex变为0了，代表我没有任务可以领取，将i设置为-1没有任务可以领取，退出当前扩容操作：1、基于CAS将sizeCtl - 1代表我退出扩容操作2、-1成功后，还要判断，我是不是最后一个退出扩容的线程（sc - 2值是否是 扩容标识戳 << 16） 如果不是，直接return结束3、如果是最后一个结束迁移的线程，将i复制为老数组长度，重新从末位到头部再次检查一圈
}
}
else if ((f = tabAt(tab, i)) == null)
// 如果发现迁移为主的数据为null，设置一个fwd，代表当前位置已经迁移
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) {
// fh与老数组进行&运算，得到runBit
// 00001111
// 00010000
// 这个计算的结果，会决定当前数据在迁移时，是放到新数组的i位置还有新数组的 i + n位置
int runBit = fh & n;
Node<K,V> lastRun = f;
// lastRun机制
// 提前循环一次链表，将节点赋值到对应的高低位Node./
// 如果链表最后面的值没有变化，那就不动指针，直接复制。
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;
}
}
}
}
}
}2.2.9 helpTransfer方法
// 协助扩容
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
// 老数组不为null，当前节点是fwd，新数组不为null
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
// 创建自己的扩容标识戳
int rs = resizeStamp(tab.length);
// 判断之前赋值的内容是否有变化，并且sizeCtl是否小于0
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs ||
sc == rs + 1 ||
sc == rs + MAX_RESIZERS ||
transferIndex <= 0)
// 有一个满足，就说明不需要协助扩容了
break;
// CAS，将sizeCtl + 1，代表来协助扩容了
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}