集合

航迹者大约 8 分钟

集合可以说是所有公司必问项。其中HashMap和ConcurrentHashMap是重中之重。

2.1 Java集合分类

简单分类，可参考

ArrayList 线程不安全，底层结构是数组，常用

LinkedList 线程不安全，底层结构是链表

Vector 线程安全，是对ArrayList所有方法加了synchronized，效率低

HashMap 线程不安全，底层使用数组加链表（红黑树）实现

LinkedHashMap 线程不安全，继承自HashMap，内部维持了一个链表实现

TreeMap 线程不安全，顺序树形结构的map

HashSet 线程不安全，底层使用HashMap实现

LinkedHashSet 线程不安全，继承自HashSet ，底层使用LinkedHashMap 实现

TreeSet 线程不安全，底层使用TreeMap 实现

2.1 HashMap

聊一聊HashMap：

HashMap是工作中很常用的一个集合类。以key-value键值对的方式体现，通过数组+链表实现（数组对象是一个实现了Map.entry接口的Node(Node是链表)）。

初始化： 数组默认长度为16，扩容每次翻倍，始终保持2的幂次方。为什么？ Node类包含hash、key、value、next（Node）四个属性。

添加数据： 当添加一个k-v时，先通过hash算法计算出桶值，再把v放到桶对应的链表的尾部。当链表长度超过阈值（默认为8）并且哈希表的总个数小于64才会自动转为红黑树。如果哈希表的长度是小于64，会先进行扩容也就是增大桶数、增大数组长度。

删除数据： 当删除指定k时，链表、红黑树会将指定的v删除掉。当为红黑树时，如果桶中元素个数减少到6（默认阈值-2），就会将红黑树重新转换为链表。这是为了表面

查询数据： 当查询指定key是，提供了俩个方法，get和getOrDefault。首先通过hash算法计算出数组的桶值（索引值），然后在从链表/红黑树中遍历获取数据。链表：使用do-while循环遍历链表，循环条件value值不为null，是比对key是否相同。

2.1.1 底层数据结构，链表变为红黑树的条件？

底层是以数组加链表构成的。

数组变量属性是Node<K,V>[] table。Node<K,V>是HashMap内部类，实现Map.Entry<K,V>接口。

Node内部类拥有四个属性：hash，key，value，next（Node）

链表在1.7之前是采用头插法的链表，1.8之后是采用尾插法。当链表个数达到8个并且数组长度超过64会变成红黑树。

当链表中数据较多是，查询的效率会下降，所以在1.8版本后做了一个升级。

当链表长度大于8并且数组长度大于64，就会转换为红黑树。

如果链表长度大于8，但是数组长度小于64，会进行扩容操作。不会转换为红黑树。

红黑树需要进行左旋，右旋，变色操作来保持平衡，当数组长度小于64时，使用数组加链表比使用红黑树查询速度更要快、效率要更高。

在HashMap有一段描述，大致意思是说：在理想状态下受随机分布的hashCode影响，链表中的节点遵循泊松分布。链表中的节点数是8的概率已经接近千分之一，这个时候链表的性能已经很差，所以在这种比较罕见和极端的情况下才会把链表转变为红黑树，大部分情况下HashMap还是使用链表，如果理想的均匀分布节点数不到8就已经自动扩容了。

2.1.2 默认容量，负载因子是什么？如何扩容（2的幂次方？）？

初始容量只是哈希表在创建时的容量，这里的容量是哈希表中桶的数量，数组初始化容量是16。

默认的负载因子是0.75f

当哈希表中的条目数超出了加载因子与当前容量的乘积时，就要对该哈希表进行扩容、rehash，也就是重建内部数据结构，扩容后的哈希表将具有两倍的原容量。

hashmap初始化容量时候，对容量大小做的处理，保证初始化容量为最近的2的幂次方，因为当数组长度为2的幂次方时，可以使用位运算来计算元素在数组中的下标，提高运算效率，除此之外还可以增加hash值的随机性，减少hash冲突。

扩容rehash操作：

如何计算下标值的？
- 通过hash(key)函数 + (n - 1) & hash] 得到的
hash(key)函数是什么？
- (h = key.hashCode()) ^ (h >>> 16)，通过高16位和低16（数据右移）位进行异或，增加随机性。
(n - 1) & hash]？
- n是数组长度，(n - 1) & hash]其实也就是让hash值除以数组长度求余，为了获取下标值。通过与操作实现求余相同的结果，与操作效率更高。
数组长度为2的n次幂的原因
- 为了保证求位置下标值进行与操作算法
//返回给定目标容量的 2 次方 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; }

2.1.3 7和8并发扩容链表头插法改为尾插法？

第二点，发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程环境下，会发生数据覆盖的情况。

如果没有hash碰撞的时候，它会直接插入元素。

如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，线程A会把线程B插入的数据给覆盖，导致数据发生覆盖的情况，发生线程不安全。

实际的报错现象就是：java.util.ConcurrentModificationException并发修改异常。

导致原因：并发争取修改导致，一个线程正在写，一个线程过来争抢，导致线程写的过程被其他线程打断，导致数据不一致。

JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，内部大量采用CAS操作，这里我简要介绍下CAS。 CAS是compare and swap的缩写，即我们所说的比较交换。cas是一种基于锁的操作，而且是乐观锁。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加version来获取数据，性能较悲观锁有很大的提高。 JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。 Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。 Java8 ConcurrentHashMap结构基本上和Java8的HashMap一样，不过保证线程安全性

putVal（）方法，jdk8取消了桶的设计，使用了Node+CAS+Synchronized来保证并发安全进行实现

for (Node<K,V>[] tab = table;;) {
     //...
     synchronized (f) {
         
     }
}

2.2.3 JDK8的改进

其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap。

相对而言， ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock + Segment + HashEntry。到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。

1.数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
2.保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自 ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
3.锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
5.查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

集合