柒夭日志：Java集合框架
图文详解了 40 多道 Java 集合框架面试高频题，目标是成功上岸，从现在开始努力，加油！！！（手动狗头），本文转载链接，并且在原文的基础上增加了一些自己的理解和思考且在最后加上了一个 Queue 部分的内容，希望能对各位读者有所帮助！！！
引言
1. 说说有哪些常见集合，并且之间有什么区别？
集合相关类和接口都在 java.util 中，主要分为 3 种，分别是：List（列表）、Map（映射）、Set（集合） 。
Java集合主要关系
其中 Collection 是集合 List、 Set、Queue 的父接口，它主要有三个子接口：
- List： 存储的元素有序，可以重复，有索引
- Set： 存储的元素无序，不可以重复，没有索引
- Queue： 队列集合，其存储的元素先入先出，后入后出
Map 是另外的接口，其是键值对映射结构的集合，这个是面试的重点内容，这里会着重讲这一部分的内容。
List
一般来说，List 可以问的东西可能不多，但是不排除面试官剑走偏锋，所以这里还是讲一讲大概内容。
2. ArrayList和LinkedList有什么区别？
- 数据结构不同
- ArrayList 是基于数组实现的
- LinkedList 是基于双链表实现的
- 多数情况下， ArrayList 更利于查找，LinkedList 更利于增删
- ArrayList基于数组实现，get(int index)可以直接通过数组下标获取，时间复杂度是O(1)；LinkedList基于链表实现，get(int index)需要遍历链表，时间复杂度是O(n)；当然，get(E element)这种查找，两种集合都需要遍历，时间复杂度都是O(n)。
- ArrayList增删如果是数组末尾的位置，直接插入或者删除就可以了，但是如果插入中间的位置，就需要把插入位置后的元素都向前或者向后移动，甚至还有可能触发扩容；双向链表的插入和删除只需要改变前驱节点、后继节点和插入节点的指向就行了，不需要移动元素。
注意，这个地方可能会出陷阱，LinkedList更利于增删更多是体现在平均步长上，不是体现在时间复杂度上，二者增删的时间复杂度都是O(n)
- 是否支持随机访问
- ArrayList基于数组，所以它可以根据下标查找，支持随机访问，当然，它也实现了RandmoAccess 接口，这个接口只是用来标识是否支持随机访问。
- 内存占⽤，ArrayList基于数组，是⼀块连续的内存空间，LinkedList基于链表，内存空间不连 续，它们在空间占⽤上都有⼀些额外的消耗 ：
- 因为 ArrayList 是预先定义好数组的，所以其有一些内存空间可能没有使用到，所以存在着一定程度上的空间浪费
- LinkedList 的每个节点都需要存储前驱以及后继，所以每个节点可能占用更多的内容和空间，以下是关于这个链表的一个简单示例：
public Class Node<T>{
private Node pre;
private T data;
private Node next;
}
3.ArrayList的扩容机制了解吗？
ArrayList是基于数组的集合，数组的容量是在定义的时候确定的，如果数组满了，再插入，就会数组溢出。所以在插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容。
ArrayList的扩容是先创建一个原先容量 1.5倍 的新数组，然后再将原数组的值遍历拷贝过去。
4.ArrayList怎么序列化的知道吗？为什么用transient修饰数组？
ArrayList的序列化不太一样，它使用 transient 修饰存储元素的 elementData 的数组，transient 关键字的作用是为了让被修饰的成员属性不被序列化。
这里可能有几个疑问哈，看我详细道来：
（1）为什么 ArrayList 不直接序列化元素呢？
出于效率考虑，数组可能长度为 100，但是实际却用了 50，剩下的 50 不用其实不用进行序列化，这样的的可以提高序列化和反序列化的效率，还可以节省内存空间。
（2）那 ArrayList 怎么序列化呢？
ArrayList 通过两个方法 readObject、writeObject自定义序列化和反序列化策略。实际上直接使用 ObjectOutputStream 和 ObjectInputStream 来进行序列化和反序列化。
5.快速失败(fail-fast)和安全失败(fail-safe)了解吗？
快速失败（fail-fast） ：快速失败是 Java 集合的一种错误检测机制
- 在用迭代器遍历一个集合对象时，如果线程A遍历过程中，线程B对集合对象的内容进行了修改（增加、删除、修改），则会抛出 Concurrent Modification Exception。
- 原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount ****变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。每当迭代器使用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异常，终止遍历。
- 注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改 modCount 值刚好又设置为了expectedmodCount 值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的 bug。
- 场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如 ArrayList 类。
安全失败（fail-safe） : 其是 Java 集合的另一种错误检测机制
- 采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
- 原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。
- 缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
- 场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如CopyOnWriteArrayList类。
6.有哪几种实现ArrayList线程安全的方法？
fail-fast是一种可能触发的机制，实际上，ArrayList的线程安全仍然没有保证，一般，保证ArrayList的线程安全可以通过这些方案：
- 使用 Vector 代替 ArrayList，虽然可以，但是不推荐，不推荐的原因如下：
Vector 是一个历史遗留类，它与 ArrayList 一样，都是基于数组实现的，不同的是 Vector 支持线程同步，即同一时刻只允许一个线程对于 Vector 进行写操作（增删改） ，以保证多线程环境下的数据一致性，但是需要频繁对 Vector 示例进行加锁和释放锁的操作，因此导致 Vector 的读写效率从整体上来说，远远比不是 ArrayList，所以不推荐使用。
- 使用 Collections.synchronizedList 包装 ArrayList，然后操作包装后的 list。
- 使用 CopyOnWriteArrayList 代替 ArrayList。
- 在使用 ArrayList 时，应用程序通过同步机制去控制 ArrayList 的读写。
7.CopyOnWriteArrayList了解多少？
CopyOnWriteArrayList就是线程安全版本的ArrayList。
它的名字叫 CopyOnWrite ——写时复制，已经明示了它的原理。
CopyOnWriteArrayList 采用了一种读写分离的并发策略。CopyOnWriteArrayList 容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。
8.Arraylist 和 Vector 的区别
- ArrayList在内存不够时扩容为原来的1.5倍，Vector是扩容为原来的2倍。
- Vector属于线程安全级别的，但是大多数情况下不使用Vector，因为操作Vector效率比较低。
9.怎么在遍历 ArrayList 时移除一个元素？
foreach删除会导致快速失败问题，可以使用迭代器的 remove() 方法。
Iterator itr = list.iterator();
while(itr.hasNext()) {
if(itr.next().equals("jay") {
itr.remove();
}
}
Map
在Map中，毫无疑问最重要的就是HashMap，这个基本是面试中的必考点，所以需要重点准备 ！！！！
10.能说一下HashMap的数据结构吗？
这个问题需要分成两个阶段来进行回答，分别是 JDK 1.8 以前和 JDK 1.8 之后。
JDK 1.8 以前，采用的数据结构是 数组 + 链表 ， 但是 JDK1.8 及以前的版本还有人在用？应该没有吧 .........
接下来来盘一下 JDK 1.8 中 HashMap 的数据结构：
其采用的数据结构是 数组 + 链表 + 红黑树 。
数据结构如下图所示：
其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。
- 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
- 如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
- 如果链表长度>8&数组大小>=64，链表转为红黑树
- 如果红黑树节点个数<6 ，转为链表
11.你对红黑树了解多少？为什么不用二叉树/平衡树呢？
红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：
- 每个节点要么是黑色，要么是红色的；
- 根节点永远是黑色的
- 所有叶子节点都是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
- 每个红色节点的两个子节点一定是黑色的；
- 从任一节点到其子树中的每个叶子节点的路径都包含相同数量的黑色节点；
这里我们提一个点哈，为什么不采用二叉树呢？
红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都是 O (log n)，避免二叉树最坏的情况下的
O(log n)，避免了二叉树最坏情况下的 O（n）时间复杂度。
那我们再提一个点，为什么不用平衡二叉树：
平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。
12.红黑树怎么保持平衡的知道吗？
红黑树保持平衡的方式一共有两种：旋转 和 染色 。
- 旋转：旋转分为两种，左旋以及右旋
左旋
右旋
- 染⾊：
染色
13.HashMap的put流程知道吗？
这里先来看一下那个流程图
- 首先是进行哈希值的扰东，获取一个新的哈希值。 （key == null）? 0 : (h = key.hashCode() ^ (h >>> 16))
-
- 判断tab是否位空或者长度为0，如果返回的是 true ，则进行扩容操作。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
- 根据哈希值计算下标，如果对应小标正好没有存放数据，则直接插入即可否则需要覆盖。
tab[i = (n - 1) & hash])
- 判断tab[i]是否为树节点，如果不是树节点的话，将向链表中插入数据，如果是树节点，则向树中插入节点。
- 如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树。
treeifyBin(tab, hash);
- 最后所有元素处理完成后，判断其是否超过阈值：threshold， 如果超过则扩容。
14.HashMap怎么查找元素的呢？
首先来看一下流程图：
HashMap的查找就简单很多：
- 使用扰动函数，获取新的哈希值
- 计算数组下标，获取节点
- 当前节点和key匹配，直接返回
- 否则，当前节点是否为树节点，查找红黑树
- 否则，遍历链表查找
15.HashMap的哈希/扰动函数是怎么设计的?
HashMap的哈希函数是先拿到 key 的 hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。
static final int hash(Object key) {
int h;
// key的hashCode和key的hashCode右移16位做异或运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这种设计方式其目标就是为了降低哈希碰撞的概率。
16.为什么哈希/扰动函数能降hash碰撞？
因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为
-2147483648~2147483647， 这样加起来就大概有 40 亿个映射空间。
这里提一我看到的腾讯的面试题，用1kb的空间，如何对 40 亿个 QQ 号怎么实现去重，这里用到的是位运算加上哈希的知识点，感兴趣的同学可以自行百度了解一下
只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。
假如 HashMap 数组的初始大小才 16，就需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。
源码中模运算就是将散列值和数组长度 - 1 作一个与运算（&） 的操作，位运算比 （取余 %） 运算更快 。
bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
return h & (length-1);
}
顺便说一下，这也正好解释了为什么 HashMap 的数组长度要取 2 的整数幂。因为这样（数组长度 - 1）正好相当于一个 “低位掩码” 。与 ****操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2 进制表示是0000 0000 0000 0000 0000 0000 0000 1111。和某个散列值做 与 操作如下，结果就是截取了最低的四位值。
这样会更加快捷一些，但是新的问题来了，就算散列值的分布再松散，如果要是只取最后几位的值，其产生的碰撞也会很严重。如果散列本身处理的不是很好，在分布上面就会产生一个等差数列的漏洞，如果正好让最后几个低位呈现规律性重复的话，那就更加难以处理了。
这个时候 扰动函数 的价值就体现出来了，我们来看一下扰动函数的示意图：
这里采用了向右移动 16 位的方法，正好是 32 bit 的一半，然后让自己的高半区和低半区进行异或，就是为了混合原始哈希码的高位以及低位，借此来加大低位的随机性，从而降低哈希冲突。而且混合后的低位并不是完全舍弃了高位的东西，其掺杂了高位的部分特征，这样高位本身的信息变相地也保留了一些下来。
17.为什么HashMap的容量是2的幂次方呢？
这里主要有两个原因：
- 方便进行哈希取余
将元素放到 table 数组的上面，然后利用 hash 值 取余（%） 数组的大小来确定位置，然而 HashMap 采用了另一种位运算方法，即 hash 值 与（&） 数组大小 - 1 的方法，这两种方法最终实现的效果是一致的，其原因就在于 HashMap 的容量，HashMap 的大小是 2 的倍数，2的倍数就意味着该数的二进制位数只有一位是 1，而该数-1就可以得到二进制位上1变成0，后面的0变成1，再通过&运算，就可以得到和 取余（%） 一样的效果，并且效率要高得多。
当 HashMap 的容量是 2 的 n 次幂的时候，（n - 1）的 2 进制就是 1111111 xxx 111 的形式，这样与添加的元素的 hash 值进行位运算的时候，就可以得到充分的散列，使得添加的元素均匀地分布在 HashMap 的每一个位置上，从而减少 Hash 碰撞。
- 扩容机制
第二原因就在于扩容机制上面了，HashMap 的扩容机制是扩容后的大小是原来的 2 倍，即其扩容后的大小是 2 的倍数，然后将已经产生哈希碰撞的元素转移到新的 table 中去。
这个时候我们可以看一下 HashMap 的扩容方法 putVal 的源码：
if （++size > threadshold）{
resize()
}
afterNodeInsertion(evict)
return null;
这里我们可以看到，当你的添加进来后的 HashMap 的大小大于 负载因子 * HashMap （这里指threadshold ）的时候就会产生扩容。
18.如果初始化HashMap，传一个17的值new HashMap<>，它会怎么处理？
简单来说，就是初始化时，传的不是2的倍数时，HashMap会向上寻找离得最近的2的倍数，所以如果传入17的话，HashMap的实际容量就是32。
我们来看看一下 HashMap 的初始化的源码：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
- 阀值 threshold ，通过⽅法 tableSizeFor ****进⾏计算，是根据初始化传的参数来计算的。
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
- 同时，tableSizeFor 这个方法也要寻找比初始值大的，且最小的二进制数值，比如我传入了 33 ,其大于 32，所以我往上继续寻找，找到了 64，其就是 HashMap 的初始化容量了。
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; }
- MAXIMUM_CAPACITY = 1 << 30，这个是临界范围，也就是最⼤的Map集合。
- 计算过程是向右移位1、2、4、8、16，和原来的数做|运算，这主要是为了把⼆进制的各个位置都填上1，当⼆进制的各个位置都是1以后，就是⼀个标准的2的倍数减1了，最后把结果加1再返回即可。
这里以 17 为例，看一下初始化计算 table 容量的过程：
容量计算
19.你还知道哪些哈希函数的构造方法呢？
HashMap里哈希构造函数的方法叫：
- 除留取余法：H（key)=key % p（p<=N） ,关键字除以一个不大于哈希表长度的正整数p，所得余数为地址，当然HashMap里进行了优化改造，效率更高，散列也更均衡。
除此之外，还有这几种常见的哈希函数构造方法：
- 直接定址法 ： 直接根据 key 来映射到对应的数组位置，例如1232放到下标1232的位置。
- 数字分析法 ： 取 key 的某些数字（例如十位和百位）作为映射的位置
- 平方取中法 ： 取 key 平方的中间几位作为映射的位置
- 折叠法 ： 将 key 分割成位数相同的几段，然后把它们的叠加和作为映射的位置
散列函数构造
20.解决哈希冲突有哪些方法呢？
我们到现在已经知道，HashMap 使用链表 的原因为了处理哈希冲突，这种方法就是所谓的：
- 链地址法：
在冲突的位置拉取一个链表，然后把冲突的元素放进去，然后由于链表的效率太低，在 JDK 1.8 之后进行了改进，改进成了红黑树 + 链表的方式，当链表长度小于 8 的时候，采用链表的方式，当链表长度大于 8 的时候，采用红黑树的方式。
除了链地址法以外，在数据结构中还有几种常见的解决哈希冲突的方法：
- 开放地址法：开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。
然而找空闲的位置方法也有很多种：
- 线行探查法：从冲突的位置开始，依次判断下一个位置是否存在空闲，直到找到空闲的位置
- 平方探查法：从从冲突的位置 x 开始， 从冲突的位置x开始，第一次增加 1^2 个位置，第二次增加2^2，依次类推，直至找到空闲的位置
- 此处省略 1000 万字 .................
- 再哈希法:换种哈希函数，重新计算冲突元素的地址
- 建立公共溢出区：再建立一个数组，然后将冲突的元素放到里面去。
21.为什么HashMap链表转红黑树的阈值为8呢？
树化发生主要在 table 数组的长度大于64，且链表的长度大于8的时候。
为什么是8呢？源码的注释也给出了答案。
源码注释
红黑树节点的大小大概是普通节点大小的两倍，所以选择转红黑树，其实是一种牺牲了空间换时间的策略，其更多的是作为一种兜底的策略，主要目标是为了保证极端情况下的查找效率。
那为什么会选择 8 作为阈值呢？这主要和统计学有一定的关系。在理想的情况下，使用随机哈希码的方式，链表里面的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为8的情况，发生概率仅为0.00000006。
那为什么红黑树转回链表的阈值选择 6 ，而不是选择 8 呢 ？
这是因为如果这个阈值也设为 8 的话，如果发生 Hash 碰撞了，然后节点的增减都恰好在 8 的附近的话，就会导致链表和红黑树不断发生转换，从而导致资源的浪费。
22.扩容在什么时候呢？为什么扩容因子是0.75？
为了减少哈希冲突发生的概率，当当前 HashMap 的元素个数达到一个临界值（容量 * 负载因子） 的时候，就会自动触发扩容，把所有元素rehash之后再放在扩容后的容器中，这是一个相当耗费时间的操作,这里我们可以看一下HashMap 中 pushVal 中的扩容部分的源码。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
·········
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
可以看到，当你添加进来的元素达到了临界值，即源码中的 threshold 的时候，其就会自动发生扩容，那你可能有一个疑问，那这里的 临界值（threadshold） 是怎么来的呢？现在我们一起来看一下resize 方法：
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
·······
threshold = newThr;
这个临界值（threadshold） 是由两个部分组成的，分别是 DEFAULT_LOAD_FACTOR 即默认扩容因子和 DEFAULT_INITIAL_CAPACITY 即默认容量，这里的 newThr 便是我们的新的临界值，所以我们可以得出一条如下的公式：
临界值（threshold ）= 默认扩容因⼦ （DEFAULT_LOAD_FACTOR）* 默认容量（DEFAULT_INITIAL_CAPACITY ）
那就是当你的容量⼤于 16 * 0.75 = 12 的时候，就会自动触发扩容操作。
那我们回到这个问题哈，为什么选择 0.75 作为 HashMap 的默认扩容因子呢？
简单来说，这是对 空间成本 加上 时间成本 平衡的考虑（其实也可以说是概率与数学的综合考量，O(∩_∩)O哈哈~），我这里简单说一下哈，有不对的地方各位可以共同来探讨。
HashMap 的初始化长度是 16，默认的加载因子（扩容因子） 是 0.75，0.75 是对空间和时间效率的一个平衡选择，根据泊松分布，加载因子为 0.75 的时候产生碰撞的概率最小，大致就是这样了。但是这个 0.75 并不是固定不变的，可以根据你的情况进行调整：
- 如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值。
- 如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
这里引用 HashMap 中的一段注释：
在上面我们讲过，HashMap 的散列构造方式是 Hash 取余，而负载因子就决定了当元素个数达到多少的时候就实现扩容。
如果我们的扩容因子设置的比较大的话，空位比较少的时候才来扩容，这样就大大增加了发生哈希冲突的概率，查找的时间成本也就打打增加了。
但是如果设置的太小的话，元素比较少，空位比较多的时候就发生扩容了，这样发生哈希碰撞的概率就降低了，虽然查找的时间成本降低了，但是得利用更多的空间去存储元素，这样空间成本就增加了。
23.HashMap 的扩容机制了解吗？
HashMap 自 Java 8 以后，其是基于数组 + 链表 + 红黑树实现的，但⽤于存放key值的桶数组的长度是固定的，由初始化参数确定。
那么，随着数据的插入数量增加以及负载因子的作用下，就需要扩容来存放更多的数据。但是扩容过程中有一个非常重要的点，那就是 Java 8 中的优化操作，可以不需要重新计算每个元素的哈希值。
上面我们说过，HashMap的初始容量是2的次幂，因为这个点，所以 HashMap 每次扩容之后的长度都会变成原来的 2 倍，由于新的容量是 2 的次幂，所以元素只有两种可能：
- 在原来的位置
- 在原来位置的基础上移动 2 的次幂。
看下面这张图，n 是 table 的长度，图 a 表示扩容前的 key1 和 key2 两种 key 确定索引的位置，图 b 表示扩容后key1和key2两种key确定索引位置。
扩容之后的索引计算
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
扩容位置变化
所以在扩容时，只需要看原来的hash值新增的那一位是0还是1就行了
- 是0的话索引没变
- 是 1 的化变成 原索引 + oldCap
下面来看看容量由 16 扩容为 32 的示意图：
扩容节点迁移示意图
扩容节点的迁移主要的逻辑如下：
扩容主要逻辑
24.Java 8 对HashMap主要做了哪些优化呢？为什么？
Java 8 对于 HashMap 的主要变化有以下 5 个方面：
- 数据结构：有数组+ 链表变成了 数组 + 链表 + 红黑树
原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由 O(n) 降为 O(log n)
- 链表的插入方式：链表的插入方式从头插法改成了尾插法，即原本插入的时候，如果数组的位置上有元素了，jdk 1.7 是将元素放到数组中，然后原本的元素添加到链表中，作为后继节点。jdk 1.8 之后用的方式是遍历链表，然后将元素的位置放到链表最后面。
原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，在多线程的环境下会产生环。
- 扩容方式 （rehash 部分） ：扩容的时候 Java 7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。
原因：提高扩容的效率，更快地扩容。
- 散列函数：jdk 1.7 做了四次移位和四次异或，jdk1.8只做一次。
原因：做 4 次的话，边际效用也不大，改为一次，提升效率。
- 扩容的时间点：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容（具体扩容可以看 HashMap 的扩容函数 put）；
25.你能自己设计实现一个HashMap吗？
看到这题不要慌，红黑树版本的我们大概率是写不出来的，但是对于这道题目，我们还不至于寄，我们可以尝试写一下数组加上链表版本的，首先我们来对于 HashMap 设计的细节进行逐一分析：
- 散列函数的选择：hashCode()+除留余数法
- 哈希冲突的解决方法：链地址法
- 扩容方法：节点重新hash获取位置
然后代码如下：
package com.qinyao.map;
import java.util.HashMap;
/**
* @ClassName MyHashMap
* @Description 自定义实现 HashMap，使用 链表 + 数组的方式实现
* @Version 1.0.0
* @Author LinQi
* @Date 2023/10/02
*/
public class MyHashMap<K, V> {
/**
* HashMap 链表节点类
*
* @param <K> key 键
* @param <V> value 值
*/
private class Node<K, V> {
// HashMap节点 键
private K key;
// HashMap节点 值
private V value;
// 后继节点
private Node<K, V> next;
/**
* 构造方法
*
* @param key 节点的键
* @param value 节点的值
*/
public Node(K key, V value) {
this.key = key;
this.value = value;
}
/**
* 构造方法
*
* @param key 节点的键
* @param value 节点的值
* @param next 节点的后继
*/
public Node(K key, V value, Node<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
/**
* 成员变量：默认容量
*/
private final int DEFAULT_CAPACITY = 16;
/**
* 成员变量：这里不使用 double , 使用float计算，在转换成整数的时候会进行舍入
*/
private final float LOAD_FACTOR = 0.75f;
/**
* HashMap 的元素个数
*/
private int size;
/**
* 桶数组
*/
Node<K, V>[] buckets;
/**
* 无参构造器，设置桶数组的默认容量为 16
*/
public MyHashMap() {
buckets = new Node[DEFAULT_CAPACITY];
size = 0;
}
/**
* 有参构造器，初始化 HashMap 的容量
*
* @param capacity HashMap 初始化容量
*/
public MyHashMap(int capacity) {
buckets = new Node[capacity];
size = 0;
}
/**
* 返回 HashMap 的元素个数
*
* @return HashMap 的元素个数
*/
public int size() {
return size;
}
/**
* 哈希函数，获取地址
*
* @param key 存储的 key
* @return 存储位置的缩影
*/
private int getIndex(K key, int length) {
//获取hash code
int hashCode = key.hashCode();
//和桶数组长度取余
int index = hashCode % length;
// 获取到插入位置的索引
return Math.abs(index);
}
/**
* put方法
*
* @param key
* @param value
* @return
*/
public void put(K key, V value) {
//判断是否需要进行扩容
if (size >= buckets.length * LOAD_FACTOR) {
resize();
}
// 将元素插入对应的桶数组
putVal(key, value, buckets);
}
/**
* 扩容方法
*/
private void resize() {
//创建一个原本容量两倍的桶数组
Node<K, V>[] newBuckets = new Node[buckets.length * 2];
//将当前元素重新散列到新的桶数组
rehash(newBuckets);
//将数组进行拷贝
buckets = newBuckets;
}
/**
* 重新散列当前元素
*
* @param newBuckets 扩容后的桶数组，这里获取原本桶数组的大小，进行再哈希取余
*/
private void rehash(Node<K, V>[] newBuckets) {
//map大小重新计算
size = 0;
//将旧的桶数组的元素全部刷到新的桶数组里
for (int i = 0; i < buckets.length; i++) {
//数组元素为空，直接跳过
if (buckets[i] == null) {
continue;
}
Node<K, V> node = buckets[i];
while (node != null) {
//将元素放入新数组
putVal(node.key, node.value, newBuckets);
node = node.next;
}
}
}
/**
* 将元素存入指定的node数组
*
* @param key 存储的 key
* @param value 存储的 value
* @param table 存储的桶数组
*/
private void putVal(K key, V value, Node<K, V>[] table) {
//获取位置
int index = getIndex(key, table.length);
Node node = table[index];
//插入的位置为空
if (node == null) {
table[index] = new Node<>(key, value);
size++;
return;
}
//插入位置不为空，说明发生冲突，使用链地址法,遍历链表
while (node != null) {
//如果key相同，就覆盖掉
if ((node.key.hashCode() == key.hashCode()) && ((node.key == key) || node.key.equals(key))) {
node.value = value;
return;
}
node = node.next;
}
//当前key不在链表中，插入链表头部
Node newNode = new Node(key, value, table[index]);
table[index] = newNode;
size++;
}
/**
* 获取元素
*
* @param key
* @return
*/
public V get(K key) {
//获取key对应的地址
int index = getIndex(key, buckets.length);
if (buckets[index] == null) {
return null;
}
Node<K, V> node = buckets[index];
//查找链表，当链表节点不为空的时候，继续查找
while (node != null) {
if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) {
return node.value;
}
node = node.next;
}
return null;
}
}
26.HashMap 是线程安全的吗？多线程下会有什么问题？
HashMap 并不是线程安全的，其在多线程的环境下可能会产生下列问题：
- put 和 get 并发时，可能导致 get 为 null。线程 1 执⾏ put 时，因为元素个数超出 threshold⽽导致rehash，线程 2 此时执⾏ get，有可能导致这个问题，这个问题在 JDK 1.7 和 JDK 1.8 中都存在。
- 多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
- 多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
27.有什么办法能解决HashMap线程不安全的问题呢？
Java 中有Collections.synchronizedMap、ConcurrentHashMap以及 HashTable 可以实现线程安全的 Map。
- Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
- ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized（双重锁机制）。
- HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大；
28.HashMap和HashTable的区别？
HashMap和Hashtable都实现了Map接口。
- HashMap可以接受为null的key和value，key为null的键值对放在下标为0的头结点的链表中，而Hashtable则不行。
- HashMap是非线程安全的，HashTable是线程安全的。Jdk1.5提供了ConcurrentHashMap，它是HashTable的替代。
- Hashtable很多方法是同步方法，在单线程环境下它比HashMap要慢。
- 哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
29.能具体说一下ConcurrentHashmap的实现吗？
ConcurrentHashmap线程安全在jdk1.7版本是基于分段锁实现，在jdk1.8是基于CAS+synchronized 实现。
JDK 1.7 ：分段锁实现
从结构上说，1.7版本的ConcurrentHashMap采用分段锁机制，里面包含一个Segment数组，Segment继承于ReentrantLock，Segment则包含HashEntry的数组，HashEntry本身就是一个链表的结构，具有保存key、value的能力能指向下一个节点的指针。
实际上就是相当于每个Segment都是一个HashMap，默认的Segment长度是16，也就是支持16个线程的并发写，Segment之间相互不会受到影响。
JDK1.7 ConcurrentHashMap示意图
put流程
整个流程和HashMap非常类似，只不过是先定位到具体的Segment，然后通过ReentrantLock去操作而已，后面的流程，就和HashMap基本上是一样的。
- 计算hash，定位到segment，segment如果是空就先初始化
- 使用ReentrantLock加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功
- 遍历HashEntry，就是和HashMap一样，数组中key和hash一样就直接替换，不存在就再插入链表，链表同样操作
****get流程
get也很简单，key通过hash定位到segment，再遍历链表定位到具体的元素上，需要注意的是value是volatile的，所以get是不需要加锁的。
JDK 1.8：CAS + Synchronized 双重自检锁
jdk1.8实现线程安全不是在数据结构上下功夫，它的数据结构和HashMap是一样的，数组+链表+红黑树。它实现线程安全的关键点在于put流程。
put流程
- 首先计算hash，遍历node数组，如果node是空的话，就通过CAS+自旋的方式初始化
tab = initTable();
node数组初始化：
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
//如果正在初始化或者扩容
if ((sc = sizeCtl) < 0)
//等待
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //CAS操作
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
- 如果当前数组位置是空则直接通过CAS自旋写入数据
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
- 如果hash==MOVED，说明需要扩容，执行扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
- 如果都不满足，就使用synchronized写入数据，写入数据同样判断链表、红黑树，链表写入和HashMap的方式一样，key hash一样就覆盖，反之就尾插法，链表长度超过8就转换成红黑树
synchronized (f){
……
}
ConcurrentHashmap jdk1.8put流程
get查询
get很简单，和HashMap基本相同，通过key计算位置，table该位置key相同就返回，如果是红黑树按照红黑树获取，否则就遍历链表获取。
30.HashMap 内部节点是有序的吗？
HashMap是无序的，根据 hash 值随机插入。如果想使用有序的Map，可以使用LinkedHashMap 或者 TreeMap。
31.一般用什么作为HashMap的key?
一般用Integer、String这种不可变类当 HashMap 当 key。String类比较常用。
- 因为 String 是不可变的，所以在它创建的时候`hashcode``就被缓存了，不需要重新计算。这就是 HashMap 中的key经常使用字符串的原因。
- 获取对象的时候要用到 equals() 和 hashCode() 方法，而Integer、String这些类都已经重写了 hashCode() 以及 equals() 方法，不需要自己去重写这两个方法。
32.讲讲 LinkedHashMap 底层原理，以及其是怎么实现有序的？
HashMap是无序的，迭代HashMap所得到元素的顺序并不是它们最初放到HashMap的顺序，即不能保持它们的插入顺序。
LinkedHashMap继承于HashMap，是HashMap和LinkedList的融合体，具备两者的特性。每次put操作都会将entry(节点)插入到双向链表的尾部。
接下来我们来简单说一下 LinkedHashMap 是怎么实现有序的：
LinkedHashMap维护了一个双向链表，有头尾节点，同时 LinkedHashMap 节点 Entry 内部除了继承 HashMap 的 Node 属性，还有 before 和 after 用于标识前置节点和后置节点。
Entry节点
可以实现按插入的顺序或访问顺序排序。
LinkedHashMap实现原理
33.讲讲 TreeMap 以及 TreeMap 是怎么实现有序的？
TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序。
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
}
TreeMap 的继承结构：
TreeMap的特点：
- TreeMap是有序的key-value集合，通过红黑树实现。根据键的自然顺序进行排序或根据提供的Comparator进行排序。
- TreeMap继承了AbstractMap，实现了NavigableMap接口，支持一系列的导航方法，给定具体搜索目标，可以返回最接近的匹配项。如floorEntry()、ceilingEntry()分别返回小于等于、大于等于给定键关联的Map.Entry()对象，不存在则返回null。lowerKey()、floorKey、ceilingKey、higherKey()只返回关联的key。
那接下来我们来讲一下 TreeMap 是怎么实现有序的？
TreeMap
Set
Set 这里可能只有一部分题目，肯没有那么全 o(╥﹏╥)o，后面大家可以提出来，然后我来改进。
34.讲讲HashSet的底层实现？
HashSet 基于 HashMap 实现。放入HashSet中的元素实际上由HashMap的key来保存，而HashMap的value则存储了一个静态的Object对象。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map; //基于HashMap实现
//...
}
HashSet的add方法，直接调用HashMap的put方法，将添加的元素作为key，new一个Object作为value，直接调用HashMap的put方法，它会根据返回值是否为空来判断是否插入元素成功。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashSet套娃
而在HashMap的putVal方法中，进行了一系列判断，最后的结果是，只有在key在table数组中不存在的时候，才会返回插入的值。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
35.HashSet、LinkedHashSet 和 TreeSet 的区别？
- HashSet 是 Set 接口的主要实现类 ，HashSet 的底层是 HashMap，线程不安全的，可以存储 null 值;
- LinkedHashSet 是 HashSet 的子类，能够按照添加的顺序遍历；
- TreeSet 底层使用红黑树，能够按照添加元素的顺序进行遍历，排序的方式可以自定义。
Queue
36.讲一下ArrayDeque？
ArrayDeque实现了双端队列，内部使用循环数组实现，默认大小为16。它的特点有：
- 在两端添加、删除元素的效率较高
- 根据元素内容查找和删除的效率比较低。
- 没有索引位置的概念，不能根据索引位置进行操作。
ArrayDeque 和 LinkedList 都实现了 Deque 接口，如果只需要从两端进行操作，ArrayDeque效率更高一些。如果同时需要根据索引位置进行操作，或者经常需要在中间进行插入和删除（LinkedList有相应的 api，如add(int index, E e)），则应该选 LinkedList 。
ArrayDeque 和 LinkedList都是线程不安全的，可以使用 Collections 工具类中synchronizedXxx()转换成线程同步。
37.讲一下 JDK 提供的阻塞队列？
阻塞队列是 java.util.concurrent 包下重要的数据结构，BlockingQueue提供了线程安全的队列访问方式：当阻塞队列进行插入数据时，如果队列已满，线程将会阻塞等待直到队列非满；从阻塞队列取数据时，如果队列已空，线程将会阻塞等待直到队列非空。并发包下很多高级同步类的实现都是基于BlockingQueue实现的。BlockingQueue 适合用于作为数据共享的通道。
使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现。
阻塞队列和一般的队列的区别就在于：
- 多线程支持，多个线程可以安全的访问队列
- 阻塞操作，当队列为空的时候，消费线程会阻塞等待队列不为空；当队列满了的时候，生产线程就会阻塞直到队列不满
JDK 一共提供了 7 种阻塞队列，如下所示：
- ArrayBlockingQueue
有界阻塞队列，底层采用数组实现。ArrayBlockingQueue 一旦创建，容量不能改变。其并发控制采用可重入锁来控制，不管是插入操作还是读取操作，都需要获取到锁才能进行操作。此队列按照先进先出（FIFO）的原则对元素进行排序。默认情况下不能保证线程访问队列的公平性，参数fair可用于设置线程是否公平访问队列。为了保证公平性，通常会降低吞吐量。
private static ArrayBlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<Integer>(10,true);//fair
- LinkedBlockingQueue
LinkedBlockingQueue是一个用单向链表实现的有界阻塞队列，可以当做无界队列也可以当做有界队列来使用。通常在创建 LinkedBlockingQueue 对象时，会指定队列最大的容量。此队列的默认和最大长度为Integer.MAX_VALUE。此队列按照先进先出的原则对元素进行排序。与 ArrayBlockingQueue 相比起来具有更高的吞吐量。
- PriorityBlockingQueue
支持优先级的无界阻塞队列。默认情况下元素采取自然顺序升序排列。也可以自定义类实现compareTo()方法来指定元素排序规则，或者初始化PriorityBlockingQueue时，指定构造参数Comparator来进行排序。
PriorityBlockingQueue 只能指定初始的队列大小，后面插入元素的时候，如果空间不够的话会自动扩容。
- DelayQueue:支持延时获取元素的无界阻塞队列。队列使用PriorityBlockingQueue来实现。队列中的元素必须实现Delayed接口，在创建元素时可以指定多久才能从队列中获取当前元素。只有在延迟期满时才能从队列中提取元素。
- SynchronousQueue：不存储元素的阻塞队列，每一个put必须等待一个take操作，否则不能继续添加元素。支持公平访问队列。
SynchronousQueue可以看成是一个传球手，负责把生产者线程处理的数据直接传递给消费者线程。队列本身不存储任何元素，非常适合传递性场景。SynchronousQueue的吞吐量高LinkedBlockingQueue和ArrayBlockingQueue。
- LinkedTransferQueue
由链表结构组成的无界阻塞TransferQueue队列。相对于其他阻塞队列，多了tryTransfer和transfer方法。
transfer方法：如果当前有消费者正在等待接收元素（take或者待时间限制的poll方法），transfer可以把生产者传入的元素立刻传给消费者。如果没有消费者等待接收元素，则将元素放在队列的tail节点，并等到该元素被消费者消费了才返回。
tryTransfer方法：用来试探生产者传入的元素能否直接传给消费者。如果没有消费者在等待，则返回false。和上述方法的区别是该方法无论消费者是否接收，方法立即返回。而transfer方法是必须等到消费者消费了才返回。
- LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。
总结：JDK使用通知模式实现阻塞队列，所谓通知模式，就是当生产者往满的队列里添加元素时会阻塞生产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用。
补充点
40.在常见的集合类中，哪些集合类是线程安全的，哪些集合类是线程不安全的？
- 线程安全的集合类：
- Vector：比ArrayList多了同步机制。
- Hashtable。
- ConcurrentHashMap：是一种高效并且线程安全的集合。
- Stack：栈，也是线程安全的，继承于Vector。
- 线程不安全的集合类：
- Hashmap
- Arraylist
- LinkedList
- HashSet
- TreeSet
- TreeMap
41.迭代器 Iterator 是什么？
Iterator模式用同一种逻辑来遍历集合。它可以把访问逻辑从不同类型的集合类中抽象出来，不需要了解集合内部实现便可以遍历集合元素，统一使用 Iterator 提供的接口去遍历。它的特点是更加安全，因为它可以保证，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常。
public interface Collection<E> extends Iterable<E> {
Iterator<E> iterator();
}
主要有三个方法：hasNext()、next()和remove()。
42 . Iterator 和 Listerator 有什么区别？
ListIterator 是 Iterator的增强版。
- ListIterator遍历可以是逆向的，因为有previous()和hasPrevious()方法，而Iterator不可以。
- ListIterator有add()方法，可以向List添加对象，而Iterator却不能。
- ListIterator可以定位当前的索引位置，因为有nextIndex()和previousIndex()方法，而Iterator不可以。
- ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改。
- ListIterator只能用于遍历List及其子类，Iterator可用来遍历所有集合。
43.如何让一个集合不能被修改？
可以采用Collections包下的unmodifiableMap/unmodifiableList/unmodifiableSet方法，通过这个方法返回的集合，是不可以修改的。如果修改的话，会抛出 java.lang.UnsupportedOperationException异常.
List<String> list = new ArrayList<>();
list.add("x");
Collection<String> clist = Collections.unmodifiableCollection(list);
clist.add("y"); // 运行时此行报错
System.out.println(list. size());
对于List/Set/Map集合，Collections包都有相应的支持。
那使用final关键字进行修饰可以实现吗？
答案是不可以。
final关键字修饰的成员变量如果是是引用类型的话，则表示这个引用的地址值是不能改变的，但是这个引用所指向的对象里面的内容还是可以改变的。
而集合类都是引用类型，用final修饰的话，集合里面的内容还是可以修改的。
转载自:https://juejin.cn/post/7284158980112384035