本文主要介绍ConcurrentHashMap的put操作如果有错误的地方欢迎大家指出。
1、ConcurrentHashMap的put操作
ConcurrentHashMap的put操作主要有3种方式
/**
*
* @param key 传入的key
* @param value value传入的value
* @return 如果写入冲突（说明此前有和他相同的节点，也就是key和hash值和他一模一样），则返回冲突的节点的值，如果没有冲突，则返回null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
/**
* 将原有的Map中的键值对全部移动到现在的HashMap中，
* 如果节点已经存在（key相同并且hashcode相同），则把原来的值进行更新反之添加到集合中
*/
public void putAll(Map<? extends K, ? extends V> m) {
tryPresize(m.size()); //重新调整表的大小使得能够容纳所有的元素
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putVal(e.getKey(), e.getValue(), false);
}
/**
* 和put方法类似，只是如果发生写冲突，不进行旧值的更新
*/
public V putIfAbsent(K key, V value) {
return putVal(key, value, true);
}
本文主要分析第一种方式（其他方式基本一样），废话不多说，直接上源码
//这个方法为put方法的入口方法，他调用了putVal方法，没什么好说的
public V put(K key, V value) {
return putVal(key, value, false);
}
/**
*
* @param key 传入的key
* @param value 传入的value
* @param onlyIfAbsent 如果为true，表示如果发生写冲突，旧值不进行更新，如果为false，则旧值进行更新
* @return 如果有写冲突则返回原来的旧的value，没有则返回null
*/
final V putVal(K key, V value, boolean onlyIfAbsent) {
//如果传入的key或者value为null，则抛出空指针异常（注意，这里有HashMap有比较大的区别）
if (key == null || value == null) throw new NullPointerException();
//通过hash算法计算出key对应的hash值
int hash = spread(key.hashCode());
//binCount = 0 ： 表示对应的桶位还没有放入过值，直接放入
//binCount = 2 ： 表示有可能是树形结构
//binCount为其他数字，有具体含义，下面会介绍
int binCount = 0;
//通过自旋方式放入值
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//表示是第一次放入值，表还没有进行初始化，则先进行初始化工作（初始化工作不是在构造函数中完成的，而是在第一次put的时候才进行）
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//cas获得所在桶位的头节点
//如果桶位的头结点为null，则可以尝试使用cas给头节点赋值（这里的put没有进行加锁）
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;
}
//如果当前节点的hash值为MOVED，表示当前节点为forwarding节点，表示散列表正在扩容，则尝试帮助其他线程扩容
else if ((fh = f.hash) == MOVED)
//尝试帮助扩容的方法，下面会详解
tab = helpTransfer(tab, f);
//到这说明当前节点为链表或者红黑树，则加锁put
else {
//记录下oldVal的值，如果有冲突，会把冲突的值写入到这个变量中，最后会return这个值
V oldVal = null;
//put操作对头节点加锁
synchronized (f) {
//判断当前的头节点是不是之前的头节点，有可能在这么多判断过程中，头节点已经被改动过
if (tabAt(tab, i) == f) {
//fh>=0 表示当前为链表节点
if (fh >= 0) {
//1 当前插入key与所有key都不一样时，即没有发生写冲突，把node插入到链表末尾，并且此时的binCount表示为链表长度
//2 如果发生写冲突 bincount-1表示冲突位置
binCount = 1;
//自旋
for (Node<K,V> e = f;; ++binCount) {
K ek;
//如果当前节点的hash和key与要插入节点的hash和key相同，说明有写冲突，把当前节点的value值赋值给oldValue
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek))))
oldVal = e.val;
//如果onlyIfAbsent的值为false，则将节点的值进行更新
if (!onlyIfAbsent)
e.val = value;
//跳出当前自旋
break;
}
Node<K,V> pred = e;
//如果当前节点为null，则把当前节点之前一个节点的next指向当前节点，跳出自旋
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//如果当前是TreeBin类型的，binCount设置为2
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
//调用putTreeVal方法进行插入，（putTreeVal大概的功能是如果有冲突，则返回那个冲突节点，如果没有冲突，则返回null）
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
//binCount!=0 则其有可能是链表或者红黑树
if (binCount != 0) {
//binCount >= TREEIFY_THRESHOLD肯定为链表，并且有可能会树化，调用树化的方法
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
//代表有冲突，则返回冲突的值，不需要进行扩容的判断
if (oldVal != null)
return oldVal;
break;
}
}
}
//没有冲突，则要把总节点数目+1，并且看现在是否要触发扩容
addCount(1L, binCount);
return null;
｝
ConcurrentHashMap初始化表的工作（当第一次put元素的时候会跳到此方法）
/**
* Initializes table, using the size recorded in sizeCtl.
* sizeCtl < 0
* 1. -1 表示当前table正在初始化，当前线程需要自旋等待..
* 2.其他负数表示当前table数组正在进行扩容 ,高16位表示：扩容的标识戳 低16位表示： 当前参与并发扩容的线程数量+1
* *
* sizeCtl = 0，表示创建table数组时 使用默认大小进行创建
* *
* sizeCtl > 0
* 1. 如果table未初始化，表示初始化大小
* 2. 如果table已经初始化，表示下次扩容时的 触发条件（阈值）
*/
private final Node<K,V>[] initTable() {
//sc表示局部的sizeCtl；
Node<K,V>[] tab; int sc;
//自旋，跳出自旋的条件是当前table已经进行初始化过
while ((tab = table) == null || tab.length == 0) {
//表示当前table正在初始化（有线程在创建table数组），当前线程需要自旋等待..
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
//cas设置sizeCtl的值为-1，如果设置成功，尝试进行初始化工作
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//在之前过程中，有其他线程已经完成了初始化工作（这种情况有可能发生）
if ((tab = table) == null || tab.length == 0) {
//n表示创建的表的大小，默认为16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
//sc表示下次要扩容的阀值 0.75n
sc = n - (n >>> 2);
}
} finally {
//1.如果当前线程是第一次创建map.table的线程话，sizeCtl表示的是下一次扩容的阈值
//2.表示当前线程 并不是第一次创建map.table的线程，当前线程进入到else if块时，将sizeCtl设置为了-1 ，
//那么这时需要将其修改为进入时的值本质还是下一次扩容的阀值。
sizeCtl = sc;
}
break;
}
}
return tab;
}
ConcurrentHashMap中TreeBin节点添加元素的方法
/**
* Finds or adds a node.
* @return null if added
*
* 注意：调用此方法时一定是处于加锁状态
* 1、自旋找到插入的位置
* 2、头插法 维护双向链表
* 3、将节点插入到红黑树中
* 尝试获取写锁（如果当前没有读线程，则cas将当前状态设置为写锁状态，如果当前有写锁，则尝试去竞争锁，如果竞争锁失败，将自己挂起，等待读线程唤醒）
* 获得了写锁，进行红黑树的调整，使他满足红黑树的特性
* 释放写锁
* （注意：如果插入失败，表示有写冲突，则返回null）
*/
final TreeNode<K,V> putTreeVal(int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//自旋查找要插入的位置
for (TreeNode<K,V> p = root;;) {
//dir为要往哪边查找，如果为-1，向左走，如果是1，向右走
int dir, ph; K pk;
// 设置头节点=根节点=新增的这个节点
if (p == null) {
first = root = new TreeNode<K,V>(h, k, v, null, null);
break;
}
//首先会根据hash值进行判断，如果插入节点的hash值大于当前节点的hash值，则往右走，反之往左走
else if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//如果当前2者hash值一样，并且key还是相同的，则返回当前节点
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
//如果2者的hash值相同，key不同，则先看其是否实现了Comparable接口，如果实现了则根据其compareTo方法返回dir
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//如果没有实现，则根据当前节点递归的向左，向右查找，在根据一定的排序规则进行dir的计算
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.findTreeNode(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.findTreeNode(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
//xp 想要表示的是 插入节点的 父节点
TreeNode<K,V> xp = p;
//如果插入节点的值为null，则进行插入工作
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//x表示插入节点，f表示修改链表之前的头结点
//先在链表中插入节点（头插法）
TreeNode<K,V> x, f = first;
first = x = new TreeNode<K,V>(h, k, v, f, xp);
if (f != null)
f.prev = x;
//往红黑树中插入数据
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//将父亲节点变色
if (!xp.red)
x.red = true;
else {
//尝试获取写锁
lockRoot();
try {
//调整红黑树使得红黑树平衡
root = balanceInsertion(root, x);
} finally {
//释放写锁
unlockRoot();
}
}
break;
}
}
//检查让root节点确保Wie红黑树的头节点
assert checkInvariants(root);
return null;
}
ConcurrentHashMap中TreeBin节点添加元素时候的写锁的获取和释放
首先看一下红黑树中关键的变量
//红黑树的根节点
TreeNode<K,V> root;
//链表的头结点
volatile TreeNode<K,V> first;
//等待线程（当前lockState为读锁状态）
volatile Thread waiter;
/**
* 1.写锁状态 写是独占状态，以散列表来看，真正进入到TreeBin中的写线程 同一时刻 只有一个线程。 1
* 2.读锁状态 读锁是共享，同一时刻可以有多个线程 同时进入到 TreeBin对象中获取数据。 每一个线程 都会给 lockStat + 4
* 3.等待者状态（写线程在等待），当TreeBin中有读线程目前正在读取数据时，写线程无法修改数据，那么就将lockState的最低2位 设置为 0b 10
*/
volatile int lockState;
// values for lockState
static final int WRITER = 1; // set while holding write lock
static final int WAITER = 2; // set when waiting for write lock
static final int READER = 4; // increment value for setting read lock
获取写锁和释放写锁
/**
* Acquires write lock for tree restructuring.
*/
private final void lockRoot() {
//尝试获取写锁，如果失败表示当前有读进程
if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
contendedLock(); // offload to separate method
}
/**
* 尝试去竞争写锁
*/
private final void contendedLock() {
boolean waiting = false;
//自旋
for (int s;;) {
//条件成立：说明目前TreeBin中没有读线程在访问红黑树
if (((s = lockState) & ~WAITER) == 0) {
//cas设置当前为写状态
if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
//如果当前为等待状态，将等待状态消除
if (waiting)
waiter = null; //helpGc
return;
}
}
//当前没有wait线程，则将其设置为waiter线程，将等待位设置true
else if ((s & WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
waiting = true;
waiter = Thread.currentThread();
}
}
//如果连续2次失败，则挂起当前线程，等待读线程唤醒
else if (waiting)
LockSupport.park(this);
}
}
/**
* Releases write lock for tree restructuring.
*/
private final void unlockRoot() {
lockState = 0;
｝
