ConCurrentHashMap源码分析,面试常问

ConCurrentHashMap源码分析,面试常问

都说ConCurrentHashMap是线程安全,但又比HashTable效率高。底层实现原理是什么?常用的HashMap为什么线程不安全?

HashMap底层是数组+链表结构,既然有数组,那肯定会涉及到容量不足需要扩容的场景
或是极限情况下的元素覆盖问题。
ConCurrentHashMap源码分析,面试常问
上图假如此时有两个线程都通过了if判断,又恰好他们put元素的哈希值一样此时就会出现元素的覆盖。 其他HashMap详细资料。。。。



下面主要介绍ConCurrentHashMap实现线程安全方式(源码分析)

源码中几个比较重要的属性介绍

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

transient关键字说明此属性不会加入对象序列化,table代表整个哈希表。

private transient volatile Node<K,V>[] nextTable; 

这是一个连接表,用于哈希表扩容,扩容完成后会被重置为 null。

private transient volatile long baseCount; 

该属性保存着整个哈希表中存储的所有的结点的个数总和,有点类似于 HashMap 的 size 属性。

private transient volatile int sizeCtl; 

这是一个重要的属性,无论是初始化哈希表,还是扩容 rehash 的过程,都是需要依赖这个关键属性的。该属性有以下几种取值:

0:默认值
-1:代表哈希表正在进行初始化
大于0:相当于 HashMap 中的 threshold,表示阈值
小于-1:代表有多个线程正在进行扩容
该属性的使用还是有点复杂的,在我们分析扩容源码的时候再给予更加详尽的描述,此处了解其可取的几个值都分别代表着什么样的含义即可。






下面先关注put方法:

putVal 的方法比较多,我们分两个部分进行分析。

//第一部分 final V putVal(K key, V value, boolean onlyIfAbsent) {     //对传入的参数进行合法性判断     if (key == null || value == null) throw new NullPointerException();     //计算键所对应的 hash 值     int hash = spread(key.hashCode());     int binCount = 0;     for (Node<K,V>[] tab = table;;) {         Node<K,V> f; int n, i, fh;         //如果哈希表还未初始化,那么初始化它         if (tab == null || (n = tab.length) == 0)             tab = initTable();         //根据键的 hash 值找到哈希数组相应的索引位置         //如果为空,那么以CAS无锁式向该位置添加一个节点         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {             if (casTabAt(tab, i, null,                          new Node<K,V>(hash, key, value, null)))                 break;                            } 
其中initTable()方法在下面展开说明,这是一个初始化哈希表的操作,它同时只允许一个线程进行初始化操作。 
private final Node<K,V>[] initTable() {     Node<K,V>[] tab; int sc;     //如果表为空才进行初始化操作     while ((tab = table) == null || tab.length == 0) {         //sizeCtl 小于零说明已经有线程正在进行初始化操作         //当前线程应该放弃 CPU 的使用         if ((sc = sizeCtl) < 0)             Thread.yield(); // lost initialization race; just spin         //否则说明还未有线程对表进行初始化,那么本线程就来做这个工作         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {             //保险起见,再次判断下表是否为空             try {                 if ((tab = table) == null || tab.length == 0) {                     //sc 大于零说明容量已经初始化了,否则使用默认容量                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;                     @SuppressWarnings("unchecked")                     //根据容量构建数组                     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];                     table = tab = nt;                     //计算阈值,等效于 n*0.75                     sc = n - (n >>> 2);                 }             } finally {                 //设置阈值                 sizeCtl = sc;             }             break;         }     }     return tab; } 

关于 initTable 方法的每一步实现都已经给出注释,该方法的核心思想就是,只允许一个线程对表进行初始化,
如果不巧有其他线程进来了,那么会让其他线程交出 CPU 等待下次系统调度。这样,保证了表同时只会被一个线程初始化。

接着,我们回到 putVal 方法,这样的话,我们第一部分的 putVal 源码就分析结束了,下面我们看后一部分的源码:

//检测到桶结点是 ForwardingNode 类型,协助扩容 else if ((fh = f.hash) == MOVED)      tab = helpTransfer(tab, f); //桶结点是普通的结点,锁住该桶头结点并试图在该链表的尾部添加一个节点 else {        V oldVal = null;        synchronized (f) {            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;                       }                  }            }            //向红黑树中添加元素,TreeBin 结点的hash值为TREEBIN(-2)            else if (f instanceof TreeBin) {                Node<K,V> p;                binCount = 2;                  if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,                                      value)) != null) {                    oldVal = p.val;                    if (!onlyIfAbsent)                       p.val = value;                 }            }        }    }   //binCount != 0 说明向链表或者红黑树中添加或修改一个节点成功   //binCount  == 0 说明 put 操作将一个新节点添加成为某个桶的首节点   if (binCount != 0) {          //链表深度超过 8 转换为红黑树          if (binCount >= TREEIFY_THRESHOLD)              treeifyBin(tab, i);          //oldVal != null 说明此次操作是修改操作          //直接返回旧值即可,无需做下面的扩容边界检查          if (oldVal != null)              return oldVal;            break;         }     } } //CAS 式更新baseCount,并判断是否需要扩容 addCount(1L, binCount); //程序走到这一步说明此次 put 操作是一个添加操作,否则早就 return 返回了 return null; 

首先需要介绍一下,ForwardingNode 这个节点类型,

static final class ForwardingNode<K,V> extends Node<K,V> {         final Node<K,V>[] nextTable;         ForwardingNode(Node<K,V>[] tab) {             //注意这里             super(MOVED, null, null, null);             this.nextTable = tab;         }     //省略其 find 方法 } 

这个节点内部保存了一 nextTable 引用,它指向一张 hash 表。在扩容操作中,我们需要对每个桶中的结点进行分离和转移,如果某个桶结点中所有节点都已经迁移完成了(已经被转移到新表 nextTable 中了),那么会在原 table 表的该位置挂上一个 ForwardingNode 结点,说明此桶已经完成迁移。

ForwardingNode 继承自 Node 结点,并且它唯一的构造函数将构建一个键,值,next 都为 null 的结点,反正它就是个标识,无需那些属性。但是 hash 值却为 MOVED。

所以,我们在 putVal 方法中遍历整个 hash 表的桶结点,如果遇到 hash 值等于 MOVED,说明已经有线程正在扩容 rehash 操作,整体上还未完成,不过我们要插入的桶的位置已经完成了所有节点的迁移。

由于检测到当前哈希表正在扩容,于是让当前线程去协助扩容。

版权声明:玥玥 发表于 2021-04-14 22:08:55。
转载请注明:ConCurrentHashMap源码分析,面试常问 | 女黑客导航