-
Notifications
You must be signed in to change notification settings - Fork 0
ConcurrentHashMap
The ConcurrentHashMap in Java1.8 which present algorithms for shrinking and expanding allowing relatively efficient concurrency. Let's explore it!
public V put(K key, V value) {
return putVal(key, value, false);
}
The third argument is 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[] tab = table;;) {
Node 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(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 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;
if ((p = ((TreeBin)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;
}
As the name implies, if onlyIfAbsent is true, then the operation only works if the value is missing. at first, if key == null or value == null, this operation is over(throw new NullPointerException()). then, the key and value must be nonNull, so get it's hashCode, we see:
int hash = spread(key.hashCode());
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
static final int HASH_BITS = 0x7fffffff;
I think the purpose is to get a hash that can make the distribution evenly, 31 bits.
int binCount = 0;
This variable is used to count the number of elements required for the iteration to complete the operation. The next step is a large for loop!
for (Node[] tab = table;;) {
Node 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(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 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;
if ((p = ((TreeBin)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;
}
}
}
Let's take a closer look at it .
Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
first, if tab is not properly initilized. You must first initialize it.
Let's see:
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;
}
Place the condition in the while loop, and we take the sizeCtl to control this process. when first thread into initTable,then it convert sizeCtl to a negative number(-1), then carry out its real work. and the second/third/fourth threads..will yield directly or begin to yield after the failure of the competition. And the most important is that other threads will just Waiting for the only thread until it completes the task... the only thread Locked the work of other threads. when the only thread complete its work, it set the table, and set the sizeCtl, note that the value of sizeCtl is three quarters of the current table length. then it back to the outer for loop, and take a loop again.
so we keep looking at this loop:
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
}
now, we have initlize the table properly, so we can take the entry from the table array. we just take the hash value & the (length - 1)(a perfect all-bit-in-1 value), thus get the corresponding slot. We first deal with the null logic(After all if it is null, then we have no more things to do, the principle here should be simple things put in front). We put our new key, the new value, the new hash into the table i position through CAS operation(It can correctly handle several CAS competition conditions based on the return value). if success, we done.
else it take a loop again, and it will get a Node(key/value). so let's we look at the third case:
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
the helpTransfer logic is a big one, so let's skip it now ,and then back to look at it closely. the fourth case:
else {
V oldVal = null;
synchronized (f) {
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;
if ((p = ((TreeBin)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;
}
}
we first lock the node f, and then verify that the current location is f ? if no, we just exit and take a loop again. if it's true, this node has been locked by us. the next step is we must put the key/value into the slot(datastrucs). ConcurrentHashMap divides the node into two categories, linked list nodes, and non-linked nodes. The linked list nodes' hashCode is greater than or equal to 0(because the value is get from &HASH_BITS(0x7fffffff)). The non-linked list nodes' hashCode is less than 0, and its' value is fixed(MOVED(-1) for forwarding nodes TREEBIN(-2) for roots of trees RESERVED(-3) for transient reservations ).
We track this list to see if there is a match with the entry entry, or to the tail node.
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;
}
}
}
if has a match, wo update the value according to the onlyIfAbsent variable. else we just add a node to the list tail, and it become the tail node.
both case, the putVal operation has done(break).
let's see the other case, the slot node is TREEBIN, this means that the nodes has been contructed into a tree