ConcurrentHashMap源码分析_JDK1.8版本

阅读量：7110 次

发布时间：2019-06-28

本文共 9242 字，大约阅读时间需要 30 分钟。

ConcurrentHashMap源码分析_JDK1.8版本

声明

文章均为本人技术笔记，转载请注明出处

[1] https://segmentfault.com/u/yzwall

[2] blog.csdn.net/j_dark/

JDK1.6版本

ConcurrentHashMap结构

在JDK1.6中，ConcurrentHashMap将数据分成一段一段存储，给每一段数据配一把锁，当一个线程获得锁互斥访问一个段数据时，其他段的数据也可被其他线程访问；每个Segment拥有一把可重入锁，因此ConcurrentHashMap的分段锁数目即为Segment数组长度。ConcurrentHashMap结构：每一个segment都是一个HashEntry<K,V>[] table， table中的每一个元素本质上都是一个HashEntry的单向队列（单向链表实现）。每一个segment都是一个HashEntry<K,V>[] table， table中的每一个元素本质上都是一个HashEntry的单向队列。

锁分离实现

当一个线程访问Node/键值对数据时，必须获得与它对应的segment锁，其他线程可以访问其他Segment中的数据（锁分离）；

ConcurrentHashMap声明

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable

无锁算法：CAS

乐观锁与悲观锁

悲观锁比如synchronized锁，为确保其他线程不会干扰当前线程工作，因此挂起其他需要锁的线程，等待持有锁的线程释放；

乐观锁总是假设没有冲突发生去做操作，如果检测到冲突就失败重试，知道成功为止；

CAS算法

CAS(Compare And Swap)：CAS算法包含三个参数CAS(V, E, N)，判断预期值E和内存旧值是否相同(Compare)，如果相等用新值N覆盖旧值V(Swap)，否则失败；

当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，其他线程失败（失败线程不会被阻塞，而是被告知“失败”，可以继续尝试）；

CAS在硬件层面可以被编译为机器指令执行，因此性能高于基于锁占有方式实现线程安全；

ConcurrentHashMap结构图示

与JDK1.6对比

JDK 1.8取消类segments字段，直接用table数组存储键值对，JDK1.6中每个bucket中键值对组织方式是单向链表，查找复杂度是O(n)，JDK1.8中当链表长度超过TREEIFY_THRESHOLD时，链表转换为红黑树，查询复杂度可以降低到O(log n)，改进性能；

锁分离

JDK1.8中，一个线程每次对一个桶（链表 or 红黑树）进行加锁，其他线程仍然可以访问其他桶；

线程安全

ConcurrentHashMap底层数据结构与HashMap相同，仍然采用table数组+链表+红黑树结构；

一个线程进行put/remove操作时，对桶（链表 or 红黑树）加上synchronized独占锁；

ConcurrentHashMap采用CAS算法保证线程安全；

ConcurrentHashMap基本数据结构

transient volatile Node<K,V>[] table：键值对桶数组

private transient volatile Node<K,V>[] nextTable： rehash扩容时用到的新键值对数组

private transient volatile long baseCount：<span id = "jump1"></span>记录当前键值对总数，通过CAS更新，对所有线程可见

private transient volatile int sizeCtl

sizeCtl表示键值对总数阈值，通过CAS更新, 对所有线程可见
- 当sizeCtl < 0时，表示多个线程在等待扩容；
- 当sizeCtl = 0时，默认值；
- 当sizeCtl > 0时，表示扩容的阈值；

private transient volatile int cellBusy：自旋锁；

private transient volatile CounterCell[] counterCells: counter cell表，长度总为2的幂次；

static class Segment<K,V>：在JDK1.8中，Segment类仅仅在序列化和反序列化时发挥作用；

// 视图private transient KeySetView
    
      keySetprivate transient ValuesView
     
       valuesprivate transient EntrySetView
      
        entrySet

描述键值对：Node<K, V>

static class Node
    
      implements Map.Entry
     
       {    final int hash;    final K key;    // 键值对的value和next均为volatile类型    volatile V val;    volatile Node
      
        next;    ...}

ConcurrentHashMap重要方法分析

构造函数

ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

public ConcurrentHashMap(int initialCapacity,                         float loadFactor, int concurrencyLevel) {    if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)        throw new IllegalArgumentException();    if (initialCapacity < concurrencyLevel)   // Use at least as many bins        initialCapacity = concurrencyLevel;   // as estimated threads    long size = (long)(1.0 + (long)initialCapacity / loadFactor);    int cap = (size >= (long)MAXIMUM_CAPACITY) ?        MAXIMUM_CAPACITY : tableSizeFor((int)size);    this.sizeCtl = cap;}

该构造器会根据输入的initialCapacity确定一个 >= initialCapacity的最小2的次幂；

concurrentLevel：在JDK1.8之前本质是ConcurrentHashMap分段锁总数，表示同时更新ConcurrentHashMap且不产生锁竞争的最大线程数；在JDK1.8中，仅在构造器中确保初始容量>=concurrentLevel，为兼容旧版本而保留；

添加/更新键值对：putVal

putVal方法分析

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;        // 不断CAS探测，如果其他线程正在修改tab，CAS尝试失败，直到成功为止    for (Node
    
     [] tab = table;;) {        Node
     
       f; int n, i, fh;        // 空表，对tab进行初始化        if (tab == null || (n = tab.length) == 0)            tab = initTable();        /**         * CAS探测空桶         * 计算key所在bucket表中数组索引: i = (n - 1) & hash)         */        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {            // CAS添加新键值对            if (casTabAt(tab, i, null,                         new Node
      
       (hash, key, value, null)))                break;                   // no lock when adding to empty bin        }        // 检测到tab[i]桶正在进行rehash,        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; } } } // 更新baseCount addCount(1L, binCount); return null;}

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

获取键值对：get

public V get(Object key) {    Node
    
     [] tab; Node
     
       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;        }        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方法通过CAS保证键值对的原子性，当tab[i]被锁住，CAS失败并不断重试，保证get不会出错；

删除键值对：remove

扩容机制

transfer

当baseCount超过sizeCtl，将table中所有bin内的键值对拷贝到nextTable；

待补充；

helpTransfer

待补充；

table原子操作方法

获取tab[i]：tabAt

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

tabAt方法原子读取table[i]；调用Unsafe对象的getObjectVolatile方法获取tab[i]，由于对volatile写操作happen-before于volatile读操作，因此其他线程对table的修改均对get读取可见；

((long)i << ASHIFT) + ABASE)计算i元素的地址

CAS算法更新键值对：casTabAt

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

casTabAt通过compareAndSwapObject方法比较tabp[i]和v是否相等，相等就用c更新tab[i];

更新键值对：setTabAt

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

仅在synchronized同步块中被调用，更新键值对；

CAS更新baseCount

addCountaddCount

private final void addCount(long x, int check) {    CounterCell[] as; long b, s;    // s = b + x，完成baseCount++操作；    if ((as = counterCells) != null ||        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {        CounterCell a; long v; int m;        boolean uncontended = true;        if (as == null || (m = as.length - 1) < 0 ||            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||            !(uncontended =              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {            // 多线程CAS发生失败时执行            fullAddCount(x, uncontended);            return;        }        if (check <= 1)            return;        s = sumCount();    }    if (check >= 0) {        Node
    
     [] tab, nt; int n, sc;        // 当更新后的键值对总数baseCount >= 阈值sizeCtl时，进行rehash        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&               (n = tab.length) < MAXIMUM_CAPACITY) {            int rs = resizeStamp(n);            // sc < 0 表示其他线程已经在rehash            if (sc < 0) {                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||                    transferIndex <= 0)                    break;                // 其他线程的rehash操作已经完成，当前线程可以进行rehash                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))                    transfer(tab, nt);            }            // sc >= 0 表示只有当前线程在进行rehash操作，调用辅助扩容方法transfer            else if (U.compareAndSwapInt(this, SIZECTL, sc,                                         (rs << RESIZE_STAMP_SHIFT) + 2))                transfer(tab, null);            s = sumCount();        }    }}

addCount负责对baseCount + 1操作，CounterCell是Striped64类型，否则应对高并发问题；