勿忘初心

个人签名

530篇博客

ConcurrentHashMap源码解析(1)

勿忘初心2018-12-19 15:56

此文已由作者赵计刚授权网易云社区发布。

欢迎访问网易云社区,了解更多网易技术产品运营经验。


注:在看这篇文章之前,如果对HashMap的层不清楚的话,建议先去看看HashMap源码解析。

http://www.cnblogs.com/java-zhao/p/5106189.html

1、对于ConcurrentHashMap需要掌握以下几点

  • Map的创建:ConcurrentHashMap()
  • 往Map中添加键值对:即put(Object key, Object value)方法
  • 获取Map中的单个对象:即get(Object key)方法
  • 删除Map中的对象:即remove(Object key)方法
  • 判断对象是否存在于Map中:containsKey(Object key)
  • 遍历Map中的对象:即keySet().iterator(),在实际中更常用的是增强型的for循环去做遍历

2、ConcurrentHashMap的创建

注:在往下看之前,心里先有这样一个映像:ConcurrentHashMap的数据结构:一个指定个数的Segment数组,数组中的每一个元素Segment相当于一个HashTable

2.1、使用方法:

Map<String, Object> map = new ConcurrentHashMap<String, Object>();

2.2、源代码:

 ConcurrentHashMap相关属性:

    /**
     * 用于分段
     */
    // 根据这个数来计算segment的个数,segment的个数是仅小于这个数且是2的几次方的一个数(ssize)
    static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    // 最大的分段(segment)数(2的16次方)
    static final int MAX_SEGMENTS = 1 << 16;
    
    /**
     * 用于HashEntry
     */
    // 默认的用于计算Segment数组中的每一个segment的HashEntry[]的容量,但是并不是每一个segment的HashEntry[]的容量
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    // 默认的加载因子(用于resize)
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 用于计算Segment数组中的每一个segment的HashEntry[]的最大容量(2的30次方)
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * segments数组
     * 每一个segment元素都看做是一个HashTable
     */
    final Segment<K, V>[] segments;
    
    /**
     * 用于扩容
     */
    final int segmentMask;// 用于根据给定的key的hash值定位到一个Segment
    final int segmentShift;// 用于根据给定的key的hash值定位到一个Segment

Segment类(ConcurrentHashMap的内部类)

    /**
     * 一个特殊的HashTable
     */
    static final class Segment<K, V> extends ReentrantLock implements
            Serializable {

        private static final long serialVersionUID = 2249069246763182397L;

        transient volatile int count;// 该Segment中的包含的所有HashEntry中的key-value的个数
        transient int modCount;// 并发标记

        /*
         * 元素个数超出了这个值就扩容 threshold==(int)(capacity * loadFactor)
         * 值得注意的是,只是当前的Segment扩容,所以这是Segment自己的一个变量,而不是ConcurrentHashMap的
         */
        transient int threshold;
        transient volatile HashEntry<K, V>[] table;// 链表数组
        final float loadFactor;

        /**
         * 这里要注意一个很不好的编程习惯,就是小写l,容易与数字1混淆,所以最好不要用小写l,可以改为大写L
         */
        Segment(int initialCapacity, float lf) {
            loadFactor = lf;//每个Segment的加载因子
            setTable(HashEntry.<K, V> newArray(initialCapacity));
        }

        /**
         * 创建一个Segment数组,容量为i
         */
        @SuppressWarnings("unchecked")
        static final <K, V> Segment<K, V>[] newArray(int i) {
            return new Segment[i];
        }

        /**
         * Sets table to new HashEntry array. Call only while holding lock or in
         * constructor.
         */
        void setTable(HashEntry<K, V>[] newTable) {
            threshold = (int) (newTable.length * loadFactor);// 设置扩容值
            table = newTable;// 设置链表数组
        }

说明:只列出了Segement的全部属性和创建ConcurrentHashMap时所用到的方法。

HashEntry类(ConcurrentHashMap的内部类)

    /**
     * Segment中的HashEntry节点 类比HashMap中的Entry节点
     */
    static final class HashEntry<K, V> {
        final K key;// 键
        final int hash;//hash值
        volatile V value;// 实现线程可见性
        final HashEntry<K, V> next;// 下一个HashEntry

        HashEntry(K key, int hash, HashEntry<K, V> next, V value) {
            this.key = key;
            this.hash = hash;
            this.next = next;
            this.value = value;
        }

        /*
         * 创建HashEntry数组,容量为传入的i
         */
        @SuppressWarnings("unchecked")
        static final <K, V> HashEntry<K, V>[] newArray(int i) {
            return new HashEntry[i];
        }
    }

ConcurrentHashMap(int initialCapacity,float loadFactor,int concurrencyLevel)

 1     /**
 2      * 创建ConcurrentHashMap
 3      * @param initialCapacity 用于计算Segment数组中的每一个segment的HashEntry[]的容量, 但是并不是每一个segment的HashEntry[]的容量
 4      * @param loadFactor
 5      * @param concurrencyLevel 用于计算Segment数组的大小(可以传入不是2的几次方的数,但是根据下边的计算,最终segment数组的大小ssize将是2的几次方的数)
 6      * 
 7      * 步骤:
 8      * 这里以默认的无参构造器参数为例,initialCapacity==16,loadFactor==0.75f,concurrencyLevel==16
 9      * 1)检查各参数是否符合要求
10      * 2)根据concurrencyLevel(16),计算Segment[]的容量ssize(16)与扩容移位条件sshift(4)
11      * 3)根据sshift与ssize计算将来用于定位到相应Segment的参数segmentShift与segmentMask
12      * 4)根据ssize创建Segment[]数组,容量为ssize(16)
13      * 5)根据initialCapacity(16)与ssize计算用于计算HashEntry[]容量的参数c(1)
14      * 6)根据c计算HashEntry[]的容量cap(1)
15      * 7)根据cap与loadFactor(0.75)为每一个Segment[i]都实例化一个Segment
16      * 8)每一个Segment的实例化都做下面这些事儿:
17      * 8.1)为当前的Segment初始化其loadFactor为传入的loadFactor(0.75)
18      * 8.2)创建一个HashEntry[],容量为传入的cap(1)
19      * 8.3)根据创建出来的HashEntry的容量(1)和初始化的loadFactor(0.75),计算扩容因子threshold(0)
20      * 8.4)初始化Segment的table为刚刚创建出来的HashEntry
21      */
22     public ConcurrentHashMap(int initialCapacity,float loadFactor,int concurrencyLevel) {
23         // 检查参数情况
24         if (loadFactor <= 0f || initialCapacity < 0 || concurrencyLevel <= 0)
25             throw new IllegalArgumentException();
26 
27         if (concurrencyLevel > MAX_SEGMENTS)
28             concurrencyLevel = MAX_SEGMENTS;
29 
30         /**
31          * 找一个能够正好小于concurrencyLevel的数(这个数必须是2的几次方的数)
32          * eg.concurrencyLevel==16==>sshift==4,ssize==16
33          * 当然,如果concurrencyLevel==15也是上边这个结果
34          */
35         int sshift = 0;
36         int ssize = 1;// segment数组的长度
37         while (ssize < concurrencyLevel) {
38             ++sshift;
39             ssize <<= 1;// ssize=ssize*2
40         }
41 
42         segmentShift = 32 - sshift;// eg.segmentShift==32-4=28 用于根据给定的key的hash值定位到一个Segment
43         segmentMask = ssize - 1;// eg.segmentMask==16-1==15 用于根据给定的key的hash值定位到一个Segment
44         this.segments = Segment.newArray(ssize);// 构造出了Segment[ssize]数组 eg.Segment[16]
45 
46         /*
47          * 下面将为segment数组中添加Segment元素
48          */
49         if (initialCapacity > MAXIMUM_CAPACITY)
50             initialCapacity = MAXIMUM_CAPACITY;
51         int c = initialCapacity / ssize;// eg.initialCapacity==16,c==16/16==1
52         if (c * ssize < initialCapacity)// eg.initialCapacity==17,c==17/16=1,这时1*16<17,所以c=c+1==2
53             ++c;// 为了少执行这一句,最好将initialCapacity设置为2的几次方
54         int cap = 1;// 每一个Segment中的HashEntry[]的初始化容量
55         while (cap < c)
56             cap <<= 1;// 创建容量
57 
58         for (int i = 0; i < this.segments.length; ++i)
59             // 这一块this.segments.length就是ssize,为了不去计算这个值,可以直接改成i<ssize
60             this.segments[i] = new Segment<K, V>(cap, loadFactor);
61     }

注意:这个方法里边我在头部所写的注释非常重要,在这块注释写明了:

  • 每一个参数的作用
  • 整个ConcurrentHashMap的一个创建步骤(以默认的参数值为例)