区块链技术博客
www.b2bchain.cn

Java源码

这篇文章主要介绍了Java源码,通过具体代码讲解6064并且分析了Java源码的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了Java源码。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=6064。具体如下:

Java集合源码

Java集合源码

发布日期:   2019-09-18
文章字数:   3.8k
阅读时长:   14 分
阅读次数:  

ConcurrentHashMap

碰到线程不安全场景下,需要使用 Map 的时候,我们第一个想到的 API 估计就是ConcurrentHashMap,ConcurrentHashMap 内部封装了锁和各种数据结构来保证访问 Map 是线程安全的。

从类注释可以得到的信息是:

  • 所有的操作都是线程安全的
  • 多个线程同时进行 put、remove 等操作时并不会阻塞,可以同时进行
  • 迭代过程中,即使 Map 结构被修改,也不会抛 ConcurrentModificationException 异常
  • 除了数组 + 链表 + 红黑树的基本结构外,新增了转移节点,是为了保证扩容时的线程安全的节点
  • 提供了很多 Stream 流式方法,比如forEach、search、reduce 等等

一、结构

Java源码

ConcurrentHashMap 和 HashMap

相同之处

  • 数组和链表的结构几乎一样,两个map对底层的操作思路是一样的,但是实现不一样。
  • 它们都实现了map接口,都继承了AbstractMap类,大多数方法都是相同的,我们需要把HashMap切换到ConcurrentHashMap也不需要考虑太多的兼容性问题。

不同之处

  • 红黑树结构不同。HashMap红黑树的节点叫TreeNode,维护着红黑树的结构,比如新增节点、查找节点;ConcurrentHashMap中红黑树被拆分了,TreeNode仅维护属性和查找节点功能,并且新增了TreeBin,用来维护红黑树的结构,负责root的加锁和解锁。
  • 新增ForwardingNode,转移节点,扩容时,通过这个节点保证线程的安全。
  • 各种操作过程不是很相同

二、put操作

put是面试中的重中之重。在线程安全方面加入了一些代码。

首先了解一下

synchronized是悲观锁,这种线程一旦得到锁,其他需要锁的线程就挂起的情况就是悲观锁。

CAS是英文单词Compare And Set的缩写,翻译过来就是比较并设置。CAS操作的就是乐观锁,每次不加锁,而是假设没有冲突而去完成某项操作,如果因为冲突失败就重试,直到成功为止。

参考博客

put步骤:

  • 如果table数组是空的,则初始化,否则就直接进入下一步
  • 根据key计算出hash值,找到槽点位置(也就是数组中的某个位置),进入自旋死循环!
  • 如果这个位置上没有值,通过cas来创建
  • 如果这个位置上有值,判断是不是在转移节点上(就是判断是不是正在扩容),如果在,则需要等待扩容结束
  • 在这个槽点上,先锁住这个槽点,保证只有一个线程进来了,再判断是链表还是红黑树,用各自的方法新增,红黑树的新增也改了,要锁住根节点
  • 新增完成后再判断下要不要扩容,这个是扩容的时机,和HashMap是一样的,但是扩容过程不一样
    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;               //table是空的,进行初始化             if (tab == null || (n = tab.length) == 0)                 tab = initTable();               //如果当前索引位置没有值,直接创建             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {                   //cas 在 i 位置创建新的元素,当 i 位置是空时,即能创建成功,结束for循环,否则继续自旋                 if (casTabAt(tab, i, null,                              new Node<K,V>(hash, key, value, null)))                     break;                   // no lock when adding to empty bin             }             //MOVED是转移节点的hash值,是一个固定的值             //如果当前索引位置是转移节点(MOVED),表示该位置正在扩容,就会一直等待扩容完成             else if ((fh = f.hash) == MOVED)                 tab = helpTransfer(tab, f);               //如果该位置上有值了             else {                 V oldVal = null;                   //先把数组的节点node f锁住,其余线程不能操作                 synchronized (f) {                       //这里再次判断 i 索引位置的数据没有被修改                       //binCount 被赋值的话,说明走到了修改表的过程里面                     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;                                 }                             }                         }                           //红黑树的情况,这里没有使用 TreeNode,使用的是 TreeBin                           //TreeBin 持有红黑树的引用,并且会对其加锁,保证其操作的线程安全                         else if (f instanceof TreeBin) {                             Node<K,V> p;                             binCount = 2;                               //putTreeVal方法里面,给红黑树重新着色旋转时,会锁住红黑树的根节点                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,                                                            value)) != null) {                                   //满足if的话,把老的值给oldVal                                 oldVal = p.val;                                 if (!onlyIfAbsent)                                     p.val = value;                             }                         }                     }                 }                   //binCount不为空,并且 oldVal 有值的情况,说明已经新增成功了                 if (binCount != 0) {                       // 链表是否需要转化成红黑树                     if (binCount >= TREEIFY_THRESHOLD)                         treeifyBin(tab, i);                     if (oldVal != null)                         return oldVal;                     break;                 }             }         }           //check 容器是否需要扩容,如果需要去扩容,调用 transfer 方法去扩容           //如果已经在扩容中了,check有无完成         addCount(1L, binCount);         return null;     }

ConcurrentHashMap 在 put 过 程中,采用了哪些手段来保证线程安全。

(1)数组初始化时的线程安全

看一下initTable的源码

    //初始化 table,通过对 sizeCtl 的变量赋值来保证数组只能被初始化一次         private final Node<K,V>[] initTable() {         Node<K,V>[] tab; int sc;           //通过自旋保证初始化成功         while ((tab = table) == null || tab.length == 0) {               // 小于 0 代表有线程正在初始化,释放当前 CPU 的调度权,重新发起锁的竞争             if ((sc = sizeCtl) < 0)                 Thread.yield(); // lost initialization race; just spin                // CAS 赋值保证当前只有一个线程在初始化,-1 代表当前只有一个线程能初始化               // 保证了数组的初始化的安全性             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {                   //CAS成功后再次判断有没有初始化完成                 try {                       // 很有可能执行到这里的时候,table 已经不为空了,这里是双重 check                     if ((tab = table) == null || tab.length == 0) {                           // 进行初始化                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;                         @SuppressWarnings("unchecked")                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];                         table = tab = nt;                         sc = n - (n >>> 2);                     }                 } finally {                     sizeCtl = sc;                 }                 break;             }         }         return tab;     }

数组初始化时,首先通过自旋来保证一定可以初始化成功,然后通过 CAS 设置 sizeCtl 变量的值,来保证同一时刻只能有一个线程对数组进行初始化,CAS 成功之后,还会再次判断当前数组是否已经初始化完成,如果已经初始化完成,就不会再次初始化,通过自旋 + CAS + 双重 check 等手段保证了数组初始化时的线程安全。

sizeCtl:默认为0,sizeCtl中记录size大小的偏移量,用来控制table的初始化和扩容操作.它的数值有以下含义

  • -1 :代表table正在初始化,其他线程应该交出CPU时间片,退出
  • -N: 表示正有N-1个线程执行扩容操作
  • >0: 如果table已经初始化,代表table容量,默认为table大小的0.75,如果还未初始化,代表需要初始化的大小

(2)新增槽点时的线程安全

  • 通过自旋死循环保证一定可以新增成功,for (Node<K,V>[] tab = table;;)

  • 当前槽点为空时,通过 CAS 新增

    • 这里没有在判断槽点为空的情况下直接赋值,因为在判断槽点为空和赋值的瞬间,很有可能槽点已经被其他线程赋值了,所以我们采用 CAS 算法,能够保证槽点为空的情况下赋值成功,如果恰好槽点已经被其他线程赋值,当前 CAS 操作失败,会再次执行 for 自旋,再走槽点有值的 put 流程。
  • 当前槽点有值,锁住当前槽点

    • 就是发生hash冲突的时候,此时数组上这个槽点,可能是链表、可能是红黑树,通过锁住槽点,保证同一时刻只有一个线程能对这个槽点进行修改。

      Java源码

  • 红黑树旋转时,锁住红黑树的根节点,保证同一时刻,当前红黑树只能被一个线程旋转

    • Java源码

(3)扩容时的线程安全

ConcurrentHashMap 的扩容时机和 HashMap 相同,都是在 put 方法的最后一步检查是否需要扩容,但两者扩容过程完全不同。ConcurrentHashMap中put最后一步就是addCount方法,其中有一个transfer方法,它就是扩容方法。主要思路是:

  • 先把老数组中的值拷贝到扩容后的新数组上,从数组的尾巴开始拷贝

  • 拷贝数组的槽点时,先把原数组槽点锁住,保证原数组槽点不能操作,成功拷贝到新数组时,把原数组槽点赋值为转移节点

  • 这时如果有新数据正好需要 put 到此槽点时,发现槽点为转移节点,就会一直等待,所以在扩容完成之前,该槽点对应的数据是不会发生变化的

  • 从数组的尾部拷贝到头部,每拷贝成功一次,就把原数组中的节点设置成转移节点

  • 所有数组数据都拷贝到新数组时,直接把新数组整个赋值给数组容器,结束

通过在原数组上设置转移节点,put 时碰到转移节点时会等待扩容成 功之后才能 put 的策略,来保证了整个扩容过程中肯定是线程安全的,因为数组的槽点一旦被 设置成转移节点,在没有扩容完成之前,是无法进行操作的。

ps:一开始我看的时候没看明白,这个意思是,把一个槽点拷贝完后,设置为转移节点,那就说明数组正在扩容,还没拷贝完,需要继续等待,如果这个槽点不是转移节点,那可以put,put完在拷贝到新数组上就可以了

三、get操作

读的话,就比较简单,先获取数组的下标,然后通过判断数组下标的 key 是否和我们的 key 相等,相等的话直接返回,如果下标的槽点是链表或红黑树的话,分别调用相应的查找数据的方法,整体思路和 HashMap 很像

    public V get(Object key) {         Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;           //计算键的hashcode         int h = spread(key.hashCode());           //不是空的数组 && 并且当前索引的槽点数据不是空的,否则该key对应的值不存在,返回null         if ((tab = table) != null && (n = tab.length) > 0 &&             (e = tabAt(tab, (n - 1) & h)) != null) {               //槽点第一个值和key相等,直接返回             if ((eh = e.hash) == h) {                 if ((ek = e.key) == key || (ek != null && key.equals(ek)))                     return e.val;             }               //如果是红黑树或者转移节点,使用对应的find方法             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;     }

四、问题

(1)ConcurrentHashMap 和 HashMap 的相同点和不同点

相同点

  • 都是数组 + 链表 +红黑树的数据结构,所以基本操作的思想相同,具体实现有所差别
  • 都实现了Map接口,都继承了AbstractMap类,方法差不多相似

不同点

  • 前者线程安全,后者作为共享变量线程不安全
  • 数据结构上,HashMap用的是TreeNode,ConcurrentHashMap新增了TreeBin,以及转移节点,导致内部实现上有较大差别

(2)ConcurrentHashMap 通过哪些手段保证了线程安全。

  • 储存 Map 数据的数组被 volatile 关键字修饰,一旦被修改,立马就能通知其他线程
  • put时用的是无限死循环+cas算法来保证一定新增成功,如果put的时候,这个hash值正好是转移节点,会等扩容完毕再push,保证老数组的值不会变
  • 对数组槽点操作,会先锁住,然后再对链表或红黑树操作,对红黑树操作时也会锁住根节点,保证旋转时的线程安全。

(3)ConcurrentHashMap 是如何发现当前槽点正在扩容的。

ConcurrentHashMap 新增了一个节点类型,叫做转移节点,当我们发现当前槽点是转移节点时(其 hash 值是 -1),即表示 Map 正在进行扩容。

(4)描述一下 CAS 算法在 ConcurrentHashMap 中的应用?

https://www.jianshu.com/p/ae25eb3cfb5d

CAS 其实是一种乐观锁,一般有三个值,分别为:赋值对象,原值,新值,在执行的时 候,会先判断内存中的值是否和原值相等,相等的话把新值赋值给对象,否则赋值失败,整个过 程都是原子性操作,没有线程安全问题。

put 方法中,有使用到 CAS ,是结合无限 for 循环一起使用的,其步骤是

  • 首先计算出数组索引的下标,拿出下标对应的原值

  • CAS 覆盖当前下标的值,赋值时,如果发现内存值和 1 拿出来的原值相等,执行赋值,退出

    循环,否则不赋值,进行下一次for循环

(5)两种 Map 扩容时,有啥区别?

HashMap 是直接在老数据上面进行扩容,ConcurrentHashMap 就不太一样,扩容过程是这样的:

  • 从数组的队尾开始拷贝
  • 拷贝数组的槽点时,先把原数组槽点锁住,拷贝成功到新数组时,把原数组槽点赋值为转移节点
  • 从数组的尾部拷贝到头部,每拷贝成功一次,就把原数组的槽点设置成转移节点,这样就把每一个槽点拷贝过来了
  • 所有数组数据都拷贝到新数组时,直接把新数组整个赋值给数组容器,拷贝完成

简单来说,通过扩容时给槽点加锁,和发现槽点正在扩容就等待的策略,保证了 ConcurrentHashMap 可以慢慢地一个一个槽点的转移,保证了扩容时的线程安全

(6)ConcurrentHashMap 在 Java 7 和 8 中关于线程安全的做法有啥不同?

拿 put 方法为例,Java 7 的做法是:

  • 把数组进行分段,找到当前 key 对应的是那一段
  • 将当前段锁住,然后再根据 hash 寻找对应的值,进行赋值操作

Java 7 的做法比较简单,缺点也很明显,就是当我们需要 put 数据时,我们会锁住改该数据对 应的某一段,这一段数据可能会有很多,比如我只想 put 一个值,锁住的却是一段数据,导致这一段的其他数据都不能进行写入操作,大大的降低了并发性的效率


Java集合源码

JUC.Collectionsjuc集合类,主要是cow(包括数组、set),然后是concurrenthashmap,然后queue占个大头,四个queue,都是非常重要的! COW 底层是一个数组,用transient和volatile
2019-09-20 Java集合源码
CopyOnWriteArrayList并发容器,是一种线程安全的list,它具有以下特征: 线程安全的,多线程环境下可以直接使用,无需加锁 通过锁 + 数组拷贝 + volatile 关键字保证了线程安全 每次数组操作,都会把数组拷
2019-09-17 Java集合源码

本文地址https://www.b2bchain.cn/?p=6064

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » Java源码
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们