Java集合源码解析-ConcurrentHashMap(JDK8)(下)

简介: Java集合源码解析-ConcurrentHashMap(JDK8)

finnish 是一个标志,如果为 true 则说明整张表的迁移操作已经全部完成了,我们只需要重置 table 的引用并将 nextTable 赋为空即可。否则,CAS 式的将 sizeCtl 减一,表示当前线程已经完成了任务,退出扩容操作。


如果退出成功,那么需要进一步判断是否还有其他线程仍然在执行任务。


image.png


我们说过 resizeStamp(n) 返回的是对 n 的一个数据校验标识,占 16 位


image.png


的值为 16,那么位运算后,整个表达式必然在右边空出 16 个零。也正如我们所说的,sizeCtl 的高 16 位为数据校验标识,低 16 为表示正在进行扩容的线程数量

(resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2

表示当前只有一个线程正在工作,相对应的,如果

(sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT

说明当前线程就是最后一个还在扩容的线程,那么会将 finishing 标识为 true,并在下一次循环中退出扩容方法。


这一块的难点在于对 sizeCtl 的各个值的理解,关于它的深入理解,这里推荐一篇文章。



着重理解位操作


看到这里,真的为 Doug Lea 精妙的设计而折服,针对于多线程访问问题,不但没有拒绝式得将他们阻塞在门外,反而邀请他们来帮忙一起工作。


好了,我们一路往回走,回到我们最初分析的 putVal 方法。接着前文的分析,当我们根据 hash 值,找到对应的桶结点,如果发现该结点为 ForwardingNode 结点,表明当前的哈希表正在扩容和 rehash,于是将本线程送进去帮忙扩容。否则如果是普通的桶结点,于是锁住该桶,分链表和红黑树的插入一个节点,具体插入过程类似 HashMap,此处不再赘述。


当我们成功的添加完成一个结点,最后是需要判断添加操作后是否会导致哈希表达到它的阈值,并针对不同情况决定是否需要进行扩容,还有 CAS 式更新哈希表实际存储的键值对数量。这些操作都封装在 addCount 这个方法中,当然 putVal 方法的最后必然会调用该方法进行处理。下面我们看看该方法的具体实现,该方法主要做两个事情。一是更新 baseCount,二是判断是否需要扩容。


//第一部分,更新 baseCount
private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    //如果更新失败才会进入的 if 的主体代码中
    //s = b + x  其中 x 等于 1
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        //高并发下 CAS 失败会执行 fullAddCount 方法
        if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null ||!(uncontended =U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
这一部分主要完成的是对 baseCount 的 CAS 更新。
//第二部分,判断是否需要扩容
if (check >= 0) {
     Node<K,V>[] tab, nt; int n, sc;
     while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&(n = tab.length) < MAXIMUM_CAPACITY) {
          int rs = resizeStamp(n);
          if (sc < 0) {
             if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||transferIndex <= 0)
               break;
               if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                  transfer(tab, nt);
               }
           else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
               s = sumCount();
            }
    }

这部分代码也是比较简单的,不再赘述。

至此,对于 put 方法的源码分析已经完全结束了,很复杂但也很让人钦佩

下面我们简单看看 remove 方法的实现。


8.4.2 remove 方法实现并发删除

无非就是先定位再删除



首先遍历整张表的桶结点,如果表还未初始化或者无法根据参数的 hash 值定位到桶结点,那么将返回 null


如果定位到的桶结点类型是ForwardingNode 结点,调用 helpTransfer 协助扩容

否则就老老实实的给桶加锁,删除一个节点


最后会调用 addCount 方法 CAS 更新 baseCount 的值。


8.4.3 size

size 方法的作用是为我们返回哈希表中实际存在的键值对的总数


image.png



可能你会有所疑问,ConcurrentHashMap 中的 baseCount 属性不就是记录的所有键值对的总数吗?直接返回它不就行了吗?


之所以没有这么做,是因为我们的 addCount 方法用 CAS 更新 baseCount,但很有可能在高并发的情况下,更新失败,那么这些节点虽然已经被添加到哈希表中了,但是数量却没有被统计.


还好,addCount 方法在更新 baseCount 失败的时候,会调用 fullAddCount 将这些失败的结点包装成一个 CounterCell 对象,保存在 CounterCell 数组中;

那么整张表实际的 size 其实是 baseCount 加上 CounterCell 数组中元素的个数.



8.4.4 get

get 方法可以根据指定的键,返回对应的键值对,由于是读操作,所以不涉及到并发问题

源码也是比较简单的


image.png



8.4.5 clear

clear 方法将删除整张哈希表中所有的键值对,删除操作也是一个桶一个桶的进行删除

public void clear() {
    long delta = 0L; // negative number of deletions
    int i = 0;
    Node<K,V>[] tab = table;
    while (tab != null && i < tab.length) {
        int fh;
        Node<K,V> f = tabAt(tab, i);
        if (f == null)
            ++i;
        else if ((fh = f.hash) == MOVED) {
            tab = helpTransfer(tab, f);
            i = 0; // restart
        }
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    Node<K,V> p = (fh >= 0 ? f :(f instanceof TreeBin) ?((TreeBin<K,V>)f).first : null);
                        //循环到链表或者红黑树的尾部
                        while (p != null) {
                            --delta;
                            p = p.next;
                        }
                        //首先删除链、树的末尾元素,避免产生大量垃圾  
                        //利用CAS无锁置null  
                        setTabAt(tab, i++, null);
                    }
                }
            }
        }
        if (delta != 0L)
            addCount(delta, -1);
    }
目录
相关文章
|
6月前
|
Java 大数据 API
Java Stream API:现代集合处理与函数式编程
Java Stream API:现代集合处理与函数式编程
339 100
|
6月前
|
Java API 数据处理
Java Stream API:现代集合处理新方式
Java Stream API:现代集合处理新方式
352 101
|
6月前
|
算法 Java
50道java集合面试题
50道 java 集合面试题
|
5月前
|
存储 算法 安全
Java集合框架:理解类型多样性与限制
总之,在 Java 题材中正确地应对多样化与约束条件要求开发人员深入理解面向对象原则、范式编程思想以及JVM工作机理等核心知识点。通过精心设计与周密规划能够有效地利用 Java 高级特征打造出既健壮又灵活易维护系统软件产品。
158 7
|
7月前
|
存储 缓存 安全
Java集合框架(二):Set接口与哈希表原理
本文深入解析Java中Set集合的工作原理及其实现机制,涵盖HashSet、LinkedHashSet和TreeSet三大实现类。从Set接口的特性出发,对比List理解去重机制,并详解哈希表原理、hashCode与equals方法的作用。进一步剖析HashSet的底层HashMap实现、LinkedHashSet的双向链表维护顺序特性,以及TreeSet基于红黑树的排序功能。文章还包含性能对比、自定义对象去重、集合运算实战和线程安全方案,帮助读者全面掌握Set的应用与选择策略。
558 23
|
6月前
|
存储 Java Go
对比Java学习Go——函数、集合和OOP
Go语言的函数支持声明与调用,具备多返回值、命名返回值等特性,结合`func`关键字与类型后置语法,使函数定义简洁直观。函数可作为一等公民传递、赋值或作为参数,支持匿名函数与闭包。Go通过组合与接口实现面向对象编程,结构体定义数据,方法定义行为,接口实现多态,体现了Go语言的简洁与高效设计。
174 4
|
7月前
|
安全 Java 开发者
Java集合框架:详解Deque接口的栈操作方法全集
理解和掌握这些方法对于实现像浏览器后退功能这样的栈操作来说至关重要,它们能够帮助开发者编写既高效又稳定的应用程序。此外,在多线程环境中想保证线程安全,可以考虑使用ConcurrentLinkedDeque,它是Deque的线程安全版本,尽管它并未直接实现栈操作的方法,但是Deque的接口方法可以相对应地使用。
380 12
|
7月前
|
存储 缓存 安全
Java集合框架(三):Map体系与ConcurrentHashMap
本文深入解析Java中Map接口体系及其实现类,包括HashMap、ConcurrentHashMap等的工作原理与线程安全机制。内容涵盖哈希冲突解决、扩容策略、并发优化,以及不同Map实现的适用场景,助你掌握高并发编程核心技巧。
|
7月前
|
安全 Oracle Java
JAVA高级开发必备·卓伊凡详细JDK、JRE、JVM与Java生态深度解析-形象比喻系统理解-优雅草卓伊凡
JAVA高级开发必备·卓伊凡详细JDK、JRE、JVM与Java生态深度解析-形象比喻系统理解-优雅草卓伊凡
531 0
JAVA高级开发必备·卓伊凡详细JDK、JRE、JVM与Java生态深度解析-形象比喻系统理解-优雅草卓伊凡
|
8月前
|
并行计算 Java API
Java List 集合结合 Java 17 新特性与现代开发实践的深度解析及实战指南 Java List 集合
本文深入解析Java 17中List集合的现代用法,结合函数式编程、Stream API、密封类、模式匹配等新特性,通过实操案例讲解数据处理、并行计算、响应式编程等场景下的高级应用,帮助开发者提升集合操作效率与代码质量。
353 1

推荐镜像

更多
  • DNS