ConcurrentHashMap在Java8中的实现改动较大，网上关于ConcurrentHashMap的文章也很少有基于java8的，将个人的一些理解记录下来以供分享。
Node
ConcurrentHashMap底层是通过数组+链表(树)来实现的，数组中存储的就是Node。它与HashMap中的定义很相似，但是有一些差别它对value和next属性设置了volatile同步锁，它不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map.get()方法。
transient volatile Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
//当前节点的hash值
final int hash;
//当前节点的Key
final K key;
//当前节点的值，保证了可见性
volatile V val;
//下一个节点
volatile Node<K,V> next;
...
TreeNode
树节点类，另外一个核心的数据结构。 当链表长度过长的时候，会转换为TreeNode。 但是与HashMap不相同的是，它并不是直接转换为红黑树，而是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。 而且TreeNode在ConcurrentHashMap继承自Node类，而并非HashMap中的集成自LinkedHashMap.Entry
TreeBin
这个类并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。另外这个类还带有了读写锁。 这里仅贴出它的构造方法。可以看到在构造TreeBin节点时，仅仅指定了它的hash值为TREEBIN常量，这也就是个标识位
ForwardingNode
一个用于连接两个table的节点类。它包含一个nextTable指针，用于指向下一张表。而且这个节点的key value next指针全部为null，它的hash值为-1. 这里面定义的find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找。通过名称也很容易理解这个节点的含义这个节点主要作用就是重定向，在resize过程中尽可能不影响对数据对读取。
关键方法
put方法
ConcurrentHashMap中key可为null吗？value可以为null吗？为什么呢？HashMap又是什么情况呢？ 通过下面的代码可以发现，ConcurrentHashMap中的key和value都不能为null,这是因为在Node中计算hash的时候使用的是key.hashCode() ^ val.hashCode()；而在HashMap中是Objects.hashCode(key) ^ Objects.hashCode(value);
主要的处理步骤有：
- 计算key的hash值
- 如果没有初始化需要进行初始化
- 通过按位与进行快速取模计算出桶位置，如果该位置没有元素则通过CAS插入，如果该节点是FWD节点，则帮助完成扩容
- 如果有元素，也不是FWD节点则对该节点进行加锁后插入元素
- 插入元素后，进行元素计数加1，在该步操作中可能会出发扩容操作
final V putVal(K key, V value, boolean onlyIfAbsent) {
//concurrentHashMap要求key,value都不能为null.为什么呢？这是因为 Node中计算hash的方法是key.hashCode() ^ val.hashCode()；
//如果key或者value为null在此处计算hash值的时候会出现NPE
if (key == null || value == null) throw new NullPointerException();
//计算key的hash值（两次hash计算，通过掩码运算得到内部hash值)
int hash = spread(key.hashCode());
int binCount = 0;
//死循环直到操作成功
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//此处如果tab=null,或者tab.length-0表示表没有初始化，此处需要完成初始化！
//这个就是ConcurrentHashMap将初始化延迟到第一次put操作时候完成
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//i=(n-1)&hash这个计算和HashMap相同，这个是对hash值对快速取模操作，i的值即表示该数据存放的桶号
//如果在i位置的桶中没有元素则通过CAS操作试图将元素插入到该位置，如果插入成功则退出循环！在向空桶中添加元素时是无锁操作
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//如果这个桶的节点的hash值是MOVED则表示该节点在进行扩容操作
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
//对正常的桶通过synchronized进行加锁，synchronized锁已经进行了很大性能优化
V oldVal = null;
synchronized (f) {
//重复检查当前桶是否有发生改变,如果没有发生改变才做后续处理
if (tabAt(tab, i) == f) {
//fn是这个桶的hash值，大于等于0表示链表节点
if (fh >= 0) {
binCount = 1;
//向后遍历，如果存在重复的key则更新value否则插入到链表尾部跳出循环
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;
//put操作时候onlyIfAbsent为false，所以此处会进行值更新
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) {
//如果链表的长度大于等于8则需要将链表转换为树，可以发现首先是将数据插入到链表中再判断是否需要进行转换为树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//计数增加1，该操作中可能会出发扩容操作
addCount(1L, binCount);
return null;
}
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
//BASECOUNT 为baseCount属性的偏移量，如果原值是baseCount则更新为b+x;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
if (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);
return;
}
if (check <= 1)
return;
s = sumCount();
}
//counterCells为null,check>0 ,s=b+x, 在put方法中x=1,b=baseCount,在resize之前
//sizeCtl=16*0.75=12
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
//sc小于0表示 sc绝对值-1个线程在进行扩容，sc=0表示还没有初始化，此处不可能为0，如果大于0表示需要下次
//扩容的阈值
if (sc < 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);
}
//对sizeCtl更新如果成功就扩容，否则计算大小继续循环
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
//n为数组大小
int n = tab.length, stride;
//NCPU表示机器的CPU核心数,如NCPU=4，第一次n=16,stride=16;否则stride=n>>>3/ncpu
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
//如果nextTab为空，表示尚未进行扩容处理
if (nextTab == null) { // initiating
try {
//创建长度为原来两倍的数组，并赋值给nextTab
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赋值
nextTable = nextTab;
//transferIndex时扩容前数组的长度
transferIndex = n;
}
//获取扩容后的数组长度
int nextn = nextTab.length;
//创建forwarding节点
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;
//只要advance=true就一直循环下去
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
//如果transferIndex<=0则退出while循环
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
//第一次 i=nextIndex-1,nextIndex=transferIndex=n=tab.length,即i是原有数组长度减去1
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
//如果数组i位置为空则直接fwd节点插入
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//如果节点的哈希值为MOVED表示已经处理过了，则将advance设置为true，处理其他的桶，这样有效避免了多线程重复处理过程
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
//否则对该节点进行加锁
synchronized (f) {
//加锁后再次判断i位置是否是加锁的对象
if (tabAt(tab, i) == f) {
//ln表示低位节点，hn表示高位节点，在经过一次扩容后，根据桶号计算 h&(n-1)可以知道
//该节点要不在原位置，要不就向后移动扩容大小位，ln就是位置不变的元素，hn就是移动扩容
//大小的元素
Node<K,V> ln, hn;
//fh节点的hash值，大于0标志正常链表节点
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
//从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;
}
//从f节点开始遍历非最后一个节点,计算出高位节点和低位节点
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);
}
//i是tab中元素的索引，n是tab的长度
//在nextTab中i节点中设置ln
setTabAt(nextTab, i, ln);
//在i+n位置上插入hn
setTabAt(nextTab, i + n, hn);
//将原有i位置设置为forwarding节点
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;
}
}
}
}
}
}
相关推荐
ConcurrentHashMap源码分析源码分析 代码解释非常详细！！！！
Java并发系列之ConcurrentHashMap源码分析 ConcurrentHashMap是Java中一个高性能的哈希表实现，它解决了HashTable的同步问题，允许多线程同时操作哈希表，从而提高性能。 1. ConcurrentHashMap的成员变量： ...
源码分析见我博文：http://blog.csdn.net/wabiaozia/article/details/50684556
在Java并发编程领域，`ConcurrentHashMap`是一个至关重要的类，它提供了线程安全的哈希映射功能，且性能优异。在JDK8中，`ConcurrentHashMap`的实现方式与之前的版本（如JDK6）有了显著变化，去除了Segment锁段的...
通过以上分析，我们可以看到ConcurrentHashMap如何通过锁分段技术来解决HashMap在并发环境下的线程安全问题，并通过巧妙的设计减少线程间锁的竞争，从而提升性能。因此，在设计需要高并发性能的程序时，...
程序员面试加薪必备_ConcurrentHashMap底层原理与源码分析深入详解
3. **HashMap与ConcurrentHashMap源码分析**： - HashMap在Java 1.7中不是线程安全的，而在1.8中通过分段锁实现了一定程度的并发性。 - ConcurrentHashMap在Java 1.8中采用了CAS（Compare and Swap）和...
#### 五、ConcurrentHashMap源码分析 - **概述**：`ConcurrentHashMap`是Java提供的线程安全的哈希表实现。它使用分段锁技术来提高并发性能。 - **关键特性**： - **分段锁**：将哈希表分成多个段，每个段使用一个...
《JUC并发编程与源码分析视频课》是一门深入探讨Java并发编程的课程，主要聚焦于Java Util Concurrency（JUC）库的使用和源码解析。JUC是Java平台提供的一组高级并发工具包，它极大地简化了多线程编程，并提供了更...
"Android 开源框架源码分析" Android 是一个开源的操作系统，而其框架源码的分析则是其中一个非常重要的方面。今天，我们将对 Android 开源框架源码进行分析，涉及的内容包括 EventBus、Glide、OkHttp、Android ...
本文将对ConcurrentHashMap#put方法的源码进行详细分析，从而帮助读者更好地理解ConcurrentHashMap的工作机理。 一、ConcurrentHashMap的底层原理 ConcurrentHashMap是基于哈希表实现的，可以存储大量的数据。其...
ConcurrentHashMap理论概述,实现原理,简单的源码分析,put和get的简单学习
2. **源码分析：ArrayList** `ArrayList`是基于动态数组实现的列表，其内部维护了一个Object类型的数组。当我们添加元素时，如果数组已满，会自动扩容。扩容策略通常是将容量扩大到原来的1.5倍，这在源码中可以通过...
ArrayList核心源码+扩容机制分析LinkedList核心源码分析HashMap核心源码+底层数据结构分析ConcurrentHashMap核心源码+底层数据结构分析LinkedHashMap核心源码分析CopyOnWriteArrayList核心源码分析...
我们首先来理解`computeIfAbsent`方法的基本概念，然后再深入分析这个问题的成因及解决方案。 `computeIfAbsent`是JDK 1.8中新增的一个功能强大的方法，它的作用是在给定的键不存在于映射中时，通过提供的函数来...
Java源码分析是软件开发过程中一个重要的学习环节，它能帮助开发者深入理解代码背后的逻辑，提升编程技巧，以及优化程序性能。在这个过程中，我们通常会关注类的设计、算法的应用、数据结构的选择，以及如何利用Java...
"java并发源码分析之实战编程"这个主题深入探讨了Java平台上的并发处理机制，旨在帮助开发者理解并有效地利用这些机制来提高程序性能和可扩展性。在这个专题中，我们将围绕Java并发库、线程管理、锁机制、并发容器...
BoneCP是一款高效、轻量级的Java数据库连接池实现，它的源码分析对于我们理解数据库连接池的工作原理，优化数据库性能以及进行二次开发具有重要意义。 首先，我们需要了解数据库连接池的基本概念。数据库连接池是...