概要

我们在上一篇对HashTable进行了原理解析，再加上之前我们对HashMap的原理解析，这篇对ConcurrentHashMap的解析可称为数据结构解析三步曲了。

在这里我们也来总结一下他们的特点:

• HashMap采用数组+链表+红黑树方式实现,提高查找效率;它永远长度是2的整倍数，可能出现hash冲突造成get出现死循环，在多线程下无法保证数据安全。
• HashTable采用数组+链表的方式实现,采用Synchronized关键字锁方法的方式锁住了整个table来保证在多线程下的数据安全,但这样无疑使执行效率变得低下
• ConcurrentHashMap采用数组+链表+红黑树的方式实现,采用Synchronized关键字实现分段锁技术降低锁的颗粒度，利用多个锁控制多个私有的小table,来保证多线程下的数据安全,提高执行效率.

让你能清晰的了解三者的区别:

散列表	实现方式	数据安全	数据安全实现方式	key\value是否可为Null
HashMap	数组+单向链表+红黑树	不安全	无	可为Null
HashTable	数组+单向链表	安全	Synchronized	不可为 Null
ConcurrentHashMap	数组+单向链表+红黑树	安全	Synchronized实现分段锁技术	不可为 Null

ConcurrentHashMap

1.继承关系

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

2.常量&构造方法

    //ConcurrentHashMap容量极限
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    //ConcurrentHashMap容量初始大小
    private static final int DEFAULT_CAPACITY = 16;
    //数组容量极限
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //默认并发级别
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    //默认负载因子大小
    private static final float LOAD_FACTOR = 0.75f;
    //链表转红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;
    //节点数小于等6保持单向链表状态
    static final int UNTREEIFY_THRESHOLD = 6;
    //红黑树容量最小64
    static final int MIN_TREEIFY_CAPACITY = 64;
    //每个转移步骤的最小复归数
    private static final int MIN_TRANSFER_STRIDE = 16;
    private static final int RESIZE_STAMP_BITS = 16;
    //可以帮助调整大小的最大线程数
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    //记录生成戳的偏移位
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
    //控制table初始化和扩容的标记量
    //-1时 表示 正在初始化或正在扩容
   //-(1+n) 表示 活动调整的线程数量
    private transient volatile int sizeCtl;

    //节点hash字段编码
    static final int MOVED     = -1; // 转发节点的hash
    static final int TREEBIN   = -2; // hash树的根
    static final int RESERVED  = -3; // 临时保留的hash
    static final int HASH_BITS = 0x7fffffff; //普通节点hash的可用位
 //默认构造方法
 public ConcurrentHashMap() {
 }
 //指定初始化容量大小
 public ConcurrentHashMap(int initialCapacity) {
        //若指定的容量小于0 则抛出IllegalArgumentException异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        //获取table容量
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }
 //指定初始容量大小 & 指定负载因子大小
 public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }
 //指定初始容量大小 & 指定负载因子大小 & 估算更新线程的并发数目
 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;
    }
//传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
 public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;
        putAll(m);
    }

3.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;
        }

        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 Helpers.mapEntryToString(key, val);
        }
        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;
        }
    }

4.TreeNode红黑树实现

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;
        }

        Node<K,V> find(int h, Object k) {
            return findTreeNode(h, k, 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;
                    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;
        }
    }

5.spread的计算实现

将(XORs)较高的哈希值向较低的哈希值扩展(XORs)，并强制执行将最高位置0

 static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
 }

6.ConcurrentHashMap put的源码实现

public V put(K key, V value) {
        return putVal(key, value, false);
    }

final V putVal(K key, V value, boolean onlyIfAbsent) {
        //key 和 value 不可为Null,若为null则将抛出 NullPointerException异常
        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;
            //判定tab为Null 或 长度为0
            if (tab == null || (n = tab.length) == 0)
                //初始化tab
                tab = initTable();
             //通过执行tabAt函数寻找tab索引下的Entry
            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
            }
            else if ((fh = f.hash) == MOVED) 
                tab = helpTransfer(tab, f); //在调整大小过程中帮助转移
            else {
                V oldVal = null;
                synchronized (f) { //对tab中一个节点加锁，这个锁锁在Entry的根节点上的
                    if (tabAt(tab, i) == f) { //做判定 若tab中第i个元素 等于 f节点
                       //此判定若成功 说明f节点下是一个普通节点 即链表节点
                        if (fh >= 0) {
                            binCount = 1;
                             //遍历整个链表
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                //判定若成功则修改节点下的value值
                                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;
                                 //若指向的下一个节点为null
                                if ((e = e.next) == null) {
                                    //new出一个新节点进行插入 此处即我们存储put进来的值的新索引位置
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        //若 f类型TreeBin 黑红树
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                             //执行putTreeValue方法进行添加或查询节点操作
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                        else if (f instanceof ReservationNode)
                            throw new IllegalStateException("Recursive update");
                    }
                }
                if (binCount != 0) {
                     //当节点长度大于等于8时
                    if (binCount >= TREEIFY_THRESHOLD)
                        //将原来的链表存储方式转换为黑红树存储
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

梳理以下ConcurrentHashTable put函数的执行过程

• 1.key 和 value 不可为Null,若为null则将抛出 NullPointerException异常
• 2.判定tab为Null 或 长度为0 判定成功则初始化table
• 3.否则 通过执行tabAt函数寻找tab索引下的Entry若为空 则判定是否需要比较并进行交换
• 4.若tabAt函数寻找tab索引下的Entry不为空 则判定f.hash是否为MOVE 若判定成功 则在调整tab大小过程中帮助转移
• 5.1.若以上条件都不成立 则 对tab中一个节点加锁，这个锁锁在Entry的根节点上的
• 5.1.1 做判定 若tab中第i个元素 等于 f节点 此判定若成功 说明f节点下是一个普通节点 即链表节点
• 5.1.1.1 遍历整个链表,查找符合条件的节点修改节点下的值
• 5.1.2 若 f类型TreeBin 黑红树 则执行putTreeValue方法进行添加或查询节点操作
• 5.2 当节点长度大于等于8时 将原来的链表存储方式转换为黑红树存储
• 6.添加到总数中,若容量小则进行扩容

7.ConcurrentHashMap get的源码实现

public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        //计算hash值
        int h = spread(key.hashCode());
         //table 不为null & table长度大于0 & table索引位置下的Entry不为null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            //做判定Hash匹配成功
            if ((eh = e.hash) == h) {
                //key的匹配成功
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    //返回节点下的vlaue
                    return e.val;
            }
            else if (eh < 0)  //hash节点小于0
                 //使用find函数在单向链表中查找value
                return (p = e.find(h, key)) != null ? p.val : null;
             //通过while循环,遍历e下的子节点查找value
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

8.ConcurrentHashMap treeifyBin的源码实现

单向链表转为黑红树

private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n;
         //判定单向链表不为null
        if (tab != null) {
            //判定tab长度若小于黑红树最小长度
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                //对黑红树进行扩容
                tryPresize(n << 1);
             //tab指定索引下数据不为null & hash值大于0 
             //这里将tab赋给b 原因是为下面Synchronized准备的
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
               //加锁 锁住了b 是为了降低锁的颗粒度
                synchronized (b) {
                    if (tabAt(tab, index) == b) {
                        TreeNode<K,V> hd = null, tl = null;
                         //遍历b下的节点
                        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指定的索引设置进以hd为头部节点的TreeBin中
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }

梳理以下ConcurrentHashTable treeifyBin函数的执行过程

• 1.判定黑红树是否需要扩容
• 2. tab指定索引下数据不为null & hash值大于0，这里将tab赋给b 原因是为下面Synchronized准备的
• 2.1加锁 锁住了b 是为了降低锁的颗粒度
• 2.3 遍历b下的节点，新建黑红树节点
• 2.4 将上一个子节点设置成下一个节点的父节点，设置下一个节点，设置子节点
• 2.5 将tab指定的索引设置进以hd为头部节点的TreeBin中

9.ConcurrentHashMap initTable的源码实现

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(); // 让出线程执行资源
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;//指定数组大小
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

This ALL! Thanks EveryBody!