JUC-17-ConcurrentHashMap

前言

• ConcurrentHashMap 是一个并发散列映射表，它允许完全并发的读取，并且支持给定数量的并发更新。
• 而HashTable和同步包装器包装的 HashMap，使用一个全局的锁来同步不同线程间的并发访问，同一时间点，只能有一个线程持有锁，也就是说在同一时间点，只能有一个线程能访问容器，这虽然保证多线程间的安全并发访问，但同时也导致对容器的访问变成串行化的了。

https://blog.csdn.net/weixin_44460333/article/details/86770169

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

https://zhuanlan.zhihu.com/p/21673805

https://www.jianshu.com/p/865c813f2726

1. JDK 1.7 概述

• 在JDK1.7版本中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成，如下图所示：

• Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，也就是上面的提到的锁分离技术，而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构一样

2. JDK 1.8 实现

• JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现
• 并发控制使用Synchronized和CAS来操作， 整个看起来就像是优化过且线程安全的HashMap
• 虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本

说明：ConcurrentHashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树是为了提高查找效率。

• 在深入JDK1.8的put和get实现之前要知道一些常量设计和数据结构，这些是构成ConcurrentHashMap实现结构的基础，下面看一下基本属性：

  // node数组最大容量：2^30=1073741824  

  private  static  final  int  MAXIMUM_CAPACITY =  1  <<  30    ;  

  // 默认初始值，必须是2的幂数  

  private  static  final  int  DEFAULT_CAPACITY =  16    ;  

  //数组可能最大值，需要与toArray（）相关方法关联  

  static  final  int  MAX_ARRAY_SIZE = Integer.MAX_VALUE -  8    ;  

  //并发级别，遗留下来的，为兼容以前的版本  

  private  static  final  int  DEFAULT_CONCURRENCY_LEVEL =  16    ;  

  // 负载因子  

  private  static  final  float  LOAD_FACTOR =  0    .75f;  

  // 链表转红黑树阀值,> 8 链表转换为红黑树  

  static  final  int  TREEIFY_THRESHOLD =  8    ;  

  //树转链表阀值，小于等于6（tranfer时，lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量，<=UNTREEIFY_THRESHOLD 则untreeify(lo)）  

  static  final  int  UNTREEIFY_THRESHOLD =  6    ;  

  static  final  int  MIN_TREEIFY_CAPACITY =  64    ;  

  private  static  final  int  MIN_TRANSFER_STRIDE =  16    ;  

  private  static  int  RESIZE_STAMP_BITS =  16    ;  

  // 2^15-1，help resize的最大线程数  

  private  static  final  int  MAX_RESIZERS = (    1  << (    32  - RESIZE_STAMP_BITS)) -  1    ;  

  // 32-16=16，sizeCtl中记录size大小的偏移量  

  private  static  final  int  RESIZE_STAMP_SHIFT =  32  - RESIZE_STAMP_BITS;  

  // forwarding nodes的hash值  

  static  final  int  MOVED     = -    1    ;  

  // 树根节点的hash值  

  static  final  int  TREEBIN   = -    2    ;  

  // ReservationNode的hash值  

  static  final  int  RESERVED  = -    3    ;  

  // 可用处理器数量  

  static  final  int  NCPU = Runtime.getRuntime().availableProcessors();  

  //存放node的数组  

  transient  volatile  Node<K,V>[] table;  

  /*控制标识符，用来控制table的初始化和扩容的操作，不同的值有不同的含义  

  *当为负数时：-    1    代表正在初始化，-N代表有N-    1    个线程正在 进行扩容  

  *当为    0    时：代表当时的table还没有被初始化  

  *当为正数时：表示初始化或者下一次进行扩容的大小  
*/

  private  transient  volatile  int  sizeCtl;

基本属性定义了ConcurrentHashMap的一些边界以及操作时的一些控制，下面看一些内部的一些结构组成，这些是整个ConcurrentHashMap整个数据结构的核心

2.1 Node

• Node是ConcurrentHashMap存储结构的基本单元，继承于HashMap中的Entry，用于存储数据，源代码如下

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }

• Node数据结构很简单，从上可知，就是一个链表，但是只允许对数据进行查找，不允许进行修改

2.2 TreeNode

• TreeNode继承与Node，但是数据结构换成了二叉树结构，它是红黑树的数据的存储结构，用于红黑树中存储数据，当链表的节点数大于8时会转换成红黑树的结构，他就是通过TreeNode作为存储结构代替Node来转换成黑红树源代码如下

static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node<K,V> next,
             TreeNode<K,V> parent) {
        super(hash, key, val, next);
        this.parent = parent;
    }

2.3 TreeBin

• TreeBin从字面含义中可以理解为存储树形结构的容器，而树形结构就是指TreeNode，所以TreeBin就是封装TreeNode的容器，它提供转换黑红树的一些条件和锁的控制，部分源码结构如下

static final class TreeBin<K,V> extends Node<K,V> {
    TreeNode<K,V> root;
    volatile TreeNode<K,V> first;
    volatile Thread waiter;
    volatile int lockState;
    // values for lockState
    static final int WRITER = 1; // set while holding write lock
    static final int WAITER = 2; // set when waiting for write lock
    static final int READER = 4; // increment value for setting read lock

https://www.jianshu.com/p/865c813f2726

未完待续 ： 等我有空接着写。

参考博客 ： https://www.jianshu.com/p/865c813f2726

打赏