devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

ConcurrentHashMap源码分析，轻取面试Offer（二）_(a = as[threadlocalrandom.getprobe() & m]) == null

作者：AllinToyou | 2024-02-15 11:28:44

赞

踩

(a = as[threadlocalrandom.getprobe() & m]) == null

 

上篇ConcurrentHashMap源码分析，轻取面试Offer（一）中降到了看源码的方法，下面接上篇继续分析源码

先来上篇注释过的代码段和遗留的问题。

  1. final V putVal(K key, V value, boolean onlyIfAbsent) {
  2.         //ConcurrentHashMap中key和value都不允许为空
  3.         if (key == null || value == null) throw new NullPointerException();
  4.         //key的哈希值，忍住好奇！先不看其原理
  5.         int hash = spread(key.hashCode());
  6.         //冲突次数 或者说 链表存放尝试次数
  7.         int binCount = 0;
  8.         for (Node<K,V>[] tab = table;;) {//相当于while true
  9.             Node<K,V> f; int n, i, fh;
  10.             if (tab == null || (n = tab.length) == 0)//如果还没初始化则进行初始化
  11.                 tab = initTable();
  12.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果table对应位置为空，DCL机制存放到相应位置，并跳出循环
  13.                 if (casTabAt(tab, i, null,
  14.                              new Node<K,V>(hash, key, value, null)))
  15.                     break;                   // no lock when adding to empty bin
  16.             }//刚才看到这···································
  17.             else if ((fh = f.hash) == MOVED)//先不看这，小本本上记一下，我这里疑惑。
  18.                 tab = helpTransfer(tab, f);
  19.             else {//如果不走上面，一定会走这，意思是table数组，想放的哪个位置已经有人了
  20.                 V oldVal = null;//用于保存旧的value值
  21.                 synchronized (f) {//这里加了个锁，这个f是table[]的一个小格子，很微小，只锁定了hashcode相同的key的操作
  22.                     if (tabAt(tab, i) == f) {//DCL机制，再来看看现在的f是不是之前的f，因为之前没加锁，有可能会不一样嘛
  23.                         if (fh >= 0) {//fh就是f的hashcode值，上面有，为什么要判断这，小本本上记一下，我这里疑惑。
  24.                             binCount = 1;//尝试次数为1了，因为放到table对应位置，发现不为null才来的这里
  25.                             for (Node<K,V> e = f;; ++binCount) {//这个for循环没必要刚开始就仔细看，我猜它的作用就是把新的key放到链表尾部
  26.                                 K ek;
  27.                                 if (e.hash == hash &&
  28.                                     ((ek = e.key) == key ||
  29.                                      (ek != null && key.equals(ek)))) {
  30.                                     oldVal = e.val;
  31.                                     if (!onlyIfAbsent)
  32.                                         e.val = value;
  33.                                     break;
  34.                                 }
  35.                                 Node<K,V> pred = e;
  36.                                 if ((e = e.next) == null) {//把新的key放到链表尾部
  37.                                     pred.next = new Node<K,V>(hash, key,
  38.                                                               value, null);
  39.                                     break;
  40.                                 }
  41.                             }
  42.                         }//if (fh >= 0)的结束处
  43.                         else if (f instanceof TreeBin) {
  44.                     //别看了，大概意思不就是如果是红黑树那就放到红黑树里，先别深入
  45.                             Node<K,V> p;
  46.                             binCount = 2;
  47.                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  48.                                                            value)) != null) {
  49.                                 oldVal = p.val;
  50.                                 if (!onlyIfAbsent)
  51.                                     p.val = value;
  52.                             }
  53.                         }
  54.                     }
  55.                 }
  56.                 if (binCount != 0) {//发现这里判断binCount ，按照刚才的思路，binCount 肯定大于0，所以肯定会执行，那就看看
  57.                     if (binCount >= TREEIFY_THRESHOLD)//点TREEIFY_THRESHOLD发现它是8，英文介绍说他是转成红黑树的阈值，和刚才的热身题对应起来了。吆西。
  58.                         treeifyBin(tab, i);//转成红黑树，咋转的先不看，好奇心害死猫，但mark一下，是在这里转的
  59.                     if (oldVal != null)//如果是覆盖了原来的值，那就返回原来的值
  60.                         return oldVal;//返回
  61.                     break;
  62.                 }
  63.             }
  64.         }
  65.         addCount(1L, binCount);//map中的key个数+1
  66.         return null;
  67.     }
  • spread(key.hashCode());------------------计算hash
  • initTable();------------------初始化，
  • tabAt(tab, i = (n - 1) & hash))------------------查看内存中最新值
  • casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))------------------用CAS的方式插入新结点
  • helpTransfer(tab, f);------------------？？？
  • putTreeVal(hash, key,value)--------------把新结点放到红黑树里
  • treeifyBin(tab, i);--------------------把 tab 第 i 个节点下的链表转成红黑树
  • addCount(1L, binCount);------------------执行完putVal，相当于count ++

下面要做的，不是看你不懂的函数helpTransfer，既然不懂，看了也糊，从懂的地方看，最后回过头来看这。

spread函数：

  1. static final int spread(int h) {
  2.         return (h ^ (h >>> 16)) & HASH_BITS;//HASH_BITS的值为0x7fffffff
  3.     }

发现他就是把 key 的 hashCode() h，将其与 自己的高16位进行异或运算，与HASH_BITS进行与运算消除负hash。

initTable()函数

  1. /**
  2.      * Initializes table, using the size recorded in sizeCtl.
  3.      */
  4.     private final Node<K,V>[] initTable() {
  5.         Node<K,V>[] tab; int sc;
  6.         while ((tab = table) == null || tab.length == 0) {
  7.             if ((sc = sizeCtl) < 0)//为什么判断他小于0？不懂，继续往下看
  8.                 Thread.yield(); // 线程让步，有前人正在初始化，退让，下次获取权限就退出该函数了
  9.             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//通过CAS的方式，如果sc=0，就把它置为-1
  10.                 try {
  11.                     if ((tab = table) == null || tab.length == 0) {//DCL 双重验证
  12.                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;//sc如果小于0，则置为16，按照我们当前的思路，这里肯定大于0，没变相当于，！sizeCtl可以表示初始化的大小
  13.                         @SuppressWarnings("unchecked")
  14.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];//创建了~
  15.                         table = tab = nt;
  16.                         sc = n - (n >>> 2);//sc的值改变为 n - 0.25n，也就是 0.75n
  17.                     }
  18.                 } finally {
  19.                     sizeCtl = sc;//sc 赋值给 sizeCtl ！sizeCtl可以表示阈值，
  20.                 }
  21.                 break;
  22.             }
  23.         }
  24.         return tab;
  25.     }

tabAt函数

  1. @SuppressWarnings("unchecked")
  2.     static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
  3.         return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
  4.     }

这个函数的意思即为，查看当前内存中最新的 table[i] 的值

这里有的小白会问table不是volatie修饰的么？为什么还要这样去看？这不是多次一举么？

  1. 答：
  2. table确实是volatie的，这只是代表数组的引用是内存可见的，但不代表引用地址指向的内容是可见的

（maspaint简单画了一下）如图：

因此需要用这种方式来查看内存中最新的。

casTabAt

  1. static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
  2.                                         Node<K,V> c, Node<K,V> v) {
  3.         return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
  4.     }

用cas的方式来放进去。

helpTransfer，这个先放放，剧透一下，这个是帮助其他线程进行扩容操作的。

  1. ？？
  2. 还有这种操作，66

putTreeVal

  1. 在红黑树中添加一个节点的操作
  2.  
  3. 我想你们应该都懂，我就不放了。
  4.  
  5. 不懂的同学我相信看了会更晕，就不放了先

treeifyBin

  1. private final void treeifyBin(Node<K,V>[] tab, int index) {
  2.         Node<K,V> b; int n, sc;
  3.         if (tab != null) {
  4.             if ((n = tab.length) < MIN_TREEIFY_CAPACITY)//MIN_TREEIFY_CAPACITY=64，只有table.length 不< 64 时候，他才会转成红黑树
  5.                 tryPresize(n << 1);//tab.length < 64 进行双倍扩容（左移一位）
  6.             else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
  7.                 synchronized (b) {
  8.                     if (tabAt(tab, index) == b) {//DCL 检查
  9.                         TreeNode<K,V> hd = null, tl = null;//下面是转红黑树的操作，对算法感兴趣的可以看看，看思路务必先略过
  10.                         for (Node<K,V> e = b; e != null; e = e.next) {
  11.                             TreeNode<K,V> p =
  12.                                 new TreeNode<K,V>(e.hash, e.key, e.val,
  13.                                                   null, null);
  14.                             if ((p.prev = tl) == null)
  15.                                 hd = p;
  16.                             else
  17.                                 tl.next = p;
  18.                             tl = p;
  19.                         }
  20.                         setTabAt(tab, index, new TreeBin<K,V>(hd));//这里又多了个函数
  21.                     }
  22.                 }
  23.             }
  24.         }
  25.     }

看setTablAt

  1. static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
  2.         U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
  3.     }

与上面类似，为了安全才这样做

····重点来了，敲黑板！！！

addCount 大体就是让count++，并且如果table不够大，那就扩若，如果已经在扩容了，那就去帮着扩容

在看这个函数前，想想之前CAS的知识

自旋锁是有可能失败的，所以他是unsafe底下的方法，ConcurrentHashMap为了让它变成安全，Doug Lea加了两个内存可见的变量：

  1.     /**
  2.      * Base counter value, used mainly when there is no contention,
  3.      * but also as a fallback during table initialization
  4.      * races. Updated via CAS.
  5. 翻译：
  6. 基本计数器值，主要用于没有争用时，但也用作表初始化竞赛期间的后备值。通过CAS更新
  7.      */
  8.     private transient volatile long baseCount;//也就是这个变量是存储当前一共有多少key，（但不一定准确，因为CAS 时候有可能失败，该变量未统计CAS失败的个数）
  9.  
  10.     /**
  11.      * Table of counter cells. When non-null, size is a power of 2.
  12.      */
  13.     private transient volatile CounterCell[] counterCells;//CAS计数失败时候保存在这里
  14.  
  15. //可以猜出来counterCells不为null之前已经有过baseCount CAS失败，发生失败代表并发不低
  16.  
  17. //baseCount CAS失败时 则在counterCells数组中使用随机数随便取一个索引位置之前记录的数据进行数量累加CAS
  18. //这也解释了为什么额外的计数器采用数组而不是int之类的，因为CAS的机制，并发太高时候他就容易失败，采用数组做缓冲。
  19.  
  1. addCount(long x, int check)
  2.  
  3. /*
  4. ····第一个参数 x
  5. 这个函数有两个参数，第一个参数为long 也就是add计数的个数，来复习一下我们当时怎么调用的它：
  6. */
  7. addCount(1L, binCount);
  8. //因为我们这个put就put了一个，所以是1L，
  9. /*为啥是长整型？
  10. put还能放map呢，还有并发等等，有问题可以先记下来，后面再想，先跟着我的思路
  12. ····第二个参数 check
  13. 我们当时调用的时候传过来的是binCount，调用put插入时>=0,直接放在table上为0，否则按链表或者红黑树次序为 1，2，3，4....以此类推，上一博客中提到了。
  14. 扩展：
  15. 删除或清理节点时（如replaceNode，clear方法，）传过来的是-1
  16. */

继续往下看，先上jdk源代码，小白先别细看，只看我注释就好！！贴上来为了让大家对源码长什么样有个数：

  1. /**
  2.      * Adds to count, and if table is too small and not already
  3.      * resizing, initiates transfer. If already resizing, helps
  4.      * perform transfer if work is available.  Rechecks occupancy
  5.      * after a transfer to see if another resize is already needed
  6.      * because resizings are lagging additions.
  7.      *
  8.      * @param x the count to add
  9.      * @param check if <0, don't check resize, if <= 1 only check if uncontended
  10.     
  11. 翻译：
  12. *添加计数
  13. 如果表太小且尚未调整大小，则调用transfer。
  14. 如果正在调整大小，且还有活干，那就去帮忙去。
  15. 在转移之后重新检查占用率，看看是否已经需要再调整大小，因为调整大小是滞后的添加。
  17. *@ PARAM-X要添加的计数
  19. * @ PARAM检查是否为0，不检查调整大小，如果<＝1只检查是否未争用
  22. 大体看一眼，先知道大概有几个if ，不用细看，会晕车。
  26. */
  27.     private final void addCount(long x, int check) {
  28.         CounterCell[] as; long b, s;
  29.         if ((as = counterCells) != null ||
  30.             !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
  31.             //······### Mark ###·······
  32.             CounterCell a; long v; int m;
  33.             boolean uncontended = true;
  34.             if (as == null || (m = as.length - 1) < 0 ||
  35.                 (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
  36.                 !(uncontended =
  37.                   U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
  38.                 fullAddCount(x, uncontended);
  39.                 return;//······### Mark ###·······
  40.             }
  41.             if (check <= 1)//······### Mark ###·······
  42.                 return;
  43.             s = sumCount();
  44.         }
  45.         if (check >= 0) {
  46.             Node<K,V>[] tab, nt; int n, sc;
  47.             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
  48.                    (n = tab.length) < MAXIMUM_CAPACITY) {
  49.                 int rs = resizeStamp(n);//······### Mark ###·······
  50.                 if (sc < 0) {//······### Mark ###·······
  51.                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  52.                         sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
  53.                         transferIndex <= 0)
  54.                         break;
  55.                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  56.                         transfer(tab, nt);
  57.                 }
  58.                 else if (U.compareAndSwapInt(this, SIZECTL, sc,
  59.                                              (rs << RESIZE_STAMP_SHIFT) + 2))
  60.                     transfer(tab, null);//······### Mark ###·······
  61.                 s = sumCount();
  62.             }
  63.         }
  64.     }

跟着我的思路继续看，我们是从putVal函数进来的，当时addCount(1L, binCount);这么调用的，现在假设binCount = 0

  1. private final void addCount(long x, int check) {
  2.         CounterCell[] as; long b, s;
  3. //并发量很高才会进入这里，这里我们先想竞争不大，略过if
  4.         if (...) {
  5.             //...忽略
  6.         }
  7.         if (check >= 0) {//我们put方法会进来，所以继续看
  8.             Node<K,V>[] tab, nt; int n, sc;
  9.             //s是ConcurrentHashMap中实际元素个数，sum 简写，sizeCtl 是阈值
  10.             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
  11.                    (n = tab.length) < MAXIMUM_CAPACITY) {
  12.             //while循环判断，当前元素个数 > 阈值 且 table 不为空，且tab.length小于MAXIMUM_CAPACITY（MAXIMUM_CAPACITY 的值为 1 << 30）
  13.                 int rs = resizeStamp(n);//···Mark···这里自适应调整新table的大小为合适的2的次幂，比如n是15，那rs就是32
  14.                 if (sc < 0) {//sc=sizeCtl初始是阀值，sc肯定大于0，先不看这
  15.                     //...省略
  16.                 }
  17.                 ，
  18.                 else if (U.compareAndSwapInt(this, SIZECTL, sc,
  19.                                              (rs << RESIZE_STAMP_SHIFT) + 2))
  20.                     transfer(tab, null);//启动transfer，因为扩容需要把之前的table中的元素都转移到新table中
  21.                 s = sumCount();sumCount是正真的计算map元素数量的方法：计算baseCount和counterCells数组存的总和，意思是每次循环都是获取最新值
  22.             }
  23.         }
  24.     }

 

看了上面提到的，想必各位对ConcurrentHashMap的putVal操作有了大概的了解，大概知道他是怎么放得，这时候需要自己点源码顺着上面的思路过一遍，一定要再多看几遍！

继续探讨，请看下篇：ConcurrentHashMap源码分析，轻取面试Offer（三）

本章伏笔：

  • 第一个if干啥了？
  • 为啥是check <= 1?
  • resizeStamp(n); 这么神奇?这个函数咋做到的？
  • sc < 0？ 还能小于0？
  • transfer(tab, null); ------------扩容，干了啥？
  • 你说的多个线程帮忙扩容怎么帮的？

注：本篇为CSDN--Star_Java原创，转载请注明出处！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/84155
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号