-
ConcurrentHashMap源码解析 1.内部结构
ConcurrentHashMap—内部结构
简介
- ConcurrentHashMap 是 HashMap 的线程安全版本，内部也是使用 (数组 + 链表 + 红黑树) 的结构来存储元素，相比于同样线程安全的
HashTable(底层方法都加了synchronized)来说，效率各方面都有极大的提升。
ConcurrentHashMap 的整体流程
整体流程跟 HashMap 比较类似，大致是以下几步：
- 如果桶数组未初始化，则初始化；
- 如果待插入的元素所在的桶为空，则尝试把元素直接插入到桶的第一个位置；
- 如果正在扩容，则当前线程一起加入到扩容的过程中；
- 如果待插入元素所在的桶不为空且不在迁移元素，则锁住这个桶（分段锁）；
- 如果当前桶中元素以链表方式存储，则在链表中寻找该元素或者插入元素；
- 如果当前桶中元素以红黑树方式存储，则在红黑树中寻找该元素或者插入元素；
- 如果元素存在，则返回旧值；
- 如果元素不存在，整个Map的元素个数+1，并检查是否需要扩容。
添加元素操作中使用的锁主要有（自旋锁 (CAS) + synchronized + 分段锁）
为什么是 synchronized 不是 ReentrantLock?
因为
synchronized已经得到了极大地优化，在特定情况下并不比 ReentrantLock 差。数据结构
字段分析
常量
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable { private static final long serialVersionUID = 7249069246763182397L; // 散列表数组最大长度 private static final int MAXIMUM_CAPACITY = 1 << 30; // 散列表默认长度 private static final int DEFAULT_CAPACITY = 16; // 默认并发级别 jdk1.7遗留下来的，1.8只是初始化的时候用了，1.8不代表并发级别，散列表长度才代表并发级别 private static final int DEFAULT_CONCURRENCY_LEVEL = 16; // 默认加载因子 private static final float LOAD_FACTOR = 0.75f; // 树化阈值 和MIN_TREEIFY_CAPACITY一起控制(链表长度大于8并且数组长度大于64才转为红黑树) static final int TREEIFY_THRESHOLD = 8; // 树转链表阈值 static final int UNTREEIFY_THRESHOLD = 6; // 树化条件二 数组长度达到64 static final int MIN_TREEIFY_CAPACITY = 64; // 线程迁移数据最小步长，控制线程迁移任务最小区间的一个值(即桶位的跨度) private static final int MIN_TRANSFER_STRIDE = 16; // 扩容相关，计算扩容时生成的一个 标识戳 private static int RESIZE_STAMP_BITS = 16; // 计算出来的值是65535((1 << 16) - 1) 代表并发扩容的最多线程数 private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; // 扩容相关， private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; // 当node节点的hash值是-1时，表示当前节点是FWD节点(已经被迁移的节点) static final int MOVED = -1; // node节点的hash值是-2，表示当前节点已经树化，且当前节点为TreeBin对象，TreeBin对象代理操作红黑树 static final int TREEBIN = -2; static final int RESERVED = -3; // 0x7fffffff -> (0111 1111 1111 1111 1111 1111 1111 1111) 可以将一个负数通过位与(&)运算后得到正数，但不是取绝对值 static final int HASH_BITS = 0x7fffffff; // 当前系统的CPU数量 static final int NCPU = Runtime.getRuntime().availableProcessors(); // 1.8序列化 为了兼容1.7的ConcurrentHashMap而保存的(核心代码没有用到) private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField("segments", Segment[].class), new ObjectStreamField("segmentMask", Integer.TYPE), new ObjectStream Field("segmentShift", Integer.TYPE) };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
成员变量
// 散列表 长度一定是2的次方数 transient volatile Node<K,V>[] table; // 扩容过程中，会将扩容中的新table赋值给nextTable保持引用，扩容结束后会被设置为null private transient volatile Node<K,V>[] nextTable; // LongAdder中的baseCount，未发生竞争时 或者 当前LongAdder处于加锁状态时，增量累加到baseCount中Cell数组初始化被加锁时 将数据写入到base中 private transient volatile long baseCount; /* * 1.sizeCtl < 0 * 1.1 sizeCtl = -1 表示有线程正在创建table数组，当前线程需要自旋等待 * 1.2 其它表示当前table数组正在扩容，高16位表示：扩容的标识戳，低16位表示：(1 + nThread) nThread是当前参与并发扩容的线程数量 * 2.sizeCtl = 0 * 表示创建table数组时，使用DEFAULT_CAPACITY(16)大小 * 3.sizeCtl > 0 * 两种情况 * 3.1 如果table未初始化，表示初始化大小 * 3.2 如果table已经初始化，表示下次扩容时的触发条件(阈值) */ private transient volatile int sizeCtl; // HashMap只是一个线程负责迁移数据 而ConcurrentHashMap支持多线程并发迁移数据 效率更高 // 扩容过程中 记录当前进度，所有线程都需要从transferIndex中分配区间任务，去执行自己的任务 private transient volatile int transferIndex; // LongAdder中的cellsBusy (同步状态 0表示LongAdder对象无锁 1表示LongAdder对象有锁) private transient volatile int cellsBusy; // LongAdder中的cells数组 当baseCount发生竞争后，会创建cells数组 // 线程会通过计算hash值 取到自己对应的cell中，将增量累加到指定cell中 // 总数 = sum(cells) + baseCount private transient volatile CounterCell[] counterCells; // 相当于HashMap中的keySet、values和entrySet private transient KeySetView<K,V> keySet; private transient ValuesView<K,V> values; private transient EntrySetView<K,V> entrySet;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
静态代码块
// UnSafe类 底层都是native方法，调用C++的方法，直接操作内存 private static final sun.misc.Unsafe U; // 表示sizeCtl属性在ConcurrentHashMap中内存偏移地址 private static final long SIZECTL; // 表示TRANSFERINDEX属性在ConcurrentHashMap中内存偏移地址 private static final long TRANSFERINDEX; // 表示BASECOUNT属性在ConcurrentHashMap中内存偏移地址 private static final long BASECOUNT; // 表示CELLSBUSY属性在ConcurrentHashMap中内存偏移地址 private static final long CELLSBUSY; // 表示CELLVALUE属性在CounterCell中内存偏移地址 private static final long CELLVALUE; // 表示table数组中第一个元素的偏移地址 private static final long ABASE; private static final int ASHIFT; static { try { U = sun.misc.Unsafe.getUnsafe(); // 获取UnSafe对象 Class<?> k = ConcurrentHashMap.class; // 获取地址的偏移量，直接操作内存 SIZECTL = U.objectFieldOffset (k.getDeclaredField("sizeCtl")); TRANSFERINDEX = U.objectFieldOffset (k.getDeclaredField("transferIndex")); BASECOUNT = U.objectFieldOffset (k.getDeclaredField("baseCount")); CELLSBUSY = U.objectFieldOffset (k.getDeclaredField("cellsBusy")); Class<?> ck = CounterCell.class; CELLVALUE = U.objectFieldOffset (ck.getDeclaredField("value")); Class<?> ak = Node[].class; // 拿到数组的第一个元素的偏移地址 ABASE = U.arrayBaseOffset(ak); // 拿到数组单元占用空间大小，scale表示table数组中每一个单元所占用空间大小 // 结合上面的ABASE，就可以访问数组中的每一个位置的元素 int scale = U.arrayIndexScale(ak); // 判断scale是否是2的幂 // 1 0000 & 0 1111 = 0 if ((scale & (scale - 1)) != 0) throw new Error("data type scale not a power of two"); // 为了内存寻址(找数组位置)用 // numberOfLeadingZeros() 这个方法是返回当前数值转换为二进制后，从高位到低位开始统计，看有多少个0连续在一块 // 8(Integer数组) => 1000 numberOfLeadingZeros(8) = 32 - 4 = 28 // 4(int数组) => 100 numberOfLeadingZeros(4) = 32 - 3 = 29 // ASHIFT = 31 - 29 = 2 ？？ // ABASE + (5 << ASHIFT) ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); } catch (Exception e) { throw new Error(e); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
内部类
Node
static class Node<K,V> implements Map.Entry<K,V> { final int hash; // key的哈希值 final K key; volatile V val; // volatile修饰 保证内存可见性 volatile Node<K,V> next; // next指针 Node(int hash, K key, V val, Node<K,V> next) { this.hash = hash; this.key = key; this.val = val; this.next = next; } public final K getKey() { return key; } public final V getValue() { return val; } public final int hashCode() { return key.hashCode() ^ val.hashCode(); } public final String toString(){ return key + "=" + val; } public final V setValue(V value) { throw new UnsupportedOperationException(); } // 比较两个节点是否完全相同 public final boolean equals(Object o) { Object k, v, u; Map.Entry<?,?> e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry<?,?>)o).getKey()) != null && (v = e.getValue()) != null && (k == key || k.equals(key)) && (v == (u = val) || v.equals(u))); } // 在Node结构中用不到这个find方法，只有在当前桶位变为TreeNode 或 ForwardingNode才可能会用到 Node<K,V> find(int h, Object k) { Node<K,V> e = this; if (k != null) { do { K ek; // 判断两个节点的key是否相同，先比较哈希值，然后比较内存地址和equals if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; } while ((e = e.next) != null); } return null; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
TreeNode
// 继承于Node // TreeNode不仅仅可以构成红黑树结构 也可以构成双向链表结构 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; // 前驱节点 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; } Node<K,V> find(int h, Object k) { return findTreeNode(h, k, null); } /** * Returns the TreeNode (or null if not found) for the given key * starting at given root. */ final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) { if (k != null) { TreeNode<K,V> p = this; do { int ph, dir; K pk; TreeNode<K,V> q; TreeNode<K,V> pl = p.left, pr = p.right; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (pk != null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.findTreeNode(h, k, kc)) != null) return q; else p = pl; } while (p != null); } return null; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
ForwardingNode
// 继承Node节点 static final class ForwardingNode<K,V> extends Node<K,V> { /** * 表示新哈希表的引用 表示正在扩容或者数据正在迁移的过程中 * 1.如果当前是写线程，帮助进行并发扩容 * 2.如果是读线程，调用find方法去新哈希表中去查询 */ final Node<K,V>[] nextTable; ForwardingNode(Node<K,V>[] tab) { // hash值默认是-1 其他属性都是null super(MOVED, null, null, null); this.nextTable = tab; } // 到新表中取读数据 Node<K,V> find(int h, Object k) { // loop to avoid arbitrarily deep recursion on forwarding nodes outer: for (Node<K,V>[] tab = nextTable;;) { Node<K,V> e; int n; if (k == null || tab == null || (n = tab.length) == 0 || (e = tabAt(tab, (n - 1) & h)) == null) return null; for (;;) { int eh; K ek; if ((eh = e.hash) == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; if (eh < 0) { if (e instanceof ForwardingNode) { tab = ((ForwardingNode<K,V>)e).nextTable; continue outer; } else return e.find(h, k); } if ((e = e.next) == null) return null; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
参考
- ConcurrentHashMap 是 HashMap 的线程安全版本，内部也是使用 (数组 + 链表 + 红黑树) 的结构来存储元素，相比于同样线程安全的
-
相关阅读:
IO流内容总结
【联邦学习+区块链】TORR: A Lightweight Blockchain for Decentralized Federated Learning
MATLAB程序设计与应用 2.4 MATLAB常用内部函数
[科普文] Web3 中的资产负债表
独立站+TikTok是下个风口吗
【技术驿站】分布式基础与常见面试问题
java计算机毕业设计springboot+vue城市轨道交通线路查询系统
【DockerCE】Docker-CE 20.10.18正式版发布
Nginx请求强制缓存设置
redis7==源码阅读1：Makefile构成
- 原文地址：https://blog.csdn.net/weixin_53407527/article/details/127747585
