Let's not fight bald old today. Recharge ourselves and fight bald old again in the future!
Note: the concurrent HashMap chat is after 1.8!
Brothers and sisters all say that HashMap thread is not safe. If you want thread safety, use ConcurrentHashMap. Then why is it thread safe? Ah? Why? Don't think about it. It must look like it from the put() method! Please come out for a walk, brother!
// Ouch, it's old. Like HashMap, putVal method is called
public V put(K key, V value) {
return putVal(key, value, false);
}
// Ouch, the final modification method is not allowed to be rewritten. It seems very confident!
final V putVal(K key, V value, boolean onlyIfAbsent) {
// Check that the passed value is not null
if (key == null || value == null) throw new NullPointerException();
// Find the hash value through the hashcode of the key, that is, the location of the element
int hash = spread(key.hashCode());
int binCount = 0;
// Traversal table
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// Determine whether initialization is required
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// If the current position to be put is empty, it is put in through cas + spin without locking, and the loop will jump out after success
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
}
// Need to expand capacity
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// Here comes the big play. Ouch, it's locked
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
// Description is a linked list. Elements are added through a linked list
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) {
// Red black tree, add elements by tree
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) {
// Determine whether to convert to red black tree
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
To sum up, it is locked! Briefly describe:
1: Find the position where the key should be placed through hashcode
2: Whether it has been initialized. If not, call initTable()
3: Whether the value of the current position is empty. If it is empty, add elements through CAS optimistic lock (brother, don't panic, CAS will be said later)
4: Determine whether capacity expansion is required
5: Add synchronized to add elements. If it is a linked list, traverse the linked list to add elements. If it is a red black tree, call the method of adding elements in the red black tree!
Now that we know why threads are safe, let's take a look at the initTable() method. We can't be fooled and lose!
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// Initialization required
while ((tab = table) == null || tab.length == 0) {
// sizeCtl is old
// If = - 1, another thread is initializing,
// -N indicates that N-1 threads are expanding
// >0 represents capacity
if ((sc = sizeCtl) < 0)
// Since there are other threads initializing, let's be polite!
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {// Determine whether to initialize through CAS! (CAS again, curious!)
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 {
// Assign the capacity size to sizeCtl. Does it mean that > 0 represents the capacity
sizeCtl = sc;
}
break;
}
}
return tab;
}
In short, if you need to initialize, first see if there are other threads initializing. If there is one, be polite, and if not, let me! Pay special attention to sizeCtl!
I've seen CAS twice. I can't talk about it, eh! Not to mention, let's take a look at get(). This function is very common. By the way, press and hold the restless heart. get() is very simple!
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// Ask the civilian where key is
int h = spread(key.hashCode());
// Has it been initialized
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// If the hash of the specified element is the same as that of the header node, the value of the header node will be returned directly
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// If the head node hash is less than 0, it is either expanding or red black tree
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// It's not the head, that's the linked list. Go through it one by one!
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
Briefly describe:
1: Find the position of the key through the hashcode of the key
2: Determine whether it is a header node, and return directly if it is
3: If the hash of the head node is less than 0, it is either expanding the capacity or red black tree. Find it through find
4: Finally, the linked list, traversal search!
Finally finished, ConcurrentHashMap. Is that forcing CAS? Let's put it on the next charge!
HMM... I don't even leave a praise when I think of the old guard. I only read silently. Hey, the old guard, give me a praise!, Next time we talk about CAS, make sure it's easy to understand! (mainly because I haven't mastered it thoroughly. Come back when I master it thoroughly!)
Reference article: Guide brother's Java learning