[JDK源码]-J.U.C-ConcurrentHashMap

由于作者水平有限，如有什么错误点，多谢指出。

ConcurrentHashMap

public class ConcurrentHashMap extends AbstractMap
    implements ConcurrentMap, Serializable {
    //保存K-V 节点
	static class Node implements Map.Entry {
        final int hash;
        final K key;
        volatile V val;
        volatile Node next;
	}
    //链表Node 转为 TreeNode 节点，继承了Node节点
     static final class TreeNode extends Node {
        TreeNode parent;  // red-black tree links
        TreeNode left;
        TreeNode right;
        TreeNode prev;    
        boolean red;
     }
    //链表Node转为红黑树，放在 数组位置上的头节点，本身不保存数据
    static final class TreeBin extends Node {
        TreeNode root;
        volatile TreeNode first;
        volatile Thread waiter;	//等待线程
        volatile int lockState;	//锁状态
        static final int WRITER = 1; // 写锁
        static final int WAITER = 2; // 等待写锁
        static final int READER = 4; // 读锁
    }
    //保存数据的数组 2的倍数
     transient volatile Node[] table;

    
    private transient volatile Node[] nextTable;

    
    private transient volatile long baseCount;

    
    private transient volatile int sizeCtl;

    
    private transient volatile int transferIndex;

    
    private transient volatile int cellsBusy;

    
    private transient volatile CounterCell[] counterCells;

    // 通过迭代器遍历时候 的 几种视图
    private transient KeySetView keySet;
    private transient ValuesView values;
    private transient EntrySetView entrySet;  

    static final int MOVED     = -1; // resize时 forwarding 节点 的hash值
    static final int TREEBIN   = -2; // 红黑树根节点的hash值
    static final int RESERVED  = -3; // 创建 reservationNode 节点的hash值
    static final int HASH_BITS = 0x7fffffff; // 正常hash用的位数
   static final class ReservationNode extends Node {
        ReservationNode() {
            super(RESERVED, null, null, null);
        }
    }
	//创建初始容量的
    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        //最大容量  MAXIMUM_CAPACITY = 1<<30 
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        //此时保存 hash表的最大容量
        this.sizeCtl = cap;
    }
    //转移操作时，如果slot没有节点可以转移或已经转移成功，将在相应的slot放上这个类的对象
    static final class ForwardingNode extends Node {
        final Node[] nextTable;
        ForwardingNode(Node[] tab) {
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }
    }
    //减少hash冲突，异或的结果继续和HASH_BITS 与运算
    static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;//0x7fffffff
    }
}

put

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(); //不允许放入空值
    int hash = spread(key.hashCode());	//计算 hash
    int binCount = 0; //记录元素个数
    for (Node[] tab = table;;) {	//循环直到 插入成功
        Node f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)//为空 初始化 hash表
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        //根据hash值找到应该保存的数组的位置，如果没放入，通过CAS，封装成 Node对象放入索引位 i的位置
            if (casTabAt(tab, i, null,
                         new Node(hash, key, value, null)))
                break;                  
        }
        //这里，f就是找到下标位i的node元素，这时根据MOVED标志看看是数组正在扩容还是数据迁移，如果迁移，那么调用helpTransfer方法帮助完成迁移
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {	//对f上锁
                if (tabAt(tab, i) == f) {	//索引下标 i 处节点没有被更改
                    if (fh >= 0) {	//链表
                        binCount = 1;
                        for (Node e = f;; ++binCount) {//遍历链表
                            K ek;
                            //当前与 要放入的 hash 相同
                            if (e.hash == hash &&
                                ((ek = e.key) == key || //比较 地址
                                 //比较 equals 
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;	//保存找到的旧值
                                if (!onlyIfAbsent)//如果没有设置 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) {
                        //红黑树，在 slot中放置了一个 TreeBin对象 ，然后才是根节点 所以直接设置2
                        Node p;
                        binCount = 2;
               //插入红黑树，如果返回值不为空，说明红黑树包含了K，根据onlyIfAbsent 来决定是否覆盖原来的值
                        if ((p = ((TreeBin)f).putTreeval(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                //节点超过 TREEIFY_THRESHOLD = 8
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);//转换为红黑树
                if (oldVal != null)//如果发生了冲突，替换原来的值，则返回
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);//增加一个节点计数，看看是否需要扩容
    return null;
}

initTable初始化过程

private final Node[] initTable() {
    Node[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {//循环直到成功
        if ((sc = sizeCtl) < 0)
            Thread.yield(); 
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {//双重判断，避免CAS成功，但后面释放了sc后 又有线程进入
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;//默认16
                    @SuppressWarnings("unchecked")
                    Node[] nt = (Node[])new Node[n];//创建数组
                    table = tab = nt;
                    //sc保存最大的数量，这个n是 0.75
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

addCount

private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    if ((as = counterCells) != null ||//已经创建
        //直接在baseCount 变量上计数。如果失败进入初始化 as，
        !U.compareAndSwapLong(this, baseCOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        //初始化as
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);//创建as或者添加计数器
            return;
        }
        if (check <= 1)//如果check<= 1 直接退出
            return;
        s = sumCount();//获取当前hash表的数据量
    }
    if (check >= 0) {//检查表的大小，要不要扩容
        Node[] tab, nt; int n, sc;
        //s是当前数据量，大于等于 当前容量  && 数组不为空 && 数组小于最大容量
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);	//计算扩容时 使用的stamp
            if (sc < 0) { //如果sc小于0，表明已经开始扩容
                //stamp 已经改变  || 达到最大帮助resize的线程数  	MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
                //nextTable 为空，扩容完毕 
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                //增加帮助 resize 的线程数
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt); //如果成功 开始扩容
            }
            //将 sc设置为  (rs << RESIZE_STAMP_SHIFT) + 2)
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);//开始扩容
            s = sumCount(); //重新计算 数据量
        }
    }
}

transfer扩容

private final void transfer(Node[] tab, Node[] nextTab) {
    int n = tab.length, stride;
    //计算每个线程负责的区间，单核就单线程
    //否则(n >>> 3) / NCPU。   最小值MIN_TRANSFER_STRIDE = 16
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; 
    if (nextTab == null) {            // 初始化目标数组
        try {
            @SuppressWarnings("unchecked")
            Node[] nt = (Node[])new Node[n << 1]; //2倍扩容
            nextTab = nt;
        } catch (Throwable ex) {      // OOM异常，设置 sizeCtl 返回
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;	//设置 原来数组的长度
    }
    int nextn = nextTab.length; //目标数组长度
    ForwardingNode fwd = new ForwardingNode(nextTab); //创建转移节点
    boolean advance = true;		
    boolean finishing = false; 
    for (int i = 0, bound = 0;;) { //循环直到扩容成功
        Node f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            //如果 寻找的区间 还没有完成
            if (--i >= bound || finishing)//如果完成迁移 那么不需要继续前进
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {//没有可分的区间了，也不需要前进
                i = -1;			
                advance = false;
            }
            //原子分割区间 ：通过操作  transferIndex 变量
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                     //如果可以继续分，获取区间的长度，否则设置0
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;	//获得的区间
                i = nextIndex - 1; //设置开始转移的下标i为nextIndex - 1（
                advance = false;
            }
        }
        //没有可分的区间 || i>=数组长度  || 开始下标+n >= 扩容后的数组长度
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {	//扩容完成
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1); //重新设置sizeCtl 
                return;
            }
            //帮助线程数 - 1
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                //如果 resizeStamp 改变 直接退出
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true;
                i = n; // 开始下标设置为 数组大小
            }
        }
        //如果当前索引下标 i 处没有存放元素，那么将其设置为 fwd = ForwardingNode 
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED)//节点的 hash 值为 MOVED，表示当前节点已经删除
            advance = true; 
        else {
            //对 头节点上锁 避免别的线程在转移期间进行插入操作
            synchronized (f) {
                if (tabAt(tab, i) == f) { //如果头节点没有发生变化  进行转移，否则重试
                    Node ln, hn;
                    if (fh >= 0) {			//当前节点为链表结构
                        int runBit = fh & n;	//获取当前头节点 对原数组长度对应 的 runBit
                        Node lastRun = f; // lastRun 节点
                        //遍历链表 
                        for (Node p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;//当前节点hash & 数组长度 
                             //如果当前节点的b和上一个b不同，将当前节点的b位设置位新的runBit，并且将当前节点p设置为lastRun
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }//runBit = 0，将 lastRun保存 ln
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {//到否则保存 hn
                            hn = lastRun;
                            ln = null;
                        }
                        //从头节点开始遍历，直到 找到 lastRun节点
                        for (Node p = f; p != lastRun; p = p.next) {
                            //当前节点的 hash  key val
                            int ph = p.hash; K pk = p.key; V pv = p.val;
                            if ((ph & n) == 0)//如果 为0 ，那么连接到 ln中
                                ln = new Node(ph, pk, pv, ln);
                            else//否则 hn中
                                hn = new Node(ph, pk, pv, hn);
                        }
                        //ln放入 nextTab 的原理index位置
                        setTabAt(nextTab, i, ln);
                        //hn放入 i + n 
                        setTabAt(nextTab, i + n, hn);
                        //链表已转移 用 fwd 来补填原来的位置
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    else if (f instanceof TreeBin) {//红黑树的情况
                        TreeBin t = (TreeBin)f;
                        TreeNode lo = null, loTail = null;//lo 头节点和 loTail尾节点
                        TreeNode hi = null, hiTail = null;//h 的
                        int lc = 0, hc = 0;
                        //从第一个节点开始遍历	生成 lo  ho 两个链表
                        for (Node e = t.first; e != null; e = e.next) {
                            int h = e.hash;	//当前节点的 hash值
                            TreeNode p = new TreeNode
                                (h, e.key, e.val, null, null);
                            if ((h & n) == 0) {// 为0 的情况 lo链表
                            //将loTail赋值给 prev，如果当前为null，将当前p节点作为lo头节点
                                if ((p.prev = loTail) == null)
                                    lo = p;
                                else// 否则通过 next 变量来构造双向链表
                                    loTail.next = p;
                                loTail = p;
                                ++lc;
                            }
                            else {//hi 链表
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                        //类似于链表  多了判断是否  要不要转回链表
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                            (hc != 0) ? new TreeBin(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin(hi) : t;
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                }
            }
        }
    }
}

helpTransfer方法

多线程帮助resize

final Node[] helpTransfer(Node[] tab, Node f) {
    Node[] nextTab; int sc;
    //数组不为空 && f  ForwardingNode && nextTab不为空 
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode)f).nextTable) != null) {
        int rs = resizeStamp(tab.length); 	// 保存  rs
        //在转移过程中 && 原数组未 改变 && 仍在进行转移 
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            //如果 sc 已经改变   帮助转移线程已达最大   没有可以获取的帮助区间   拜拜 
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            //CAS 增加帮助线程数量   开始帮助
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

treeifyBin

private final void treeifyBin(Node[] tab, int index) {
    Node b; int n, sc;
    //数组长度 <64 的时候 resize 
    if (tab != null) {
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {// 尝试将链表转化为红黑树
            synchronized (b) {	//上锁
                if (tabAt(tab, index) == b) {//当前slot 节点仍未改变
                    TreeNode hd = null, tl = null;
                    //遍历整个链表 生成TreeNode 
                    for (Node e = b; e != null; e = e.next) {
                        TreeNode p =
                            new TreeNode(e.hash, e.key, e.val,
                                              null, null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    // 创建红黑树 并将TreeBin节点放到 数组上
                    setTabAt(tab, index, new TreeBin(hd));
                }
            }
        }
    }
}

remove删除

public V remove(Object key) {
    return replaceNode(key, null, null);
}

// 将节点值替换为v，如果cv非空，则将cv匹配为条件。 如果结果值为空，则删除。  	
final V replaceNode(Object key, V value, Object cv) {
    int hash = spread(key.hashCode());	//计算hash
    for (Node[] tab = table;;) {	//循环
        Node f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0 ||	//数组长度
            (f = tabAt(tab, i = (n - 1) & hash)) == null) //要删除的 k 存在不存在
            break;
        else if ((fh = f.hash) == MOVED)	//如果正在扩容迁移数组，那么帮助
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            boolean validated = false;
            synchronized (f) {
                if (tabAt(tab, i) == f) {	//查找下标 i处节点有没有发生变化
                    if (fh >= 0) {	//链表结构
                        validated = true;
                        //遍历链表
                        for (Node e = f, pred = null;;) {
                            K ek;
                            if (e.hash == hash &&	//当前节点的hash值 与 要删除的 相同
                                ((ek = e.key) == key || //地址相同或者 equals 判断相同
                                 (ek != null && key.equals(ek)))) {
                                V ev = e.val;
                                //cv 为空  比较值 和当前 地址相同  再通过equals方法判断
                                if (cv == null || cv == ev ||
                                    (ev != null && cv.equals(ev))) {
                                    oldVal = ev;	//保存替换掉的值
                                    if (value != null) //替换原来的 V 为空不替换
                                        e.val = value;
                                    else if (pred != null) //删除时 前一个节点是不是根节点
                                        pred.next = e.next;
                                    else//前一个节点为头节点  直接替换原来的头节点
                                        setTabAt(tab, i, e.next);
                                }
                                break;
                            }
                            pred = e;
                            if ((e = e.next) == null)
                                break;
                        }
                    }
                    else if (f instanceof TreeBin) {//红黑树结构
                        validated = true;
                        TreeBin t = (TreeBin)f;//转为 TreeBin
                        TreeNode r, p;
                        //根节点	 找到要删除节点
                        if ((r = t.root) != null &&
                            (p = r.findTreeNode(hash, key, null)) != null) {
                            V pv = p.val;	//获取 val
                            //如果 cv 为空	如上述一样
                            if (cv == null || cv == pv ||
                                (pv != null && cv.equals(pv))) {
                                oldVal = pv;
                                if (value != null)
                                    p.val = value;
                                else if (t.removeTreeNode(p))
                                    //要不要转换成 链表
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    }
                }
            }
            //如果替换或删除的K在hash表中存在
            if (validated) {
                if (oldVal != null) {	//如果找到了替换掉的值
                    if (value == null)		//删除节点
                        addCount(-1L, -1);	//减少节点计数
                    return oldVal;
                }
                break;
            }
        }
    }
    return null;
}

get

public V get(Object key) {
    Node[] tab; Node e, p; int n, eh; K ek;
    int h = spread(key.hashCode());	//计算hash
    //数组检查
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //通过hash 比较
        if ((eh = e.hash) == h) {
            //通过地址和 equals 比较
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val; //找到返回它
        }
        else if (eh < 0)
            // 调用 find 查找
            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;
}

[JDK源码]-J.U.C-ConcurrentHashMap

C/C++/C#相关栏目本月热门文章