并发编程之ConcurrentHashMap源码解读-1.7

作者 : 开心源码 本文共11736个字,预计阅读时间需要30分钟 发布时间: 2022-05-14 共266人阅读

上一篇文章并发编程之ConcurrentHashMap源码解读-1.8中,我们详细解读了JDK 1.8 中ConcurrentHashMap的源码。既然都提到了JDK 1.8的ConcurrentHashMap,那么就不得不提JDK 1.7的ConcurrentHashMap,两者的实现是有很大不同的。这篇文章中就让我们来一探索竟吧!本文主要包括以下几个部分:

  1. 前言
  2. 基本原理
  3. 基础组件
  4. put
  5. 扩容
  6. get
  7. size
  8. 总结

1. 前言

由于ConcurrentHashMap在JDK 1.7 & 1.8中有着截然不同的实现,故有必要再详情下ConcurrentHashMap 在 JDK 1.7中的实现(本文基于的JDK 版本为 1.7.0_80)。在进入正文之前,老规矩,先提出几个问题:

  • Q1:为什么不使用HashTable?
    HashTable采用了对所有可能存在线程安全的方法加synchronized锁的方式,来实现线程安全。锁粒渡过粗,效率低下。
  • Q2:ConcurrentHashMap如何实现线程安全?
    ConcurrentHashMap内部维护了一个Segment[],而Segment继承自ReentrantLock,put的时候,先定位到具体的Segment,而后获取Segment锁,只有成功取得锁的线程才能插入数据。从而利用ReentrantLock实现线程安全。
  • Q3:ConcurrentHashMap如何降低锁的粒度的?
    维护多个Segment,插入数据的时候只锁对应的Segment,而不是锁所有的Segment。
  • Q4:ConcurrentHashMap扩容的时候支持并发读写吗?
    扩容的时候,定位到同一个Segment的写线程会阻塞至扩容完成。读线程不受影响,总是能通过UNSAFE.getObjectVolatile拿到最新的值,并且通过volatile HashEntry 保证扩容后的数组可见性。

2. 基本原理

  1. 内部持有一个Segment<K,V>[],用来将锁进行分段,从而降低锁的粒度,提升并发性能。
    1.1 Segment 继承自ReentrantLock,保证其有锁的特性。
    1.2 Segment 同时持有volatile HashEntry<K,V>[],用来存储相应的key-value,同时保证了HashEntry之间的可见性。
    1.3 Segment<K,V>[]会在构造函数被调用的时候初始化,扩容的时候仅仅扩容Segment中的HashEntry<K,V>[],这里会初始化Segment[0],用来当作初始化其它Segment的模板。
  2. put的先进行hash扰动运算,而后定位到具体的segment,而后根据情况决定初始化segment或者者请求锁。
    2.1 hash扰动(目标是充分混合hash特征,减少冲突)。
    2.2 计算索引得到segment[i],假如它尚未初始化,则先初始化segment[i]。
    2.3 尝试获取segment[i]锁,获取锁失败,则自旋或者者阻塞至成功取得锁。
    2.4 定位HashEntry<K,V>[j]升级链表,升级后视情况决定能否扩容。
    2.5 释放锁。
  3. get的时候同样先进行hash扰动运算,而后定位到具体的segment,而后定位到具体的HashEntry<K,V>,遍历取值。
    3.1 取具体的HashEntry<K,V>的时候,利用UNSAFE.getObjectVolatile保证取到的是最新的HashEntry<K,V>
  4. 统计size的时候,会先尝试在不加锁的情况下,累加各个segment的count,循环两次。假如中途数据没有更改,则认为数据正确,假如更改,则在加锁的情况下再统计一次。
    [图片上传中…(0073Cjx6ly1gkj896whqvj3020020dfw.jpg-ef6b90-1608789320783-0)]

从上面的流程中,我们可以清晰的看到ConcurrentHashMap中的数据结构为Segment<K,V>[]+HashEntry<K,V>[]

ConcurrentHashMap 结构图.png

put 流程

put流程.png

3. 基础组件

属性

默认初始化容量static final int DEFAULT_INITIAL_CAPACITY = 16;默认加载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;默认并发级别static final int DEFAULT_CONCURRENCY_LEVEL = 16;存储HashEntry<K,V>[]的Segment<K,V>[]final Segment<K,V>[] segments;

Segment

继承自ReentrantLock,具备锁的特性static final class Segment<K,V> extends ReentrantLock implements Serializable {        获取锁失败时最大自旋次数        static final int MAX_SCAN_RETRIES =            Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;        用来实际存储数据的HashEntry<K,V>[]        transient volatile HashEntry<K,V>[] table;        当前Segment的实际数据量        transient int count;        修改次数        transient int modCount;        阈值,用来指导扩容        transient int threshold;        加载因子,扩容后计算新的threshold        final float loadFactor;        Segment(float lf, int threshold, HashEntry<K,V>[] tab) {            this.loadFactor = lf;            this.threshold = threshold;            this.table = tab;        }        省略部分方法和代码        final V put(K key, int hash, V value, boolean onlyIfAbsent) {            ...................        }}    

我们都说ConcurrentHashMap利用的是锁分段的思想,这里的锁就是Segment,它通过继承ReentrantLock 来取得锁的特性。另外一点需要注意的是,调用put方法的时候,其实是调用Segment内的put方法。关于ReentrantLock是如何实现锁功能的,感兴趣的可以看另一篇文章并发编程之AQS探秘

HashEntry

 链表 static final class HashEntry<K,V> {        final int hash;        final K key;        定义为volatile保证可见性        volatile V value;        指向下一个节点的指针        volatile HashEntry<K,V> next;        HashEntry(int hash, K key, V value, HashEntry<K,V> next) {            this.hash = hash;            this.key = key;            this.value = value;            this.next = next;        } }   


4. put

之前,我们梳理了put的流程。下面结合源码看下各个部分的实现,重点是思考如何保证每个步骤的线程安全。

先看下构造方法

    public ConcurrentHashMap(int initialCapacity,                             float loadFactor, int concurrencyLevel) {        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)            throw new IllegalArgumentException();        if (concurrencyLevel > MAX_SEGMENTS)            concurrencyLevel = MAX_SEGMENTS;        // Find power-of-two sizes best matching arguments        int sshift = 0;        int ssize = 1;       这里得到的ssize始终是2的N次幂,由于采用的是从1循环往左移动一位        while (ssize < concurrencyLevel) {            ++sshift;            ssize <<= 1;        }        this.segmentShift = 32 - sshift;        this.segmentMask = ssize - 1;        超过最大值,设置为最大值        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        看是否整除        int c = initialCapacity / ssize;        无法整除        if (c * ssize < initialCapacity)            取大的            ++c;        int cap = MIN_SEGMENT_TABLE_CAPACITY;        计算每个HashEntry[]的初始长度        while (cap < c)            cap <<= 1;        // create segments and segments[0]        初始Segment<K,V>[0]做为初始其它Segment的模板(就可以通过s0取得cap、loadFactor)        Segment<K,V> s0 =            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),                             (HashEntry<K,V>[])new HashEntry[cap]);        初始Segment<K,V>[],这里初始化之后Segment<K,V>[]就不会再扩容了,扩容的时候仅仅是扩容Segment<K,V>[i]中的HashEntry[]        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];        赋值ss[0]        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]        this.segments = ss;    }

上面可以看到Segment<K,V>[]是在构造方法被调用的时候就初始化的,而Segment<K,V>[i](包含其内部的HashEntry<K,V>[])则是在put的时候才会初始化。

入口

    public V put(K key, V value) {        Segment<K,V> s;        if (value == null)            throw new NullPointerException();        进行hash扰动,充分混合hash特征,减少冲突        int hash = hash(key);        计算segment索引        int j = (hash >>> segmentShift) & segmentMask;        取指定segment        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment            初始化segment            s = ensureSegment(j);        调用segement.put方法        return s.put(key, hash, value, false);    }

put的核心逻辑其实是在Segment.put中。

初始化Segment[i]

    private Segment<K,V> ensureSegment(int k) {        final Segment<K,V>[] ss = this.segments;        long u = (k << SSHIFT) + SBASE; // raw offset        Segment<K,V> seg;        取指定Segment最新值        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {            用构造函数时初始话的ss[0]作为模板初始化ss[i]            Segment<K,V> proto = ss[0]; // use segment 0 as prototype            容量            int cap = proto.table.length;            加载因子/默认0.75            float lf = proto.loadFactor;            阈值,超过这个值并且HashEntry[].length小于数组最大长度,则需要扩容            int threshold = (int)(cap * lf);            初始话HashEntry[]            HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];            再次检查能否为空,感知其它线程初始化            if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))                == null) { // recheck                初始化Segment<K,V>                Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);                循环利用CAS设置ss[i]=s,直到成功                while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))                       == null) {                    if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))                        break;                }            }        }        return seg;    }

从源码中,我们看到了几点保证线程安全的措施:1)利用UNSAFE.getObjectVolatile保证能拿到最新的Segment<K,V>[i]的值。2)利用CAS升级Segment<K,V>[i]的值,直到成功或者者Segment<K,V>[i]不为空,这里保证升级肯定成功或者者不升级时可见其它线程升级的最新值,避免了多线程同时升级。

调用segment.put完成赋值

   final V put(K key, int hash, V value, boolean onlyIfAbsent) {            尝试非阻塞的情况下拿锁,成功返回null            拿锁失败,则自旋,或者者阻塞至成功取得锁            这里锁的是当前segment[i],故当多个线程同时往相同的segment[i]里put时,            只有拿到锁的线程能成功设置值,获取锁失败的线程将会自旋或者者阻塞直到成功取得锁            HashEntry<K,V> node = tryLock() ? null :                scanAndLockForPut(key, hash, value);            V oldValue;            try {                利用临时变量来存储table,防止在中间过程中频繁的对table进行volatile读写,优化性能                HashEntry<K,V>[] tab = table;                计算当前key在HashEntry[] 中的下标                int index = (tab.length - 1) & hash;                获取对应下标的HashEntry<K,V>                volatile读,保证拿到最新的HashEntry<K,V>[i],使非volatile变量也可以有volatile语义,配合UNSAFE.putOrderedObject使用                HashEntry<K,V> first = entryAt(tab, index);                 循环链表,做数据插入                for (HashEntry<K,V> e = first;;) {                    if (e != null) {                        K k;                        替换已有节点的值                        if ((k = e.key) == key ||                            (e.hash == hash && key.equals(k))) {                            oldValue = e.value;                            if (!onlyIfAbsent) {                                e.value = value;                                ++modCount;                            }                            break;                        }                        指向下一个节点,继续遍历                        e = e.next;                    }                    else {                        if (node != null)                            node.setNext(first);                        else                            新链表插入旧链表的头部                            node = new HashEntry<K,V>(hash, key, value, first);                        计数                        int c = count + 1;                        超过阈值&&小于最大长度                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)                            扩容                            rehash(node);                        else                            升级原来的HashEntry[]                            volatile写,使非volatile变量也可以有volatile写的语义                            setEntryAt(tab, index, node);                        ++modCount;                        count = c;                        oldValue = null;                        break;                    }                }            } finally {                解锁                unlock();            }            return oldValue;        }

在这个方法里,有几点值得注意的地方:

  1. 这里利用ReentrantLock来实现加锁和解锁,从而保证线程安全。多线程同时往相同的segment[i]里put时,只有拿到锁的线程能成功设置值,获取锁失败的线程将会自旋或者者阻塞直到成功取得锁。
  2. 这里升级链表采用的是头插法,不同于1.8版本的尾插式。

entryAt

    static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {        return (tab == null) ? null :            (HashEntry<K,V>) UNSAFE.getObjectVolatile            (tab, ((long)i << TSHIFT) + TBASE);    }

使非volatile定义的变量也能有volatile读的语义,即能读到最新值。
setEntryAt

   static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,                                       HashEntry<K,V> e) {        UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);    }

使非volatile定义的变量也能有volatile写的语义,即能禁止写操作的指令重排序,但是不保证内存可见性,故要配合UNSAFE.getObjectVolatile来使用,以便能取到最新的值。、


5. 扩容

ConcurrentHashMap在升级HashEntry<K,V>[]之前要进行扩容的检查,假如当前segment元素数量操作阈值且数组长度小于最大值的时候,就要进行扩容。扩容主要做了两件事:

  1. 创立一个原数组两倍大小的数组。
  2. 将老数组的元素转移到新的数组中。转移数组的过程中,先循环找到扩容后,后续节点索引都保持不变的节点将其插入到对应的槽位,从而达到链表的复用。再分别对剩余的节点进行转移。

这种解决方式可以最大限度的重用已有链表,最好的情况是链表的头部以后都保持不变,这样可以重用整个链表,当然最坏的方式是最后一个节点保持不变,则需要重建除最后一个节点外的所有链表。这里有点相似1.8 ConcurrentHashMap中的高低位,感兴趣的可以去看之前的文章关于高低位的详情并发编程之ConcurrentHashMap源码解读-1.8

 private void rehash(HashEntry<K,V> node) {            HashEntry<K,V>[] oldTable = table;            int oldCapacity = oldTable.length;            int newCapacity = oldCapacity << 1;            新的阈值            threshold = (int)(newCapacity * loadFactor);            初始化一个oldTable 2倍容量的数组            HashEntry<K,V>[] newTable =                (HashEntry<K,V>[]) new HashEntry[newCapacity];            利用(n-1)&hash计算下标            int sizeMask = newCapacity - 1;            循环转移原有链表            for (int i = 0; i < oldCapacity ; i++) {                HashEntry<K,V> e = oldTable[i];                if (e != null) {                    HashEntry<K,V> next = e.next;                    int idx = e.hash & sizeMask;                    单节点链表,直接赋值                    if (next == null)   //  Single node on list                        newTable[idx] = e;                    else { // Reuse consecutive sequence at same slot                        最后一个后面索引保持不变的链表节点                        HashEntry<K,V> lastRun = e;                        lastRun对应的索引                        int lastIdx = idx;                       循环找到lastRun,由于lastRun后的索引都不变,故这里可以直接复用lastRun节点及其后面的节点,无需重新构建链表                        for (HashEntry<K,V> last = next;                             last != null;                             last = last.next) {                            int k = last.hash & sizeMask;                            if (k != lastIdx) {                                lastIdx = k;                                lastRun = last;                            }                        }                        复用lastRun                        newTable[lastIdx] = lastRun;                        // Clone remaining nodes                        解决除了lastRun之外的剩余节点,这里要一个个遍历,重构链表                        for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {                            V v = p.value;                            int h = p.hash;                            int k = h & sizeMask;                            HashEntry<K,V> n = newTable[k];                            newTable[k] = new HashEntry<K,V>(h, p.key, v, n);                        }                    }                }            }            计算扩容之前构建的new Node 对应的下标            int nodeIndex = node.hash & sizeMask; // add the new node            把newTable中对应下标的链表,插入到当前Node的尾部            即将当前Node插入到newTable[nodeIndex]的头部            node.setNext(newTable[nodeIndex]);            重新为newTable[nodeIndex]赋值            newTable[nodeIndex] = node;            更改table的指向            table = newTable;        }

这里由于put的第一步加了锁,保证了只有一个线程在扩容,这样就保证了扩容时的线程安全,同时因为HashEntry<K,V>[] table被定义成volatile,这里就保证了扩容最后一步更改table指向为newTable的时候对其它线程立马可见。


6. get

    public V get(Object key) {        Segment<K,V> s; // manually integrate access methods to reduce overhead        HashEntry<K,V>[] tab;        hash扰动        int h = hash(key);        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;        利用UNSAFE.getObjectVolatile取最新的Segment[u]        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&            (tab = s.table) != null) {           同样利用UNSAFE.getObjectVolatile取最新的HashEntry<K,V>[i]           遍历链表取值            for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile                     (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);                 e != null; e = e.next) {                K k;                if ((k = e.key) == key || (e.hash == h && key.equals(k)))                    return e.value;            }        }        return null;    }

值得注意的是,尽管Segment[i]未被定义成volatile,但是仍可以通过UNSAFE.getObjectVolatile,获得最新的值。HashEntry<K,V>[i]同理。

7. size

假如要统计ConcurrentHashMap中的元素数量,我们可以怎样做呢?很自然的想法就是统计每个Segment的count,而后累加。但是这样就行了吗?显然是不行的,试想假如统计的过程中,count值发生了改变,该怎样办。那么最安全的办法就是把Segment全锁起来,这样其它线程就没办法更改里面的值,即可以放心的统计了。这样是安全了,但是效率低下,那么ConcurrentHashMap是如何处理的呢?

public int size() {        // Try a few times to get accurate count. On failure due to        // continuous async changes in table, resort to locking.        final Segment<K,V>[] segments = this.segments;        最终返回的size        int size;        size超过32位        boolean overflow; // true if size overflows 32 bits        modCount的和        long sum;         // sum of modCounts        上次统计的modCount的和        long last = 0L;   // previous sum        不加锁尝试的次数,从-1开始,最大值等于2,总共三次        int retries = -1; // first iteration isn't retry        try {            死循环统计            for (;;) {                  三次以后加锁                if (retries++ == RETRIES_BEFORE_LOCK) {                    for (int j = 0; j < segments.length; ++j)                        对所有segment加锁,这里会强制创立所有segment,创立并锁住segment,可以防止其它线程调用put等操作                        ensureSegment(j).lock(); // force creation                }                复位sum                sum = 0L;                复位size                size = 0;                overflow = false;                遍历segment数组                for (int j = 0; j < segments.length; ++j) {                    通过UNSAFE.getObjectVolatile保证取到最新的segment的值                    Segment<K,V> seg = segmentAt(segments, j);                    if (seg != null) {                       累加modCount                        sum += seg.modCount;                        int c = seg.count;                        累加count                        if (c < 0 || (size += c) < 0)                            overflow = true;                    }                }                第二次循环或者者之后,modCount的和与上一次一致,即没发生变化,则认为结果正确                if (sum == last)                    break;                将modCount的和赋值给last,用来进行下次循环的比较                last = sum;            }        } finally {            if (retries > RETRIES_BEFORE_LOCK) {                for (int j = 0; j < segments.length; ++j)                   释放锁                    segmentAt(segments, j).unlock();            }        }        return overflow ? Integer.MAX_VALUE : size;    }
  1. 循环尝试在不加锁的情况下,累加segment.count。
  2. 两次统计之间count未发生变化(判断变化的依据是,两次循环的modCount一致),则认为得到正确结果,否则继续尝试。
  3. 达到尝试次数上限3,则为每个segment加锁统计。

8. 总结

这篇文章中,我们对JDK 1.7 ConcurretHashMap的源码进行了分析,下面用几个问题对上面的内容进行总结。

1. ConcurrentHashMap是如何保证线程安全的?

  • 从读(get)的层面,利用Unsafe.getObjectVolatile保证取到的是最新的Segment&HashEntry<K,V>[i],保证写线程对读线程的可见性,从而保证线程安全
  • 从写(put)的层面,利用ReentrantLock 可重入锁保证每次只有一个线程对Segment[i]做数据插入,从而保证了线程安全。
  • 从扩容(rehash)的层面,由于只有put的时候才会调用到rehash,同样利用ReentrantLock 可重入锁保证线程之间的互斥性,从而保证线程安全。
  • 从计数(size)层面,put的时候进行自增,统计的时候先尝试不加锁统计,当计数期间结果改变的时候再采用ReentrantLock 可重入锁保证统计期间其它线程无法更改数据,从而实现线程安全。

2. ConcurrentHashMap什么情况下才会触发扩容?

  • 当前Segment[i]的元素数量超过阈值(负载因子*初始数量),且数组长度小于最大长度时

3. 能否支持并发扩容?

  • 不支持,扩容的时候定位到相同Segment,准备做数据更改的线程会阻塞。

4. 扩容的时候能否支持并发读写?

  • 扩容的时候支持并发读。
  • 扩容的时候不支持并发写(同一个Segment),此时其它往这个Segment写数据的线程会阻塞。

ConcurrentHashMap作为一个并发编程的热点,无论工作还是面试中,都会有很高的出现频率。相信通过对源码的解读,大家都能有些许收获。当然,因为水平有限,难免文章中有疏漏的地方,欢迎批评指正。我们下一篇文章见….

参考 java并发编程的艺术

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 并发编程之ConcurrentHashMap源码解读-1.7

发表回复