Java并发包——线程安全的Map相关类
Java并发包——线程安全的Map相关类
摘要：本文主要学习了Java并发包下线程安全的Map相关的类。
部分内容来自以下博客：
https://blog.csdn.net/bill_xiang_/article/details/81122044
https://www.cnblogs.com/zhaojj/p/8942647.html
分类
参照之前在学习集合时候的分类，可以将JUC下有关Map相关的类进行分类。
ConcurrentHashMap：继承于AbstractMap类，相当于线程安全的HashMap，是线程安全的哈希表。JDK1.7之前使用分段锁机制实现，JDK1.8则使用数组+链表+红黑树数据结构和CAS原子操作实现。
ConcurrentSkipListMap：继承于AbstractMap类，相当于线程安全的TreeMap，是线程安全的有序的哈希表。通过“跳表”来实现的。
ConcurrentHashMap
JDK1.7的分段锁机制
Hashtable之所以效率低下主要是因为其实现使用了synchronized关键字对put等操作进行加锁，而synchronized关键字加锁是对整个对象进行加锁。也就是说在进行put等修改Hash表的操作时，锁住了整个Hash表，从而使得其表现的效率低下。
因此，在JDK1.5到1.7版本，Java使用了分段锁机制实现ConcurrentHashMap。
简而言之，ConcurrentHashMap在对象中保存了一个Segment数组，即将整个Hash表划分为多个分段。而每个Segment元素，即每个分段则类似于一个Hashtable。在执行put操作时首先根据hash算法定位到元素属于哪个Segment，然后使用ReentrantLock对该Segment加锁即可。因此，ConcurrentHashMap在多线程并发编程中可是实现多线程put操作。
Segment类是ConcurrentHashMap中的内部类，继承于ReentrantLock类。ConcurrentHashMap与Segment是组合关系，一个ConcurrentHashMap对象包含若干个Segment对象，ConcurrentHashMap类中存在“Segment数组”成员。
HashEntry也是ConcurrentHashMap的内部类，是单向链表节点，存储着key-value键值对。Segment与HashEntry是组合关系，Segment类中存在“HashEntry数组”成员，“HashEntry数组”中的每个HashEntry就是一个单向链表。
JDK1.8的改进
在JDK1.7的版本，ConcurrentHashMap是通过分段锁机制来实现的，所以其最大并发度受Segment的个数限制。因此，在JDK1.8中，ConcurrentHashMap的实现原理摒弃了这种设计，而是选择了与HashMap类似的数组+链表+红黑树的方式实现，而加锁则采用CAS原子更新、volatile关键字、synchronized可重入锁实现。
JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）。
JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了。
JDK1.8版本的扩容操作支持多线程并发。在之前的版本中如果Segment正在进行扩容操作，其他写线程都会被阻塞，JDK1.8改为一个写线程触发了扩容操作，其他写线程进行写入操作时，可以帮助它来完成扩容这个耗时的操作。
JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表。
重要属性
sizeCtl：标志控制符。这个参数非常重要，出现在ConcurrentHashMap的各个阶段，不同的值也表示不同情况和不同功能：
负数代表正在进行初始化或扩容操作。-1表示正在进行初始化操作。-N表示有N-1个线程正在进行扩容操作。
其为0时，表示hash表还未初始化。
正数表示下一次进行扩容的大小，类似于扩容阈值。它的值始终是当前容量的0.75倍，如果hash表的实际大小>=sizeCtl，则进行扩容。
构造方法
需要说明的是，在构造方法里并没有对集合进行初始化操作，而是等到了添加元素的时候才进行初始化，属于懒汉式的加载方式。
而且loadFactor参数在JDK1.8中也不再有加载因子的意义，仅为了兼容以前的版本，加载因子由sizeCtl来替代。
同样，concurrencyLevel参数在JDK1.8中也不再有多线程运行的并发度的意义，仅为了兼容以前的版本。
// 空参构造器。
public ConcurrentHashMap() {
} // 指定初始容量的构造器。
public ConcurrentHashMap(int initialCapacity) {
// 参数有效性判断。
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
// 设置标志控制符。
this.sizeCtl = cap;
} // 指定初始容量，加载因子的构造器。
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
} // 指定初始容量，加载因子，并发度的构造器。
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
// 参数有效性判断。
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
// 比较初始容量和并发度的大小，取最大值作为初始容量。
if (initialCapacity < concurrencyLevel)
initialCapacity = concurrencyLevel;
// 计算最大容量。
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
// 设置标志控制符。
this.sizeCtl = cap;
} // 包含指定Map集合的构造器。
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
// 设置标志控制符。
this.sizeCtl = DEFAULT_CAPACITY;
// 放置指定的集合。
putAll(m);
}
初始化方法
集合并不会在构造方法里进行初始化，而是在用到集合的时候才进行初始化，在初始化的同时会设置集合的阈值。
初始化方法主要应用了关键属性sizeCtl，如果sizeCtl小于0，表示其他线程正在进行初始化，就放弃这个操作，在这也可以看出初始化只能由一个线程完成。如果获得了初始化权限，就用CAS方法将sizeCtl置为-1，防止其他线程进入。初始化完成后，将sizeCtl的值改为0.75倍的集合容量，作为阈值。
在初始化的过程中为了保证线程安全，总共使用了两步操作：
1）通过CAS原子更新方法将sizeCtl设置为-1，保证只有一个线程进入。
2）线程获取初始化权限后内部通过 if ((tab = table) == null || tab.length == 0) 二次判断，保证只有在未初始化的情况下才能执行初始化。
// 初始化集合，使用CAS原子更新保证线程安全，使用volatile保证顺序和可见性。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// 死循环以完成初始化。
while ((tab = table) == null || tab.length == 0) {
// 如果sizeCtl小于0则表示正在初始化，当前线程让步。
if ((sc = sizeCtl) < 0)
Thread.yield();
// 如果需要初始化，并且使用CAS原子更新。判断SIZECTL保存的sizeCtl值是否和sc一致，一致则将sizeCtl更新为-1。
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// 第一个线程初始化之后，第二个线程还会进来所以需要重新判断。类似于线程同步的二次判断。
if ((tab = table) == null || tab.length == 0) {
// 如果没有指定容量则使用默认容量16。
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 初始化一个指定容量的节点数组。
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
// 将节点数组指向集合。
table = tab = nt;
// 扩容阀值，获取容量的0.75倍的值，写法略叼更高端比直接乘高效。
sc = n - (n >>> 2);
}
} finally {
// 将sizeCtl的值设为阈值。
sizeCtl = sc;
}
break;
}
}
return tab;
}
添加方法
1）校验数据。判断传入一个key和value是否为空，如果为空就直接报错。ConcurrentHashMap是不可为空的（HashMap是可以为空的）。
2）是否要初始化。判断table是否为空，如果为空就进入初始化阶段。
3）如果数组中key指定的桶是空的，那就使用CAS原子操作把键值对插入到这个桶中作为头节点。
4）协助扩容。如果这个要插入的桶中的hash值为-1，也就是MOVED状态（也就是这个节点是ForwordingNode），那就是说明有线程正在进行扩容操作，那么当前线程就进入协助扩容阶段。
5）插入数据到链表或者红黑树。如果这个节点是链表节点，那么就遍历这个链表，如果有相同的key值就更新value值，如果没有发现相同的key值，就在链表的尾部插入该数据。如果这个节点是红黑树节点，那就需要按照树的插入规则进行插入。
6）转化成红黑树。插入结束之后判断如果是链表节点，并且个数大于8，就需要把链表转化为红黑树存储。
7）添加结束之后，需要给增加已存储的数量，并判断是否需要扩容。
// 添加元素。
public V put(K key, V value) {
return putVal(key, value, false);
} // 添加元素。
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 排除null的数据。
if (key == null || value == null) throw new NullPointerException();
// 计算hash，并保证hash一定大于零，负数表示在扩容或者是树节点。
int hash = spread(key.hashCode());
// 节点个数。0表示未加入新结点，2表示TreeBin或链表结点数，其它值表示链表结点数。主要用于每次加入结点后查看是否要由链表转为红黑树。
int binCount = 0;
// CAS经典写法，不成功无限重试。
for (Node<K,V>[] tab = table;;) {
// 声明节点、集合长度、对应的数组下标、节点的hash值。
Node<K,V> f; int n, i, fh;
// 如果没有初始化则进行初始化。除非构造时指定集合，否则默认构造不初始化，添加时检查是否初始化，属于懒汉模式初始化。
if (tab == null || (n = tab.length) == 0)
// 初始化集合。
tab = initTable();
// 如果已经初始化了，并且使用CAS根据hash获取到的节点为null。
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 使用CAS比较该索引处是否为null防止其它线程已改变该值，null则插入。
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
// 添加成功，跳出循环。
break;
}
// 如果获取到节点不为null，并且节点的hash为-1，则表示节点在扩容。
else if ((fh = f.hash) == MOVED)
// 帮助扩容。
tab = helpTransfer(tab, f);
// 产生hash碰撞，并且没有扩容操作。
else {
V oldVal = null;
// 锁住节点。
synchronized (f) {
// 这里volatile获取首节点与节点对比判断节点还是不是首节点。
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;
}
}
}
// 如果是红黑树节点。
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。
if (binCount >= TREEIFY_THRESHOLD)
// 尝试转为红黑树。
treeifyBin(tab, i);
if (oldVal != null)
// 返回原值。
return oldVal;
break;
}
}
}
// 集合容量加一并判断是否要扩容。
addCount(1L, binCount);
return null;
}
修改容量并判断是否需要扩容
1）尝试对baseCount和CounterCell进行增加的操作，这些操作基于CAS原子操作，同时使用volatile保证顺序和可见性。备用方法fullAddCount()则会死循环插入。
2）判断是否要扩容操作，并且支持多个线程协助进行扩容。
// 修改容量并判断是否要扩容。
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// counterCells不为null，或者使用CAS对baseCount增加失败了，说明产生了并发，需要进一步处理。
// counterCells初始为null，如果不为null，说明产生了并发。
// 如果counterCells仍然为null，但是在使用CAS对baseCount增加的时候失败，表示产生了并发。
if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
// 如果counterCells是null的，或者counterCells的个数小于0。
// 或者counterCells的每一个元素都是null。
// 或者用counterCells数组中随机位置的值进行累加也失败了。
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
// 继续更新counterCells和baseCount。
fullAddCount(x, uncontended);
return;
}
// 删除或清理节点时是-1，插入索引首节点0，第二个节点是1。
if (check <= 1)
return;
// 计算map元素个数。
s = sumCount();
}
// 如果check的值大于等于0，需要检查是否要扩容。删除或清理节点时是-1，此时不检查。
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// 当元素个数大于阈值，并且集合不为空，并且元素个数小于最大值。循环判断，防止多线程同时扩容跳过if判断。
while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) {
// 生成与n有关的标记，且n不变的情况下生成的一定是一样的。
int rs = resizeStamp(n);
// sc在单线程时是大于等于0的，如果小于0说明有其他线程正在扩容。
// 如果小于0说明有线程执行了else里面的判断，导致rs左移16位并在低位+2赋值给sc。
if (sc < 0) {
// 在第一次左移16位的sc，经过第二次右移16位之后，还和rs相同，说明已经扩容完成。
// 线程执行扩容，会使用CAS让sc自增，如果sc和右移并累加后的rs相等，说明已经扩容完成。
// 线程执行扩容，会使用CAS让sc自增，如果sc和右移并累加最大值后的rs相等，说明已经扩容完成。
// 如果下个节点是null，说明已经扩容完成。
// 如果transferIndex小于等于0，说明集合已完成扩容，无法再分配任务。
if ((sc >>> RESIZE_STAMP_SHIFT) != rs ||
sc == rs + 1 ||// 此处应为 sc == (rs << RESIZE_STAMP_SHIFT) + 1
sc == rs + MAX_RESIZERS ||// 此处应为 sc == (rs << RESIZE_STAMP_SHIFT) + MAX_RESIZERS
(nt = nextTable) == null ||
transferIndex <= 0)
// 跳出循环。
break;
// 使用CAS原子累加sc的值。
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// 扩容。
transfer(tab, nt);
}
// 如果sizeCtl大于或等于0，说明第一次扩容，并且使用CAS设置sizeCtl为rs左移后的负数，并且低位+2表示有2-1个线程正在扩容。
else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
// 进行扩容操作。
transfer(tab, null);
// 计算map元素个数，baseCount和counterCells数组存的总和。
s = sumCount();
}
}
}
帮助扩容方法
1）判断集合已经完成初始化，并且节点是ForwordingNode类型（表示正在扩容），并且当前节点的子节点不为null，如果不成立则不需要扩容。
2）循环判断是否扩容成功，如果没有就使用CAS原子操作累加扩容的线程数，并且进行协助扩容。
// 帮助扩容。
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
// 如果表不为null，并且是fwd类型的节点，并且节点的子节点也不为null。
if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
// 得到标识符。
int rs = resizeStamp(tab.length);
// 如果nextTab没有被并发修改，并且tab也没有被并发修改，并且sizeCtl小于0说明还在扩容。
while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
// 在第一次左移16位的sc，经过第二次右移16位之后，还和rs相同，说明已经扩容完成。
// 线程执行扩容，会使用CAS让sc自增，如果sc和右移并累加后的rs相等，说明已经扩容完成。
// 线程执行扩容，会使用CAS让sc自增，如果sc和右移并累加最大值后的rs相等，说明已经扩容完成。
// 如果transferIndex小于等于0，说明集合已完成扩容，无法再分配任务。
if ((sc >>> RESIZE_STAMP_SHIFT) != rs ||
sc == rs + 1 ||// 此处应为 sc == (rs << RESIZE_STAMP_SHIFT) + 1
sc == rs + MAX_RESIZERS ||// 此处应为 sc == (rs << RESIZE_STAMP_SHIFT) + MAX_RESIZERS
transferIndex <= 0)
// 跳出循环。
break;
// 使用CAS原子累加sc的值。
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
// 扩容。
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
扩容方法
1）根据CPU核心数平均分配给每个CPU相同大小的区间，如果不够16个，默认就是16个。
2）有且只能由一个线程构建一个nextTable，这个nextTable是扩容后的数组（容量已经扩大）。
3）外层使用for循环处理每个区间里的根节点，内层使用while循环让线程领取未扩容的区间。
4）处理每个区间的头节点，如果头结点为空，则直接放置一个ForwordingNode，通知其他线程帮助扩容。
5）处理每个区间的头节点，如果头结点不为空，并且hash不为-1，那么就同步头节点，开始扩容。判断头结点是链表还是红黑树：如果是链表，则拆分为高低两个链表。如果是红黑树，拆分为高低两个红黑树，并判断是否需要转为链表。
// 进行扩容操作。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 根据cpu个数找出扩容时的最小分组，最小是16。
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE;
// 表示第一次扩容，因为在addCount()方法中，第一次扩容的时候传入的nextTab的值是null。
if (nextTab == null) {
try {
// 创建新的扩容后的节点数组。
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
// 将新的数组赋值给nextTab。
nextTab = nt;
} catch (Throwable ex) {
// 扩容失败，设置sizeCtl为最大值。
sizeCtl = Integer.MAX_VALUE;
return;
}
// 将新的数组赋值给nextTable。
nextTable = nextTab;
// 记录要扩容的区间最大值，说明是逆序迁移，从高位向低位迁移。
transferIndex = n;
}
// 设置扩容后的容量。
int nextn = nextTab.length;
// 创建一个fwd节点，用于占位，fwd节点的hash默认为-1。当别的线程发现这个槽位中是fwd类型的节点，则跳过这个节点。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// 如果是false，需要处理区间上的当前位置，如果是true，说明需要处理区间上的下一个位置。
boolean advance = true;
// 完成状态，如果是true，就结束此方法。
boolean finishing = false;
// 死循环，i表示最大下标，bound表示最小下标。
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// 循环判断是否要处理区间上的下一个位置，每个线程都会在这个循环里获取区间。
while (advance) {
int nextIndex, nextBound;
// i自减一并判断是否大于等于bound，以及是否已经完成了扩容。
// 如果i自减后大于等于bound并且未完成扩容，说明需要处理当前i位置上的节点，跳出while循环。
// 如果i自减后小于bound并且未完成扩容，说明区间上没有节点需要处理，在while循环里继续判读。
// 如果已经完成扩容，跳出while循环。
if (--i >= bound || finishing)
// 跳出while循环。
advance = false;
// 如果要扩容的区间最大值小于等于0，说明没有区间需要扩容了。
else if ((nextIndex = transferIndex) <= 0) {
// i会在下面的if块里判断，从而进入完成状态判断。
i = -1;
// 跳出while循环。
advance = false;
}
// 首次while循环进入，CAS判断transferIndex和nextIndex是否一致，将transferIndex修改为最大值。
else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
// 当前线程处理区间的最小下标。
bound = nextBound;
// 初次对i赋值，当前线程处理区间的最大下标。
i = nextIndex - 1;
// 跳出while循环。
advance = false;
}
}
// 判读是否完成扩容。
// 如果i小于0，表示已经处理了最后一段空间。
// 如果i大于等于原容量，表示超过下标最大值。
// 如果i加上原容量大于等于新容量，表示超过下标最大值。
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
// 如果完成扩容，finishing为true，表示最后一个线程完成了扩容。
if (finishing) {
// 删除成员变量。
nextTable = null;
// 更新集合。
table = nextTab;
// 更新阈值。
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 如果没完成扩容，当前线程完成这段区间的扩容，将sc的低16位减1。
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 如果判断是否是最后一个扩容线程，如果不等于，说明还有其他线程在扩容，当前线程返回。
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// 如果相等，说明当前最后一个线程完成扩容，扩容结束，并再次进入while循环检查一次。
finishing = advance = true;
// 再次循环检查一下整张表。
i = n;
}
}
// 正常处理区间，如果原数组i位置是null，就使用fwd占位。
else if ((f = tabAt(tab, i)) == null)
// 如果成功写入fwd占位，进入while循环，继续处理区间的下一个节点。
advance = casTabAt(tab, i, null, fwd);
// 正常处理区间，如果原数组i位置不是null，并且hash值是-1，说明别的线程已经处理过了。
else if ((fh = f.hash) == MOVED)
// 进入while循环，继续处理区间的下一个节点。
advance = true;
// 到这里，说明这个位置有实际值了，且不是占位符。
else {
// 对这个节点上锁，防止添加元素的时候向链表插入数据。
synchronized (f) {
// 判断i下标处的桶节点是否和f相同，二次校验。
if (tabAt(tab, i) == f) {
// 声明高位桶和低位桶。
Node<K,V> ln, hn;
// 如果f的hash值大于0，表示是链表结构。红黑树的hash默认是-2。
if (fh >= 0) {
// 获取原容量最高位同节点hash值的与运算结果，用来判断将该节点放到高位还是低位。
int runBit = fh & n;
// 定义尾节点，暂时取f节点，后面会更新。
Node<K,V> lastRun = f;
// 遍历这个节点。
for (Node<K,V> p = f.next; p != null; p = p.next) {
// 获取原容量最高位同节点hash值的与运算结果，用来判断将该节点放到高位还是低位。
int b = p.hash & n;
// 如果节点的hash值和首节点的hash值，同原容量最高位与运算的结果不同。
if (b != runBit) {
// 更新runBit，用于下面判断lastRun该赋值给ln还是hn。
runBit = b;
// 更新lastRun，保证后面的节点与自己的取于值相同，避免后面没有必要的循环。
lastRun = p;
}
}
// 如果最后更新的runBit是0，设置低位节点。
if (runBit == 0) {
ln = lastRun;
hn = null;
}
// 如果最后更新的runBit是1，设置高位节点。
else {
hn = lastRun;
ln = null;
}
// 再次循环，生成两个链表，lastRun作为停止条件，这样就是避免无谓的循环。
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
// 如果与运算结果是0，那么创建低位节点。
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
// 如果与运算结果是1，那么创建高位节点。
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// 设置低位链表，放在新数组的i位置。
setTabAt(nextTab, i, ln);
// 设置高位链表，放在新数组的i+n位置。
setTabAt(nextTab, i + n, hn);
// 将旧的链表设置成fwd占位符。
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);
// 与运算结果为0的放在低位。
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
// 与运算结果为1的放在高位。
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 如果树的节点数小于等于6，那么转成链表，反之，创建一个新的树。
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin<K,V>(lo) : t;
// 如果树的节点数小于等于6，那么转成链表，反之，创建一个新的树。
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin<K,V>(hi) : t;
// 设置低位树，放在新数组的i位置。
setTabAt(nextTab, i, ln);
// 设置高位数，放在新数组的i+n位置。
setTabAt(nextTab, i + n, hn);
// 将旧的树设置成fwd占位符。
setTabAt(tab, i, fwd);
// 继续处理区间的下一个节点。
advance = true;
}
}
}
}
}
}
获取方法
根据指定的键，返回对应的键值对，由于是读操作，所以不涉及到并发问题，步骤如下：
1）判断查询的key对应数组的首节点是否null。
2）先判断数组的首节点是否为寻找的对象。
3）如果首节点不是，并且是红黑树结构，另做处理。
4）如果是链表结构，遍历整个链表查询。
5）如果都不是，那就返回null值。
// 获取元素。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 计算hash，并保证hash一定大于零，负数表示在扩容或者是树节点。
int h = spread(key.hashCode());
// 如果集合不为null，并且集合长度大于0，并且指定位置上的元素不为null。
if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {
// 如果hash相等。
if ((eh = e.hash) == h) {
// 如果首节点是要找的元素。
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 如果正在扩容或者是树节点。
else if (eh < 0)
// 尝试查找元素，找到返回元素，找不到返回null。
return (p = e.find(h, key)) != null ? p.val : null;
// 如果不是首节点，则遍历集合查找。
while ((e = e.next) != null) {
if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
删除方法
删除操作，可以看成是用null替代原来的节点，因此合并在这个方法中，由这个方法一起实现删除操作和替换操作。
replaceNode()方法中的三个参数，key表示想要删除的键，value表示想要替换的元素，cv表示想要删除的key对应的值。
// 删除元素。
public V remove(Object key) {
return replaceNode(key, null, null);
} // 删除元素
final V replaceNode(Object key, V value, Object cv) {
// 计算hash，并保证hash一定大于零，负数表示在扩容或者是树节点。
int hash = spread(key.hashCode());
// CAS经典写法，不成功无限重试。
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果集合是null，或者集合长度是0，或者指定位置上的元素是null。
if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null)
// 跳出循环。
break;
// 如果获取到节点不为null，并且节点的hash为-1，则表示节点在扩容。
else if ((fh = f.hash) == MOVED)
// 帮助扩容。
tab = helpTransfer(tab, f);
// 产生hash碰撞，并且没有扩容操作。
else {
V oldVal = null;
// 是否进入了同步代码。
boolean validated = false;
// 锁住节点。
synchronized (f) {
// 这里volatile获取首节点与节点对比判断节点还是不是首节点。
if (tabAt(tab, i) == f) {
// 判断是否是链表节点。
if (fh >= 0) {
validated = true;
// 循环查找指定元素。
for (Node<K,V> e = f, pred = null;;) {
K ek;
// 找到元素了。
if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
V ev = e.val;
// 如果cv为null，或者cv不为null时cv和指定元素上的值相同，才更新或者删除节点。
if (cv == null || cv == ev || (ev != null && cv.equals(ev))) {
oldVal = ev;
// 如果新值不为null，替换。
if (value != null)
e.val = value;
// 如果新值是null，并且当前节点非首结点，删除。
else if (pred != null)
pred.next = e.next;
// 如果新值是null，并且当前节点是首结点，删除。
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
// 如果遍历集合也没有找到。
if ((e = e.next) == null)
// 跳出循环。
break;
}
}
// 如果是红黑树节点。
else if (f instanceof TreeBin) {
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
// 找到元素了。
if ((r = t.root) != null && (p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
// 如果cv为null，或者cv不为null时cv和指定元素上的值相同，才更新或者删除节点。
if (cv == null || cv == pv || (pv != null && cv.equals(pv))) {
oldVal = pv;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
// 如果进入了同步代码。
if (validated) {
// 如果更新或者删除了节点。
if (oldVal != null) {
// 如果value为null，说明是删除操作。
if (value == null)
// 将数组长度减一。
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}
计算集合容量
ConcurrentHashMap中baseCount用于保存tab中元素总数，但是并不准确，因为多线程同时增删改，会导致baseCount修改失败，此时会将元素变动存储于counterCells数组内。
当需要统计当前的size的时候，除了要统计baseCount之外，还需要加上counterCells中的每个桶的值。
值得一提的是即使如此，统计出来的依旧不是当前tab中元素的准确值，在多线程环境下统计前后并不能暂停线程操作，因此无法保证准确性。
// 计算集合容量。
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
} // 计算集合容量，baseCount和counterCells数组存的总和。
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
Hashtable、Collections.synchronizedMap()、ConcurrentHashMap之间的区别
Hashtable是线程安全的哈希表，它是通过synchronized来保证线程安全的；即，多线程通过同一个“对象的同步锁”来实现并发控制。Hashtable在线程竞争激烈时，效率比较低（此时建议使用ConcurrentHashMap）。当一个线程访问Hashtable的同步方法时，其它线程如果也在访问Hashtable的同步方法时，可能会进入阻塞状态。
Collections.synchronizedMap()使用了synchronized同步关键字来保证对Map的操作是线程安全的。
ConcurrentHashMap是线程安全的哈希表。在JDK1.7中它是通过“锁分段”来保证线程安全的，本质上也是一个“可重入的互斥锁”（ReentrantLock）。多线程对同一个片段的访问，是互斥的；但是，对于不同片段的访问，却是可以同步进行的。在JDK1.8中是通过使用CAS原子更新、volatile关键字、synchronized可重入锁实现的。
最新文章
- 崔用志-微信开发-java版本
- linux命令行中单个减号表示标准输入输出流
- js类型检测
- Map拷贝 关于对象深拷贝 浅拷贝的问题
- 在亚马逊amazon的AWS上安装Node和MongoDB服务器
- Mybatis的缺陷
- [codevs 1503]愚蠢的宠物（特殊的LCA）
- 李洪强iOS开发之OC[010] - 有参方法的声明实现和调用
- Django学习笔记——安装（linux环境）
- 传感器 -UIAccelerometer
- 利用好CSS,实现Qt控件美化
- setPluginsEnabled(true) 谁知道android的4.3之后为什么会报错
- 关于通过addClass与removeClass用jquery控制有良好兼容的CSS3样式
- iOS 自动构建套件 - flow.ci + fir.im + Coding
- choose the max from numbers, use scanf and if else (v1:21.9.2017，v2:23.9.2017)
- javascript参数传递中处理+号
- ajax（2）
- [Abp 源码分析]十一、权限验证
- SQL注入关联分析
- FCM算法的matlab程序2