1 CountDownLatch
The utility model relates to a disposable baffle. After the thread reaches the baffle, it will be blocked. Until all relevant threads reach the baffle, all threads will wake up at the same time and then execute down.
The source code is very simple.
2 CyclicBarrier
A CountDownLatch that can loop is in the code. After the loop is completed, the number of times to allow all threads to wake up can be specified, and then the loop can be completed.
The source code is relatively simple.
3 ConcurrentHashMap
Basically, it is very similar to HashMap. I have seen the put method source code of HashMap before. Here, I only look at the concurrency part, and I will also mention some.
3.1 algorithm and data structure
3.1.1 HashTable
Is an array of elements. Each array is composed of a linked list of elements.
Calculate the hash value of the element, and then calculate the hash value to obtain the subscript of the element in the array (generally by calculating the remainder, and the divisor is generally the length of the array).
After getting the array subscript, traverse the linked list to store the elements. If the hash value already exists, the element is overwritten (this is a hash collision, also known as hash collision).
3.1.2 HashMap
It is an optimization of hashTable: 1 Arrays can be expanded. 2. When the number of elements in the linked list reaches a certain number, it will be transformed into a red black tree, and when the number of elements is less than a certain number, it will become a linked list.
3.1.3 ConcurrentHashMap
It is an optimization of HashMap. Use separate locks, that is, each linked list or red black tree is a lock. This is a small optimization.
3.2 important methods putVal and putTreeVal
As like as two peas in HashMap, except for the use of separate locks just now, that is, each linked list or red black tree is a lock. This is a small optimization.
Here we only mention why the root node of the tree should be locked when balancing the tree? Why is the linked list always unlocked?
/** 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)
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;
}
/**
* Finds or adds a node.
* @return null if added
*/
final TreeNode<K,V> putTreeVal(int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if (p == null) {
first = root = new TreeNode<K,V>(h, k, v, null, null);
break;
}
else if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
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);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
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;
}
}
assert checkInvariants(root);
return null;
}