ConcurrentHashMap分析(JDK1.8)

ConcurrentHashMap 里有 50+ 个子类, 一共 6k+ 行代码, 对于初学者直接阅读有一些难度. 本文详细介绍 ConcurrentHashMap 中的一些 关键要素(概念/代码), 掌握这些再看这个类的实现细节(代码), 就比较容易看懂.

推荐 JDK1.8 使用 liberica-1.8 版本, 这个版本的 JDK 所有源码都有, 方便阅读.
Oracle 版本的 JDK1.8 有一些类是没有源码的, 只有 .class 文件(比如 Unsafe 类), .class 反编译出来的代码看起来很难受.

这一小节是基础知识, 和 ConcurrentHashMap 设计没啥关系, JDK 中很多类都用到了 Unsafe 类.

Unsafe 类的主要功能:

1. 获取类的字段(或数组的元素)的 偏移地址(offset).
2. 通过对象的 偏移地址 获取/修改 对象的值(或引用).
3. CAS 操作.
4. 阻塞(park)/唤醒(unpark) 线程.
5. 内存分配与回收.

ConcurrentHashMap 使用 Unsafe 的代码片段(有删减):

    // Unsafe mechanics
    private static final sun.misc.Unsafe U;
    
    private static final long SIZECTL;
    private static final long Abase;
    private static final int ASHIFT;

    static {
        try {
            // 获取 Unsafe 实例
            U = sun.misc.Unsafe.getUnsafe();
            // 获取 ConcurrentHashMap 的 Class 对象
            Class k = ConcurrentHashMap.class;
            // ConcurrentHashMap 的 sizeCtl 成员/字段 的 地址偏移量(相对于ConcurrentHashMap对象的起始地址)
            SIZECTL = U.objectFieldOffset
                (k.getDeclaredField("sizeCtl"));
            
            // 获取 Node[] 数组的 Class 对象
            Class ak = Node[].class;
            // Node[] 数组的 第一个元素 的 地址偏移量(相对于数组对象的地址地址)
            Abase = U.arraybaseOffset(ak);
            // Node[] 数组一个元素的 地址偏移量scale
            int scale = U.arrayIndexScale(ak);
            // 偏移量scale 必须是 2的(n次)幂, 不是 2的幂则报错
            if ((scale & (scale - 1)) != 0)
                throw new Error("data type scale not a power of two");
            // Integer.numberOfLeadingZeros(scale): 计算 偏移量sacle 在转成二进制后, 
            // 从左往右看, 第一个 非0数 的左边一共有多少个 0.
            // 假设 sacle=4, 那么 Integer.numberOfLeadingZeros(scale) 就等于 29.
            // ASHIFT 表示: 元素的移位数
            // 解释起来有点抽象, 看下面的 tabAt 方法的分析
            ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
        } catch (Exception e) {
            throw new Error(e);
        }
    }

对 以上定义的 偏移量 的使用:

    // 获取 tab[] 在 下标i 处的对象; 相当于 具有 volatile 语义的 tab[i]
    static final  Node tabAt(Node[] tab, int i) {
        // ((long)i << ASHIFT) : 下标 i 处 Node 对象的地址偏移量(相对于tab对象的第一个元素的地址),
        // ((long)i << ASHIFT) + Abase : 下标 i 处 Node 对象的地址偏移量(相对于tab对象的起始地址),
        // U.getObjectVolatile(tab, ((long)i << ASHIFT) + Abase) : 获取 tab[] 在 下标i 处的对象, 使用 volatile 语义.
        // 比如:
        // 假设 tab[] 中的一个 Node 元素所占内存偏移量为 4(scale=4), 那么,
        // 易知 ASHIFT=2; 假设要获取下标为3(i=3)处的对象, 那么,
        // 易知 ((long)i << ASHIFT)=12, 因此可通过 getObjectVolatile 获取 tab[i] 的对象, 即, tab起始地址偏移 12+Abase 处的对象.
        // 在这个例子中, i << ASHIFT 等价于 i*4.
        return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + Abase);
    }



    
    private final Node[] initTable() {
        //略
            // this 表示当前的 ConcurrentHashMap(以下简称CHM) 对象, 
            // SIZECTL 是 CHM.sizeCtl 字段的 地址偏移量.
            // 所以 U.compareAndSwapInt(this, SIZECTL, sc, -1) 意为:
            // 如果 this.sizeCtl == sc, 就把 this.sizeCtl 赋值为 -1, 且这是一个原子操作.
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
        //略
    }

普通结点类型 Node:

 
static class Node implements Map.Entry {
    final int hash;
    final K key;
    volatile V val;
    volatile Node next;
    // 成员方法略
}

扩容时 bin 的头部存放的结点类型 ForwardingNode:

    

    
    static final class ForwardingNode extends Node {
        final Node[] nextTable;
        ForwardingNode(Node[] tab) {
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }

        Node find(int h, Object k) {
            // loop to avoid arbitrarily deep recursion on forwarding nodes
            outer: for (Node[] tab = nextTable;;) {
                Node e; int n;
                if (k == null || tab == null || (n = tab.length) == 0 ||
                    (e = tabAt(tab, (n - 1) & h)) == null)
                    return null;
                for (;;) {
                    int eh; K ek;
                    if ((eh = e.hash) == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                    if (eh < 0) {
                        if (e instanceof ForwardingNode) {
                            tab = ((ForwardingNode)e).nextTable;
                            continue outer;
                        }
                        else
                            return e.find(h, k);
                    }
                    if ((e = e.next) == null)
                        return null;
                }
            }
        }
    }

红黑树结构的结点类型 TreeBin (CHM中最复杂的一个子类):

    

    
    static final class TreeBin extends Node {
        TreeNode root;
        volatile TreeNode first;
        volatile Thread waiter;
        volatile int lockState;
        // values for lockState
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // increment value for setting read lock
        // 方法略
}

CHM中主要的 成员变量:

    

    
     // CHM的 所有元素 都放在这个数组中
    transient volatile Node[] table;

    
     // 扩容时用于存放数据的变量, 扩容完成后会置为null
    private transient volatile Node[] nextTable;

    
     // 取值说明:
     // 0: 未指定初始容量
     // 正数(大于0): 说明初始化 map 时指定了容量, 假设指定的容量大小为x, 
     //   如果 x 是 2的幂, 则 sizeCtl=x, 
     //   如果 x 不是2的幂, 则 sizeCtl 取 2^n(满足 2^n > x 且 2^(n-1) < x).
     //     比如, x=5或6或7或8时, sizeCtl=8; x=9, sizeCtl=16.
     // -1: table 正在初始化
     // -N(N大于1): N是int类型, 分为两部分, 高15位是指定容量标识, 低16位表示并行扩容线程数+1
    private transient volatile int sizeCtl;

loading…

[1]. java.util.concurrent.ConcurrentHashMap(JDK1.8)
[2]. 关于jdk1.8中ConcurrentHashMap的方方面面