1.sizeCtl
- 等于0时,表示数组还没有进行初始化(即数组为null)
- 大于0时,如果数组还没有进行初始化,表示数组的长度,如果数组已经完成初始化,表示扩容的阈值
- 小于0时,如果为-1,表示正在数组初始化,否则设该值x = - (1 + n) 那么有n个线程在协助扩容
2.initTable
- 如果table==null ,再判断sizeCtl是否为-1,如果是则调用
Thread.yeild()重新回到就绪态
- 否则通过cas将sizeCtl设置为-1,并初始化数组,将sc设为扩容阈值
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
／／ 如果 sizeCtl < 0 ,说明另外的线程执行CAS 成功，正在进行初始化。
if ((sc = sizeCtl) < 0)
// 让出 CPU 使用权
Thread.yield(); // lost initialization race; just spin
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;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
3. putVal()
- key == null || value == null 抛出异常
- 数组没有进行初始化,则进行初始化
- 如果对应桶没有存放元素,使用cas来new一个Node,并赋新值
- 如果桶中第一个元素的hash值为-1,表示正在扩容,当前线程回去协助扩容
- 否则对桶中的第一个元素作为synchronized对象锁.
判断如果是链表(元素哈希值大于0),则遍历链表,如果遇到f的hash值相等,且使用==判断相等的元素或equals等,则替换value,并break.否则该元素是新的,则向最后插入.
如果是红黑树则调用红黑树的插入方法.
- 判断是否需要将链表转为红黑树
- 调用addCount处理当前Node的个数和是否需要扩容
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();
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;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
4. 计算元素个数count
- 每个线程有一个随机值,类似与hashCode
- 数组如果为空，设置cellsBusy=0,new一个长度为2的数据，new里面的Cell对象
- 如果数组为空，判断数组是否在被创建（cellsBusy=1），这时另一个线程来了，数组为空，且busy,那么使用cas加baseCount,加成功则结束
- 数组不为空，判断哈希值&（len-1）对应的位置有没有对象，没有则创建CounterCell对象，参数即为传入的1。如果成功cas将忙由0改为1，那么会将数组中的对应位置赋值
- 如果有对象，则cas加1，如果cas失败，将会触发扩容为2倍，如果数组长度大于等于cpu核数，如果不能继续扩容了，换个位置加。
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
if ((as = counterCells) != null && (n = as.length) > 0) {
if ((a = as[(n - 1) & h]) == null) {
if (cellsBusy == 0) { // Try to attach new Cell
CounterCell r = new CounterCell(x); // Optimistic create
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
rs[j] = r;
created = true;
}
} finally {
cellsBusy = 0;
}
if (created)
break;
continue; // Slot is now non-empty
}
}
collide = false;
}
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;
else if (counterCells != as || n >= NCPU)
collide = false; // At max size or stale
else if (!collide)
collide = true;
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
if (counterCells == as) {// Expand table unless stale
CounterCell[] rs = new CounterCell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
counterCells = rs;
}
} finally {
cellsBusy = 0;
}
collide = false;
continue; // Retry with expanded table
}
h = ThreadLocalRandom.advanceProbe(h);
}
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0;
}
if (init)
break;
}
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
5. transfer
- 判断每个线程负责多少个桶,如果单核cpu,负责所有桶.否则计算原数组长度len/(8*cpu核数),如果小于16,则为16,否则为该值
- 一个线程负责这些桶,如果做完了,继续做,做之前让sizectl+1,做完了让sizectl-1,最后判断两个相等则结束.
- 一个线程对一个桶迁移时,会使用桶的第一个元素加锁,第一次遍历会找到链表末尾,对于hash后还在原来index的连续的末尾的元素,直接放到新数组的位置,其余的复制到两个对应位置.
