ConcurrentHashMap由数组+链表+红黑树组成
数组中存放的是链表的头结点，或者红黑树的根节点
如果头节点是Node类型，它后面的的就是一个普通的链表;如果头节点是TreeNode类型，它的后面就是一颗红黑树，TreeNode是Node的子类
链表和红黑树之间可以相互转换:初始的时候是链表，当链表中的元素超过某个阈值时，把链表转换成红黑树;当红黑树中的元素个数小于某个阈值时，再转换为链表。
构造方法
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
//参数校验
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
//如果初始化大小小于并发级别，设置初始化大小等于并发级别
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
//根据initialCapacity算size
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
//根据size算数组长度，cap为2的整数次方
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
cap就是Node数组的长度，保持为2的整数次方。tableSizeFor(…)方法是根 据传入的初始容量，计算出一个合适的数组长度。具体而言:1.5倍的初始容量+1，再往上取最接近的2 的整数次方，作为数组长度cap的初始值。
sizeCtl是用于控制在初始化或者并发扩容时候的线程数，只不过其初始值设置成 cap。
初始化
在上面的构造方法里只计算了数组的初始大小，并没有对数组进行初始化。当多个线程都往里面放入元素的时候，再进行初始化。这就存在一个问题:多个线程重复初始化。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//判断是否被初始化了
while ((tab = table) == null || tab.length == 0) {
//如果sizeCtl<0则自旋等待
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) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
//初始化数组
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
//sizeCtl=sc是下次扩容的阈值，n - (n >>> 2)=0.75n
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
put方法
public V put(K key, V value) {
//调用putVal(K key, V value, boolean onlyIfAbsent)方法
//onlyIfAbsent为ture时表示只有key在map不存在的时候，才往里面放，false不管存不存在都往里面放
return putVal(key, value, false);
}
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)
tab = initTable();
//如果头元素为空，则这个元素成为这个槽位的第一个Node
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
}
//正在扩容，帮助其扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//放入元素，槽内可能是一个链表，也可能是一棵红黑树，通过头节点的类型 可以判断是哪一种。
else {
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;
}
}
}
}
//一开始定义了binCount=0，并且在链表中binCount会一直+1来计数
if (binCount != 0) {
超出阈值，转换为红黑树，和扩容操作，TREEIFY_THRESHOLD=8
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 总元素个数累加1
addCount(1L, binCount);
return null;
}
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
// 数组长度小于阈值64，不做红黑树转换，直接扩容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
//链表变为红黑树
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));
}
}
}
}
}
当链表长度超过8的时候，链表会尝试转变为红黑树，但是如果此时数组长度没有超过64，则只会进行数组的扩容，只有当数组长度大于或等于64时，才考虑把链表 转换成红黑树。