1 集合概述
1.1 Collection 接口的实现类
List
Arraylist：Object[]数组Vector：Object[]数组，线程安全LinkedList： 双向链表 (JDK1.6 之前为循环链表，JDK1.7 取消了循环)
Set
HashSet(无序，唯一): 基于HashMap实现的，底层采用HashMap来保存元素LinkedHashSet:LinkedHashSet是HashSet的子类，并且其内部是通过LinkedHashMap来实现的。有点类似于我们之前说的LinkedHashMap其内部是基于HashMap实现一样，不过还是有一点点区别的TreeSet(有序，唯一): 红黑树 (自平衡的排序二叉树)
Queue
PriorityQueue:Object[]数组来实现二叉堆ArrayQueue:Object[]数组 + 双指针
Map
HashMap： JDK1.8 之前，由数组+链表组成，即“拉链法”解决冲突。JDK1.8 以后，由数组+链表/红黑树组成，当大于 8 小于 64，先进行数组扩容 (?)，当大于 64，转换成红黑树。LinkedHashMap：LinkedHashMap继承自HashMap，数组+链表/红黑树。增加双向链表，保持更新顺序，可以用作 LRUCache。Hashtable： 数组+链表组成的。TreeMap： 红黑树（自平衡的排序二叉树）
1.2 Arraylist 与 LinkedList 异同
- 线程安全：
ArrayList和LinkedList都是不同步的，也就是不保证线程安全；
- 底层数据结构：
Arraylist底层使用的是 **Object数组**LinkedList底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）
- 内存空间占用：
ArrayList会预留空间LinkedList双向链表的索引占用空间
- 插入和删除-元素位置
ArrayList采用数组存储。不指定位置，插入是 O (1)；指定位置，插入是 O (n-i)。删除时，O (n-i)。LinkedList采用链表存储，插入链表头部尾部，是 O (1)；指定位置时，插入 O (n)。
- 快速随机访问：
LinkedList不支持ArrayList支持
补充内容: RandomAccess 接口
该接口没有任何方法，仅一个标志，Arraylist 实现了该接口。
在二分查找时，如果支持随机访问，可以通过索引进行，否则只能使用迭代方式。
1.3 comparable 和 Comparator 的异同
comparable接口实际上是出自java.lang包它有一个compareTo(Object obj)方法用来排序comparator接口实际上是出自java.util包它有一个compare(Object obj1, Object obj2)方法用来排序
一般我们需要对一个集合使用自定义排序时，我们就要重写 compareTo() 方法或 compare() 方法，当我们需要对某一个集合实现两种排序方式，比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写 compareTo() 方法和使用自制的 Comparator 方法或者以两个 Comparator 来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的 Collections.sort() .
1.4 HashSet、LinkedHashSet 和 TreeSet 三者的异同
- 相同点
- 都是
Set接口的实现类，都能保证元素唯一，并且都不是线程安全的。
- 都是
- 主要区别在于底层数据结构不同。
HashSet的底层数据结构是基于HashMap实现的哈希表LinkedHashSet的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
- 底层数据结构导致应用场景不同。
HashSet用于不需要保证元素插入和取出顺序的场景LinkedHashSet用于保证元素的插入和取出顺序满足 FIFO 的场景TreeSet用于支持对元素自定义排序规则的场景。
1.5 Queue 与 Deque 的异同
Queue 是单端队列。
Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
Queue 接口 | 抛出异常 | 返回特殊值 |
|---|---|---|
| 插入队尾 | add (E e) | offer (E e) |
| 删除队首 | remove () | poll () |
| 查询队首元素 | element () | peek () |
Deque 是双端队列，在队列的两端均可以插入或删除元素。
Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：
Deque 接口 | 抛出异常 | 返回特殊值 |
|---|---|---|
| 插入队首 | addFirst (E e) | offerFirst (E e) |
| 插入队尾 | addLast (E e) | offerLast (E e) |
| 删除队首 | removeFirst () | pollFirst () |
| 删除队尾 | removeLast () | pollLast () |
| 查询队首元素 | getFirst () | peekFirst () |
| 查询队尾元素 | getLast () | peekLast () |
事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。
1.6 ArrayDeque 与 LinkedList 的异同
ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？
ArrayDeque是基于可变长的数组和双指针来实现，而LinkedList则通过链表来实现。ArrayDeque不支持存储NULL数据，但LinkedList支持。ArrayDeque插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O (1)。虽然LinkedList不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。
从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。
1.7 PriorityQueue 简介
优先队列，小根堆。
PriorityQueue利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据PriorityQueue是非线程安全的，且不支持存储NULL和non-comparable的对象。PriorityQueue默认是小顶堆，但可以接收一个Comparator作为构造参数，从而来自定义元素优先级的先后。
1.8 HashMap 和 Hashtable 的异同
- 线程是否安全：
HashMap是非线程安全的Hashtable是线程安全的, 因为Hashtable内部的方法基本都经过synchronized修饰。- 如果你要保证线程安全的话就使用
ConcurrentHashMap
- 效率：
- 因为线程安全的问题，
HashMap要比Hashtable效率高一点。 - 另外，
Hashtable基本被淘汰，不要在代码中使用它；
- 因为线程安全的问题，
- 对 Null key 和 Null value 的支持：
HashMap可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个Hashtable不允许有 null 键和 null 值，否则会抛出NullPointerException。
- 初始容量大小和每次扩充容量大小的不同 ：
- ① 创建时如果不指定容量初始值，
Hashtable默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。 - ② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而
HashMap会将其扩充为 2 的幂次方大小（HashMap中的tableSizeFor()方法保证，下面给出了源代码）。也就是说HashMap总是使用 2 的幂作为哈希表的大小, 后面会介绍到为什么是 2 的幂次方。
- ① 创建时如果不指定容量初始值，
- 底层数据结构：
HashMapJDK1.8 之前，由数组+链表组成，即“拉链法”解决冲突。JDK1.8 以后，由数组+链表/红黑树组成，当大于 8 小于 64，先进行数组扩容 (?)，当大于 64，转换成红黑树。- Hashtable 没有这样的机制。
Hashtable： 数组+链表组成的，数组是Hashtable的主体，链表则是主要为了解决哈希冲突而存在的。
1.9 HashMap 和 TreeMap 异同
TreeMap 和 HashMap 都继承自 AbstractMap ，但是需要注意的是 TreeMap 它还实现了 NavigableMap 接口和 SortedMap 接口。
实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。
实现 SortedMap 接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。示例代码如下：
综上，相比于 HashMap 来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。
1.10 ConcurrentHashMap 和 Hashtable 的异同
ConcurrentHashMap 比 Hashtable 快，后者是全表锁、粒度大，前者是分段锁、粒度小。
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
- 底层数据结构： JDK1.7 的
ConcurrentHashMap底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable和 JDK1.8 之前的HashMap的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的； - 实现线程安全的方式（重要）：
- ① 在 JDK1.7 的时候，
ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段 (Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 - 到了 JDK1.8 的时候已经摒弃了
Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和 CAS 来操作。（JDK1.6 以后对synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的HashMap，虽然在 JDK1.8 中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本； - ② **
Hashtable(同一把锁)** : 使用synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
- ① 在 JDK1.7 的时候，
2 ArrayList
2.1 ArrayList 简介
底层数据结构：
ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。
实现接口：
实现了 List , RandomAccess , Cloneable , java.io.Serializable 这些接口。
构造函数：
无参构造函数 - 元素为空数组
含初始容量的构造函数 - 小于 0，异常；等于 0，空数组；大于 0，参数大小的数组
含 Collection 类型的构造函数 - 0，空数组；size 大于 0，拷贝。
2.2 ArrayList 添加元素
add 方法
第一步，调用 ensureCapacityInternal 函数，来确保容量充足，如果不充足，则扩容；第二步，赋值，size++.
ensureCapacityInternal 方法
若空数组，则取 10 或者输入参数中最大值，然后调用 ensureExplicitCapacity 函数，判断是否需要扩容。
ensureExplicitCapacity 方法
若数组长度小于所需长度，则扩容。
new 创建空数组后添加数据的操作
刚开始，容量为 0，数组元素指向空数组；
添加第 1 个元素时，发现容量为 0，则扩容到 10，元素个数 size 为 1；
添加第 11 个元素时，所需容量 (11) 大于当前数组容量 (10)，则扩容。
2.3 ArrayList 扩容机制
ArrayList 使用grow 方法进行扩容，包含四步：
- 使用位运算，更新容量为旧容量的 1.5 倍。
- 如果新容量仍小于所需的容量，则更新为所需的容量。
- 如果新容量大于设定的数组最大容量 (MAX_ARRAY_SIZE)，则调用 hugeCapacity 检测是否溢出。
- 进行元素的复制。
hugeCapacity 方法
将所需的容量 cap 与设定的数组最大容量 (MAX_ARRAY_SIZE) 进行比较，若 cap 较大，则容量设定为 Integer 最大值，否则设置为 MAX_ARRAY_SIZE。
3 HashMap
3.1 HashMap 简介
数据结构：
HashMap JDK1.8 之前，由数组+链表组成，即“拉链法”解决冲突。JDK1.8 以后，由数组+链表/红黑树组成。当链表长度大于阈值（默认为 8）时，会首先调用 treeifyBin() 方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当哈希桶长度不小于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间；否则只会进行扩容。
另外，当链表长度小于 6 的时候，会从红黑树转为链表。
初始值：
初始容量为 16。
最大容量为 1<<30.
链条长度大于 8，调用 treeifyBin() 方法判断是否转红黑树。
哈希桶大小不小于 64，转红黑树。
链表长度小于 6，转链表。
加载因子为 0.75，控制数组存放数据的疏密程度。
null 存储：
HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。
哈希方法：
基于 hashcode 的扰动函数，高 16 位与低 16 位进行异或运算。(h = key.hashCode()) ^ (h >>> 16);
获得哈希后，与 len-1 进行与运算获得索引位置。 hash&(len-1)
尽可能降低碰撞的可能性，一次异或运算，计算快。
构造方法：
- 默认无参构造函数
- 含 Map 的构造函数
- 指定容量大小的构造函数-转换为 2
- 指定容量大小和加载因子的构造函数
3.2 补充数组容量计算的小奥秘
HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。会取大于或等于这个数的且最近的 2 次幂作为 table 数组的初始容量，使用 tableSizeFor(int) 方法，如 tableSizeFor (10) = 16（2 的 4 次幂），tableSizeFor (20) = 32（2 的 5 次幂），也就是说 table 数组的长度总是 2 的次幂。JDK1.8 源码如下：
static final int tableSizeFor (int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}3.3 hash 冲突的解决方法
- 开放地址法。+1、+2、+3 等。
- 如果某个 hash 值对应的数据比较多，会出现聚集问题。
- 再哈希法。多个哈希函数，一个冲突，则用下一个哈希函数。
- 链地址法。数组+链表。
- 公共溢出区。存放冲突数据。
3.4 HashMap 为什么不直接使用红黑树？
红黑树需要左旋、右旋、变色等操作保持平衡，数据小时，效率低。
3.5 HashMap 默认加载因子为什么为 0.75？
0.75 是时间和空间的一个平衡的选择。
若空间比较多，时间敏感，可以降低加载因子；反之，提高加载因子。
3.6 为什么链表改为红黑树的阈值是 8
源码中有注释：理想情况下使用随机的哈希码，容器中节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为 8 时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了 8，是根据概率统计而选择的。
Ignoring variance, the expected occurrences of list size k are (exp (-0.5) pow (0.5, k) /
factorial (k)).
3.7 HashMap Key 索引的计算方法
获得 key 的 hashcode，然后对 hashcode 计算哈希值。高 16 位与低 16 位进行异或运算。
(h = key.hashCode()) ^ (h >>> 16);
获得哈希后，与 len-1 进行与运算获得索引位置。
hash&(len-1)
3.8 HashMap 扩容
扩容过程
1 异常检测。若大于最大容量，不扩容；若为空，设为初值。
2 将大小扩为原来的 2 倍，生成新数组。
3 遍历就数组的每个数据，重新计算旧数组中的索引位置，将数据从旧数组移到新数组中。
4 更新引用。
为什么 2 倍扩容？
扩容时，需要重新计算索引。2 倍扩容时，可以通过简单的判断，快速计算出扩容后的索引位置。
扩容前的哈希与旧容量并运算为 0，则保存索引值不变。
扩容前的哈希与旧容量并运算不为 0，则新索引为旧索引+旧容量。
(e.hash & oldCap) == 0
3.9 HashMap put 插入原理
头插法的不好之处/为什么使用尾插法
因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环；
A 线程在插入节点 B，B 线程也在插入，遇到容量不够开始扩容，重新 hash，放置元素，采用头插法，后遍历到的 B 节点放入了头部，这样形成了环，如下图所示：
3.10 HashMap 1.7 与 1.8 不同
- 扩容后，索引计算更快捷；
- 引入了红黑树；
- 1.8 是尾插法，1.7 是头插法。比如扩容的时候，头插法会使链表上 Node 的顺序调转，而尾插法则不会。
- hash 方法扰动次数更少。
3.11 HashMap 线程不安全的原因
- 多线程下容易出现环。JDK 1.7 的时候，头插法。
- 多线程 put 操作会导致元素丢失。多线程同时 put，如果索引位置相同，则会造成其中一个 key 被覆盖。例如，都添加到链表尾部，都遍历到最后一个的时候，最后一个 next 等于当前节点，其中一个会丢失。
- put 和 get 并发操作，get 可能为 null。线程 1 put 时，若超出加载因子，则扩容+rehash。线程 2 执行 get 时，从新数组获取数据，此时新数组什么数据也没有，获取为 null。
头插法可能出问题的原因：
线程 1 和线程 2 都要扩容，此时线程 1 遍历时，局部变量 e 和 next。之后，线程 2 将数据都 rehash 完成。线程 1 继续遍历，将 e 对应的 A 元素进行 rehash，放到线程 1 哈希数组头部。e 迭代到 next 位置。对 e 元素进行 rehash，将 B 放到数组头部，从而导致 A 和 B 死循环了。
3.12 用可变类当 HashMap 的 key 有什么问题
hashcode 可能发生改变，导致 put 进去的值，无法 get 出。使用可变对象作为 key，之后修改可变对象，则无法 get 出。原因在于可变对象的 hashcode 大概率变了，此时会将该对象映射到不同的 hash 位置，因此检索不到数据。
3.13 LinkedHashMap
LinkedHashMap 用作 LRU cache。
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int maxEntries;
public LRUCache (int maxEntries) {
super (16, 0.75f, true);
this.maxEntries = maxEntries;
}
@Override
protected boolean removeEldestEntry (Map.Entry<K, V> eldest) {
return size () > maxEntries;
}
}4 ConcurrentHashMap
4.1 ConcurrentHashMap 1.7 简介
存储结构：
JDK 1.7 中 ConcurrentHashMap 是由 Segment 数组和 HashEntry 数组组成的，具体来说，ConcurrentHashMap 把哈希桶分成了多个组，每个组对应 Segment 数组的一个位置。其中，Segment 继承了 ReentrantLock 锁，是一个可重入锁。
总的来说，数据分为一段段存储，每一段数据配有一把锁，每个线程占用锁访问其中一段数据时，其他段数据也可以被其他线程访问，从而实现并发访问。
Segment 的个数一经初始化后就不再改变，默认有 16 个，即支持 16 个线程并发访问。
并发度：
默认 16。若初始化传入，则使用大于等于该值的最小的 2 的幂指数作为并发度，并且一旦确定，不可修改。如，初始化传入 17，并发度为 32.
4.2 ConcurrentHashMap 1.7 初始化
- 必要参数校验。
- 校验并发级别 concurrencyLevel 大小，如果大于最大值，重置为最大值。无惨构造默认值是 16.
- 寻找并发级别 concurrencyLevel 之上最近的 2 的幂次方值，作为初始化容量大小，默认是 16。
- 记录 segmentShift 偏移量，这个值为【容量 = 2 的 N 次方】中的 N，在后面 Put 时计算位置时会用到。默认是 32 - sshift = 28.
- 记录 segmentMask，默认是 ssize - 1 = 16 -1 = 15.
- 初始化 segments[0]，默认大小为 2，负载因子 0.75，扩容阀值是 2*0.75=1.5，插入第二个值时才会进行扩容。
4.3 ConcurrentHashMap 1.7 插入原理
首先，尝试获取锁。如果获取失败，则利用自旋获取锁；如果自旋超过 64 次，则改用阻塞获取锁。
获得锁后：
- 根据 key 的 hashcode 定位到 HashEntry
- 遍历 HashEntry，如果不为空，则判断传入的 key 和遍历的 key 相等，相等则覆盖，否则插入。
- 如果不为空，则新建立一个 HashEntry 加入到 Segment 中，同时会先判断是否需要扩容。
- 释放 Segment 的锁。
上面的源码分析了 ConcurrentHashMap 在 put 一个数据时的处理流程，下面梳理下具体流程。
- 计算要 put 的 key 的位置，获取指定位置的 Segment。
- 如果指定位置的 Segment 为空，则初始化这个 Segment.
初始化 Segment 流程：- 检查计算得到的位置的 Segment 是否为 null.
- 为 null 继续初始化，使用 Segment[0] 的容量和负载因子创建一个 HashEntry 数组。
- 再次检查计算得到的指定位置的 Segment 是否为 null.
- 使用创建的 HashEntry 数组初始化这个 Segment.
- 自旋判断计算得到的指定位置的 Segment 是否为 null，使用 CAS 在这个位置赋值为 Segment.
- Segment.put 插入 key, value 值。
Segment.put
由于 Segment 继承了 ReentrantLock，所以 Segment 内部可以很方便的获取锁，put 流程就用到了这个功能。
- tryLock () 获取锁，获取不到使用 **
scanAndLockForPut** 方法继续获取。 - 计算 put 的数据要放入的 index 位置，然后获取这个位置上的 HashEntry 。
- 遍历 put 新元素，为什么要遍历？因为这里获取的 HashEntry 可能是一个空元素，也可能是链表已存在，所以要区别对待。
如果这个位置上的 HashEntry 不存在：
如果这个位置上的 HashEntry 存在：- 如果当前容量大于扩容阀值，小于最大容量，进行扩容。
- 直接链表头插法插入。
- 判断链表当前元素 Key 和 hash 值是否和要 put 的 key 和 hash 值一致。一致则替换值
- 不一致，获取链表下一个节点，直到发现相同进行值替换，或者链表表里完毕没有相同的。
- 如果当前容量大于扩容阀值，小于最大容量，进行扩容。
- 直接头插法插入。
- 如果要插入的位置之前已经存在，替换后返回旧值，否则返回 null.
4.4 ConcurrentHashMap 1.7 获取元素原理
- 计算得到 key 的存放位置。
- 遍历指定位置查找相同 key 的 value 值。
4.5 ConcurrentHashMap 1.8 简介
数据结构：
Node 数组 + 链表 / 红黑树。当冲突链表达到一定长度时，链表会转换成红黑树。
锁的实现：
采用 CAS+synchronized 实现更加低粒度的锁，锁的级别控制在哈希桶元素的级别，也就是说只锁住这个链表头节点/红黑树的根节点，不影响其他哈希桶的读写，提高并发度。
4.6 ConcurrentHashMap 1.8 初始化
从源码中可以发现 ConcurrentHashMap 的初始化是通过自旋和 CAS 操作完成的。里面需要注意的是变量 sizeCtl ，它的值决定着当前的初始化状态。
- -1 说明正在初始化
- -N 说明有 N-1 个线程正在进行扩容
- 表示 table 初始化大小，如果 table 没有初始化
- 表示 table 容量，如果 table 已经初始化。
4.7 ConcurrentHashMap 1.8 插入原理
- 根据 key 计算出 hash 值。
- 判断是否需要进行初始化。
- 根据当前 key 定位出的 Node，拿到首节点 f
- 如果首节点 f 为空，表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
- 如果当前位置的
f.hash == MOVED == -1, 则其他线程在扩容，参与一起扩容。 - 如果都不满足，则利用 synchronized 锁住 f 节点，写入数据。
- 链表长度大于 8，进行数组扩容或转换为红黑树。
4.8 ConcurrentHashMap 1.8 获取元素原理
- 根据 hash 值计算位置。
- 查找到指定位置，如果头节点就是要找的，直接返回它的 value.
- 如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。
- 如果是链表，遍历查找之。
4.9 ConcurrentHashMap 扩容原理
ConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组里的数据移动到新的数组时，位置要么不变，要么变为 index+ oldSize，参数里的 node 会在扩容之后使用链表头插法插入到指定位置。
4.10 ConcurrentHashMap 的 get 方法是否要加锁？与 volatile 修饰的哈希桶有关系吗？
get 方法不需要加锁。
因为 Node 元素 val 和指针 next 使用 volatile 修饰的，多线程环境下，线程 A 修改节点的 val 或者新增节点的时候对线程 B 是可见的。
没有关系。
volatile 修饰哈希桶，主要是保证数组扩容时数据的可见性。
4.11 ConcurrentHashMap 不支持 key 或 value 的原因
value 为什么不能为 null，因为获取 null，不清楚 value 本身为 null 还是获取不到数据，因此存在二义性。
单线程 HashMap 可以使用 containsKey 来判断是否存在数据，但是 ConcurrentHashMap 使用 containsKey 的话，中间可能有其他线程插入数据，因此仍有问题。
key 为什么不能为 null，作者设计之初就不允许 null 存在。
4.12 ConcurrentHashMap 在 JDK 1.7 和 JDK 1.8 的区别
- 数据结构。取消了 Segment 分段锁的数据结构，使用数组+链表+红黑树的结构。
- 线程安全的机制。JDK 1.7 中采用 segment 的分段锁机制来实现线程安全；后者采用 CAS+Synchronized 来保证线程安全。
- 锁的粒度。原来对 Segment 加锁，现在对数组的元素加锁。
- 查询时间复杂度。链表的 O (n) 变红黑树的 O (logn).