ConcurrentHashMap#Put
ConcurrentHashMap#Put
put
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
//分支1:整个数组初始化
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//分支2:第[i]个元素初始化
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)
//分支3:扩容
tab = helpTransfer(tab, f);
else {
//分支4:放入元素
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
//放入链表
binCount = 1;
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) {
//如果是链表，binCount会一直累加
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);// 超过阀值，转为红黑树
if (oldVal != null)
return oldVal;
break;
}
}
}
//总元素个数累加
addCount(1L, binCount);
return null;
}过程如下：
1，tab未初始化则初始化table
2，两次hash，减少hash冲突，并计算下标
3，数组该位置为空，无碰撞，通过CAS插入
4，有碰撞
4.1、如果正在扩容，协助其它线程去扩容
4.2、如果是链表，插入链表
4.3、如果是红黑树，插入红黑树
4.4、如果链表长度超过8，转为红黑树
4.5，如果key已经存在，覆盖旧值
5，总元素个数累加，需要扩容，则扩容其余分支我们后面可以细讲，现在简略讲下分支2，它使用cas无锁模式将元素添加到空桶，代码如下：
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {找该 hash 值对应的数组下标，得到第一个节点 f，使用tabAt方法：
@SuppressWarnings("unchecked")
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);
}其中U.getObjectVolatile获取obj对象中offset偏移地址对应的object型field的值,支持volatile load语义。
volatile访问方法可用于访问表元素以及扩容中的next表的元素。 tab的使用必须由调用方进行非空检查。 所有调用者还预先检查tab的长度是否不为零（或其他等效检查），从而确保任何（length-1） & hash参数都是有效索引。 请注意，要纠正用户的并发错误，这些检查必须对局部变量进行操作。
如果数组该位置为空，用一次 CAS 操作将这个新值放入其中，跳出循环，如果 CAS 失败，那就是有并发操作，进到下一次循环，用了casTabAt方法：
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}compareAndSwapObject：
public final native boolean
compareAndSwapObject(Object var1, long var2, Object
var4, Object var5);compareAndSwapObject方法中的第一个参数和第二个参数，用于确定待操作对象在内存中的具体位置的，然后取出值和第三个参数进行比较，如果相等，则将内存中的值更新为第四个参数的值，同时返回true，表明原子更新操作完毕。反之则不更新内存中的值，同时返回false，表明原子操作失败。
这里涉及的Java Cas的特性，请看下图：
CAS，Compare and Swap 即比较并交换，设计并发算法时常用到的一种技术，java.util.concurrent 包建立在 CAS 之上。
当前的处理器基本都支持 CAS，但不同的厂家的实现不一样。
CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。 如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值 。否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该 位置的值。
利用CPU的CAS指令，同时借助JNI来完成Java的非阻塞算法。其它原子操作都是利用类似的特性完成的。而整个J.U.C都是建立在CAS之上的，因此对于synchronized阻塞算法，J.U.C在性能上有了很大的提升。
再看第四分支synchronized部分的锁代码。
其他更新操作（insert，delete和replace）需要锁。我们不想浪费空间，将不同锁对象与每个bin关联, 所以应该使用bin列表的第一个节点本身作为锁。对这些锁的锁定支持依赖于内置的“同步”监视器。
但是，将列表的第一个节点用作锁本身是不够的:当一个节点被锁定时，任何更新必须首先验证它仍然是锁定后的第一个节点，如果不是，则重试。因为新节点总是被附加到列表中，所以一旦一个节点在一个bin中是第一个节点，它就一直是第一个节点，直到删除或bin失效(通过扩缩容)。
每个bin锁的主要缺点是，受相同锁保护的bin列表中其他节点上的其他更新操作可能会暂停，例如，用户 equals（）或映射方法需要很长时间。 但是，从统计学上讲，在随机哈希码下，这不是一个普遍的问题。 理想情况下，bin中节点的频率遵循泊松分布。
如果 hash 计算的结果离散好的话，因为各个值都均匀分布，很少出现链表很长的情况，红黑树这种形式也很少会被用到的。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006，小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。
* Ideally, the frequency of nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average, given the resizing threshold
* of 0.75, although with a large variance because of resizing
* granularity. Ignoring variance, the expected occurrences of
* list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The
* first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
腾讯云开发者
