【集合】双列集合

1. HashMap

1.1 底层：数组+链表+红黑树

1.7 和1.8 区别

JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。
JDK1.8 以后的 HashMap 增加了红黑树，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

1.2 JDK1.8 添加元素

当链表长度大于阈值（默认为 8）时，会首先调用 treeifyBin()方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 resize() 方法对数组扩容。

1.2.1 put() 方法

1. 如果定位到的数组位置没有元素 就直接插入。
2. 如果定位到的数组位置有元素就和要插入的 key 比较，如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。
   

1.3 HashMap的扩容操作是怎么实现的？

resize()方法

1.4 HashMap是怎么解决哈希冲突的？（3点）

1.4.1 什么是哈希？

任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）
所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

1.4.2 什么是哈希冲突？

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。

1.4.3 如何解决哈希冲突

1. 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
2. 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
3. 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；
   链地址法的方式解决哈希冲突：
   将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下
   hash()函数
   相比于hashCode返回的int类型，我们HashMap初始的容量大小16，要远小于int类型的范围，如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率(相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的)，并且最坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化
   那么，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动。在JDK 1.8中的hash()函数如下：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
}
1
2
3
4

红黑树
通过上面的链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，哈希碰撞减少，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；

1.5 HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
因此 HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；
在保证数组长度为2的幂次方的时候，使用h&(length-1)来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length,避免空间浪费，三来来解决了“哈希值与数组大小范围不匹配”的问题；

1.5.1 那为什么是两次扰动呢？

2次扰动 = 1次位运算 + 1次异或运算
两次就够了，已经达到了高位低位同时参与运算的目的；

1.5.2 为什么数组长度要保证为2的幂次方呢？

只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，即实现了key的定位，2的幂次方也可以减少冲突次数，提高HashMap的查询效率；
如果 length 为 2 的次幂 则 length-1 转化为二进制必定是 11111……的形式，在于 h 的二进制与操作效率会非常的快，而且空间不浪费；如果 length 不是 2 的次幂，比如 length 为 15，则 length - 1 为 14，对应的二进制为 1110，在于 h 与操作，最后一位都为 0 ，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

2. ConcurrentHashMap

2.0 初始化 initTable()

重要的常量：
private transient volatile int sizeCtl;
当为负数时，-1 表示正在初始化，-N 表示 N - 1 个线程正在进行扩容；
当为 0 时，表示 table 还没有初始化；
当为其他正数时，表示初始化或者下一次进行扩容的大小。

2.1 put() 方法

1. 如果没有初始化，就调用 initTable() 方法来进行初始化；
2. 为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功；
3. 如果需要扩容，就先进行扩容；
4. 如果都不满足，则利用 synchronized 锁写入数据。如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin() 中会首先判断当前数组长度≥64时才会将链表转换为红黑树。
5. 如果添加成功就调用 addCount() 方法统计 size，并且检查是否需要扩容。

2.2 扩容方法 transfer()：默认容量为 16，扩容时，容量变为原来的两倍。

helpTransfer()：调用多个工作线程一起帮助进行扩容，这样的效率就会更高。

2.3 get() 方法

1. 计算 hash 值，定位到该 table 索引位置，如果是头节点符合就返回；
2. 如果遇到扩容时，会调用标记正在扩容结点 ForwardingNode.find()方法，查找该结点，匹配就返回；
3. 以上都不符合的话，就往下遍历结点，匹配就返回，否则最后就返回 null。

2.4 ConcurrentHashMap 的并发度是什么？

程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16，且可以在构造函数中设置。当用户设置并发度时，ConcurrentHashMap 会使用大于等于该值的最小2幂指数作为实际并发度（假如用户设置并发度为17，实际并发度则为32）

2.5 针对 ConcurrentHashMap 锁机制具体分析（JDK 1.7 VS JDK 1.8）

2.5.1 jdk1.7（Segment 数组 + HashEntry 数组 + 链表）

JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），对整个桶数组进行了分割分段(Segment，分段锁)，相当于把一个 HashMap 分成多个段，每一把锁只锁容器其中一部分数据，这样支持多线程访问。多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。

首先将数据分为一段一段（这个“段”就是 Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。
HashEntry 用于存储键值对数据。

Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。

2.5.2 jdk1.8 Node（数组 + 链表 / 红黑树）

JDK 1.8 中使用Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。

ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。

Java 8 中，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

2.6 ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

1. 粒度降低了
2. 在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存。

3. 面试题

3.1 JDK 1.7 元素迁移导致死循环（头插法）

往集合中顺序插入1，2，3

扩容后，变成

这时候会发现，因为头插法，顺序已经发生改变，假如两个线程都来操作

线程1操作完已经变成下图

这时候线程2再来操作，就会有循环

3.2 hashmap扩容后需要再次计算hash么

由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图：

数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash转换坐标的方法计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为“10000+原坐标”，即“原长度+原坐标”。如下图：

因此，在扩容时，不需要重新计算元素的hash了，只需要判断最高位是1还是0就好了。

3.3HashMap与HashTable的区别？

1. HashMap 是线程不安全的，HashTable 是线程安全的；由于线程安全，所以 HashTable 的效率比不上 HashMap；
2. HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable 不允许；
3. HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；

jdk1.7头插法循环问题：https://www.bilibili.com/video/BV1n541177Ea?spm_id_from=333.337.search-card.all.click&vd_source=b901ef0e9ed712b24882863596eab0ca
1.8 hashmap扩容后需要再次计算hash么
https://zhuanlan.zhihu.com/p/114363420
ConcurrentHashMap ：
https://snailclimb.gitee.io/javaguide/#/docs/java/collection/java-collection-questions-02
https://snailclimb.gitee.io/javaguide/#/docs/java/collection/concurrent-hash-map-source-code