ConcurrentHashMap 1.8 源码剖析(超详细)，不懂Java的女朋友们都听懂了

短命女 2023-07-05 10:15 5阅读 0赞

本文主要讨论 1.8 的源码实现，1.7的简单掠过

> ConcurrentHashMap 1.7

底层实现是数组 + 链表 + segment 分段加锁，来保证扩容时候的线程安全

segment 分段加锁，锁定的数据是每个数组节点上的整条链表

ConcurrentHashMap 在1.7中存在的问题 Hash 冲突严重导致节点上的链表过长，到时候遍历链表的效率太低

> ConcurrentHashMap 1.8

底层实现是数组 + 链表或者红黑树 + CAS + synchronized 来保证扩容时候的线程安全

加锁锁住的数据链表上的一个节点，粒度比 1.7 更细

1.8 的 Node<K， V> 节点使用的 volatile 关键字，使用了unSafe方法，通过直接操作内存的方式来保证并发处理的安全性，使用的是硬件的安全机制

##### ConcurrentHashMap原理概览 #####

ConcurrentHashMap 是通过一个 Node<k, v>\[\] 数组来保存添加到 map 中的键值对的，每一个数组下标位置节点是通过链表或者红黑树的形式来存储的

第一次添加元素的时候，map 默认初期长度为16，当往map中继续添加元素的时候，会通过 key 的hash 值和数组长度进行 **与** 操作来获取到应该存储的位置。如果当前位置没有数据，则会插入成为链表的头节点；如果有值则会判断已存在链表上的 key 是否与当前要存入的 key 一致，然后进行对应的替换或者插入操作。在插入数据的时候还会进行红黑树转换和数组扩容的判断，如果当前链表的长度大于 8 并且 map 的长度小于64，则会进行一次扩容，将原有的数据进行散列重排序然后重新计算元素所对应的位置；否则的话只操作当前的链表

扩容的步骤大致为：通过扩容数组的方式将这些节点分开，然后同一个链表中的元素通过hash值和数组长度的 **与** 操作来区分，是放在原来的位置还是放到扩容的长度中；在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。

获取元素的时候就是通过计算hash来确定该元素在数组的哪个位置，然后在通过遍历链表或树来判断key和key的hash，取出value值

##### ConcurrentHashMap 常见参数 #####

// 数组最大扩容长度
    private static final int MAXIMUM_CAPACITY = 1073741824;
    // 数组默认初始化长度
    private static final int DEFAULT_CAPACITY = 16;
    // 数组最大长度
    static final int MAX_ARRAY_SIZE = 2147483639;
    // 负载因子
    private static final float LOAD_FACTOR = 0.75F;
    // 链表转红黑树的长度
    static final int TREEIFY_THRESHOLD = 8;
    // 红黑树转链表的长度
    static final int UNTREEIFY_THRESHOLD = 6;
    // 最小树形化长度
    static final int MIN_TREEIFY_CAPACITY = 64;

##### ConcurrentHashMap源码分析 #####

> put 方法源码解析

public V put(K key, V value) { 
    	return putVal(key, value, false);
    }
    /** * 当添加键值对的时候，首先判断链表数组是否初始化了，如果没有的话就初始化数组 * 然后通过计算hash值来确定元素存放的位置 * 如果当前位置为空则直接添加，如果不为空的话，则取出这个节点来 * 如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容，复制到新的数组，则当前线程也去帮助复制 * 最后一种情况就是，如果这个节点，不为空，也不在扩容，则通过synchronized来加锁，进行添加操作 * 然后判断当前取出的节点位置存放的是链表还是树 * 如果是链表的话，则遍历整个链表，与要放的key进行比较 * 如果key相等，并且key的hash值也相等的话，则说明是同一个key，则覆盖掉value，否则的话则添加到链表的末尾 * 如果是树的话，则调用putTreeVal方法把这个元素添加到树中去 * 最后在添加完成之后，会判断在该节点处共有多少个节点（注意是添加前的个数），如果达到8个以上了的话， * 则调用treeifyBin方法来尝试将处的链表转为树，或者扩容数组 */
    final V putVal(K key, V value, boolean onlyIfAbsent) { 
        if (key == null || value == null) throw new NullPointerException();
        // 获取 key 的 hash 值
        int hash = spread(key.hashCode());
        int binCount = 0;//用来计算在这个节点总共有多少个元素，用来控制扩容或者转移为树
        for (Node<K,V>[] tab = table;;) { 
            Node<K,V> f; int n, i, fh;
            // 如果数组为null 或者 长度为0，则初始化数组
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            // 否则根据当前数组的长度和要插入元素的 key 进行 与 操作，来判断是否有 hash 冲突
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 
            	// 说明没有 hash 冲突，即当前位置没有对应的元素，使用 cas 方式进行添加，不加锁
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            // 如果有 hash 冲突，则判断当前的节点是否处于 MOVED 过程，即扩容复制数组过程
            // 则当前线程也会参与去复制，通过允许多线程复制的功能，一次来减少数组的复制所带来的性能损失
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else { 
            	/** * 如果在这个位置有元素的话，就采用synchronized的方式加锁， * 判断当前位置的存储形式是链表还是红黑树 * 如果是链表的话(hash大于0)，就对这个链表的所有元素进行遍历， * 如果找到了key和key的hash值都一样的节点，则把它的值替换到 * 如果没找到的话，则添加在链表的最后面 * 否则，是树的话，则调用putTreeVal方法添加到树中去 * * 在链表添加完之后，如果当前节点的数量在8个以上的话，则转化为树或扩容 */
                V oldVal = null;
                synchronized (f) { 
                	// 再次取出要存储的位置的元素，跟前面取出来的比较
                    if (tabAt(tab, i) == f) { 
                    	// 取出来的元素的hash值大于0，当转换为树之后，hash值为-2
                        if (fh >= 0) { 
                            binCount = 1;
                            // 遍历整个链表
                            for (Node<K,V> e = f;; ++binCount) { 
                                K ek;
                                // 要存的元素的hash，key跟要存储的位置的节点的相同的时候，替换掉该节点的value即可
                                if (e.hash == hash && ((ek = e.key) == key || 
                                (ek != null && key.equals(ek)))) { 
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                // 如果不是同样的hash，同样的key的时候，则判断该节点的下一个节点是否为空
                                // 为空的话把这个要加入的节点设置为当前节点的下一个节点
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) { 
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        // 如果不是链表而是红黑树，则通过红黑树的方式进行插入
                        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;
                            }
                        }
                    }
                }
                // binCount 用来记录节点存储的位置节点长度，如果大于8则扩张数组或将给节点的数据转为tree
                if (binCount != 0) { 
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
    
    /** * 链表转换为红黑树：当数组长度小于64的时候，扩张数组长度一倍，否则的话把链表转为树 * 扩容的时候并没有加锁 * 红黑树转换的时候加锁 */
    private final void treeifyBin(Node<K,V>[] tab, int index) { 
        Node<K,V> b; int n, sc;
        if (tab != null) { 
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            	// 扩容，不加锁
                tryPresize(n << 1);
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { 
            	// 使用synchronized同步器，将该节点出的链表转为树
                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;
                        }
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }

> get 方法源码解析

/** * get支持并发操作， * 当key为null的时候回抛出NullPointerException的异常 * get操作通过首先计算key的hash值来确定该元素放在数组的哪个位置 * 然后遍历该位置的所有节点 * 如果不存在的话返回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) { 
            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;
    }