前言
文本已收录至我的GitHub仓库,欢迎Star:github.com/bin39232820…
种一棵树最好的时间是十年前,其次是现在
絮叨
HashMap讲完了,我们来看一下和他内部结构差不多的ConcurrentHashMap
🔥史上最全的Java容器集合之ArrayList(源码解读)
🔥史上最全的Java容器集合之Vector和LinkedList(源码解读)
🔥史上最全的Java容器集合之equals 和 hashCode
本来Map家族还有一个TreeMap,但是自己对于红黑树还不是特别了解,就先放一放吧,因为用的也不多,ConcurrentHashMap可以解决线程安全问题,至于HashTable已经用的非常少了,不能为null,也是线程安全的。
ConcurrentHashMap
Tips:其实今天讲它肯定是大概的过一下,它既然是一个线程安全的容器,那么线程安全也要涉及到很多的知识点,比如
- 悲观锁与乐观锁
- 原子性,指令有序性和线程可见性
- 无锁算法
- 内存屏障
- Java内存模型
这些目前等讲JVM的时候我们再一起去探讨吧,我们今天主要是过一下它,等后面把知识点串起来就会明白的。
跟HashTable 的区别,1.7和1.8的比较
ConcurrentHashMap是conccurrent家族中的一个类,由于它可以高效地支持并发操作,以及被广泛使用,经典的开源框架Spring的底层数据结构就是使用ConcurrentHashMap实现的。与同是线程安全的老大哥HashTable相比,它已经更胜一筹,因此它的锁更加细化,而不是像HashTable一样为几乎每个方法都添加了synchronized锁,这样的锁无疑会影响到性能。
1.7和1.8实现线程安全的思想也已经完全变了其中抛弃了原有的Segment 分段锁,而采用了 CAS + synchronized 来保证并发安全性。它沿用了与它同时期的HashMap版本的思想,底层依然由“数组”+链表+红黑树的方式思想,但是为了做到并发,又增加了很多辅助的类,例如TreeBin,Traverser等对象内部类。
继承结构
跟HashMap就是一模一样
其实一个类是用来干嘛的再类的最开始的介绍是很详细的,但是我的渣渣英语水平,太难了,如果有能力的童鞋可以去好好看看。总结一下说了啥:
- JDK1.8底层是散列表+红黑树
- ConCurrentHashMap支持高并发的访问和更新,它是线程安全的
- 检索操作不用加锁,get方法是非阻塞的
- key和value都不允许为null
常量
//表的最大容量 private static final int MAXIMUM_CAPACITY = 1 << 30; //默认表的容量 private static final int DEFAULT_CAPACITY = 16; //最大数组长度 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; //树化阈值 static final int TREEIFY_THRESHOLD = 8; //去树化阈值 static final int UNTREEIFY_THRESHOLD = 6; //树化的最小容量 static final int MIN_TREEIFY_CAPACITY = 64; //转移的最小值 private static final int MIN_TRANSFER_STRIDE = 16; //生成sizeCtl的最小位数 private static int RESIZE_STAMP_BITS = 16; //进行扩容允许的最大线程数 private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; //sizeCtl所需要的偏移位数 private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; //标志值 static final int MOVED = -1; // hash for forwarding nodes static final int TREEBIN = -2; // hash for roots of trees static final int RESERVED = -3; // hash for transient reservations static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash //cpu数量 static final int NCPU = Runtime.getRuntime().availableProcessors(); //序列化属性 private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField("segments", Segment[].class), new ObjectStreamField("segmentMask", Integer.TYPE), new ObjectStreamField("segmentShift", Integer.TYPE) }; 复制代码
大部分的和HashMap差不多,只有少数的不同
成员变量
//node数组,第一次插入节点时初始化 都加了内存屏障 transient volatile Node<K,V>[] table; //用于扩容 private transient volatile Node<K,V>[] nextTable; //计算器值,通过CAS修改值,没有竞争时使用,或者出现多线程初始化时回滚 private transient volatile long baseCount; //初始化和扩容的标志,concurrent包中有很多类似用法 // -1 初始化中; -N (N-1)个线程在扩容;table没有数据 初始化的大小 ; table有数据 下一次扩容的大小 // 非常重要的一个属性,源码中的英文翻译,直译过来是下面的四行文字的意思 // sizeCtl = -1,表示有线程正在进行真正的初始化操作 // sizeCtl = -(1 + nThreads),表示有nThreads个线程正在进行扩容操作 // sizeCtl > 0,表示接下来的真正的初始化操作中使用的容量,或者初始化/扩容完成后的threshold // sizeCtl = 0,默认值,此时在真正的初始化操作中使用默认容量 //sizeCtl = -(1 + nThreads)这个,网上好多都是用第二句的直接翻译去解释代码,这样理解是错误的 // 默认构造的16个大小的ConcurrentHashMap,只有一个线程执行扩容时,sizeCtl = -2145714174, // 但是照这段英文注释的意思,sizeCtl的值应该是 -(1 + 1) = -2 // sizeCtl在小于0时的确有记录有多少个线程正在执行扩容任务的功能,但是不是这段英文注释说的那样直接用 -(1 + nThreads) // 实际中使用了一种生成戳,根据生成戳算出一个基数,不同轮次的扩容操作的生成戳都是唯一的,来保证多次扩容之间不会交叉重 叠, // 当有n个线程正在执行扩容时,sizeCtl在值变为 (基数 + n) // 1.8.0_111的源码的383-384行写了个说明:A generation stamp in field sizeCtl ensures that resizings do not overlap. private transient volatile int sizeCtl; /** * The next table index (plus one) to split while resizing. */ //transfer的table索引 private transient volatile int transferIndex; //扩容或创建counterCells的自旋锁 private transient volatile int cellsBusy; // CounterCell数组 private transient volatile CounterCell[] counterCells; // views private transient KeySetView<K,V> keySet; private transient ValuesView<K,V> values; private transient EntrySetView<K,V> entrySet; 复制代码
这里重点解释一下sizeCtl这个属性。可以说它是ConcurrentHashMap中出镜率很高的一个属性,因为它是一个控制标识符,在不同的地方有不同用途,而且它的取值不同,也代表不同的含义。
- 负数代表正在进行初始化或扩容操作
- -1代表正在初始化
- -N 表示有N-1个线程正在进行扩容操作
- 正数或0代表hash表还没有被初始化,这个数值表示初始化或下一次进行扩容的大小,这一点类似于扩容阈值的概念。还后面可以看到,它的值始终是当前ConcurrentHashMap容量的0.75倍,这与loadfactor是对应的。
构造方法
其实和HashMap是大同小异的,此时ConcurrentHashMap的构造方法逻辑和HashMap基本一致,只是多了concurrencyLevel和SizeCtl。 而且此时也没有初始化table,它是要等到第一次put的时候才初始化table,