彻底理解ConcurrentHashMap

布满荆棘的人生 2023-07-06 09:50 39阅读 0赞

# ConcurrentHashMap概述 #

[《彻底理解HashMap及LinkedHashMap》][HashMap_LinkedHashMap]介绍了HashMap及LinkedHashMap的数据结构和原理，不过遗憾的是，HashMap不是线程安全的。也就是说，在多线程环境下，操作HashMap会导致各种各样的线程安全问题，比如在HashMap扩容重哈希时出现的死循环问题，脏读问题等。HashMap的这一缺点往往会造成诸多不便，虽然在并发场景下HashTable和由同步包装器包装后的HashMap(Collections.synchronizedMap(Map<K,V> m) )可以代替HashMap，但是它们都是通过使用一个全局的锁来同步不同线程间的并发访问，因此会带来不可忽视的性能问题。庆幸的是，JDK为我们解决了这个问题，它为HashMap提供了一个线程安全的高效版本——ConcurrentHashMap。在ConcurrentHashMap中，无论是读操作还是写操作都能保证很高的性能。下面对比着分析下Java7及Java8对ConcurrentHashMap的实现。

## 1、Java7中的ConcurrentHashMap ##

Java7中的ConcurrentHashMap在进行读操作时几乎不需要加锁，而在写操作时通过锁分段技术只对所操作的段加锁而不影响客户端对其它段的访问。特别地，在理想状态下，ConcurrentHashMap可以支持最多16个线程执行并发写操作及任意数量线程的读操作。

下面分析JDK1.7源代码，探索ConcurrentHashMap数据结构及读写操作。

## 1.1、ConcurrentHashMap数据结构 ##

![2020021920453866.png][]

整个ConcurrentHashMap由一个个Segment组成，Segment代表“部分”或“一段”的意思，所以很多地方都会将其描述为分段锁。

简单理解就是，ConcurrentHashMap是一个Segment数组组成，Segment通过继承ReentrantLock来进行加锁，所以每次需要加锁的操作锁住的是一个Segment，这样只要保证每个Segment是线程安全的，也就实现了全局的线程安全。

本质上，JDK1.7中的ConcurrentHashMap就是一个Segment数组，而一个Segment实例则是一个小的哈希表。由于Segment类继承于ReentrantLock类，从而使得Segment对象能充当锁的角色，这样，每个Segment对象就可以守护整个ConcurrentHashMap的若干个桶，其中每个桶是由若干个HashEntry对象链接起来的链表。通过使用段(Segment)将ConcurrentHashMap划分为不同的部分，ConcurrentHashMap就可以使用不同的锁来控制对哈希表的不同部分的修改，从而允许多个修改操作并发进行, 这正是ConcurrentHashMap锁分段技术的核心内涵。

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
            implements ConcurrentMap<K, V>, Serializable { 
    
        /** * Mask value for indexing into segments. The upper bits of a * key's hash code are used to choose the segment. */
    	final int segmentMask;  // 用于定位段，大小等于segments数组的大小减 1，是不可变的
    	
    	/** * Shift value for indexing within segments. */
    	final int segmentShift;    // 用于定位段，大小等于32(hash值的位数)减去对segments的大小取以2为底的对数值，是不可变的
    	
    	/** * The segments, each of which is a specialized hash table */
    	final Segment<K,V>[] segments;   // ConcurrentHashMap的底层结构是一个Segment数组
    }

### 段的定义：Segment ###

Segment类继承于ReentrantLock类，从而使得Segment对象能充当锁的角色。每个Segment对象用来守护它的成员对象table中包含的若干个桶。table是一个由HashEntry对象组成的数组，table数组的每一个成员就是一个桶。

/** * Segments are specialized versions of hash tables. This * subclasses from ReentrantLock opportunistically, just to * simplify some locking and avoid separate construction. */
    static final class Segment<K,V> extends ReentrantLock implements Serializable { 
    
        /** * The number of elements in this segment's region. */
        transient volatile int count;    // Segment中元素的数量，可见的
    
        /** * Number of updates that alter the size of the table. This is * used during bulk-read methods to make sure they see a * consistent snapshot: If modCounts change during a traversal * of segments computing size or checking containsValue, then * we might have an inconsistent view of state so (usually) * must retry. */
        transient int modCount;  //对count的大小造成影响的操作的次数（比如put或者remove操作）
    
        /** * The table is rehashed when its size exceeds this threshold. * (The value of this field is always <tt>(int)(capacity * * loadFactor)</tt>.) */
        transient int threshold;      // 阈值，段中元素的数量超过这个值就会对Segment进行扩容
    
        /** * The per-segment table. */
        transient volatile HashEntry<K,V>[] table;  // 数组
    
        /** * The load factor for the hash table. Even though this value * is same for all segments, it is replicated to avoid needing * links to outer object. * @serial */
        final float loadFactor;  // 段的负载因子，其值等同于ConcurrentHashMap的负载因子
    
        //...
    }

在Segment类中，count变量是一个计数器，它表示每个Segment对象管理的table数组包含的HashEntry对象的个数，也就是 Segment中包含的HashEntry对象的总数。特别需要注意的是，之所以在每个Segment对象中包含一个计数器，而不是在ConcurrentHashMap中使用全局的计数器，是对ConcurrentHashMap并发性的考虑：因为这样当需要更新计数器时，不用锁定整个ConcurrentHashMap。事实上，每次对段进行结构上的改变，如在段中进行增加/删除节点(修改节点的值不算结构上的改变)，都要更新count的值，此外，在JDK的实现中每次读取操作开始都要先读取count的值。特别需要注意的是，**count是volatile的，这使得对count的任何更新对其它线程都是立即可见的**。

ConcurrentHashMap允许多个修改(写)操作并发进行，其关键在于**使用了锁分段技术，它使用了不同的锁来控制对哈希表的不同部分进行的修改(写)，而ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分**。实际上，每个段实质上就是一个小的哈希表，每个段都有自己的锁(Segment 类继承了ReentrantLock 类)。这样，只要多个修改(写)操作发生在不同的段上，它们就可以并发进行。

### 基本元素：HashEntry的结构 ###

static final class HashEntry<K,V> { 
       final K key;                // 声明 key 为 final 的
       final int hash;             // 声明 hash 值为 final 的
       volatile V value;           // 声明 value 被volatile所修饰
       final HashEntry<K,V> next;  // 声明 next 为 final 的
    
        HashEntry(K key, int hash, HashEntry<K,V> next, V value) { 
            this.key = key;
            this.hash = hash;
            this.next = next;
            this.value = value;
        }
    
        @SuppressWarnings("unchecked")
        static final <K,V> HashEntry<K,V>[] newArray(int i) { 
        return new HashEntry[i];
        }
    }

HashEntry用来封装具体的键值对，是个典型的四元组。与JDK1.7的HashMap中的Entry类似，这里的HashEntry也包括四个域，分别是key、hash、value和next。不同的是，在HashEntry类中，key、hash和next域都被声明为final的，value域被volatile所修饰，因此HashEntry对象几乎是不可变的，这是ConcurrentHashMap读操作并不需要加锁的一个重要原因。next域被声明为final本身就意味着我们不能从hash链的中间或尾部添加或删除节点，因为这需要修改next引用值，因此所有的节点的修改只能从头部开始。

对于put操作，可以一律添加到Hash链的头部。但是对于remove操作，可能需要从中间删除一个节点，这就需要将要删除节点的前面所有节点整个复制(重新new)一遍，最后一个节点指向要删除结点的下一个结点。大致是下面的流程，JDK1.7用头插法一来是不用遍历链表到末尾，二来是考虑到了一个所谓的热点数据(新插入的数据可能会更早用到)，但这其实是个伪命题。而JDK1.8果断放弃了这个不好的设计使用尾插法。

![20200221171129990.png][]

## 1.2、ConcurrentHashMap的快速存取 ##

在ConcurrentHashMap中，线程对映射表做读操作时，一般情况下不需要加锁就可以完成，对容器做结构性修改的操作(比如，put操作、remove操作等)才需要加锁。

实际上对ConcurrentHashMap的put操作被ConcurrentHashMap委托给特定的段来实现。以下是segment的put操作的源码：

V put(K key, int hash, V value, boolean onlyIfAbsent) { 
        lock();    // 上锁
        try { 
            int c = count;
            if (c++ > threshold) // ensure capacity
                rehash();
            HashEntry<K,V>[] tab = table;    // table是Volatile的
            int index = hash & (tab.length - 1);    // 定位到段中特定的桶
            HashEntry<K,V> first = tab[index];   // first指向桶中链表的表头
            HashEntry<K,V> e = first;
    
            // 检查该桶中是否存在相同key的结点
            while (e != null && (e.hash != hash || !key.equals(e.key)))  
                e = e.next;
    
            V oldValue;
            if (e != null) {         // 该桶中存在相同key的结点
                oldValue = e.value;
                if (!onlyIfAbsent)
                    e.value = value;        // 更新value值
            }else {          // 该桶中不存在相同key的结点
                oldValue = null;
                ++modCount;     // 结构性修改，modCount加1
                tab[index] = new HashEntry<K,V>(key, hash, first, value);  // 创建HashEntry并将其链到表头
                count = c;      //write-volatile，count值的更新一定要放在最后一步(volatile变量)
            }
            return oldValue;    // 返回旧值(该桶中不存在相同key的结点，则返回null)
        } finally { 
            unlock();      // 在finally子句中解锁
        }
    }

这里的加锁操作是针对某个具体的Segment，锁定的也是该Segment而不是整个ConcurrentHashMap。因为插入键/值对操作只是在这个Segment包含的某个桶中完成，不需要锁定整个ConcurrentHashMap。因此，其他写线程对另外15个Segment的加锁并不会因为当前线程对这个Segment的加锁而阻塞。

在将Key/Value对插入到Segment之前，首先会检查本次插入会不会导致Segment中元素的数量超过阈值threshold，如果会，那么就先对Segment进行扩容和重哈希操作，然后再进行插入。

segment中get操作的源码：

V get(Object key, int hash) { 
        if (count != 0) {             // read-volatile，首先读 count 变量
            HashEntry<K,V> e = getFirst(hash);   // 获取桶中链表头结点
            while (e != null) { 
                if (e.hash == hash && key.equals(e.key)) {     // 查找链中是否存在指定Key的键值对
                    V v = e.value;
                    if (v != null)  // 如果读到value域不为 null，直接返回
                        return v;   
                    // 如果读到value域为null，说明发生了重排序，加锁后重新读取
                    return readValueUnderLock(e); // recheck
                }
                e = e.next;
            }
        }
        return null;  // 如果不存在，直接返回null
    }

我们就知道ConcurrentHashMap不同于HashMap，它既不允许key值为null，也不允许value值为null。但是，上面有一行判断value值为null的代码，这是为什么呢？JDK官方给出的解释是，这种情形发生的场景是：初始化HashEntry时发生的指令重排序导致的，也就是在HashEntry初始化完成之前便返回了它的引用。这时，JDK给出的解决之道就是加锁重读，源码如下：

V readValueUnderLock(HashEntry<K,V> e) { 
        lock();
        try { 
            return e.value;
        } finally { 
            unlock();
        }
    }

JDK1.7中的ConcurrentHashMap进行存取时，首先会定位到具体的段，然后通过对具体段的存取来完成对整个ConcurrentHashMap的存取。特别地，无论是读操作还是写操作都具有很高的性能：在进行读操作时不需要加锁，而在写操作时通过锁分段技术只对所操作的段加锁而不影响客户端对其它段的访问。

前面分析HashEntry对象时，可以知道整个对象只有改变Value的值是可以改变的，key、hash和next指针都是final的。这意味着，我们不能把节点添加到链表的中间和尾部，也不能在链表的中间和尾部删除节点。这个特性可以保证：在访问某个节点时，这个节点之后的链接不会被改变，这个特性可以大大降低处理链表时的复杂性。与此同时，由于HashEntry类的value字段被声明是Volatile的，因此Java的内存模型就可以保证：某个写线程对value字段的写入马上就可以被后续的读线程看到。此外，由于在ConcurrentHashMap中不允许用null作为键和值，所以当读线程读到某个HashEntry的value为null时，便知道发生了重排序现象，此时便会加锁重新读入这个value值。这些特性互相配合，使得读线程即使在不加锁状态下，也能正确访问。

# 2、Java8中的ConcurrentHashMap #

Java7中实现的ConcurrentHashMap说实话还是比较复杂的，Java8对ConcurrentHashMap进行了比较大的改动。JDK1.8取消类segments字段，直接用table数组存储键值对，JDK1.6及1.7中每个bucket中键值对组织方式是单向链表，查找复杂度是O(n)，JDK1.8中当链表长度超过TREEIFY\_THRESHOLD时，链表转换为红黑树，查询复杂度可以降低到O(logN)，改进性能。

## 2.1、ConcurrentHashMap的数据结构 ##

![20200219210219880.png][]

**基本元素：Node**

Node用来封装具体的键值对，是个典型的四元组。与HashMap中的Node类似，两者都实现了Map.Entry接口。不同的是在HashMap中，key与hash声明成final，value与next是普通变量。而在ConcurrentHashMap中，key与hash声明成final，value与next声明成volatile。JDK1.8中，无论是HashMap中的Node还是ConcurrentHashMap中的Node，四大变量的声明上都与JDK1.7有差别。

另外一个特殊的点是ConcurrentHashMap中的Node不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map.get()方法。

static class Node<K,V> implements Map.Entry<K,V> { 
        final int hash;			// 声明hash值为final 的
        final K key;			// 声明key为final 的
        volatile V val;			// 声明value被volatile所修饰
        volatile Node<K,V> next;	//声明next被volatile所修饰
    
        Node(int hash, K key, V val, Node<K,V> next) { 
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }
    
        public final K getKey()       {  return key; }
        public final V getValue()     {  return val; }
        public final int hashCode()   {  return key.hashCode() ^ val.hashCode(); }
        public final String toString(){  return key + "=" + val; }
    	// 不允许调用此方法直接改变Node的value
        public final V setValue(V value) { 
            throw new UnsupportedOperationException();
        }
    
        public final boolean equals(Object o) { 
            Object k, v, u; Map.Entry<?,?> e;
            return ((o instanceof Map.Entry) &&
                    (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                    (v = e.getValue()) != null &&
                    (k == key || k.equals(key)) &&
                    (v == (u = val) || v.equals(u)));
        }
    
        /** * Virtualized support for map.get(); overridden in subclasses. */
        Node<K,V> find(int h, Object k) { 
            Node<K,V> e = this;
            if (k != null) { 
                do { 
                    K ek;
                    if (e.hash == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                } while ((e = e.next) != null);
            }
            return null;
        }
    }

## 2.1、ConcurrentHashMap的构造函数 ##

public ConcurrentHashMap(int initialCapacity) { 
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

这个初始化方法有点意思，通过提供的初始容量，计算了sizeCtl，sizeCtl = 【 (1.5 \* initialCapacity + 1)，然后向上取最近的2的n次方】。

如initialCapacity为10，那么得到sizeCtl为16，如果initialCapacity为11，得到sizeCtl为32。sizeCtl这个属性使用的场景很多。大部分时候，我们会使用无参构造函数进行实例化。

## 2.3、ConcurrentHashMap的存取 ##

putVal方法源码：

public V put(K key, V value) { 
        return putVal(key, value, false);
    }
    
    
    final V putVal(K key, V value, boolean onlyIfAbsent) { 
        if (key == null || value == null) throw new NullPointerException();
        // 得到hash值
        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();
            // 找该hash值对应的数组下标，得到第一个节点f
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 
                //如果数组该位置为空，
                //用一次CAS操作将这个新值放入其中即可，这个put操作就结束了
                //如果CAS失败，那就是有并发操作，进到下一个循环就好了
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            // hash 居然可以等于-1？这里其实是在扩容
            else if ((fh = f.hash) == MOVED)
                // 当前线程参与帮助数据迁移
                tab = helpTransfer(tab, f);
    
            else {  // 到这里就是说，f 是该位置的头结点，而且不为空
    
                V oldVal = null;
                // 获取数组该位置的头结点的监视器锁
                synchronized (f) { 
                    if (tabAt(tab, i) == f) { 
                        if (fh >= 0) {  // 头结点的 hash 值大于 0，说明是链表
                            // 用于累加，记录链表的长度
                            binCount = 1;
                            // 遍历链表
                            for (Node<K,V> e = f;; ++binCount) { 
                                K ek;
                                // 如果发现了"相等"的 key，判断是否要进行值覆盖，然后也就可以break 了
                                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) { 
                    // 判断是否要将链表转换为红黑树，临界值和HashMap一样，也是8
                    if (binCount >= TREEIFY_THRESHOLD)
                        // 如果当前数组的长度小于64，那么会选择进行数组扩容，而不是转换为红黑树
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        // 
        addCount(1L, binCount);
        return null;
    }

synchronized (f) \{\}操作通过对桶的首元素，即链表表头或红黑树根节点加锁，从而实现对整个桶进行加锁，有锁分离思想的体现。

这个put方法依然沿用HashMap的put方法的思想，根据hash值计算这个新插入的点在table中的位置i，如果i位置是空的，直接放进去，否则进行判断，如果i位置是树节点，按照树的方式插入新的节点，否则把i插入到链表的末尾。ConcurrentHashMap中依然沿用这个思想，有一个最重要的不同点就是ConcurrentHashMap不允许key或value为null值。另外由于涉及到多线程，put方法就要复杂一点。在多线程中可能有以下两个情况：

*  如果一个或多个线程正在对ConcurrentHashMap进行扩容操作，当前线程也要进入扩容的操作中。这个扩容的操作之所以能被检测到，是因为transfer方法中在空结点上插入forward节点，如果检测到需要插入的位置被forward节点占有，就帮助进行扩容；
 *  如果检测到要插入的节点是非空且不是forward节点，就对这个节点（即链表或红黑树的首元素）加锁，这样就保证了线程安全。尽管这个有一些影响效率，但是还是会比HashTable的synchronized要好得多。

initTable方法主要就是初始化一个合适大小的数组，然后设置sizeCtl。注意sizeCtl被定义为了volatile变量，具备并发可见性。初始化方法中的并发问题是通过对sizeCtl进行一个CAS操作来控制的。

private final Node<K,V>[] initTable() { 
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) { 
            // 初始化的锁已经被其他线程拿到了
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            // CAS一下，将sizeCtl设置为-1，代表抢到了锁
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { 
                try { 
                    if ((tab = table) == null || tab.length == 0) { 
                        // DEFAULT_CAPACITY默认初始容量是16
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        // 初始化数组，长度为16 或初始化时提供的长度
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        // 将这个数组赋值给table，table是volatile 的
                        table = tab = nt;
                        // 如果n为16 的话，那么这里sc = 12
                        // 其实就是 0.75 * n
                        sc = n - (n >>> 2);
                    }
                } finally { 
                    // 设置sizeCtl为sc，我们就当是12吧
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

get方法源码

public V get(Object key) { 
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        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;
            }
            // e.hash值为负表示正在扩容
            else if (eh < 0)
                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;
    }

get方法从来都是最简单的：

1.  计算hash值
2.  根据hash值找到数组对应的位置: (n - 1) & h
3.  根据该位置处结点性质进行相应查找，如果该位置为null，那么直接返回null就可以了；如果该位置处的节点刚好就是我们需要的，返回该节点的值即可；如果该位置节点的hash值小于0，说明正在扩容，或者是红黑树；如果以上3条都不满足，那就是链表，进行遍历比对即可。

get操作的流程很简单，也很清晰，并且全程无锁。get操作可以无锁是由于Node元素的val和指针next是用volatile修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。

### Unsafe与CAS ###

在JDK1.8的ConcurrentHashMap实现中，随处可以看到U, 大量使用了U.compareAndSwapXXX的方法，这个方法是利用一个CAS算法实现无锁化的修改值的操作，它可以大大降低锁代理的性能消耗。这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作。因为当前线程中的值已经不是最新的值，你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁的思想是比较类似的。

### 3个原子操作 ###

tabAt方法在putVal与get方法多处被调用，用于定位hash表中的一个节点，入参是Node数组以及数组的索引，索引值通常(n - 1) & h。

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { 
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

![0c24cc31dff1413b9a460c516de5ebf3.png][]

casTabAt方法利用CAS算法将Node节点设置到i位置上，将c和table\[i\]作比较，相同则插入v

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) { 
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

![77bafe8b7ac64c69b95e22c80f4c07fb.png][]

setTabAt方法设置节点位置的值，仅在上锁代码块中被调用。

static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { 
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

总的来说，JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+volatile+HashEntry，到JDK1.8版本中synchronized+CAS+volatile+Node+红黑树，相对而言：

*  JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是Node（有链表或红黑树时就是首节点）
 *  JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了
 *  JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档

JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock呢？

*  因为锁的粒度降低了，在相对而言的低粒度加锁方式下，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了
 *  JVM的开发团队从来都没有放弃synchronized，而且基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然，在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据。

volatile的读写和CAS可以实现线程之间的通信，整合到一起就实现了Concurrent包得以实现的基石。在阅读JUC下的类时会发现一个通用的模式：volatile修饰多线程共享变量，CAS原子更新共享变量实现线程同步，二者搭配来实现线程之间的通信。很多操作都是先读volatile变量的最新值，然后赋给局部变量，然后一顿操作，最后CAS进行同步，若过程中共享变量被其它线程更改则会导致CAS失败，重新尝试。

[HashMap_LinkedHashMap]: https://blog.csdn.net/fuzhongmin05/article/details/104355841
[2020021920453866.png]: https://img-blog.csdnimg.cn/2020021920453866.png
[20200221171129990.png]: https://img-blog.csdnimg.cn/20200221171129990.png
[20200219210219880.png]: https://img-blog.csdnimg.cn/20200219210219880.png
[0c24cc31dff1413b9a460c516de5ebf3.png]: https://img-blog.csdnimg.cn/0c24cc31dff1413b9a460c516de5ebf3.png
[77bafe8b7ac64c69b95e22c80f4c07fb.png]: https://img-blog.csdnimg.cn/77bafe8b7ac64c69b95e22c80f4c07fb.png