ConcurrentHashMap的put方法

原创

在下是首席架构师

发布于 2022-08-01 13:13:45

8600

文章被收录于专栏：从入门到出门从入门到出门

计算key的哈希值
for自旋保证put成功
- 如果没有初始化就初始化table
  - 有可能多个线程去调用initTable()方法去初始化,用cas加锁就行了，成功一次就行了
- 通过与哈希取模计算数组下标，如果下标节点为null，就通过cas放进数组当前下标的位置
- 如果当前下标有值，并且发现当前节点正在做扩容迁移操作，就去帮助扩容
- 如果既有值，又没在扩容，就锁住这个数组下标节点，开始进行put操作
  - 第一种情况当前节点是一个链表
    - 遍历整个链表
    - 判断hash相同，并且key也相同，则覆盖
    - 如果hash不存在，此时已经遍历到了最后一个节点e，然后把当前的key/value添加到链表e节点的后i面，尾插法
  - 第二种情况当前节点是红黑树
    - 将节点放入红黑树，具体怎么放的参考我另一篇同系列下的文章之红黑树
- put进去之后，会对链表长度进行判断，如果链表的长度大于等于8,进行扩容或者转化为红黑树
  - 链表的扩容
    - 如果tab的长度小于64，则调用tryPresize()方法进行扩容
    - 链表的扩容的本质是16->32，将数组扩容一倍，然后将老数组的数据迁移到新的数组
    - 如果为空就初始化数组，跟之前的initTable()方法一样
    - 如果已经是最大容量了，直接返回
    - 判断sizeCtl是否小于0，因为只有在扩容中的时候sizeCtl才会小于0变成-1,
    - 多线程扩容，高16位表示当前的扩容标记，保证唯一性,低16位表示当前扩容的线程数量,每增加一个扩容线程，就会在低16位+1
      - 实现数据转移 transfer()
      - 计算每个线程处理数据的区间大小，默认最小是16，当数组长度大时，会扩大区间大小
      - 链表的情况
      - 遍历旧链表，使用hash&新数组长度重新计算数组下标位置，
      - ln表示低位链表，hn表示高位链表
      - 低位链表表示遍历到某一个链表节点时发现这个节点及其后方节点都不需要变，直接将后面的所有节点变为一个链表
      - 红黑树的情况
      - 左旋右旋...
扩容完成之后，统计个数，table的size+1
- HashMap里面是有一个成员变量 size来统计个数
- 如果竞争不激烈的情况下，直接用cas将baseCount+1
- 如果竞争激烈的情况下，采用counterCells数组进行计数
- counterCells长度为2，随机负载，落到0下标就对0下标的value进行cas操作，落到1下标就对1下标进行cas操作
- 这样就将竞争程度下降了一倍，统计size()的时候，遍历counterCells数组，将数组值进行累加，然后baseCount+counterCells数组累加的数。
- 如果counterCells长度为2不够，counterCells会动态扩容。