热门标签
热门文章
- 1免费的客服质检系统：开源多模态AI能力引擎平台_ai客服系统 开源
- 2一起做ROS-DEMO系列 (2):基于find_object_2d的目标模板匹配识别_安装find_object_2d包cannot locate node of type [find_
- 3生成式AI：大模型与大数据的神奇结合_大模型根据感知数据生成方案
- 4excel数据分析 - 10个清洗文本类函数_excel中去除所有文本的函数
- 5双向最大匹配算法思想详解，分词器及全文检索工具及Lucene框架简介_双向匹配
- 6深入理解循环神经网络（RNN）：案例和代码详解_rnn代码
- 7SpringBoot微服务架构学习
- 8Idea集成ChatGPT插件---AI帮你写代码_idea继承chatgpt插件
- 9开源中文大语言模型汇总_中文大模型
- 10关于嵌入式系统的学习路线图_zlg_boot smartarm2200
当前位置: article > 正文
Java并发编程——ConcurrentHashMap详解_java concurrenthashmap
作者：Monodyee | 2024-04-09 08:35:29
赞
踩
java concurrenthashmap
引出
场景：针对用户来做一个访问次数的记录。
通过HashMap进行记录，key为用户名，value为访问次数。
public class ConcurrentHashMapDemo { private static final HashMap<String, Integer> USER_ACCESS_COUNT = new HashMap<>(); public static void main(String[] args) { //针对用户来做一个访问次数的记录 Integer count = USER_ACCESS_COUNT.get("tom"); //线程安全问题:有可能数据被覆盖 if (count == null) { //没有该用户 USER_ACCESS_COUNT.put("tom", 1); } else { //访问次数+1 USER_ACCESS_COUNT.put("tom", count + 1); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
乍一看，我们通过如上代码记录用户的访问次数感觉应该是没有问题的。但是如果在多线程情况下，这种代码就会造成数据被覆盖的可能。
所以在多线程环境下我们使用HashMap是不安全的，需要引出ConcurrentHashMap。
为什么引入ConcurrentHashMap？
1.线程不安全的HashMap
在多线程环境下，使用HashMap的put操作会引起死循环，原因是多线程会导致HashMap的Entry链表形成环形数据结构，导致Entry的next节点永远不为空，就会产生死循环获取Entry。
2.效率低下的HashTable
HashTable容器使用sychronized来保证线程安全，采取锁住整个表结构来达到同步目的，在线程竞争激烈的情况下，当一个线程访问HashTable的同步方法，其他线程也访问同步方法时，会进入阻塞或轮询状态；如线程1使用put方法时，其他线程既不能使用put方法，也不能使用get方法，效率非常低下。
3.ConcurrentHashMap的锁分段技术可提升并发访问效率
首先将数据分成一段一段地存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
存储结构和实现
在JDK7和JDK8中，concurrentHashMap的实现方式是不同的。
JDK1.7采用的是segment分段锁，锁的粒度较大。
在JDK1.8中了segment，并且大量使用了synchronized，以及CAS无锁操作以保证ConcurrentHashMap操作的线程安全性；同时引入了红黑树，极大的提高了性能。
结构图
从上图可以初步了解其结构，当链表达到一定长度后会将链表转为红黑树。
基本使用
ConcurrentHashMap支持Java8中的lambda表达式，对代码进行了简化。
computeIfAbsent
如果key不存在，则调用后面的函数式接口计算，把计算后的val作为值。
public class ConcurrentHashMapDemo {
private static final ConcurrentHashMap<String, Integer> USER_ACCESS_COUNT = new ConcurrentHashMap<>();
public static void main(String[] args) {
//如果key不存在，则调用后面的函数式接口计算，把计算后的val作为值
USER_ACCESS_COUNT.computeIfAbsent("cc", k -> 1);
System.out.println(USER_ACCESS_COUNT.get("cc"));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
运行程序之后我们可以发现输出 1 ；
如果存在key呢？这个方法还生效吗？我们可以试下：
public class ConcurrentHashMapDemo {
private static final ConcurrentHashMap<String, Integer> USER_ACCESS_COUNT = new ConcurrentHashMap<>();
public static void main(String[] args) {
//如果key不存在，则调用后面的函数式接口计算，把计算后的val作为值
USER_ACCESS_COUNT.put("cc", 2);
USER_ACCESS_COUNT.computeIfAbsent("cc", k -> 1);
System.out.println(USER_ACCESS_COUNT.get("cc"));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
运行程序之后我们可以发现输出 2；可以发现该方法并没有生效，只有key不存在的时候才会生效。
computeIfPresent
如果key存在则修改并返回value，如果不存在则返回null。
public class ConcurrentHashMapDemo {
private static final ConcurrentHashMap<String, Integer> USER_ACCESS_COUNT = new ConcurrentHashMap<>();
public static void main(String[] args) {
//如果key存在则修改，如果不存在则返回null
System.out.println(USER_ACCESS_COUNT.computeIfPresent("cc", (k, v) -> v + 1));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
通过输出我们可以发现输出null；在试下如果key存在呢？
public class ConcurrentHashMapDemo {
private static final ConcurrentHashMap<String, Integer> USER_ACCESS_COUNT = new ConcurrentHashMap<>();
public static void main(String[] args) {
//如果key存在则修改，如果不存在则返回null
USER_ACCESS_COUNT.put("cc",1);
System.out.println(USER_ACCESS_COUNT.computeIfPresent("cc", (k, v) -> v + 1));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
运行程序，可以发现输出2；在原有数据上进行了计算并返回该key的值。
merge（合并数据）
如果指定的键尚未与(非空)值相关联，则将其与给定值相关联。
-
key - 与指定值关联的键
-
value - 如果不存在则使用的值
-
remappingFunction - 重新计算值(如果存在)的函数
public class ConcurrentHashMapDemo {
private static final ConcurrentHashMap<String, Integer> USER_ACCESS_COUNT = new ConcurrentHashMap<>();
//merge
public static void main(String[] args) {
ConcurrentHashMap<Integer, Integer> concurrentHashMap = new ConcurrentHashMap();
Stream.of(1, 2, 3, 4, 6, 2, 3, 6, 8, 1).forEach(v -> {
concurrentHashMap.merge(v, 5, Integer::sum);
});
System.out.println(concurrentHashMap);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
输出结果：
{1=10, 2=10, 3=10, 4=5, 6=10, 8=5}
- 1
源码分析
关键属性
在了解ConcurrentHashMap的具体方法实现前，我们需要系统的来看一下几个关键的地方。
-
table
volatile Node<K,V>[] table;//装载Node的数组，作为ConcurrentHashMap的数据容器，采用懒加载的方式，直到第一次插入数据的时候才会进行初始化操作，数组的大小总是为2的幂次方。
-
nextTable
volatile Node<K,V>[] nextTable;//扩容时使用，平时为null，只有在扩容的时候才为非null -
sizeCtl
volatile int sizeCtl;
该属性用来控制table数组的大小，根据是否初始化和是否正在扩容有几种情况：
当值为负数时：如果为-1表示正在初始化，如果为-N则表示当前正有N-1个线程进行扩容操作；
当值为正数时：如果当前数组为null的话表示table在初始化过程中，sizeCtl表示为需要新建数组的长度；
若已经初始化了，表示当前数据容器（table数组）可用容量也可以理解成临界值（插入节点数超过了该临界值就需要扩容），具体指为数组的长度n 乘以 加载因子loadFactor；
当值为0时，即数组长度为默认初始值。 -
sun.misc.Unsafe U
在ConcurrentHashMapde的实现中可以看到大量的U.compareAndSwapXXXX的方法去修改ConcurrentHashMap的一些属性。这些方法实际上是利用了CAS算法保证了线程安全性，这是一种乐观策略，假设每一次操作都不会产生冲突，当且仅当冲突发生的时候再去尝试。而CAS操作依赖于现代处理器指令集，通过底层CMPXCHG指令实现。CAS(V,O,N)核心思想为：若当前变量实际值V与期望的旧值O相同，则表明该变量没被其他线程进行修改，因此可以安全的将新值N赋值给变量；若当前变量实际值V与期望的旧值O不相同，则表明该变量已经被其他线程做了处理，此时将新值N赋给变量操作就是不安全的，在进行重试。而在大量的同步组件和并发容器的实现中使用CAS是通过sun.misc.Unsafe类实现的，该类提供了一些可以直接操控内存和线程的底层操作，可以理解为java中的“指针”。该成员变量的获取是在静态代码块中：static { try { U = sun.misc.Unsafe.getUnsafe(); ....... } catch (Exception e) { throw new Error(e); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
构造方法
可以看到ConcurrentHashMap的构造方法中并没有初始化，可以得出他是在数据插入的时候初始化。
public ConcurrentHashMap() {
}
- 1
- 2
Put
public V put(K key, V value) {
return putVal(key, value, false);
}
- 1
- 2
- 3
transient volatile Node<K,V>[] table; //装在node的数组
- 1
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; //自旋（;;） {cas} for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; //如果tab为空，说明还没有初始化. if (tab == null || (n = tab.length) == 0) tab = initTable(); //初始化完成后，进入到下一次循环 //(n - 1) & hash) -> 0-15 ->计算数组下标位置. else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //如果当前的node的位置为空，直接存储到该位置. //通过cas来保证原子性. if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; synchronized (f) { //锁住当前的node节点，避免线程安全问题 if (tabAt(tab, i) == f) {//重新判断（） //针对链表来处理 if (fh >= 0) { binCount = 1; //统计了链表的长度 for (Node<K,V> e = f;; ++binCount) { K ek; //是否存在相同的key，如果存在，则覆盖 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } //如果不存在，则把当前的key/value添加到链表中 Node<K,V> pred = e; //说明到了最后一个节点，直接添加到尾部 if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } //针对红黑树的处理 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; } } } } if (binCount != 0) { //如果链表长度大于等于8，则会调用treeifyBin方法 扩容 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); 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
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
initTable 初始化
private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; //只要tab没有初始化，就不断循环直到初始完成 while ((tab = table) == null || tab.length == 0) { if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin //通过cas自旋（通过CAS来占用一个锁的标记）-1 为锁的标记 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //说明当前线程抢到了锁 try { if ((tab = table) == null || tab.length == 0) { int n = (sc > 0) ? sc : DEFAULT_CAPACITY; @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = tab = nt; sc = n - (n >>> 2); //扩容的阈值. } } finally { sizeCtl = sc; } break; } } return tab; }
- 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
treeifyBin 扩容还是转换
会根据阈值来判断，是转化为红黑树还是扩容。
private final void treeifyBin(Node<K,V>[] tab, int index) { Node<K,V> b; int n, sc; if (tab != null) { //如果table长度小于64. if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); //扩容 else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { synchronized (b) { //红黑树转化. if (tabAt(tab, index) == b) { TreeNode<K,V> hd = null, tl = null; for (Node<K,V> e = b; e != null; e = e.next) { TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null); if ((p.prev = tl) == null) hd = p; else tl.next = p; tl = p; } setTabAt(tab, index, new TreeBin<K,V>(hd)); } } } } }
- 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
tryPresize 扩容
注意点：会存在两种情况进行扩容
一般情况下，不管什么数据结构，新增结点的时候，如果数组长度超过阈值（sizeCtl=加载因子0.75*数组长度），则会进行2倍扩容。
红黑树，新增结点的时候当链表长度超过8位，转换红黑树时，如果数组长度小于默认阈值MIN_TREEIFY_CAPACITY=64位，会扩大原来长度的2倍。（注意这里是小于，会转换红黑树已经代表冲突太多了，不然链表其实就够了。意思就是你数据hash冲突太多了，导致变成红黑树，必须扩容，把hash值打散，让红黑树的数据降下来。）
该方法用来实现扩容。
-
多线程并发扩容（允许多个线程来协助扩容）
- 记录当前的线程数量（sizeCtl）
- 当每个线程完成数据迁移之后，推出的时候，要剪掉协助扩容的线程数量
-
扩容的本质
- 创建一个新的数组（16->32,32->64）
- 然后把老数据迁移到新数组中
-
sizeStamp : 扩容戳
private final void tryPresize(int size) { //用来判断扩容的目标大小. int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); int sc; while ((sc = sizeCtl) >= 0) { //说明要做数组的初始化. Node<K,V>[] tab = table; int n; // 初始化. if (tab == null || (n = tab.length) == 0) { n = (sc > c) ? sc : c; //如果初始容量|扩容的目标容量，谁最大选谁. if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if (table == tab) { @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; } } } //已经是最大容量了，不能扩容了。直接返回 else if (c <= sc || n >= MAXIMUM_CAPACITY) break; else if (tab == table) { int rs = resizeStamp(n); //扩容戳. 保证当前扩容范围的唯一性. //第一次扩容的时候，不会走这段逻辑 if (sc < 0) { Node<K,V>[] nt; //表示扩容结束 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; //表示没有结束，每增加一个扩容线程，则在低位+1. if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } //第一次扩容走这段逻辑 注意不同的是低位+2 else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, 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
必须要有一个地方去记录，在当前扩容范围内，有多少个线程参与数据的迁移工作. 必须要保证所有的线程完成了迁移的动作，才能够表示扩容完成。
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
- 1
- 2
- 3
0000 0000 0000 0000 0000 0000 0001 0000 -> 27位
0000 0000 0000 0000 1000 0000 0001 1011
resizeStamp返回的数: 1000 0000 0001 1011 0000 0000 0000 0000
rs << RESIZE_STAMP_SHIFT) + 2 ,二进制左移16位+2
1000 0000 0001 1011 0000 0000 0000 0010 ->表示当前有一个线程来扩容。
扩容戳的高位16表示当前的扩容标记， 保证唯一性；低16位表示当前扩容的线程数量。
transfer 数据迁移
如何实现多个线程对同一个容器做数据迁移.
- 数据的迁移
- 需要计算当前线程的数据迁移空间（任务拆分）
- 创建一个新的数组（容量为扩容后的大小）
- 实现数据转移
- 如果是红黑树
- 数据迁移后，不满足红黑树的条件，则红黑树转链表
- 如果是链表
- 高低位迁移
- 如果是红黑树
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; //计算每个线程处理的数据的区间大小，最小是16。 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range //表示扩容之后的数组，在原来的基础上扩大两倍 if (nextTab == null) { // initiating try { @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; transferIndex = n; } //transferIndex = old table[] 的长度。 int nextn = nextTab.length; //用来表示已经迁移完的状态，也就是说，如果某个old数组的节点完成了迁移，则需要更改成fwd。 ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { Node<K,V> f; int fh; while (advance) { int nextIndex, nextBound; if (--i >= bound || finishing) advance = false; else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { bound = nextBound; i = nextIndex - 1; advance = false; } //假设数组长度是32, //第一次 [16(nextBound),31(i)] //第二次 [0,15] } //是否扩容结束 if (i < 0 || i >= n || i + n >= nextn) { int sc; if (finishing) { nextTable = null; table = nextTab; sizeCtl = (n << 1) - (n >>> 1); return; } if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) return; finishing = advance = true; i = n; // recheck before commit } } //得到数组下标为31的位置的值。 else if ((f = tabAt(tab, i)) == null) //说明当前数组位置为空。 advance = casTabAt(tab, i, null, fwd); //直接改成fwd -> 表示迁移完成. else if ((fh = f.hash) == MOVED) //判断是否已经被处理过了，如果是，则进入下一次 区间遍历 advance = true; // already processed else { //加锁->针对当前要去迁移的节点。 synchronized (f) { if (tabAt(tab, i) == f) { //保证迁移过程中，其他线程调用put()方法时，必须要等待。 Node<K,V> ln, hn; //以下为针对不同类型的节点做不同的处理 //链表和红黑树 if (fh >= 0) { int runBit = fh & n; Node<K,V> lastRun = f; for (Node<K,V> p = f.next; p != null; p = p.next) { int b = p.hash & n; if (b != runBit) { runBit = b; lastRun = p; } } if (runBit == 0) { ln = lastRun; hn = null; } else { hn = lastRun; ln = null; } for (Node<K,V> p = f; p != lastRun; p = p.next) { int ph = p.hash; K pk = p.key; V pv = p.val; if ((ph & n) == 0) ln = new Node<K,V>(ph, pk, pv, ln); else hn = new Node<K,V>(ph, pk, pv, hn); } setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } //红黑树 else if (f instanceof TreeBin) { TreeBin<K,V> t = (TreeBin<K,V>)f; TreeNode<K,V> lo = null, loTail = null; TreeNode<K,V> hi = null, hiTail = null; int lc = 0, hc = 0; for (Node<K,V> e = t.first; e != null; e = e.next) { int h = e.hash; TreeNode<K,V> p = new TreeNode<K,V> (h, e.key, e.val, null, null); if ((h & n) == 0) { if ((p.prev = loTail) == null) lo = p; else loTail.next = p; loTail = p; ++lc; } else { if ((p.prev = hiTail) == null) hi = p; else hiTail.next = p; hiTail = p; ++hc; } } ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin<K,V>(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin<K,V>(hi) : t; setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } } } } } }
- 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
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
高低位迁移
数组下标的计算方式是： i = (n - 1) & hash)
随着扩容导致长度n的值是变化的，所以key的hash值不同，导致部分key可能会发生迁移
会导致数据的位置的迁移
从下图的计算可以看出容量为16和32的时候，部分key的值会不同。
当数组扩容之后，会存在两种情况
-
数组位置不会发生变化
-
数组位置会发生变化
意味着，数据在做迁移的时候，有些数据需要迁移，有些数据不要迁移。那么该如何识别呢？核心代码如下。
if (fh >= 0) { int runBit = fh & n; Node<K,V> lastRun = f; for (Node<K,V> p = f.next; p != null; p = p.next) { int b = p.hash & n; if (b != runBit) { runBit = b; lastRun = p; } } if (runBit == 0) { ln = lastRun; hn = null; } else { hn = lastRun; ln = null; } for (Node<K,V> p = f; p != lastRun; p = p.next) { int ph = p.hash; K pk = p.key; V pv = p.val; if ((ph & n) == 0) ln = new Node<K,V>(ph, pk, pv, ln); else hn = new Node<K,V>(ph, pk, pv, hn); } setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; }
- 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
迁移的流程可以看下图：
如何统计元素个数
ConcurrentHashMap如何统计元素个数？
private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;
- 1
- 2
-
如果竞争不激烈的情况下，直接用cas( baseCount+1)
-
如果竞争激烈的情况下，采用数组的方式来进行计数。
private final void addCount(long x, int check) { CounterCell[] as; long b, s; //统计元素个数 if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { //会完成CounterCell的初始化以及元素的累加 fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); } //是否要做扩容 if (check >= 0) { Node<K,V>[] tab, nt; int n, sc; //helpTransfer -> 第一次扩容的场景. while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); if (sc < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); } } }
- 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
private final void fullAddCount(long x, boolean wasUncontended) { int h; if ((h = ThreadLocalRandom.getProbe()) == 0) { ThreadLocalRandom.localInit(); // force initialization h = ThreadLocalRandom.getProbe(); wasUncontended = true; } boolean collide = false; // True if last slot nonempty for (;;) { CounterCell[] as; CounterCell a; int n; long v; if ((as = counterCells) != null && (n = as.length) > 0) { if ((a = as[(n - 1) & h]) == null) { if (cellsBusy == 0) { // Try to attach new Cell CounterCell r = new CounterCell(x); // Optimistic create if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { boolean created = false; try { // Recheck under lock //针对已经初始化的数组的某个位置，去添加一个CounterCell。 CounterCell[] rs; int m, j; if ((rs = counterCells) != null && (m = rs.length) > 0 && rs[j = (m - 1) & h] == null) { rs[j] = r; created = true; } } finally { cellsBusy = 0; } if (created) break; continue; // Slot is now non-empty } } collide = false; } else if (!wasUncontended) // CAS already known to fail wasUncontended = true; // Continue after rehash else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) break; else if (counterCells != as || n >= NCPU) collide = false; // At max size or stale else if (!collide) collide = true; //扩容部分. else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { //获得锁 try { if (counterCells == as) {// Expand table unless stale CounterCell[] rs = new CounterCell[n << 1]; //扩容一倍 for (int i = 0; i < n; ++i) //遍历数组，添加到新的数组中。 rs[i] = as[i]; counterCells = rs; } } finally { cellsBusy = 0; } collide = false; continue; // Retry with expanded table } h = ThreadLocalRandom.advanceProbe(h); } //如果CounterCell为空, 保证在初始化过程的线程安全性。 else if (cellsBusy == 0 && counterCells == as && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { //一旦cas成功，说明 当前线程抢到了锁。 boolean init = false; try { // Initialize table if (counterCells == as) { //初始化长度为2的数组， CounterCell[] rs = new CounterCell[2]; rs[h & 1] = new CounterCell(x); //把x保存到某个位置. counterCells = rs; //复制给成员变量counterCells init = true; } } finally { cellsBusy = 0; //释放锁. } if (init) break; } //最终的情况， 直接修改baseCount。 else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x)) break; // Fall back on using base } }
- 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
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
具体流程图如下：
关于红黑树的实现分析
我们知道ConcurrentHashMap中，数据存储结构是由链表和红黑树组成的，前面的内容中全部是基于链表的结构来分析的，那么接下来简单分析一下红黑树这个数据结构。
演示网站
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
什么是红黑树
红黑树是一种特殊的平衡二叉树，平衡二叉树具备的特征是：二叉树左子树和右子树的高度差的绝对值不超过1。
为了更好的理解平衡二叉树，我们先来了解一下二叉搜索树（Binary Search Tree)，二叉搜索树的特征是：如果二叉树的左子树不为空，则左子树上所有节点均小于它的根节点的值；如果二叉树的右子树不为空，则右子树的的所有节点均大于它根节点的值，如下图所示，这就是一棵符合平衡二叉搜索树特征的二叉树。
二叉搜索树理论上来说，时间复杂度为O(logn)，但是在一种极端情况下，会出现如下图所示的情况，如果插入的元素都是符合大于根节点的值时，相当于二叉树变成了链表结构，这个时候对于数据的查询、插入、删除等操作，时间复杂度变成了O(n)。
出现这个问题的原因是二叉搜索树没有一种机制来实现自动平衡，因此为了解决这个问题，引入了平衡二叉树，平衡二叉树能够保证在极端的情况下，二叉树仍然能够保持绝对平衡，也就是左子树和右子树的高度差的绝对值不超过1，平衡二叉树为了满足绝对的平衡，在插入和删除元素的时候，只要存在不满足条件的情况，就需要通过旋转来保持平衡，而这个平衡过程比较耗时。因此为了二叉树的平衡方面以及性能方面做好权衡，引入了红黑树，它相当于适当放宽了平衡的要求，所以它又称为特殊的平衡二叉树。
旋转又分为左旋和右旋。
左旋
右旋
红黑树的平衡规则
红黑树既然是一种特殊的平衡二叉树，那么它必然有一种规则来实现平衡，因此一棵红黑树必须满足以下五个特征：
-
红黑树的每个节点颜色只能是红色或者黑色。
-
根节点是黑色。
-
如果当前的节点是红色，那么它的子节点必须是黑色。
-
所有叶子节点（NIL节点，NIL节点表示叶子节点为空的节点）都是黑色。
-
从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点。
注意点：
所有节点在添加的时候都是以红色来添加（破坏红黑树结构的可能性比较小）
总结
-
使用 JAVA8。
-
安全性的保障。
-
原理分析
- put方法元素添加， 构建数据
- 解决hash冲突的问题 - 链式寻址
- 扩容 -> 数组的扩容 ->
- 数据迁移
- 多线程并发协助数据迁移
- 高低位迁移， 需要迁移的数据放在高位链，不需要迁移的放在地位链， 然后一次性把高位和地位set到指定的新的数组下标位置。
- 元素的统计
- 数组的方式， 分片的设计思想。
- 汇总数组+baseCount的值来完成数据累加
- 当链表长度大于等于8，并且数组长度大于64的时候，链表转化为红黑树
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/391514
推荐阅读
相关标签
