美文网首页
源码阅读 - ConcurrentHashMap

源码阅读 - ConcurrentHashMap

作者: 烟小花飞花 | 来源:发表于2018-05-29 11:18 被阅读0次

    0. ConcurrentHashMap是什么

    • key和value都不能为null,和HashTable一样
    • 默认大小为16,扩容时为2的幂,扩容阈值为0.75*cap
    • 节点相同的标准为hash相等并且k1==k2 || k1.equals(k2)

    1. 实现的本质

    • 数组+链表+红黑树
    • volatile + CAS

    2. 常用api解析

    2.0 重要子类解析

    Node节点,数组的元素类型

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        Node(int hash, K key, V val, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }
    

    TreeBin:放在tab[i]位置的节点,当该节点的内容是红黑树时使用,其中:

    • root:红黑树的根节点
    • first:链表的头节点
    static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;
        volatile TreeNode<K,V> 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
        ...
    }
    
    //红黑树的节点
    static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next,
                 TreeNode<K,V> parent) {
            super(hash, key, val, next);
            this.parent = parent;
        }
    }
    

    Forwarding节点,扩容时把旧表的tab[i]位置移动到新表后,在旧表的i位置插入该节点。

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

    2.1 构造函数

    public ConcurrentHashMap()
    public ConcurrentHashMap(int initialCapacity)
    public ConcurrentHashMap(Map<? extends K, ? extends V> m)
    public ConcurrentHashMap(int initialCapacity, float loadFactor)
    public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
    

    2.2 initTable初始化

    初始化只能由一个线程进行,抢占到的线程将sizeCtl设为-1,未抢占到的线程进行yield()操作。初始化完成之后sizeCtl的值为0.75*n

    /**
     * Initializes table, using the size recorded in sizeCtl.
     */
    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            //sc小于0表示未抢占到,自旋
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            //抢占到的线程把sizeCtl置为-1,防止其他线程进入
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        //默认大小为16
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        //写入table
                        table = tab = nt;
                        //写入sc=0.75*n
                        sc = n - (n >>> 2);
                    }
                } finally {
                    //table初始化完成后,写入正确的sizeCtl
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }
    

    2.3 数组元素原子操作

    arrayBaseOffset获取数组中第一个元素的偏移地址。即数组对象头的偏移距离。
    arrayIndexScale获取数组中每一个元素的大小。
    2^n = scale,则ASHIFT = n
    i<<ASHIFT = i * 2^ASHIFT = i * scale
    所以((long)i << ASHIFT) + ABASE=i * scale + ABASE即为内存中元素的真实位置。
    使用getObjectVolatile putObjectVolatile是为了保证读写原子性,同时直接读写到内存而不是线程缓存。

    ...
    private static final long ABASE;
    private static final int ASHIFT;
    ...
    ABASE = U.arrayBaseOffset(ak);
    int scale = U.arrayIndexScale(ak);
    if ((scale & (scale - 1)) != 0)
        throw new Error("data type scale not a power of two");
    // 2^ASHIFT = scale
    ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
    
    @SuppressWarnings("unchecked")
    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);
    }
    //参数分别为 table数组、index、expect、update
    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);
    }
    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }
    

    2.4 put方法

    /**
     * Maps the specified key to the specified value in this table.
     * Neither the key nor the value can be null.
     *
     * <p>The value can be retrieved by calling the {@code get} method
     * with a key that is equal to the original key.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with {@code key}, or
     *         {@code null} if there was no mapping for {@code key}
     * @throws NullPointerException if the specified key or value is null
     */
    public V put(K key, V value) {
        return putVal(key, value, false);
    }
    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        //key和value都不能为null
        if (key == null || value == null) throw new NullPointerException();
        //将key的hash无符号右移16位,然后与其本身异或,再将符号位置0
        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();
            //如果tab[i]是空,使用原子操作更新,不加锁
            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
            }
            //如果当前节点是一个fwd节点,则本线程帮助完成扩容
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                //锁住tab[i]位置的第一个元素,相当于锁住tab[i]整个位置
                synchronized (f) {
                    //检查tab[i]位置元素有无变化
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                //如果节点已经存储过(key和hash分别相等)
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    //如果onlyIfAbsent为false,更新
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                //tab[i]位置的链表上没有元素,则插入到链表最后
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        //如果f是红黑树的根节点
                        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) {
                    //如果链表上的节点大于等于8个,转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
    
    //将key的hash无符号右移16位,然后与其本身异或,再将符号位置0
    //目的是为了减少hash冲突,使分布更均匀
    static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }
    

    helpTransfer方法,如果正在扩容,则帮助进行扩容:

    /**
     * Helps transfer if a resize is in progress.
     */
    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        Node<K,V>[] nextTab; int sc;
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                //多一个线程帮助扩容时,sc+1
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }
    

    红黑树节点的put方法:

    /**
     * Finds or adds a node.
     * @return null if added
     */
    //红黑树中添加节点,如果是添加加点返回null,如果是更新节点返回旧节点
    final TreeNode<K,V> putTreeVal(int h, K k, V v) {
        Class<?> kc = null;
        boolean searched = false;
        for (TreeNode<K,V> p = root;;) {
            int dir, ph; K pk;
            //如果根节点是空,新建根节点
            if (p == null) {
                first = root = new TreeNode<K,V>(h, k, v, null, null);
                break;
            }
            //先比较hash
            else if ((ph = p.hash) > h)
                dir = -1;
            else if (ph < h)
                dir = 1;
            //hash相等时比较key
            else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                return p;
            //hash相等,但是key不等
            else if ((kc == null &&
                      (kc = comparableClassFor(k)) == null) ||
                     (dir = compareComparables(kc, k, pk)) == 0) {
                //如果key没实现Comparable<K>接口,或者compareTo()方法返回0
                if (!searched) {
                    TreeNode<K,V> q, ch;
                    searched = true;
                    if (((ch = p.left) != null &&
                         (q = ch.findTreeNode(h, k, kc)) != null) ||
                        ((ch = p.right) != null &&
                         (q = ch.findTreeNode(h, k, kc)) != null))
                        return q;
                }
                //决胜局,使用系统的hash值比较,若还有相等,dir=-1
                dir = tieBreakOrder(k, pk);
            }
            TreeNode<K,V> xp = p;
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
                //在树中找到插入的位置,链表中放到链表头部
                TreeNode<K,V> x, f = first;
                first = x = new TreeNode<K,V>(h, k, v, f, xp);
                if (f != null)
                    f.prev = x;
                if (dir <= 0)
                    xp.left = x;
                else
                    xp.right = x;
                //如果父节点是黑色,x设为红色
                if (!xp.red)
                    x.red = true;
                //如果父节点是红色,进行调整
                else {
                    lockRoot();
                    try {
                        //按照红黑树的规则进行调整
                        root = balanceInsertion(root, x);
                    } finally {
                        unlockRoot();
                    }
                }
                break;
            }
        }
        assert checkInvariants(root);
        return null;
    }
    

    检查key是否实现了Comparable<Key>接口:

    /**
     * Returns x's Class if it is of the form "class C implements
     * Comparable<C>", else null.
     */
    static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
            //如果是string,直接返回
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            //获取c实现的全部接口
            if ((ts = c.getGenericInterfaces()) != null) {
                for (int i = 0; i < ts.length; ++i) {
                    //如果是参数化类型,并且原始类型是Comparable,参数只有一个,且为c
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                        ((p = (ParameterizedType)t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }
    

    以指定的节点为根,在树种查找key节点,未找到返回null:

    /**
     * Returns the TreeNode (or null if not found) for the given key
     * starting at given root.
     */
    final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
        if (k != null) {
            TreeNode<K,V> p = this;
            do  {
                int ph, dir; K pk; TreeNode<K,V> q;
                TreeNode<K,V> pl = p.left, pr = p.right;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                //如果key实现了Comparable<K>接口,并且compareTo()方法返回值不为0
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                //递归查找右子树
                else if ((q = pr.findTreeNode(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
        }
        return null;
    }
    

    进行红黑树平衡调整时,先锁住树根:

    /**
     * Acquires write lock for tree restructuring.
     */
    private final void lockRoot() {
        if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
            contendedLock(); // offload to separate method
    }
    /**
     * Releases write lock for tree restructuring.
     */
    private final void unlockRoot() {
        lockState = 0;
    }
    /**
     * Possibly blocks awaiting root lock.
     */
    private final void contendedLock() {
        boolean waiting = false;
        for (int s;;) {
            //lockState为0或WAITER时,抢占
            if (((s = lockState) & ~WAITER) == 0) {
                if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                    if (waiting)
                        waiter = null;
                    return;
                }
            }
            //如果WAITER位为0,将WAITER位置1
            else if ((s & WAITER) == 0) {
                if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                    waiting = true;
                    waiter = Thread.currentThread();
                }
            }
            else if (waiting)
                LockSupport.park(this);
        }
    }
    

    2.5 get方法

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code key.equals(k)},
     * then this method returns {@code v}; otherwise it returns
     * {@code null}.  (There can be at most one such mapping.)
     *
     * @throws NullPointerException if the specified key is null
     */
    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) {
            //如果tab[i]就是要查找的节点
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            //如果是特殊节点,用find方法
            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;
    }
    

    Node节点调用find方法有3种情况:

    • MOVED: ForwardingNode
    • TREEBIN: TreeBin
    • RESERVED: ReservationNode
      都继承了Node类,在子类中分别重写了find方法

    2.6 remove方法

    /**
     * Removes the key (and its corresponding value) from this map.
     * This method does nothing if the key is not in the map.
     *
     * @param  key the key that needs to be removed
     * @return the previous value associated with {@code key}, or
     *         {@code null} if there was no mapping for {@code key}
     * @throws NullPointerException if the specified key is null
     */
    public V remove(Object key) {
        return replaceNode(key, null, null);
    }
    /**
     * Implementation for the four public remove/replace methods:
     * Replaces node value with v, conditional upon match of cv if
     * non-null.  If resulting value is null, delete.
     */
    final V replaceNode(Object key, V value, Object cv) {
        int hash = spread(key.hashCode());
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            //如果tab是空,或者tab[i]位置为空,结束
            if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
                break;
            //如果tab[i]位置是fwd节点,参与扩容
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                boolean validated = false;
                //锁住tab[i]位置
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        //普通节点
                        if (fh >= 0) {
                            validated = true;
                            for (Node<K,V> e = f, pred = null;;) {
                                K ek;
                                //链表循环往后查找,如果找到
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    V ev = e.val;
                                    if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                        oldVal = ev;
                                        //如果新值不为空,替换
                                        if (value != null)
                                            e.val = value;
                                        //如果不是tab[i]位置的第一个节点,删除节点
                                        else if (pred != null)
                                            pred.next = e.next;
                                        //如果是tab[i]位置的第一个节点,原子替换
                                        else
                                            setTabAt(tab, i, e.next);
                                    }
                                    break;
                                }
                                //往链表后查找
                                pred = e;
                                if ((e = e.next) == null)
                                    break;
                            }
                        }
                        //如果是红黑树
                        else if (f instanceof TreeBin) {
                            validated = true;
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> r, p;
                            //如果找到节点
                            if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) {
                                V pv = p.val;
                                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));
                                }
                            }
                        }
                    }
                }
                if (validated) {
                    if (oldVal != null) {
                        if (value == null)
                            addCount(-1L, -1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        return null;
    }
    

    2.7 扩容方法

    如果tab[i]位置的节点超过8个,转换成红黑树

    /**
     * Replaces all linked nodes in bin at given index unless table is
     * too small, in which case resizes instead.
     */
    private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            //如果长度小于64,扩容
            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) {
                        TreeNode<K,V> hd = null, tl = null;
                        //转为双向链表
                        for (Node<K,V> e = b; e != null; e = e.next) {
                            TreeNode<K,V> p =
                                new TreeNode<K,V>(e.hash, e.key, e.val,
                                                  null, null);
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;
                            tl = p;
                        }
                        //把红黑树放到tab[i]位置
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }
    

    扩大table的长度:

    /**
     * Tries to presize table to accommodate the given number of elements.
     *
     * @param size number of elements (doesn't need to be perfectly accurate)
     */
    private final void tryPresize(int size) {
        int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
            tableSizeFor(size + (size >>> 1) + 1);
        int sc;
        while ((sc = sizeCtl) >= 0) {
            Node<K,V>[] tab = table; int n;
            //未初始化,进行初始化
            if (tab == null || (n = tab.length) == 0) {
                n = (sc > c) ? sc : c;
                if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                    try {
                        if (table == tab) {
                            @SuppressWarnings("unchecked")
                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                            table = nt;
                            sc = n - (n >>> 2);
                        }
                    } finally {
                        sizeCtl = sc;
                    }
                }
            }
            else if (c <= sc || n >= MAXIMUM_CAPACITY)
                break;
            else if (tab == table) {
                int rs = resizeStamp(n);
                if (sc < 0) {
                    Node<K,V>[] nt;
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    //多一个线程进行扩容操作,sc+1
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                //实际进行扩容的路径
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
            }
        }
    }
    

    把双向链表转为红黑树:

    /**
     * Creates bin with initial set of nodes headed by b.
     */
    TreeBin(TreeNode<K,V> b) {
        super(TREEBIN, null, null, null);
        this.first = b;
        TreeNode<K,V> r = null;
        for (TreeNode<K,V> x = b, next; x != null; x = next) {
            next = (TreeNode<K,V>)x.next;
            x.left = x.right = null;
            //如果根为空
            if (r == null) {
                x.parent = null;
                x.red = false;
                r = x;
            }
            else {
                K k = x.key;
                int h = x.hash;
                Class<?> kc = null;
                for (TreeNode<K,V> p = r;;) {
                    int dir, ph;
                    K pk = p.key;
                    //确定节点x的插入方向
                    if ((ph = p.hash) > h)
                        dir = -1;
                    else if (ph < h)
                        dir = 1;
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);
                        TreeNode<K,V> xp = p;
                    //插入节点x
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
                        //调整红黑树
                        r = balanceInsertion(r, x);
                        break;
                    }
                }
            }
        }
        this.root = r;
        assert checkInvariants(root);
    }
    

    并行扩容transfer方法:

    • 每个线程每次处理stride个元素。
    • 索引ibound时,本线程本次处理完成,i0时,整体数组处理完成,更新tablesizeCtl的值。
    • 多一个线程进行扩容操作时,sc+1,完成后每个线程sc-1
    /**
     * Moves and/or copies the nodes in each bin to new table. See
     * above for explanation.
     */
    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        int n = tab.length, stride;
        //stride最小为16
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        if (nextTab == null) {            // initiating
            try {
                //新表扩容的大小为2*n
                @SuppressWarnings("unchecked")
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab;
            transferIndex = n;
        }
        int nextn = nextTab.length;
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        boolean advance = true;
        boolean finishing = false; // to ensure sweep before committing nextTab
        for (int i = 0, bound = 0;;) {
            Node<K,V> f; int fh;
            while (advance) {
                int nextIndex, nextBound;
                //判断是否到本线程处理的边界
                if (--i >= bound || finishing)
                    advance = false;
                //判断是否到table的边界
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                //读取本线程本次需要处理的部分,即i到bound部分
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            //i<0说明table数组整体处理完了
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                //结束处理,赋值table和sizeCtl
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            else {
                //锁住tab[i]位置的节点f
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        Node<K,V> ln, hn;
                        //如果是链表节点
                        if (fh >= 0) {
                            int runBit = fh & n;
                            Node<K,V> lastRun = f;
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            //循环完成后lastRun后面的节点与lastRun在新table中在一个格子
                            //感觉这一趟循环没有什么意义啊?反正后面还要循环一趟
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            //重新遍历tab[i]位置的链表,第n位为0的放到ln头部,为1的放到hn头部
                            for (Node<K,V> p = f; p != lastRun; p = p.next) {
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                if ((ph & n) == 0)
                                    ln = new Node<K,V>(ph, pk, pv, ln);
                                else
                                    hn = new Node<K,V>(ph, pk, pv, hn);
                            }
                            //把ln和hn分别放到新表的i和i+n位置
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            //旧表的i位置标为MOVED
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                        //如果是红黑树节点
                        else if (f instanceof TreeBin) {
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> lo = null, loTail = null;
                            TreeNode<K,V> hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            //红黑树的所有节点同时也在一个双向链表上
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode<K,V> p = new TreeNode<K,V>
                                    (h, e.key, e.val, null, null);
                                //第n位为0时放在lo后
                                if ((h & n) == 0) {
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                //第n位为1时放在hi后
                                else {
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            //新的链表如果少于6个,转为单链表,否则转为红黑树,如果另外一个链是空的,直接把原来的t放过去
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin<K,V>(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin<K,V>(hi) : t;
                            //把ln和hn分别放入新表的i和i+n位置
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            //旧表的i位置设为MOVED
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }
    

    3. 总结

    • 默认大小16,每次扩容时为原来的2倍,扩容阈值为0.75*n
    • 指定初始化大小时,容量为大于指定数的最小的2的幂,由tableSizeFor()方法实现
    • table长度大于64,并且单个位置的节点数大于8个,会将该位置转为红黑树,否则只是扩大table的长度
    • 在进行写操作时,每次只锁tab[i]位置,不是整表上锁
    • sizeCtl比较难理解
      • -1是表示在初始化,初始化只能由一个线程进行,其他线程yield()操作,在initTable()方法中
      • 0x80xx00xx时(即resizeStamp(n)<<RESIZE_STAMP_SHIFT+2),表示在扩容操作,在tryPresize()方法中
      • 0x80xx00xx时(上种情况下+n),表示并发扩容操作,每多一个线程,进行sizeCtl+1操作,在putVal() remove()方法中,节点为REMOVED情况下,完成扩容操作后,每退出一个线程,进行sizeCtl-1操作,直到(sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT,表示最后一个线程完成,在transfer()方法中

    4. 参考

    1. ConcurrentHashMap源码build 1.8.0_121-b13版本
    2. Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析
    3. ConcurrentHashMap总结
    4. 二叉树 - 红黑树

    相关文章

      网友评论

          本文标题:源码阅读 - ConcurrentHashMap

          本文链接:https://www.haomeiwen.com/subject/khbcdftx.html