ConcurrentHashMap源码分析

小咪咪 2024-03-26 16:31 168阅读 0赞

format_png

概述

ConcurrentHashMap（CHM）是日常开发中使用频率非常高的一种数据结构，想对于普通的HashMap，CHM提供了线程安全的读写，CHM里面使用了许多比较精妙的优化&操作。本文主要对CHM的整体结构、初始化，查找，插入等做分析。
CHM在1.8之前和之后有比较大的变动，1.8之前主要通过Segment 分段锁 来解决并发问题，1.8及之后就没有这些臃肿的数据结构了，其数据结构与普通的HashMap一样，都是Node数组+链表+红黑树

format_png 1

一颗红黑树应满足如下性质：

  1. 根节点是黑色的

    • 外部节点均为黑色（图中的 leaf 节点，通常在表述的时候会省略）
    • 红色节点的孩子节点必为黑色（通常插入的节点为红色）
    • 从任一外部节点到根节点的沿途，黑节点的数目相等

format_png 2

除了上面基本的数据结构之外，Node节点也是一个需要关心的数据结构，Node节点本质上是单向链表的节点，其中包含key、value、Hash、next属性

  1. static class Node<K,V> implements Map.Entry<K,V> {
  2.     final int hash;  
  3.     final K key;
  4.     volatile V val;
  5.     volatile Node<K,V> next;
  6. }

ForwardingNode节点

ForwardingNode节点（简称fwd节点）继承自Node节点，主要用于扩容，该节点里面固定Hash值为MOVED(值为-1)，同时持有新表的引用

  1. static final class ForwardingNode<K,V> extends Node<K,V> {
  2.     final Node<K,V>[] nextTable;
  3.     ForwardingNode(Node<K,V>[] tab) {
  4.         super(MOVED, null, null, null);
  5.         this.nextTable = tab;
  6.     }
  8.     Node<K,V> find(int h, Object k) {
  9.         ...
  10.     }
  11. }

TreeNode

TreeNode节点也继承自Node节点，用于表示红黑树上的节点，主要属性如下所示

  1. static final class TreeNode<K,V> extends Node<K,V> {
  2.     TreeNode<K,V> parent;  // 父节点
  3.     TreeNode<K,V> left;    // 左儿子
  4.     TreeNode<K,V> right;   // 右儿子
  5.     TreeNode<K,V> prev;    // 记录前驱节点，用于恢复链表
  6.     boolean red;
  7. }

TreeBin

TreeBin节点内部持有TreeNode节点的引用，内部实现了读写锁用于控制多线程并发在红黑树上的操作，主要属性如下所示

  1. static final class TreeBin<K,V> extends Node<K,V> {
  2.     TreeNode<K,V> root;  // 红黑树根节点
  3.     volatile TreeNode<K,V> first;  // 链表根节点，读写分离时会用到
  4.     volatile Thread waiter;  // 当前线程
  5.     volatile int lockState;  // 当前红黑树的锁状态
  6.     // values for lockState
  7.     static final int WRITER = 1; // set while holding write lock
  8.     static final int WAITER = 2; // set when waiting for write lock
  9.     static final int READER = 4; // 读锁标记
  10. }

SizeCtl

除了数据结构需要说明外，SizeCtl也是理解CHM十分重要的一个字段，他是一个整数，不同的值表示不同的状态

  1. 当SizeCtl > 0时，表示下次扩展的阈值，其中阈值计算方式：数组长度 * 扩展阈值（注意这里是固定的0.75）
  2. 当SizeCtl = 0时，表示还没有开始初始化
  3. 当sizeCtl = -1是，表示此时正在进行初始化
  4. 当SizeCtl < -1时，表示此时正在进行扩展，其中高16位表示扩容标识戳，低16位表示参与扩容的线程数+1

初始化

CHM的初始化是惰性初始化的，即当我们使用ConCurrentHashMap<String,string> map = new ConcurrentHashMap(20);创建一个CHM对象时，并不会真正的创建对象，而是只有在put时才会真正开始创建对象。

  1. public ConcurrentHashMap(int initialCapacity) {
  2.     // 只是检查参数是否合理，并设置好数组容量和扩容阈值
  3.     if (initialCapacity < 0)
  4.     throw new IllegalArgumentException();
  5. int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
  6.            MAXIMUM_CAPACITY :
  7.            tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
  8. this.sizeCtl = cap;
  9. }

初始化流程

  1. private final Node<K,V>[] initTable() {
  2.     Node<K,V>[] tab; int sc;
  3.     // 判空，注意这里是while，当线程苏醒后会记性检查直到初始化完毕
  4.     while ((tab = table) == null || tab.length == 0) {
  5.         // 如果其他线程正在初始化，则让出cpu
  6.         if ((sc = sizeCtl) < 0)
  7.             Thread.yield(); // lost initialization race; just spin
  8.         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 当前线程尝试获取创建数组的重任
  9.             try {
  10.                 // 这里需要再进行判断是否为空，防止当前线程创建完毕后又有其他线程进来重复创建
  11.                 if ((tab = table) == null || tab.length == 0) {
  12.                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  13.                     @SuppressWarnings("unchecked")
  14.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  15.                     table = tab = nt;
  16.                     // 设置阈值为0.75n
  17.                     sc = n - (n >>> 2);
  18.                 }
  19.             } finally {

发表评论

表情：
评论列表 （有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读