Java’s collections frameworks fall into two categories:

  • Non-thread-safe class framework with ArrayList, LinkedList, HashMap
  • Vector, ConcurrentHashMap, HashTable – a thread-safe framework

They are suitable for different scenarios, and some of them have been introduced in the previous section without too much description here.

This paper focuses on the framework of thread safety and lists its application scenarios.

ConcurrentHashMap

The structure of ConcurrentHashMap is similar to that of HashMap. The difference with HashMap is that HashMap inherits the Map interface while ConcurrentHashMap inherits the ConcurrentMap interface.

The basic code structure of ConcurrentHashMap is similar to that of HashMap, which has been thoroughly outlined in the previous section. Here we will focus on the specific parts of ConcurrentHashMap.

put

public V put(K key, V value) {
        return putVal(key, value, false);
}
Copy the code

The put method of ConcurrentHashMap has the same structure as that of HashMap. There is one thing that we need to pay special attention to. In a HashMap the key is passed in as the hash value, and in a ConcurrentHashMap it is passed in as the key directly.

Next, we will analyze the core putVal in detail. The code is quite long, so we will analyze it in several paragraphs. First look at the first paragraph:

if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
Copy the code

Null key or value is not allowed in concurrentHashMap. If it is null, NullPoint exceptions are thrown. The spread method hashes the hash key.

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
 }
Copy the code

If TAB is empty, initTable is called for initialization. This is actually different from HashMap from the beginning, with CasTabAt (spin adjustment and insert), or CAS lock, implemented by a CAS algorithm without locking the insert.

Here is a brief introduction to CAS locks.

CAS operates on optimistic locking, where an operation is performed each time without locking, assuming no conflicts, and retry until it succeeds if it fails due to conflicts.

When it comes to CAS, we have to mention a classic problem of ABA, which is first introduced to the follow-up pit filling.

else if ((fh = f.hash) ==MOVED)
    tab = helpTransfer(tab, f);
else {
Copy the code

If the hash value is -1, helpTransfer will be triggered, meaning that when the hash value is -1, helpTransfer will be called to speed expansion. The specific expansion algorithm is complicated, so we will not do too much analysis for the time being.

If the TAB is not empty and no other threads are currently expanding, data is written using a synchronized lock.

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; }}}}Copy the code

If it is greater than the conversion threshold it will be converted to a red-black tree, and it will be treed when count is greater than 7.

if (binCount >=TREEIFY_THRESHOLD)
    treeifyBin(tab, i);
if(oldVal ! =null)
    return oldVal;
break;
Copy the code

Unlike JDK7, which uses synchronized to lock a thread, JDK7 uses segmenting to lock a thread.

Why the difference?

Synchronized has always been a heavyweight lock, but since Java has officially upgraded it, it now uses lock upgrades. For synchronized lock acquisition, the JVM uses an optimized lock upgrade method, which is to use a biased lock to give priority to the same thread and then acquire the lock again. If the lock fails, it is upgraded to a CAS lightweight lock. If the lock fails, it will spin briefly to prevent the thread from being suspended. If all else fails, upgrade to a heavyweight lock. So it was a step up, and initially it was locked in a lot of lightweight ways. Reference from: www.cnblogs.com/aobing/p/12…

get

The specific process is as follows:

  • Based on the calculated Hashcode addressing, the value is returned directly if it is on the bucket.
  • If it’s a red-black tree you get the value as a tree.
  • If you don’t, you just iterate through the list to get the value.
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
		/ / calculate the 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)
            return(p = e.find(h, key)) ! =null ? p.val : null;
				// Find values in a linked list
        while((e = e.next) ! =null) {
            if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
                returne.val; }}return null;
}
Copy the code

CAS

CAS is an optimistic lock implementation, is a kind of lightweight lock, JUC many tool classes are based on CAS to implement. The specific process of optimistic lock is:

The thread does not lock data when reading data. When preparing to write back data, the thread compares whether the original value is changed. If the value is not changed, the thread writes back the value.

ABA problem

An overview of the

This is A classic problem with optimistic locks: A variable is currently A, thread 1 changes it to B, thread 2 changes it back to A, and the thread judging the value thinks it hasn’t changed. But it doesn’t matter, as long as the end result is correct the process doesn’t matter.

To solve

The solution is to add a version number to each CAS operation and compare the version numbers along with the values.

HashTable

From the perspective of implementation, HashTable achieves thread-safety by adding synchronized to all methods, which can ensure thread-safety, but does not achieve objective efficiency.

All data operations on HashTable are locked.

Unlike A HashMap, a HashTable does not allow a null Key or value, and an exception is thrown if a null value is inserted.

conclusion

This chapter focuses on ConcurrentHashMap, which is a very classical data structure and a very common data structure used by Java developers. We need to master it well. As we can see from the length of this article, HashTable is far less important than ConcurrentHashMap. It is no longer used in current development work, so it can be understood.

reference

[1] www.cnblogs.com/aobing/p/12…

[2] blog.csdn.net/zzu_seu/art…

[3] www.jianshu.com/p/ae25eb3cf…