两张图带你看清 ConcurrentHashMap 1.7和1.8的不同

简介: ConcurrentHashMap包可以看到这个 ConcurrentHashMap 是位于并发包下面的, 这可是大名鼎鼎的 JUC 呀并发涉及到线程安全呀,锁的知识点,还有诸如关键字 volatile 等 有关内存屏障的东西 , 还有 Unsafe 类这个更底层的! 😄嘿嘿~ 我们知道这个 HashMap 是线程不安全的~ ,而 线程安全的 Map 就有这个 HashTable 还有这个 ConcurrentHashMap 。看到这里不知道小伙伴们会不会 有个小小的疑惑 ?(・∀・(・∀・(・∀・*)为啥有了 HashTable 还要再设计这个 Concurre

ConcurrentHashMap


网络异常,图片无法展示
|



可以看到这个 ConcurrentHashMap  是位于并发包下面的, 这可是大名鼎鼎的 JUC  呀


并发涉及到线程安全呀,锁的知识点,还有诸如关键字 volatile 等 有关内存屏障的东西 , 还有 Unsafe 类这个更底层的! 😄


嘿嘿~ 我们知道这个 HashMap 是线程不安全的~  ,而 线程安全的 Map 就有这个 HashTable 还有这个 ConcurrentHashMap  。


看到这里不知道小伙伴们会不会 有个小小的疑惑 ?


(・∀・(・∀・(・∀・*)


为啥有了  HashTable  还要再设计这个

ConcurrentHashMap  呢


我们直接来到   ConcurrentHashMap  的源码处,看看作者是怎么说的😝


网络异常,图片无法展示
|


可以看到它说     ConcurrentHashMap  在检索数据时不需要锁,也不支持 锁住整个表


来阻止其他线程的访问 ,它的操作方法基本和 HashTable 一样,只是底层对锁的使用


细节不一样~


让我们直观滴感受下 HashTable 的 **特别 **吧~


网络异常,图片无法展示
|


可以看到 它几乎对所有的操作都加了这个  synchronized ,这会导致每次操作都直接锁表,效率很低!


连 get 都加锁。。


所以才有了这个  ConcurrentHashMap


特点


  • HashTable   和  ConcurrentHashMap   的 共同特点 是 不允许 key 和 value  为 null  ,  注意它们的 键值 都 不能是 null  呀  ,而 HashMap 就比较随意,都可以是 null。


  • HashTable  位于这个 java.util 包下,结合上文讲的这个   我们知道它属于 这个 fail-fast不支持并发修改    而   ConcurrentHashMap  位于 JUC 包下,属于 fail-safe  ,它 允许并发修改,但是 无法保证在迭代过程中获取到最新的值


结构


1.7 版本


请看图~



如图所示,在 JDK1.7 中, ConcurrentHashMap 是由 Segment 数组 + HashEntry


组成 ,数据结构上和 HashMap 一样,仍然是数组加链表。


ConcurrentHashMap 的一个最主要的特点就是  分段锁 (1)


它默认允许的并发量是16


它的这个分段呢,我们从图中也可以分析得出,其实就是给 HashMap 再封装一个


HashMap 的样子~  变成这个


Segment 数组 来控制这个并发~


详情请看👇


Segment 代码如下


网络异常,图片无法展示
|


SegmentConcurrentHashMap 中的一个内部类,继承了 ReentrantLock  ** 这


可重入锁(2)**


让我们来看看这个 put 操作~


@SuppressWarnings("unchecked")
public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        // 关键步骤1
        s = ensureSegment(j);
            // 关键步骤2
    return s.put(key, hash, value, false);
}
复制代码


可以发现它是通过这个 UNSAFE 类去获取这个这个 Segment  。


跟随源码来到这个 ensureSegment 方法中,这个方法主要用来创建和获取这个


Segment


可以看到 代码注释中关键步骤 3   使用到了这个 CAS锁(3)


@SuppressWarnings("unchecked")
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;
    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        Segment<K,V> proto = ss[0]; // use segment 0 as prototype
        int cap = proto.table.length;
        float lf = proto.loadFactor;
        int threshold = (int)(cap * lf);
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
            == null) { // recheck
            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                   == null) {
                 // 关键步骤 3
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                    break;
            }
        }
    }
    return seg;
}
复制代码


顺带提一下~


初始化  ConcurrentHashMap 时,会先初始化一个 Segment


网络异常,图片无法展示
|


最后来到主角~   // 上面代码注释的 关键步骤2


思路: 先通过 key 找到对应的  Segment  ,接着再对它其中的  HashEntry  进行操


作~


s.put 源码如下


final V put(K key, int hash, V value, boolean onlyIfAbsent) {
   // 步骤1
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
                 // 步骤2
                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 {
                // 步骤3
                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
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        // 步骤4
        unlock();
    }
    return oldValue;
}
复制代码


步骤 1:的主要作用是上锁tryLock()  失败的话会进入一个 自旋获取锁 的过程,不


断的尝试,当尝试的次数大于最大次数 MAX_SCAN_RETRIES 时就调用 lock() 获取锁


阻塞锁)~


步骤2: 遍历 HashEntry,如果不为空则判断传入的 key 和当前遍历的 key 是否相


等,相等时如果onlyIfAbsent=false 时 覆盖旧的 value。


步骤3:  不为空则需要新建一个 HashEntry 并加入到 Segment 中,同时会先判断是


否需要扩容。


步骤4: 最后会解除在 1 中所获取当前 Segment 的锁。


get 操作不用锁~


原理也一样,根据keyhash 值找到那个 segment,再找到里面的 hashEntry


虽然 ConcurrentHashMap    解决了这个并发问题,但是从由于数据结构和 1.7 的


HashMap 一样,所以都会有查询效率低的问题。


让我们来看看1.8的有啥不同吧~


1.8 版本


请看图~


为啥1.8 引入红黑树呢~


链表 查询时间复杂度 O(n) , 插入时间复杂度O(1)


红黑树 查询和插入时间复杂度都是 O(lgn)


主要特点~


采用了 CAS + synchronized 来保证并发安全性,放弃原有的 Segment 分段锁 。


Node 节点


网络异常,图片无法展示
|


稍微提下:


采用 volatile 修饰 是为了保证变量的 可见性禁止指令重排


put 操作


源码如下:


/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    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();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 关键点 1
            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;
            // 关键点 2
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            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;
                            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;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}
复制代码


关键点 1: 主要通过 cas 的方式去设置首节点


关键点2: 通过 synchronized 去锁住这个首节点,接着通过 if (tabAt(tab, i)


== f) 去判断是不是同个首节点  是的话再对其中的 数据进行操作


网络异常,图片无法展示
|


总结


ConcurrentHashMap


jdk版本 1.7 1.8
底层实现 数组+链表 数组+链表 / 红黑树
数据结构 Segment 数组 + HashEntry 节点 Node 节点
分段锁,默认并发是16,一旦初始化,Segment 数组大小就固定,后面不能扩容 CAS + synchronized 来保证并发安全性
put 操作 先获取锁,根据 key 的 hash 值 定位到 Segment ,再根据 key 的 hash 值 找到具体的 HashEntry ,再进行插入或覆盖,最后释放锁 根据 key 的 hash 值 定位到 Node节点,再判断首节点是否为空,空的话通过 cas 去赋值首节点 ; 首节点非空的话,会用 synchronized 去锁住首节点,并判断是是同个首节点,是的话再去操作
释放锁 需要显示调用 unlock() 不需要



目录
相关文章
|
5月前
|
存储 算法 数据可视化
【漫画算法】哈希表:古代皇帝的秘密魔法书
【漫画算法】哈希表:古代皇帝的秘密魔法书
|
存储 关系型数据库 C++
【C++从0到王者】第三十四站:红黑树是如何实现的?
【C++从0到王者】第三十四站:红黑树是如何实现的?
48 0
|
存储 测试技术 Serverless
【C++从0到王者】第三十六站:哈希
【C++从0到王者】第三十六站:哈希
45 0
24张图,九大数据结构安排得明明白白
数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不一样的处理效率。
|
存储 机器学习/深度学习 缓存
为什么要用HashMap?这样回答面试官直呼内行【手撕HashMap系列】
为什么要用HashMap?这样回答面试官直呼内行【手撕HashMap系列】
294 0
为什么要用HashMap?这样回答面试官直呼内行【手撕HashMap系列】
|
算法
算法竞赛100天第四天 —— 设计哈希表(散列表)
算法竞赛100天第四天 —— 设计哈希表(散列表)
131 0
算法竞赛100天第四天 —— 设计哈希表(散列表)
|
Java
java集合类史上最细讲解 - HashMap篇
k,v是一个Node实现了Map.Entry<K,V> jdk8以上底层为数组+链表+红黑树
94 0
java集合类史上最细讲解 - HashMap篇
|
Java 程序员
java集合类史上最细讲解 - Map篇
1.Map接口介绍 Map用于保存具有映射关系的数据:Key - Value 对于Set,底层其实依然是一个Map,但是Set选择不使用Value,也就是Set的Value值始终是一个常量😁 Map中的Key和Value可以是任何类型的数据,会封装到HashMap$Node对象中 Map中的Key不能重复,但是Value可以重复,当有相同的Key时,等价与替换操作😀
121 0
java集合类史上最细讲解 - Map篇
|
存储 算法 Java
java集合类史上最细讲解 - HashSet篇
1.Set接口方法 Set接口对象存放的数据是没有重复,且数据是无序存放的(添加顺序和存放顺序不一致,但是这个存放的顺序是固定的,不会随机变化)🤳 代码示例:
111 0
java集合类史上最细讲解 - HashSet篇
|
存储 安全 Java
java集合类史上最细讲解 - List篇
从上面的集合框架图可以看到,Java 集合框架主要包括两种类型的容器,一种是集合(Collection),存储一个元素集合,另一种是图(Map),存储键/值对映射。Collection 接口又有 3 种子类型,List、Set 和 Queue,再下面是一些抽象类,最后是具体实现类,常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。
117 0
java集合类史上最细讲解 - List篇