第10章_集合类(下)
1、HashMap的数据结构
先介绍HashMap中的一些概念。首先,我们要知道到底什么是Hash。
当我们向一个HashMap中“put"一个元素时，就需要通过一定的算法计算出应该把它放到哪个“桶”中，这个过程就叫作Hash,对应的就是HashMap中的hash()方法。
1.1 Hash
Hash一般翻译为散列,也有直接音译为哈希的，
- 就是把任意长度的输入通过散列算法转换成固定长度的输出,该输出就是散列值。
- 这种转换是一种压缩映射,也就是散列值的空间通常远小于输人的空间,不同的输人入可能会散列成相同的输出，所以不可能通过散列值来唯一地确定输入值
- 简单地说，Hash就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
所有散列函数都有如下一个基本特性:
- 如果根据同一散列函数计算出的散列值不同，那么输人值肯定也不同
- 但是，如果根据同一散列函教计算出的散列值相同，那么输人值不一定相同。
两个不同的输入值,根据同一散列函数计算出的散列值相同的现象叫作碰撞。
常见的Hash算法以下几个:
- 直接定址法：直接以关键字k或者k加上某个常数(k+c）作为Hash地址。
- 数字分析法：提取关键字中取值比较均匀的数字作为 Hash地址。
- 除留余数法：用关键字k除以某个不大于Hash表长度m 的数p，将所得余数作为Hash表地址。
- 分段叠加法：按照Hash表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短,然后将这几部分相加,舍弃最高进位后的结果就是该关键字的Hash地址；
- 平方取中法：如果关键字各个部分分布都不均匀,则可以先求出它的平方值，然后按照需求取中间的几位作为Hash地址。
- 伪随机数法：采用一个伪随机数当作 Hash 函数。
衡量一个Hash算法的重要指标就是发生碰撞的概率,以及发生碰撞的解决方案。任何Hash函数基本都无法彻底避免碰撞，常见的解决碰撞的方法有以下几种:
- 开放定址法：一旦发生了碰撞，就去寻找下一个空的散列地址,只要散列表足够大总能找到空的散列地址,并将元素存入。
- 链地址法：将Hash表的每个单元作为链表的头节点,所有Hash地址为i的元素构成一个同义词链表,即发生碰撞时就把该关键字链接在以该单元为头节点的链表的尾部；
- 再Hash法：当Hash地址发生碰撞时使用其他函数计算另一个Hash函数地址,直到不再产生冲突为止。
- 建立公共溢出区：将Hash表分为基本表和溢出表两部分，发生冲突的元素都放人溢出表。
1.2 HashMap 的数据结构
在Java中，有两种比较简单的数据结构:数组和链表。数组的特点是寻址容易，插入和删除困难;而链表的特点是寻址困难，插入和删除容易。
前面提到过，一种常用的解决Hash函数碰撞的办法叫作链地址法,其实就是将数组和链表组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组,如图10-8所示。
在图10-8中,左边很明显是一个数组，数组中的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针,用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中,反过来我们可以通过这些特征找到正确的链表再从链表中找出正确的元素。其中,根据元素特征计算元素数组下标的方法就是Hash算法。
2、HashMap的size和capacity有什么区别
了解HashMap的数据结构之后，下面介绍HashMap中的一些概念，如容量、负载因子等。本节的内容基于JDK1.8.0_73。
HashMap中主要的成员变量如下图所示。（IDEA快捷键：Ctrl+F12）
首先介绍其中两个表示大小的变量:size和capacity。
- size:记录 Map中K-V对的个数。
- capacity:容量，如果不指定，则默认容量是16 (static final int DEFAULT_INITIAL_CAPACITY = 1<<4)。
HashMap的示意图如下图所示。
打个比方，HashMap就是一个“桶”，容量（ capacity)就是这个桶当前最多可以装多少元素,而元素个数( size)表示这个桶已经装了多少元素。
例如以下代码:
Map<String,String> map = new HashMap<String,string>();
map.put("hollis", "hollischuang" );
Class<?> mapType = map.getClass();
Method capacity = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
System.out.println("capacity : " +capacity.invoke(map));
Field size = mapType.getDeclaredField("size");
size.setAccessible(true);
System.out.print1n("size : " + size.get(map));
输出结果如下：
capacity : 16、size : 1
以上代码定义了一个新的HashMap，并向其中“put”了一个元素，然后通过反射的方式打印capacity和size，其容量是16，已经存放的元素个数是1。
3、HashMap的扩容机制
3.1 背景
HashMap的容量会不会变?什么时候变?
- 其实，除了初始化时会指定HashMap的容量，在扩容时,其容量也可能改变。
- HashMap有扩容机制，当达到扩容条件时会进行扩容。而且HashMap在扩容的过程中不仅要对其容量进行扩容，还需要进行“rehash”。所以，这个过程其实是很耗时的，并且Map中的元素越多越耗时。
- rehash的过程相当于对其中所有的元素重新做一遍Hash运算，重新计算元素要分配到哪个桶中。
HashMap不是一个数组链表吗?不扩容也可以无限存储元素，为什么还要扩容呢?这其实和Hash碰撞有关。
3.2 Hash 碰撞
有很多办法可以解决Hash碰撞,其中比较常见的就是链地址法，这也是HashMap采用的方去，如图10-11所示。
- 我们在向HashMap中“put”元素时，需要先将元素定位到要存储在数组中的哪条链表上，然后把这个元素“挂”在这个链表的后面。
- 当我们从HashMap中“get”元素时，需要定位到数组中哪条链表上，然后逐一遍历链表中的元素,直到找到需要的元素为止。
- 可见，HashMap通过链表的数组这种结构解决了Hash碰撞的问题。
- 如果一个HashMap中的碰撞太多，那么数组的链表就会退化为链表,这时查询速度会大大降低。
- 所以,为了保证HashMap的读取速度，我们需要尽量保证HashMap的碰撞不要太多。
3.3 通过扩容避免 Hash碰撞
如何能有效地避免Hash碰撞呢?
我们先反向思考一下，你认为什么情况会导致HashMap的Hash碰撞比较多?示意图如图10-12所示。
无外乎两种情况:
- 容量太小。容量小,元素碰撞的概率就高了。
- Hash算法不合理。算法不合理,元素就有可能都分到同一个或几个桶中。分配不均,也会发生争抢。
所以,解决HashMap中的Hash碰撞也是从这两方面入手的。
- 首先在合适的时候扩大数组容量；
- 再通过一个合适的Hash算法将元素分配到这个数组中，既可以大大减少元素碰撞的概率,也可以避免查询效率低下的问题。
4、HashMap的loadFactor和threshold
HashMap的扩容是通过resize法实现的，下面是HashMap中的扩容方法(resize )中的一段代码:
if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
从上面的代码可以看出，扩容后的Table容量变为原来的两倍。HashMap中定义了loadFactor和lthreshold两个属性:
- loadFactor:负载因子，用来衡量HashMap“满”的程度。loadFactor的默认值为0.75f
- (static final float DEFAULT_LOAD_FACTOR = 0.75f)
- threshold:临界值，当实际K-V个数超过threshold 时,HashMap 会将容量扩容，
- threshold=容量×负载因子。
当达到扩容条件时HashMap会进行扩容,将容量扩大到原来的两倍。这个扩容条件指的是什么呢?
HashMap的扩容条件就是当HashMap中的元素个数(size)超过临界值 (threshold）时就会自动扩容。
在HashMap中, threshold = loadFactor x capacity。
对于一个默认的HashMap来说(默认容量是16）,默认情况下（默认负载因子是0.75) ,当其size大于12（16×0.75）时就会触发扩容。
验证代码如下:
package com.gyz.test.testdemo.test;
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.HashMap;
import java.util.Map;
public class Test9 {
public static void main(String[] args) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException, NoSuchFieldException {
Map<String, Object> map = new HashMap<>();
map.put("hollis1", "hollischuang");
map.put("hollis2", "hollischuang");
map.put("hollis3", "hollischuang");
map.put("hollis4", "hollischuang");
map.put("hollis5", "hollischuang");
map.put("hollis6", "hollischuang");
map.put("hollis7", "hollischuang");
map.put("hollis8", "hollischuang");
map.put("hollis9", "hollischuang");
map.put("hollis10", "hollischuang");
map.put("hollis11", "hollischuang");
map.put("hollis12", "hollischuang");
Class<?> mapType = map.getClass();
Method capacity = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
System.out.println("capacity : " + capacity.invoke(map));
Field threshold = mapType.getDeclaredField("threshold");
threshold.setAccessible(true);
System.out.println("threshold : " + threshold.get(map));
Field loadFactor = mapType.getDeclaredField("loadFactor");
loadFactor.setAccessible(true);
System.out.println("loadFactor : " + loadFactor.get(map));
map.put("hollis13", "hollischuang");
Method capacity2 = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
System.out.println("capacity : " + capacity.invoke(map));
Field size = mapType.getDeclaredField("size");
size.setAccessible(true);
System.out.println("size : "+size.get(map));
Field threshold2 = mapType.getDeclaredField("threshold");
threshold2.setAccessible(true);
System.out.println("threshold2 : " + threshold2.get(map));
Field loadFactor2 = mapType.getDeclaredField("loadFactor");
loadFactor2.setAccessible(true);
System.out.println("loadFactor2 : " + loadFactor2.get(map));
}
}
输出结果如下：
capacity : 16
threshold : 12
loadFactor : 0.75
capacity : 32
size : 13
threshold2 : 24
loadFactor2 : 0.75
当HashMap中的元素个数达到13的时候，capacity就从16扩容到32了。
HashMap中还提供了一个支持传入initialCapacity和loadFactor两个参数的方法来初始化容量和负载因子。不过,一般不建议修改loadFactor的值。
5、为什么建议集合初始化时指定容量大小
前面介绍了很多集合类,如常见的ArrayList、TreeSet和HashMap等，这些集合类其实都有很多重载的构造函数，在这些构造函数中，有一部分是可以指定容量的。 例如,ArrayList的构造函数支持传入初始容量:
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
HashMap的构造雨数同样支持传人初始容量:
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
那么,我们要不要指定集合的初始容量呢?本节以HashMap为例进行说明。
下面分别测试在不指定初始化容量和指定初始化容量的情况下程序的性能（JDK版本为1.7.0_79),代码如下:
public static void main(String[] args) {
int aHundredMillion = 10000000;
Map<Integer, Integer> map1 = new HashMap<>();
long s1 = System.currentTimeMillis();
for (int i = 0; i < aHundredMillion; i++) {
map1.put(i, i);
}
long s2 = System.currentTimeMillis();
System.out.println("未初始化容量，耗时：" + (s2 - s1));
Map<Integer, Integer> map2 = new HashMap<>(aHundredMillion / 2);
long s3 = System.currentTimeMillis();
for (int i = 0; i < aHundredMillion; i++) {
map2.put(i, i);
}
long s4 = System.currentTimeMillis();
System.out.println("初始化容量为5000000，耗时：" + (s4 - s3));
Map<Object, Object> map3 = new HashMap<>(aHundredMillion);
long s5 = System.currentTimeMillis();
for (int i = 0; i < aHundredMillion; i++) {
map3.put(i, i);
}
long s6 = System.currentTimeMillis();
System.out.println("初始化容量为10000000,耗时：" + (s6 - s5));
}
以上代码创建了3个HashMap，分别使用默认的容量（16）、元素个数的一半（5000万)、元素个数(一亿)作为初始容量初始化HashMap，然后分别向其中“put”一亿个键值对。
输出结果如下：
未初始化容量,耗时:14419
初始化容量为5800208，耗时:11916
初始化容量为1008000日，耗时:7984
由以上结果可以知道,在已知HashMap中将要存放的键值对个数的情况下,设置一个合理的初始化容量可以有效地提高性能。
如果没有设置初始容量的大小,那么随着元素的不断增加,HashMap会发生多次扩容,而HashMap的扩容机制决定了每次扩容都需要重建Hash表，这是非常影响性能的。
从上面的代码示例中,我们还发现,同样是设置初始化容量，设置的数值不同也会影响性能,当我们已知HashMap中即将存放的键值对数时,容量设置成多少合适呢?
6、HashMap的初始容量设置为多少合适
6.1 计算方法
当我们使用HashMap(int initialcapacity)初始化HashMap的容量时,JDK会默认帮我们计算一个相对合理的值作为初始容量。
但是,这个值看似合理,实际上并不尽然。因为HashMap在根据用户传入的capacity计算默认容量时,并没有考虑loadFactor这个因素,只是简单机械地计算出第一个大于这个数字的2的幂。
也就是说,如果我们设置的默认值是7，经过JDK处理之后，HasMap的容量会被设置成8，但是,这个HashMap在元素个数达到8×0.75=6时就会进行一次扩容，这明显不是我们希望见到的。
那么,到底设置成什么值比较合理呢?
这里我们可以参考JDK8中putAll方法的实现,这个实现在Guava (21.0版本)中也被采用。
这个值的计算方法如下:
return (int) ((float)expectedsize / 0.75F +1.eF);
比如我们计划向HashMap中放入7个元素，通过expectedSize/0.75F+1.0F计算, 7/0.75+1=10,10经过JDK处理之后,会被设置成16,这就大大减少了扩容的概率。
当HashMap内部维护的Hash表的容量达到75%时(默认情况下)，会触发rehash，而rehash的过程是比较耗费时间的。所以初始化容量要设置成expectedSize/0.75+1，既可以有效地减少冲突，也可以减小误差。
所以当我们明确知道HashMap中元素的个数时，把默认容量设置成expectedSize/0.75F+1.0F是一个在性能上相对好的选择,但同时会“牺牲”一些内存。
这个算法在Guava中也有实现,可以直接通过Maps类创建一个HashMap:
Map<String,String> map = Maps.newHashMapwithExpectedSize(7);
其代码实现如下:
public static <K, VHashMap<K, VnewHashMapWithExpectedSize(int expectedSize){
return new HashMap(capacity(expectedsize));
}
static int capacity(int expectedsize){
if (expectedSize< 3){
CollectPreconditions.checkNonnegative(expectedSize,"expectedSize");
return expectedSize + 1;
} else {
return expectedSize <1073741824 ? (int)((float)expectedSize / 0.75F + 1.OF)）:
}
}
但是,以上操作是一种用内存换性能的做法，真正使用的时候，还要考虑内存的影响。
6.2 小结
当我们想要在代码中创建一个HashMap时，如果已知这个Map中即将存放的元素个数,给HashMap设置初始容量可以在一定程度上提升效率。
但是,JDK并不会直接以用户传进来的数字作为默认容量，而是会进行一番运算,最终得到一个2的幂。得到这个数字的算法其实是使用了无符号右移和按位或运算来提升效率。
为了最大限度地避免扩容带来的性能消耗，建议把默认容量的数字设置成expectedSize/0.75F+1.0F。在日常开发中，可以使用Nap<String,String> map = Maps.newHash-MapwithExpectedSize(10)来创建一个HashMap,Guava会帮助我们完成计算的过程。
7、HashMap的hash()方法
8、为什么HashMap的默认容量设置成16
在介绍HashMap的基础概念时，还有两个HashMap中的常量没有介绍,即DEFAULT_INITIAL_CAPACITY和DEFAULT_LOAD_FACTOR,分别农示默认容量和默认负载因子。接下来介绍这两个概念。
通过查看源码,可以知道HashMap的默认容量为16:
static final int DEFAULT_INITIAL_CAPACITY = 1<<4; // aka 16
我们在介绍HashMap的hash()方法的时候,曾经提到过:
- 因为位运算是直接对内存数据进行操作，不需要转成十进制,所以位运算要比取模运算的效率更高，HashMap在计算元素要存放在数组中的index时,使用位运算代替了取模运算。之所以可以做等价代替,前提要求HashMap的容量一定是2的n次方。
既然是2的n次方,为什么一定要是16呢?为什么不能是4、8或者32呢?
关于这个默认容量的选择,JDK并没有给出官方解释。
根据笔者的推断,这个值应该是个经验值（Experience Value）,既然一定要设置一个默认的2的n次方作为初始值,那么就需要在效率和内存使用上做一个权衡。这个值既不能太小,也不能太大。太小了就有可能频繁发生扩容，影响效率。太大了又浪费空间，不划算。所以,16就作为一个经验值被采用了。
在JDK 8中，默认容量定义为1<<4，其故意把16写成1<<4，就是提醒开发者，这个地方是2的n次方。
HashMap在初始化的时候,把默认值设置成16，这就保证了在用户没有指定初始化容量时,容量会被设置成16,这就满足了容量是2的幂次这一要求。
如果用户指定了一个初始容量,比如指定初始容量为7,会发生什么呢?
HashMap在两个可能改变其容量的地方都做了兼容处理,分别是指定容量初始化时及扩容时。
- 在初始化容量时,如果用户指定了容量,那么HashMap会采用第一个大于这个数的2的幂作为初始容量。
- 在扩充容量时,HashMap会把容量扩充到当前容量的2倍。2的幂的2倍,还是2的幂。
通过保证初始化容量均为2的幂,并且扩容时也是扩容到之前容量的2倍,保证了HashMa的容量永远都是2的幂。
9、为什么HashMap的默认负载因子设置成0.75
负载因子表示一个Map可以达到的满的程度。这个值不宜太大,也不宜太小。
loadFactory太大，比如等于1,就会有很高的Hash冲突的概率,会大大降低查询速度。
loadFactory太小，比如等于0.5,那么频繁扩容会大大浪费空间。
所以,这个值需要介于0.5和1之间。根据数学公式推算,这个值为log2时比较合理。
另外,为了提升扩容效率，HashMap的容量（capacity)有一个固定的要求,那就是一定是2的幂。
所以,如果loadFactor是3/4,那么和capacity的乘积结果就可以是一个整数。在一般情况下,我们不建议修改loadFactory的值。
比如明确地知道Map只存储5个键值对,并且永远不会改变,则可以考虑指定loadFactory的值。
其实我们完全可以通过指定capacity达到这样的目的。
10、HashMap的线程安全问题
10.1 扩容原理
10.1.1 介绍
前面介绍了HashMap、同时介绍了Hashtable和ConcurrentHashMap等，我们多次提到，HashMap是非线程安全的,是不可以用在并发场景中的。 为什么HashMap不能用在并发场景中呢?用了又会出现什么问题呢?
10.1.2 扩容原理
如何把原来Map中的元素移动到新的Map中？下面是JDK1.7中resize()方法的实现代码:
/**
* 分析：resize(2 * table.length)
* 作用：当容量不足时（容量 > 阈值），则扩容（扩到2倍）
*/
void resize(int newCapacity) {
// 1. 保存旧数组（old table）
Entry[] oldTable = table;
// 2. 保存旧容量（old capacity ），即数组长度
int oldCapacity = oldTable.length;
// 3. 若旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值，退出
if (oldCapacity == MAXIMUM_CAPACITY) {
// 修改扩容阀值
threshold = Integer.MAX_VALUE;
return;
}
// 4. 根据新容量（2倍容量）新建1个数组，即新table
Entry[] newTable = new Entry[newCapacity];
// 5. 将旧数组上的数据（键值对）转移到新table中，从而完成扩容。initHashSeedAsNeeded(newCapacity)这个方法用来根据新的数组长度来重新初始化Hash种子
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 6. 新数组table引用到HashMap的table属性上
table = newTable;
// 7. 重新设置阈值,如果阈值超过了HashMap最大容量大小，则直接将阈值设置为 MAXIMUM_CAPACITY + 1
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
在上面的resize()方法中,调用了transfe()方法,这个方法实现的功能就是把原来的Map中元素移动到新的Map中,实现方式如下:
/**
* 分析：transfer(newTable);
* 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
* 过程：按旧链表的正序遍历链表、在新链表的头部依次插入
* @param rehash 如果这里传入的是true，说明Hash种子已经更新，需要对所有的元素进行rehash重新计算Hash值。该操作比较消耗资源，这也是JDK1.7相对JDK1.8执行效率较低的原因
*/
void transfer(Entry[] newTable, Boolean rehash) {
// 获取新数组的大小 = 获取新容量大小
int newCapacity = newTable.length
// 通过遍历 旧数组，将旧数组上的数据（键值对）转移到新数组中
for (Entry<K,V> e : table) {
// 遍历桶中所有元素
while(null != e) {
Entry<K,V> next = e.next;
// 如果是重新Hash，则需要重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 重新计算每个元素的存储位置，这里再次按照之前计算元素所在位置的方法重新进行一遍 Hash值 &（新数组长度 - 1）的计算，也是相当消耗资源的操作。1.8就采用扩容之后运用运算规律来对元素重新定位，这样相对要高效很多。
int i = indexFor(e.hash, newCapacity);
// 将元素放在数组上：采用单链表的头插入方式 = 在链表头上存放数据 = 将新插入数据的next指向原数组位置的链表头节点，然后将需放入的数据放到数组位置中，这样就实现了头插法将数据插入链表
// 即 扩容后，可能出现逆序：按旧链表的正序遍历链表、在新链表的头部依次插入
e.next = newTable[i];
// newTable[i]的值总是最新插入的值
newTable[i] = e;
// 访问下一个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
e = next;
}
}
}
首先解释这个方法做了哪些事情。
- 我们通过以下方式定义一个HashMap,设置其初始容量为4: Map<String,String> map= new HashMap<String,String>(3);
- 当我们使用3作为初始容量创建HashMap时,HashMap会采用第一个大于3的2的幂作为这个Map的初始容量,也就是4,而这个Map默认的负载因子是0.75，所以当元素个数超过3个(4×0.75)时,就会触发扩容机制。
我们依次向这个Map中添加3个元素:
map.put("A" ,"A");
map.put("B","B”);
map.put("C",“C");
如果这三个元素的Hash值刚好一样,那么它们的存储结构如图10-17所示。
当我们向其中添加第四个元素D时,就会触发扩容机制。扩容过程就是先把容量变成原来的一倍,然后从原来的HashMap中依次取出元素再添加到扩容后的HashMap中。
transfer的元素移动的主要代码就是while循环中的这几句,为了便于读者理解,以下代码增加了一些注释:
//先保存下一个节点
Entry<K,V> next = e.next;
//计算当前元素的Hash值
if (rehash){
e.hash == null == e.key ? 0 : hash(e.key);
}
//在新的Map中找到应该入的桶的下标
int i = indexFor(e.hash,newCapacity);
//先用e.next指向新的Hash表的第一个元素，将当前元素插入链表的头部
e.next = newTable[i];
//将新Hash表的头指针指向当前元素
newTable[i]=e;
//转移到下一个节点
e = next;
如果A、B、C三个元素在HashMap扩容后还是一样的Hash值,那么它们会被分到同一个桶中。扩容后它们的存储结构如图10-18所示。
可以看到,它们之间的顺序从A→B→C变成了C→B→A。这就是所谓的头插法，即把元素插入链表头部。
之所以选择使用头插法,是因为JDK的开发者认为,后插人的数据被使用到的概率更高,更容易成为热点数据,而通过头插法把它们放在队列头部,就可以使查询效率更高。
其实也正是这个头插的过程,一旦出现高并发场景,就会出现死循环的问题。接下来,我们就举一个实际的例子,重现一下上述情景。
10.2 场景重现
JDK7的HashMap头插法循环的问题视频讲解：传送
11、为什么不能在foreach循环里对集合中的元素进行remove/add操作
11.1 问题重现
如果在foreach循环里对集合中的元素进行remove/add操作会发生什么问题呢？例如：
11.1.1 普通的for循环
先使用普通的for循环在遍历元素的同时删除元素，是没问题的。
public static void main(String[] args) {
List<String> userNames = new ArrayList<String>() {
{
add("Hollis");
add("hollis");
add("HoliisChuang");
add("H");
}
}
;
for (int i = 0; i < userNames.size(); i++) {
if (userNames.get(i).equals("Hollis")){
userNames.remove(i);
}
}
System.out.println(userNames);
}
输出结果：[hollis, HoliisChuang, H]
11.1.2 增强for循环会发生什么呢？
public static void main(String[] args) {
List<String> userNames = new ArrayList<String>() {
{
add("Hollis");
add("hollis");
add("HoliisChuang");
add("H");
}
}
;
for (String userName : userNames) {
if (userName.equals("Hollis")) {
userNames.remove(userName);
}
}
System.out.println(userNames);
}
运行以上代码会发生异常：java.util.ConcurrentModificationException
之所以会出现这个异常，是因为出发了一个JAVA集合的错误检测机制---fail-fast
在增强for循环中是如何违反了规则呢？
先将增强for循环这个语法进行解糖，得到如下代码
public static void main(String[] args) {
List<String> userNames = new ArrayList<String>() {
{
add("Hollis");
add("hollis");
add("HoliisChuang");
add("H");
}
}
;
Iterator iterator = userNames.iterator();
do {
if (!iterator.hasNext())
break;
String userName = (String) iterator.next();
if (userName.equals("Hollis"))
userNames.remove(userName);
}
while (true);
System.out.println(userNames);
}
然后运行以上代码，同样会抛出异常。ConcurrentModificationException的完整堆栈如下：
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
at com.gyz.test.testdemo.test.list.ForeachTest.main(ForeachTest.java:15)
Iterator.next调用了Iterator.checkForComodification方法，而异常就是checkForComodification方法抛出的。
其实，经过debug后，我们可以发现,如果remove代码没有被执行过，那么iterator.next这一行是一直没报错的。抛出异常的时机也正是remove执行之后的那一次next方法的调用。
我们直接查看checkForComodification方法的代码来了解抛出异常的原因:
final void checkForComodification() {
if (modCount != expectedModCount){
throw new ConcurrentModificationException();
}
}
代码比较简单，执行modCount != expectedModCount时，就会抛出ConcurrentModification-Exception。
下面分析remove/add操作是如何导致modCount和expectedModCount不相等的。
11.2 remove/add操作做了什么
首先,我们要搞清楚的是，modCount和expectedModCount这两个变量表示的都是什么?通过查看源码,我们可以发现:
- modCount是ArrayList中的一个成员变量。它表示该集合实际被修改的次数。
- expectedModCount是 ArrayList中的一个内部类——Itr中的成员变量。expectedModCount表示这个迭代器期望该集合被修改的次数。其值是在
- ArrayList.iterator方法被调用时初始化的。只有通过迭代器对集合进行操作,该值才会改变。
- Itr是一个 Iterator 的实现,使用ArrayList.iterator方法可以获取的迭代器就是Itr类的实例。
它们之间的关系如下:
class ArrayList{
private int modCount;
public void add();
public void remove();
private class Itr implements Iterator<E>{
int expectedModCount = modCount;
}
public Iterator<E> iterator(){
return new Itr();
}
}
看到这里,大概很多人都能猜到为什么执行remove/add操作之后，会导致expectedModCount和modCount不相等了。
remove方法的核心逻辑如下所示。
private void fastRemove(int index){
modCount++;
int numMoved = size - index - 1;
if (numMoved >0){
System.arraycopy(elementData,index+1,elementData,index,numMoved);
}
elementData[--size] = null;// clear to let cc do its work
}
可以看到,它只修改了modCount，并没有对expectedModCount做任何操作。
之所以会抛出ConcurrentModificationException异常，是因为我们的代码中使用了增强for循环,而在增强for循环中,集合遍历是通过Iterator进行的，但元素的add/remove操作却直接使用了集合类自己的方法。这就导致Iterator在遍历元素时,会发现有一个元素在自己不知不觉的情况下就被删除/添加了,所以会抛出一个异常，用来提示用户,这个类可能发生了并发修改。
11.3 小结
我们使用的增强for循环,其实是Java提供的语法糖,其实现原理是借助Iterator进行元素的遍历。
如果在遍历过程中，不通过Iterator，而是通过集合类自身的方法对集合进行添加/删除操作，在Iterator进行下一次的遍历时，经检测发现有一次集合的修改操作并未通过自身进行，则可能发生了并发，而被其他线程执行，这时就会抛出异常，提示用户可能发生了并发修改，这就是所谓的fail-fast机制。
12、如何在遍历的同时删除ArrayList中的元素
12.1 直接使用普通for循环进行操作
因为普通for循外开没有用到Iterator，所以压根儿就没有进行fail-fast的检验。例如:
List<String> userNames = new ArrayList<String>(){
add( "Hollis");
add("hollis");
add("Hollischuang");
add("H");
}};
for (int i = 0;i<1; i++) {
if (userNames.get(i).equals("Hollis")){
userNames.remove(i);
}
}
System.out.println(userNames);
这种方案其实存在一个问题,那就是remove操作会改变List中元素的下标，可能存在漏的情况。
12.2 直接使用 Iterator进行操作
除了使用普通for循环,我们还可以直接使用Iterator提供的remove方法。例如:
public static void main(String[] args) {
List<String> userNames = new ArrayList<String>() {{
add("Hollis");
add("hollis");
add("HoliisChuang");
add("H");
}};
Iterator iterator = userNames.iterator();
while (iterator.hasNext()) {
if (iterator.next().equals("Hollis"))
iterator.remove();
}
System.out.println(userNames);
}
如果直接使用Iterator提供的remove方法，则可以修改expectedModCount的值，这样就不会再抛出异常了。其实现代码如下：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
}
catch (IndexOutOfBoundsException ex){
throw new ConcurrentModifcationException();
}
}
12.3 使用 Java 8中提供的filter
Java 8中可以把集合转换成流,对于流有一种filter操作，可以对原始流进行某项测试,通过测试的元素被留下来生成一个新Stream。
List<String> userNames = new ArrayList<String>(){{
add("Hollis");
add("hollis");
add("HollisChuang");
add("H");
}};
userNames = userNames.stream().filter(userName - lusenName.equals("Hollis")).collect(collectors.toList());
System.out.println(userNames);
12.4 使用增强for循环其实也可以
如果我们非常确定在集合中只有一个即将被删除的元素，那么其实也可以使用增强for循环,只要在删除元素之后,立刻结束循环休，不重继续遍历即可，也就是说，不让代码执行下-次的next方法。例如:
public static void main(String[] args) {
List<String> userNames = new ArrayList<String>() {
{
add("Hollis");
add("hollis");
add("HoliisChuang");
add("H");
}
}
;
for (String userName : userNames) {
if (userName.equals("Hollis")) {
userNames.remove(userName);
break;
}
}
System.out.println(userNames);
}
12.5 直接使用“fail-safe”的集合类
在Java中,除了一些普通的集合类,还有一些采用了fail-safe机制的集合类。这样的集合类在遍历时不是直接在集合内容上访问的,而是先复制原集合内容，在复制的集合上进行遍历。
这些类是在java.util.concurrent包下的,这些集合类都是“fail-safe”的，可以在多线程下并发使用和修改。
13、什么是fail-fast和fail-safe
13.1 什么是 fail-fast
首先我们看一下维基百科中关于fail-fast的解释:
在系统设计中,快速失效系统一种可以立即报告任何可能表明故障情况的系统。快速失效系统通常设计用于停止正常操作，而不是试图继续可能存在缺陷的过程。这种设计通常会在操作中的多个点检查系统的状态,因此可以及早检测到任何故障。 其实,这是一种理念,也就是在做系统设计时先考虑异常情况,一旦发生异常，就直接停止并上报。
举一个简单的fail-fast的例子:
public int divide(int divisor,int dividend){
if(dividend == 0){
throw new RuntimeException("dividend can't be nul1");
}
return divisor/dividend;
}
上面的代码是一个对两个整数做除法的方法，在divide方法中，我们对被除数做了一个简单的检查——如果其值为0，那么就直接抛出一个异常，并明确提示异常原因。这其实就是fail-fast理念的实际应用。
这样做的好处是可以预先识别一些错误情况，一方面可以避免执行复杂的其他代码,另-方面,这种异常情况被识别之后也可以针对性地做一些单独处理。
既然,fail-fast是一种比较好的机制,为什么有人说fail-fast有“坑”呢?
原因是Java的集合类中运用了fail-fast机制进行设计，一旦使用不当，触发fail-fast机制设计的代码,就会发生非预期情况。
13.2 集合类中的fail-fast
我们通常说的Java中的fail-fast机制,默认指的是Java集合的一种错误检测机制。当多个线程对部分集合进行结构上的改变的操作时，就有可能触发fail-fast机制,这时就会抛出ConcurrentModificationException。
ConcurrentModificationException:当方法检测到对象的并发修改，但不允许这种修改时就抛出该异常。
因为代码中抛出了ConcurrentModificationException，所以很多程序员感到很困惑,明明自己的代码并没有在多线程环境中执行,为什么会抛出这种与并发有关的异常呢? 其中一个比较常见的原因就是前面介绍过一种情况——在foreach循环里对某些集合中的元素进行remove/add操作,这也会导致ConcurrentModificationException。
所以,在使用Java的集合类时,如果发生ConcurrentModifioationException，则优先考虑与fail-fast有关的情况，实际上这里并没有真的发生并发，只是Iterator使用了fai1-fast的保护机制,只要发现有某一次修改是未经过自己进行的,就会抛出异常。
13.3 fail-safe
为了避免触发fail-fast机制导致异常，我们可以使用Java中提供的一些采用了fail-safe机制的集合类。
java.util.concurrent包下的容器都是“fail-safe”的，可以在多线程下并发使用和修改，也可以在foreach中执行add/remove操作。
我们以CopyOnWriteArrayList这个fail-safe的集合类为例:
public static void main(String[] args) {
List<String> userNames = new CopyOnWriteArrayList<String>() {
{
add("Hollis");
add("hollis");
add("HoliisChuang");
add("H");
}
}
;
userNames.iterator();
for (String userName : userNames) {
if (userName.equals("Hollis")) {
userNames.remove(userName);
}
}
System.out.println(userNames);
}
以上代码使用CopyOnWriteArrayList代替了ArrayList,就不会发生异常。
fail-safe集合中的所有对集合的修改都是先复制一份副本，然后在副本集合上进行的,并不是直接对原集合进行修改。并且这些修改方法,如add/remove都是通过加锁来控制并发的。
所以,CopyOnWriteArrayList中的迭代器在迭代的过程中不需要做fail-fast的并发检测（因为fail-fast的主要目的就是识别并发,然后通过异常的方式通知用户）。
虽然基于复制内容的优点是避免了ConcurrentModificationException，但同样地,迭代器并不能访问修改后的内容,例如:
public static void main(String[] args) {
List<String> userNames = new CopyOnWriteArrayList<String>() {
{
add("Hollis");
add("hollis");
add("HoliisChuang");
add("H");
}
}
;
Iterator it = userNames.iterator();
for (String userName : userNames) {
if (userName.equals("Hollis")) {
userNames.remove(userName);
}
}
System.out.println(userNames);
while (it.hasNext()) {
System.out.println(it.next());
}
}
我们得到CopyOnWriteArrayList的Iterator之后,通过for循环直接删除原数组中的值,最后在结尾处输出Iterator，结果如下:
[hollis,HollisChuang,H]
Hollis
hollis
Hollischuang
H
迭代器遍历的是开始遍历那一刻获取的集合副本,在遍历期间原集合发生的修改,迭代器是不知道的。
14、为什么Java 8中的Map引入了红黑树
14.1 红黑树
14.1.1 开篇
为了解决HashMap的效率问题,就需要考虑使用一种插入和查询效率都比较高的数据结构。对于数据结构有一定了解的读者,首先就会想到二叉查找树。
二叉查找树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势,如图10-30所示。
一棵包含n个元素的二叉查找树,它的平均时间复杂度为O(logn)。
但也有特殊情况,那就是当元素有序时,比如(1，2，3，4,5，6）这样的序列,构造出来的二叉查找树就会退化成单链表,平均时间复杂度降低为O(n),如图10-31所示。
这种树就是平衡二叉查找树(AVL树)。AVL树在查找时效率比较高。但是为了保证这棵树一直是平衡的，每次在做元素的插入和删除操作时，需要对这棵树进行平衡调整，使它一直保持为一棵平衡树。
那么,有没有一种树,可以像AVL树一样有高效的查询效率，并且在插入和删除元素时不至于有太大的性能损耗呢?
有的,这就是我们要介绍的主角——红黑树。
14.1.2 红黑树
参考：https://blog.csdn.net/cy973071263/article/details/122543826
红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。
具体来说,红黑树是满足如下条件的二叉查找树，
- 节点是红色或黑色；
- 根是黑色；
- 叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），下图中的那些null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点；
- 红色节点的子节点都是黑色
- 红色节点的父节点都是黑色
- 从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
- 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
根据上面的性质，我们来判断一下下面这课树是不是红黑树。
上面这棵树首先很容易就能知道是满足性质1-4条的，关键在于第5条性质，可能乍一看好像也是符合第5条的，但实际就会陷入一个误区，直接将图上的最后一层的节点看作叶子节点，这样看的话每一条从根节点到叶子结点的路径确实都经过了3个黑节点。
但实际上，在红黑树中真正被定义为叶子结点的，是那些空节点，如下图。
这样一来，路径1有4个黑色节点（算上空节点），路径2只有3个黑色节点，这样性质5就不满足了，所以这棵树并不是一个红黑树节点。
14.2 在HashMap中引入红黑树
因为HashMap采用的是数组+链表的结构,当链表长度过长时,会存在性能问题。所以,在JDK1.8中引人入了红黑树。
但不是说直接就把数据结构替换成了红黑树,而是在满足一定条件时,数据结构才会转成红黑树,如图10-34所示。
JDK1.8中这部分转换的代码如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//省略这部分代码
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
重点是如下两行代码：
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
当前链表长度大于TREEIFY_THRESHOLD时,此链表就会转换成红黑树。在JDK1.8中,新增了三个重要的常量:
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
- TREEIFY_THRESHOLD :表示从链表转换成红黑树的阈值,当链表中的节点数量大于或等于这个值时,链表就会转换成红黑树。
- UNTREEIFY_THRESHOLD ：表示从红黑树退化成链表的阈值,当链表中法人节点数量小于或等于这个值时,红黑树就会转换成链表。
- MIN_TREEIFY_CAPACITY ：表示从链表转换成红黑树时,容器的最小容量的阈值。只有当容量大于这个数并且链表长度大于或等于TREEIFY_THRESHOLD时,才会转换成红黑树。
为什么要设置这三个变量来控制链表和红黑树之间的互相转换呢?
主要是因为把链表转换成红黑树并不是一个简单的过程，在内存和性能方面都是有损耗的。所以,需要一些条件来限制这种转换。
- 首先需要确定一个值,当链表长度大于它时，把链表转换成红黑树，这个值既不能太大,也不能太小。
- 这个值太大了会导致链表过长,从而影响查询速率。这个值太小了会导致转换频率过高,浪费时间。
15、为什么将HashMap转换成红黑树的阈值设置为8
为了确定HashMap的数据结构从链表转换成红黑树的阈值,JDK官方人员做了推算,他们发现在理想情况下,随机hashCode算法下所有节点的分布频率会遵循泊松分布。
泊松分布(Poisson分布)是一种统计与概率学中常见的离散概率分布。泊松分布适合于描述单位时间内随机事件发生的次数，泊松分布的参数入是单位时间内随机事件的平均发生次数。
在默认负载因子是0.75的条件下,泊松分布中的概率参数入约等于0.5。根据公式:
将0.5代入入,并计算出不同的k个元素同时落到一个桶中的概率,结果如下:
- k=0：0.60653066。
- k=1：0.30326533。
- k=2：0.07581633。
- k=3：0.01263606。
- k=4：0.00157952。
- k=5：0.00015795。
- k=6：0.00001316.
- k=7：0.00000094。
- k=8：0.00000006
- k>8：小于千万分之一。
从上面的结果可以看出：一个链表中被存放8个元素的概率是0.00000006，大于8个元素的概率更低，可以认为几乎不可能发生了（这个数值在JDK的HashMap源码中也有提到）。
也许读者有这样的疑问,0.00000006已经很小了，发生的概率就很低了,如果选择8作为阈值,那么链表还有机会转换成红黑树吗?
其实,这个数值的推算是有一定前提的:理想情况下、随机Hash算法、忽略方差。
但是,很多人头现Hash算法的方式也都不一样。最差的情况就是所有元素的Hash值都一样，例如:
public int hashCode(){
return 1;
}
一个这样的Hash算法，元素落到同一个链表中的概率就高达100%了。所以,在实际情况下，不同的Hash 函数对于元素在HashMap中的存储情况是影响巨大的。而HashMap中存入的元素所采用的Hash算法是无法被JDK控制的。
为了防止一个不好的Hash算法导致链表过长，需要选定一个长度作为链表转换成红黑树的阈值。而在随机Hash的情况下,一个链表中有8个元素的概率很低(0.00000006),而且并没低到几乎不可能发生(小于千万分之一）。
所以,选择8作为这个阈值是比较合适的。在使用好的Hash算法的情况下可以避免频繁地把链表转换成红黑树,在使用坏的Hash算法的情况下，也可以在合适的时机把链表转换成红黑树,从而提高效率。
知道了TREEIFY_THRESHOLD为什么是8,就容易理解为什么把UNTREEIFY_THRESHOLD设置成6了。设置一个比8小一点的数字,主要为了避免链表和红黑树之间的转换过于频繁。
16、Java 8中Stream的相关用法
17、Java中的并发容器
开篇
前面介绍了几个并发容器,如ConcurrentHashMap和CopyOnWritcArrayList等，这些容器类都是被定义在java.util.concurrent包中的,这个包就是我们常说的并发包”，有时会用J.U.C这个简写来代替它,其实指的都是这个包。
Java的并发包是在JDK 1.5中引人的,它的主要作者是非常有名的Doug Lea，这个包中包含了很多并发编程的工具类，而且很多类的实现都包含了Java工程师对于并发编程的思考。如果想要学习并发编程,那么应该通读这个包中所有类的源码。
Java的并发包中有很多类,本节不会全部介绍，本节只聚焦在那些并发容器上，其他并发相关的类,读者可以阅读《Java工程师成神之路》系列的“并发篇”。
当前Java的并发包中（基于JDK 17）主要有以下并发容器:
- ConcurrentHashMap。
- ConcurrentLinkedDeque。
- ConcurrentLinkedQueue。
- ConcurrentNavigableMap。
- ConcurrentSkipListMap。
- ConcurrentSkipListSet。
- CopyonwriteArrayList。
- CopyonwriteArraySet。
- LinkedBlockingDeque。
- LinkedBlockingQueue。
- LinkedTransferQueue。
- ArrayBlockingQueue。
- PriorityBlockingQueue。
- SynchronousQueue。
- TransferQueue。
接下来我们就针对其中的部分并发容器做一些简单的介绍。
Linked VS Array
在并发包中我们可以看到,数据结构的实现有Linked和Array两种，如LinkedBlockingDeque和ArrayBlockingQueue,它们的主要区别和 LinkedList、ArrayList相似，一个是基于数组实现的,另一个是基于链表实现的。
ArrayBlockingQueue是基于数组实现的阻塞队列；LinkedBlockingQueue是基于链表实现的阻塞队列。
Queue表示队列，是一种特殊的线性表，特殊之处在于它只允许在队头取出元素、在队尾插入元素。 Deque表示双端队列 (Double Ended Queue)，它和Queue的区别是其队头、队尾都能添加和获取元素。
因为底层实现不同,因此它们的性质不同，使用数组实现的ArrayBlockingQueue总是有界的,而LinkedBlockingQueue可以是无界的。
- 有界队列:有固定大小的队列。
- 无界队列:没有设置固定大小的队列。
- LinkedBlockingQueue在不设置大小的时候，默认值为Integer.MAX_VALUE，可认为是无界的。
除此之外,它们还有一个重要的区别,为了保证并发安全，ArrayBlockingQueue在插入和删除数据时使用的是同一把锁。而LinkedBlockingQueue则是在插入和删除数据时分别采用了putLock和takeLock，显然LinkedBlockingQueue的并发度更高一些。
阻塞队列与非阻塞队列
在Java并发包中,队列(Queue)的实现主要分两种,一种是以ConcurrentLinkedQueue为代表的非阻塞队列,另一种是以BlockingQueue接口为代表的阻塞队列。
什么是阻塞队列,什么是非阻塞队列呢?
- 对于队列,通常有入列和出列两种操作,在通常情况下,阻塞队列和非阻塞队列的操作差别不大。但凡事都有例外,而这个例外就是阻塞队列和非阻塞队列的区别了。
- 当我们向队列中添加元素时,如果队列已满,那么入列操作就会阻塞。直到消费了队列中的元素,使得队列变得不满时,才能继续执行入列操作。
同理,当我们从队列中取出元素时,如果队列已空,那么出列操作就会阻塞,直到向队列中添加了新的元素,使得队列变得不空时,才能继续执行出列操作。
相比于非阻塞队列,阻塞队列能够防止队列容器溢出,避免数据丢失。而非阻塞队列虽然安全性不如非阻塞队列,但性能要好一些,因为它不需要阻塞。
Blocking VS Transfer
TransferQueue接口及其实现类LinkedTransferQueue是在Java 7中新增的并发容器。它继承自BlockingQueue:
public interface TransferQueue<E> extends BlockingQueue<E> {
}
也就是说,TransferQueue也是一种阻塞队列,那么它和BlockingQueue有什么区别呢?
- 区别在于,当我们向BlockingQueue中添加元素时，除非遇到队列满了的情况，否则是不会阻塞的。但对于TransferQueue来说，生产者向其中添加元素时，可以一直阻塞，直到这个元素被其他消费者消费，TransferQueue中新增的transfer就是这种机制的具体实现。
- 其实通过名字也不难看出,transfer是转移、转让的意思，需要有人接收才行，所以就需要一直阻塞直到有人消费。
CopyOnWrite
在并发容器中,有两个容器是以“CopyOnWrite”开头的,分别是CopyOnWriteArrayList和CopyOnWriteArraySet,那么什么是CopyOnWrite?它的原理又是什么呢?
CopyOnWrite简称COW,是一种用于程序设计的优化策略。其基本思路是,从一开始大家都在共享同一个内容,当某个人想要修改这个内容时,才会真正把内容复制出去形成一个新的内容后再修改,这是一种延时懒惰策略。
CopyOnWrite容器即写时复制的容器。通俗的理解是当我们向一个容器中添加元素时,不直接向当前容器中添加,而是先复制当前容器，复制出一个新的容器，然后向新的容器中添加元素,添加元素之后,再将原容器的引用指向新的容器。
CopyOnWriteArrayList中的add/remove等写方法是需要加锁的,目的是为了避免复制多个副本,导致并发写。
但CopyOn WriteArrayList中的读方法是没有加锁的:
public E get(int index){
return get(getArray(), index);
}
这样做的好处是我们可以对CopyOnWrite容器进行并发读。当然，这里读到的数据可能不是最新的。因为写时复制的思相是通讨延时更新的策略来实现数据的最终一致性的，并非强调一致性。
所以CopyOnWrite容器体现的是一种读写分离的思想，读和写不同的容器。例如，同样是并发的容器，Vector在读写的时候使用同一个容器，读写互斥，同时只能做一件事情。
Skip List
在这样一个链表中查找12这个元素,只需要遍历2个节点就可以了(9、12）。
因为我们的链表不够大,查找的元素也比较靠前，所以速度上的感知可能没那么强烈。如果是在成千上万个节点、甚至数十万、百万个节点中遍历元素呢?这样的数据结构就能大大提高效率。
像上面这种带多级索引的链表，就是跳表。跳表的一个典型使用场景就是在Redis中实现有序集合。
在了解跳表之后，再回来说ConcurrentSkipListMap和ConcurrentSkipListSet,它们的底层都是基于跳表实现的。ConcurrentSkipListMap保证了各种操作的平均O(log(n))性能。
同样是支持高并发场景的Map,有人拿ConcurrentHashMap和ConcurrentSkipListMap相比,它们的相同点是都实现了ConcurrentMap接口,提供并发安全性。除此之外,ConcurrentSkipListMap还实现了SortedMap和NavigableMap，即同时还具备排序、导航(提供了ceilingEntry/ceilingKey、floorEntry/floorKey等方法)等功能。