- 新增
public boolean add(E e) {
//检查是否需要扩容,如果需要，就扩容为Math.max(DEFAULT_CAPACITY, size + 1)
ensureCapacityInternal(size + 1);
//讨巧的写法，size++就是当前size，新增的元素下标等于新增前的size
elementData[size++] = e;
return true;
}
//检查是否需要扩容,如果需要，就扩容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//获取需要的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//这里对应了之前说的为什么有两个空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//如果需要的容量大于当前数组长度，就扩容
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//新容量不小于原始容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//创建指定长度新数组并将老数组拷贝到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 删除
//删除指定下标的元素并返回它
public E remove(int index) {
E oldValue = elementData(index);
//需要移动的元素数量，如果删除的不是末尾的元素，该值会大于0
int numMoved = size - index - 1;
if (numMoved > 0)
//直接覆盖执行段的元素
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//移除末尾元素，如果删除的是末尾，没啥好说的，如果删除的是中间，这个值已经前移了一位
elementData[--size] = null;
return oldValue;
}
//移除指定元素
public boolean remove(Object o) {
//逻辑很简单，就是for循环，找到这个元素并删除它
//并非完全循环elementData，而是循环实际大小，减少计算
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//fastRemove与remove(int index)区别不大，只是不返回元素值
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
- 批量删除
//只保留当前列表与c的交集
public boolean retainAll(Collection c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
//批量删除c中的元素
public boolean removeAll(Collection c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
//可以看到两个方法都是调用的该方法
//如果complement为true，删除c中不存在的值，否则删除c中存在的值
private boolean batchRemove(Collection c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
//循环当前列表，如果循环中item在c中出现并且等于complement，当前列表新增item
//这里还是比较巧妙的
//如果调用者为retainAll，可以看作保留c中存在的值，如果存在=true=complement，那么保留该值
//如果调用者为removeAll,可以看作保留c中不存在......
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// even if c.contains() throws.
if (r != size) {
//只考虑单线程，如果r != size说明try异常，把异常后的元素直接拷贝到保留的元素后
System.arraycopy(elementData, r, elementData, w,size - r);
w += size - r;
}
if (w != size) {
//说明的确移除了一些元素，那么需要删除w后面的元素，因为w和w之前已经是需要保留的全部元素了
for (int i = w; i < size; i++)
elementData[i] = null;
size = w;
modified = true;
}
}
return modified;
}
linkedList
- 节点类型
private static class Node{ E item; Node next; Node prev; }
- 新增
新增方法不少，最终调用的方法都是linkLast或者linkFirst或者linkBefore
//新增元素到末尾
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
//当前节点赋值给尾节点
last = newNode;
//如果原last为null，说明之前就没有任何值，当前节点赋值给头节点
if (l == null)
first = newNode;
else
//如果之前的last不为null，维护双向链表
l.next = newNode;
size++;
}
//新增元素到头部，逻辑与linkLast区别不大
private void linkFirst(E e) {
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}
//新增元素到指定下标
public void add(int index, E element) {
linkBefore(element, node(index));
}
//返回index下标的节点，如果要找的节点靠近尾部就倒着遍历，这也可以解释为什么使用双向链表
Node node(int index) {
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//新增到某个节点前面
void linkBefore(E e, Node succ) {
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
}
HashMap
- 构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;
//可以看到扩容门槛已经确定了
this.threshold = tableSizeFor(initialCapacity);
}
//返回大于等于cap并最接近cap的2的n次方，上限为MAXIMUM_CAPACITY
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
- 节点类型
//链表节点，可以看到是典型的单向链表，存储的hash并非是hashcode，而是由hash方法生成的
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
}
//红黑树节点
static final class TreeNode extends linkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
}
- 新增
public V put(K key, V value) {
//散列算法暂时不管，理解为生成一个尽可能均匀分布的值即可
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//onlyIfAbsent如果为true，只新增不替换
//evict暂时不管它
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
//如果table为空
if ((tab = table) == null || (n = tab.length) == 0)
//扩容
n = (tab = resize()).length;
//如果计算出的桶子不存在，初始化桶子，并将元素放置到桶子的头节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//到了这里桶子已经初始化过
Node e; K k;
//这里p.hash == hash没太理解，理论上永远是true
//如果头部节点key与插入key相同，就是这个节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果桶子里是树节点，插入红黑树
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
else {
//说明桶子里不是树节点，是链表，遍历链表
for (int binCount = 0; ; ++binCount) {
//找到了链表尾部，说明这个key不存在，得新增
if ((e = p.next) == null) {
//插入链表
p.next = newNode(hash, key, value, null);
//链表长度达到了TREEIFY_THRESHOLD ，树化
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//如果找到了相同key，保存这个节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//e就是相同key的节点，如果e不存在，那么上面已经进行了新增
if (e != null) {
//e如果存在，根据是否替换进行操作
//这里可以看到，null的话是直接替换的，不受onlyIfAbsent影响
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//如果执行的是替换操作，那么直接返回就好了
return oldValue;
}
}
//如果容量达到了扩容门槛，执行扩容
if (++size > threshold)
resize();
return null;
}
//扩容
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
//新容量，新扩容门槛
int newCap, newThr = 0;
if (oldCap > 0) {
//极值判断
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//正常情况，形容量为旧容量的二倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//这里说明刚刚初始化完成，新容量等于扩容门槛
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//这里说明刚刚初始化完成，且使用的无参构造方法，容量为默认值DEFAULT_INITIAL_CAPACITY
newCap = DEFAULT_INITIAL_CAPACITY;
//扩容门槛的计算如下 这里是初始化扩容门槛
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//非初始化扩容门槛计算
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//table初始化
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
//如果之前table不为空，搬运元素
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
// 如果桶子头节点不为空，赋值给e
oldTab[j] = null;
if (e.next == null)
//如果该桶就e一个独苗，把e放进新table
//为何e不会被后面覆盖
//因为这里用的与运算，e的hash不同e.hash & (newCap - 1)也不会相同
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果是树节点，对树节点进行拆分
//这里结合hash和与运算理解,运算目标是永远为2的n次方的容量-1
//现在容量多了一位,会被拆分为两个（运气差的话一个也有可能）
//但是实现用到了红黑树，不展开了
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
//到了这里就是链表了
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
//同样的思路，容量不减一与运算其实就是原值高一位的值，据此进行拆分
//这个循环也很简单，就是根据这一位拆分为loHead、hiHead两个链表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//如果n位是1，减一位与2的n次方减一进行与运算，和不减差值即为2的n次方
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
//树化
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
//可以看到，如果容量没达到MIN_TREEIFY_CAPACITY，是先扩容的
//至于扩容之后是否树化，就看运算后是否出现该桶是否达到树化门槛了，对应split方法
//上面一行是想象的，可实际并非如此，扩容代码里链表是不会变成红黑树的
//也就是说极端情况下初始化容量为16扩容两次才会出现树化，链表可以存在的最大长度为10
//10这个数字应该是准确的，我验证了以下 最终最大链表长度 实时长度应该为11未验证
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode hd = null, tl = null;
do {
TreeNode p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
- 删除
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//删除并返回元素
//matchValue:如果为true，value也得匹配才给删
//movable为红黑树相关操作，忽略
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
//判断是否存在对应的桶（找到头节点）
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//头节点就是要找的节点，省事了
node = p;
else if ((e = p.next) != null) {
//头节点不是要找的节点，判断是树还是链表，然后对应查找
if (p instanceof TreeNode)
node = ((TreeNode)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//如果找到了，根据matchValue判断是否可以删除值
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//可以删除，判断是树还是链表，然后对应删除
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
else if (node == p)
//如果是链表节点的头节点，直接替换头节点为后续节点
tab[index] = node.next;
else
//不是头节点，p在链表循环中被一直重置，直到删除节点前置节点，替换其后置节点即可
p.next = node.next;
--size;
return node;
}
}
return null;
}
- 验证最大链表长度
public class CollTest {
@Override
public int hashCode() {
return 1;
}
@Override
public boolean equals(Object obj) {
return false;
}
@Override
public String toString() {
return "CollTest{" +
"a=" + a +
'}';
}
@Test
public void test9() throws NoSuchFieldException, IllegalAccessException {
HashMap map = new HashMap();
for (int i =0; i<=9;i++){
map.put(new CollTest(),null);
}
Field table = HashMap.class.getDeclaredField("table");
table.setAccessible(true);
Object mapTable = table.get(map);
List list = null;
if(mapTable.getClass().isArray()){
list = new ArrayList();
int length = Array.getLength(mapTable);
for(int i=0;i
CopyonWriteArrayList
- 基本方法
//初始化时创建数组
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
//获取数组，什么都没做，直接返回
final Object[] getArray() {
return array;
}
//赋值数组，什么都没做，直接赋值
final void setArray(Object[] a) {
array = a;
}
- 新增
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//复制新数组，长度+1
Object[] newElements = Arrays.copyOf(elements, len + 1);
//新增的元素赋值到末尾
newElements[len] = e;
//替换数组，可以看到这里不加锁可能出现两个线程同时获取到了相同的旧数组
//然后分别创建+1长度的数组替换，最终元素就会少一个
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
- 修改
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
E oldValue = get(elements, index);
if (oldValue != element) {
//如果新值与旧值不同，赋值数组修改新数组指定下标元素，再把新数组换上去
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements[index] = element;
setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
//完全没有修改也得set一下，好多鱼，这里没看出任何意义来
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
- 删除
public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
//需要移动的元素数量，这个值再ArrayList也出现过=.=
int numMoved = len - index - 1;
if (numMoved == 0)
//没有元素需要移动，说明删除的是末尾元素，直接从开头到末尾减一位复制元素即可
setArray(Arrays.copyOf(elements, len - 1));
else {
//删除中间的元素，复制开头到指定下标前的元素，再复制指定下标后到末尾的元素
//说白了，复制的时候把要删除的元素空过去了
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}
ConcurrentHashMap
- 构造方法
public ConcurrentHashMap() {
//这里和HashMap相比没有负债因子赋值为默认值了
}
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
- 节点类型
static final class ForwardingNode extends Node {
//该节点类型为转发节点，扩容迁移中如果旧桶数组被迁移，会在远处放置一个该节点,转发到nextTable新桶数组
//实现上是直接调用find方法
final Node[] nextTable;
ForwardingNode(Node[] tab) {
//该类型节点hash为MOVED -1
super(MOVED, null, null, null);
this.nextTable = tab;
}
//查找方法
Node find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
//有见过这种写法吗，用来跳出外层循环，也可以break
outer: for (Node[] tab = nextTable;;) {
Node e; int n;
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
//新table也没有值，返回
return null;
for (;;) {
int eh; K ek;
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
//如果头节点就是要找的节点，直接返回
return e;
if (eh < 0) {
//eh < 0又是特殊节点
if (e instanceof ForwardingNode) {
//又遇到了转发节点
tab = ((ForwardingNode)e).nextTable;
continue outer;
}
else
//既然不是转发节点，那特殊节点就只有保留节点或者树代理节点了，直接调用find
return e.find(h, k);
}
if ((e = e.next) == null)
return null;
}
}
}
}
//红黑树代理节点，不做任何说明了，按照红黑树节点的安全版本理解就好，hash为TREEBIN -2
static final class TreeBin extends Node {
}
//保留节点，就是占个位置，因为null节点不能加锁
//这个类没看出来有什么存在的必要，感觉不如一直cas了，不过它不重要，跳过
static final class ReservationNode extends Node {
ReservationNode() {
//该类型节点hash为RESERVED
super(RESERVED, null, null, null);
}
Node find(int h, Object k) {
return null;
}
}
- 新增
public V put(K key, V value) {
return putVal(key, value, false);
}
//onlyIfAbsent与HashMap没有区别，如果为true，只新增不替换
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//这里hash方法变为了spread，同样的理解为生成一个均匀分布的值即可
int hash = spread(key.hashCode());
//目标桶元素个数
int binCount = 0;
for (Node[] tab = table;;) {
Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
//如果桶子数组还未初始化，初始化数组
tab = initTable();
//这里获取桶子头节点使用了tabAt,与直接获取相比增加了可见性语义（类比volatile）
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//桶数组初始化了，但是桶子不存在（没有头节点）
//创建链表节点并cas数组，成功了跳出循环，新增操作也就完成了
//如果cas失败，说明已经存在头节点了，循环，而且下次不走这里了走下面的逻辑
if (casTabAt(tab, i, null,
new Node(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) {
//这段代码与HashMap类似，不再重复说明，只是把树化的代码放到了后面
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node 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 pred = e;
if ((e = e.next) == null) {
pred.next = new Node(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node p;
//可以看到，如果是树节点binCount始终为2，不会重复树化
binCount = 2;
if ((p = ((TreeBin)f).putTreeval(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//达到树化门槛，树化
//试一下的话可以发现可存在的最终最大链表长度为9 实时为10
if (binCount >= TREEIFY_THRESHOLD)
//这里要注意，treeifyBin之后table可以变为8倍，并不是网上说的始终变为二倍
//以上为观察发现，可以试一下，本次不讨论该问题，不展开具体方法
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//这里数量+1，可以看到如果没有新增上面就return了
addCount(1L, binCount);
return null;
}
初始化桶数组，走到这里说明执行的是
private final Node[] initTable() {
Node[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
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[] nt = (Node[])new Node[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
增加完元素以后 更新元素数量 检查是否需要扩容的方法
//增加容量 检查是否需要扩容
private final void addCount(long x, int check) {
//这里出现了CounterCell[]这种并发计数结构，Adder中也有类似的实现比如LongAdder
CounterCell[] as; long b, s;
//尝试cas baseCount(数量)
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, baseCOUNT, b = baseCount, s = b + x)) {
//如果counterCells已经初始化并且cas baseCount失败
CounterCell a; long v; int m;
boolean uncontended = true;
//如果CounterCell[]未初始化或者根据当前线程计算出数组下标的位置是空的或者不是空的但是cas该下标失败
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就是总数量了，等于基础数量加上cell数组存的值
s = sumCount();
}
if (check >= 0) {
Node[] tab, nt; int n, sc;
//如果容量达到了扩容门槛sizeCtl（正常情况下存储扩容门槛），且可扩容
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
//获取一个邮戳，意义是标记本轮扩容,n不同则rs不同
//rs=Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS=16 - 1));
//numberOfLeadingZeros：返回int从最高位向左最大连续0数量 n为16的话 10000 32-5=27
//1左移15位 16位是1 其余都是0
//或运算以后第16位为1，低15位值等于27
int rs = resizeStamp(n);
//sc也就是sizeCtl如果小于0，说明正在扩容
if (sc < 0) {
//(sc >>> RESIZE_STAMP_SHIFT) != rs 无符号右移16位，如果不等于rs说明n（容量不同）轮次戳不同，不能重复进行扩容 这里可以思考sc如何推出rs的
//sc == rs + 1 不可能，这里rs高15位都是0而sc符号位是1
//sc == rs + MAX_RESIZERS 不可能，rs高15位都是0而sc符号位是1，MAX_RESIZERS 高15位都是0，怎么加也倒不了sc
//nextTable为null 成立说明扩容结束
//transferIndex成立说明迁移任务分发完成了，当前没有迁移任务了
//关于迁移任务，每个迁移任务包含16个桶，从后往前迁移分发
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))
//既然上面没有break说明扩容未结束 sc保存了基数+线程数 成功cas了sc 可以加入扩容
transfer(tab, nt);
}
//这里可以看到sc也就是sizeCtl小于0是怎么来的
//上面知道了rs的结构，rs左移16位，因为rs之前16位是1，相当于左移了31位，符号位为1，此时为int最小值
//因为低15位必然不为0，rs低15位存储容量最高位连续0数量，现在这个数字到了高16位
//那么此时低16位的值为2，就是线程数量
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
//sizeCtl = (rs << 16) + 1 + nThreads
//rs左移后+2，高16位为轮次戳，低16位为2，代表扩容进行中且线程数为1
//cas获取任务成功，开始干活
transfer(tab, null);
s = sumCount();
}
}
}
这里单独把fullAddCount拿出来分析，因为相同的模式在其他模块比如累加器也有用到，还是不跳过了
//新增数量到cell[]
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
//如果探针为0，初始化探针，其实就是随机生成，因为到了这里必然是存在竞争，再用0不好
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;
//如果cell数组已被初始化
if ((as = counterCells) != null && (n = as.length) > 0) {
//如果对应下标没有值 需要本线程去尝试创建cell
if ((a = as[(n - 1) & h]) == null) {
//cellsBusy=0表示counterCells不在初始化或者扩容状态下
if (cellsBusy == 0) { // Try to attach new Cell
CounterCell r = new CounterCell(x); // Optimistic create
//cas cellsBusy
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
//当前线程获取cell初始化权
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) {
//如果对应的下标还是为null，创建cell并放到那里
//这里里面还得再判断一次为null，因为上面判断下标为空和cas创建权并不是原子操作也没加锁
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
//到这里说明对应下标cell已经存在，且竞争激烈（调用当前方法那里cas尝试过一次），标记一下
wasUncontended = true; // Continue after rehash
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
//到这里说明对应下标cell已经存在，竞争未必激烈，再给它一次机会，成功了就很fine
break;
//这个判断如果成立，就说明counterCells被重置了，呵呵，竞争很激烈
//接下来的两个判断限制继续往下争抢的线程数量不大于cpu
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)) {
//尝试获取cell数组初始化权成功，准备扩容，因为上面可以看出来，竞争激烈的很
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);
}
//上面那一大坨都是存在cell数组的逻辑，如果不存在，那就初始化数组
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;
}
//这里传统工艺，使用cell模式失利，尝试一下修改基础数量
else if (U.compareAndSwapLong(this, baseCOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
树化方法
//与HashMap类似，但执行结果...
private final void treeifyBin(Node[] tab, int index) {
Node b; int n, sc;
if (tab != null) {
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 hd = null, tl = null;
for (Node e = b; e != null; e = e.next) {
TreeNode p =
new TreeNode(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(hd));
}
}
}
}
}
//尝试扩容
private final void tryPresize(int size) {
//这个c最终结果位size 的1.5倍+1后大于等于最接近的2的n次方
//如果size=32，那么n=32*1.5+1=49上面的64
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
//sc大于等于0说明当前不在扩容状态 sc存储的是扩容门槛或者初始化容量
while ((sc = sizeCtl) >= 0) {
Node[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {
//如果桶数组尚未初始化，那么尝试初始化，这时sc为初始化容量
//取目标容量与上面计算的c中较大值
n = (sc > c) ? sc : c;
//cas获取桶数组的初始化权
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//如果在这期间table没有被替换 严谨
if (table == tab) {
//初始化一个容量为n的桶数组，并把下次扩容门槛改为当前容量的0.75倍
Node[] nt = (Node[])new Node[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
//如果c比扩容门槛还要小或者当前容量达到极值，前者说明这期间其他线程扩容了，后者没法扩容了
break;
else if (tab == table) {
//能走到这里说明桶数组已经初始化了且容量可以执行扩容，rs前面讲过了，不谈
int rs = resizeStamp(n);
if (sc < 0) {
//说明当前正在扩容
Node[] nt;
//这几个条件上面都讲过，一样的意思，不谈
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))
//cas尝试加入扩容大军成功，执行扩容
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
//成功把sc状态cas为扩容并把自己加到了扩容大军中，执行扩容
transfer(tab, null);
}
}
}
- 查询
public V get(Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
//获取hash
int h = spread(key.hashCode());
//判断桶子是否存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
//头节点就是要找的节点
return e.val;
}
else if (eh < 0)
//特殊节点，调用节点的find方法
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
//链表节点
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
