Java 集合框架面经

1、说说有哪些常见的集合框架？

集合框架可以分为两条大的支线：

1. Map 接口：表示键值对的集合，一个键映射到一个值。键不能重复，每个键只能对应一个值。Map 接口的实现类包括 HashMap、LinkedHashMap、TreeMap 等。
2. Collection 接口：最基本的集合框架表示方式，提供了添加、删除、清空等基本操作，它主要有三个子接口：

• List 代表有序、可重复的集合，典型代表就是封装了动态数组的 ArrayList 和封装了链表的 LinkedList。
• Set 代表无序、不可重复的集合，典型代表就是 HashSet 和 TreeSet。
• Queue 代表队列，典型代表就是双端队列 ArrayDeque，以及优先级队列 PriorityQueue。

1.1 集合框架有哪几个常用工具类？

集合框架位于 java.util 包下，提供了两个常用的工具类：

1. Collections：提供了一些对集合进行排序、二分查找、同步的静态方法。
2. Arrays：提供了一些对数组进行排序、打印、和 List 进行转换的静态方法。

1.2 简单介绍一下队列？

Java 中的队列主要通过 Queue 接口和并发包下的 BlockingQueue 两个接口来实现。
优先级队列 PriorityQueue 实现了 Queue 接口，是一个无界队列，它的元素按照自然顺序排序或者 Comparator 比较器进行排序。双端队列 ArrayDeque 也实现了 Queue 接口，是一个基于数组的，可以在两端插入和删除元素的队列。

1.3 用过哪些集合类，它们的优劣？

我常用的集合类有 ArrayList、LinkedList、HashMap、LinkedHashMap。

ArrayList 可以看作是一个动态数组，可以在需要时动态扩容数组的容量，只不过需要复制元素到新的数组。优点是访问速度快，可以通过索引直接查找到元素。缺点是插入和删除元素可能需要移动或者复制元素。

LinkedList 是一个双向链表，适合频繁的插入和删除操作。优点是插入和删除元素的时候只需要改变节点的前后指针，缺点是访问元素时需要遍历链表。

HashMap 是一个基于哈希表的键值对集合。优点是可以根据键的哈希值快速查找到值，但有可能会发生哈希冲突，并且不保留键值对的插入顺序。

LinkedHashMap 在 HashMap 的基础上增加了一个双向链表来保持键值对的插入顺序。

1.4 队列和栈的区别了解吗？

队列是一种先进先出的数据结构，第一个加入队列的元素会成为第一个被移除的元素。栈是一种后进先出的数据结构，最后一个加入栈的元素会成为第一个被移除的元素。

1.5 哪些是线程安全的容器？

Vector、Hashtable、ConcurrentHashMap、CopyOnWriteArrayList、ConcurrentLinkedQueue、ArrayBlockingQueue、LinkedBlockingQueue 都是线程安全的。

1.6 Collection 继承了哪些接口？

Collection 继承了 Iterable 接口，这意味着所有实现 Collection 接口的类都必须实现 iterator() 方法，之后就可以使用增强型 for 循环遍历集合中的元素了。

2、ArrayList 和 LinkedList 有什么区别？

ArrayList 是基于数组实现的，LinkedList 是基于链表实现的。

2.1 ArrayList 和 LinkedList 的用途有什么不同？

多数情况下，ArrayList 更利于改查，LinkedList 更利于增删。

2.2 ArrayList 和 LinkedList 是否支持随机访问？

1. ArrayList 是基于数组的，也实现了 RandomAccess 接口，所以它支持随机访问，可以通过下标直接获取元素。
2. LinkedList 是基于链表的，所以它没法根据下标直接获取元素，不支持随机访问。

2.3 ArrayList 和 LinkedList 内存占用有何不同？

1. ArrayList 是基于数组的，是一块连续的内存空间，所以它的内存占用是比较紧凑的；但如果涉及到扩容，就会重新分配内存，空间是原来的 1.5 倍。
2. LinkedList 是基于链表的，每个节点都有一个指向下一个节点和上一个节点的引用，于是每个节点占用的内存空间比 ArrayList 稍微大一点。

2.4 ArrayList 和 LinkedList 的使用场景有什么不同？

ArrayList 适用的场景：

1. 随机访问频繁：需要频繁通过索引访问元素的场景。
2. 读取操作远多于写入操作：如存储不经常改变的列表。
3. 末尾添加元素：需要频繁在列表末尾添加元素的场景。

LinkedList 适用的场景：

1. 不需要快速随机访问：顺序访问多于随机访问的场景。
2. 频繁插入和删除：在列表中间频繁插入和删除元素的场景。
3. 队列和栈：由于其双向链表的特性，LinkedList 可以实现队列（FIFO）和栈（LIFO）。

2.5 链表和数组有什么区别？

1. 数组在内存中占用的是一块连续的存储空间，因此我们可以通过数组下标快速访问任意元素。数组在创建时必须指定大小，一旦分配内存，数组的大小就固定了。
2. 链表的元素存储在于内存中的任意位置，每个节点通过指针指向下一个节点。
   

3、ArrayList 的扩容机制了解吗？

当往 ArrayList 中添加元素时，会先检查是否需要扩容，如果当前容量 + 1 超过数组长度，就会进行扩容。扩容后的新数组长度是原来的 1.5 倍，然后再把原数组的值拷贝到新数组中。

4、ArrayList 怎么序列化的知道吗？

ArrayList 自定义了序列化逻辑从而只序列化有效数据，因为数组的容量一般大于实际的元素数量。

4.1 为什么 ArrayList 不直接序列化元素数组呢？

出于效率的考虑，数组可能长度 100，但实际只用了 50，剩下的 50 没用到，也就不需要序列化。

5、快速失败 fail-fast 了解吗？

在用迭代器遍历集合对象时，如果线程 A 遍历过程中，线程 B 对集合对象的内容进行了修改，就会抛出 Concurrent Modification Exception。迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用 hashNext()/next()遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异常，终止遍历。

java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如 ArrayList 类。

5.1 什么是安全失败？

采用安全失败机制的集合容器，在遍历时并不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

场景：java.util.concurrent 包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如 CopyOnWriteArrayList 类

6、有哪几种实现 ArrayList 线程安全的方法？

1. 可以使用 Collections.synchronizedList() 方法，它可以返回一个线程安全的 List。内部是通过 synchronized 关键字加锁来实现的。
2. 也可以直接使用 CopyOnWriteArrayList，它是线程安全的 ArrayList，遵循写时复制的原则，每当对列表进行修改时，都会创建一个新副本，这个新副本会替换旧的列表，而对旧列表的所有读取操作仍然在原有的列表上进行。

6.1 ArrayList 和 Vector 的区别？

Vector 属于 JDK 1.0 时期的遗留类，不推荐使用，仍然保留着是因为 Java 希望向后兼容。

ArrayList 是在 JDK 1.2 时引入的，用于替代 Vector 作为主要的非同步动态数组实现。因为 Vector 所有的方法都使用了 synchronized 关键字进行同步，所以单线程环境下效率较低。

7、CopyOnWriteArrayList 了解多少？

CopyOnWriteArrayList 就是线程安全版本的 ArrayList。采用了一种读写分离的并发策略。CopyOnWriteArrayList 容器允许并发读，读操作是无锁的。至于写操作，比如说向容器中添加一个元素，首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

8、能说一下 HashMap 的底层数据结构吗？

JDK 8 中 HashMap 的数据结构是数组 + 链表 + 红黑树：

数组用来存储键值对，每个键值对可以通过索引直接拿到，索引是通过对键的哈希值进行进一步的 hash() 处理得到的。当多个键经过哈希处理后得到相同的索引时，需要通过链表来解决哈希冲突：将具有相同索引的键值对通过链表存储起来。不过，链表过长时，查询效率会比较低，于是当链表的长度超过 8 时（且数组的长度大于 64），链表就会转换为红黑树。红黑树的查询效率是 O(logn)，比链表的 O(n) 要快。

hash() 方法的目标是尽量减少哈希冲突，保证元素能够均匀地分布在数组的每个位置上。如果键的哈希值已经在数组中存在，其对应的值将被新值覆盖。

HashMap 的初始容量是 16，随着元素的不断添加，HashMap 就需要进行扩容，阈值是capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为 0.75。扩容后的数组大小是原来的 2 倍，然后把原来的元素重新计算哈希值，放到新的数组中。

9、你对红黑树了解多少？

红黑树是一种自平衡的二叉查找树：

1. 左根右；
2. 根叶黑；
3. 不红红；
4. 黑路同；
   

9.1 为什么不用二叉树？

二叉树是最基本的树结构，每个节点最多有两个子节点，但是二叉树容易出现极端情况，比如插入的数据是有序的，那么二叉树就会退化成链表，查询效率就会变成 O(n)。

9.2 为什么不用平衡二叉树？

平衡二叉树比红黑树的要求更高，每个节点的左右子树的高度最多相差 1，这种高度的平衡保证了极佳的查找效率，但在进行插入和删除操作时，可能需要频繁地进行旋转来维持树的平衡，维护成本更高。

9.3 为什么用红黑树？

链表的查找时间复杂度是 O(n)，当链表长度较长时，查找性能会下降。红黑树是一种折中的方案，查找、插入、删除的时间复杂度都是 O(log n)。

9.4 红黑树插入删除规则？

​默认新节点为红色：
​插入逻辑：若插入后破坏红黑性质：
​情况1：父节点为黑色 → 无需调整。
​情况2：父节点为红色，递归调整。

删除逻辑：更复杂，需处理黑节点删除后的黑高减少问题。

10、红黑树怎么保持平衡的？

旋转和染色：

1. 旋转：通过左旋和右旋来调整树的结构，避免某一侧过深。
2. 染⾊：修复红黑规则，从而保证树的高度不会失衡。

11、HashMap 的 put 流程知道吗？

1. 首先计算键的哈希值，通过 hashCode() 高位运算和扰动函数，减少哈希冲突。
2. 进行第一次的数组扩容，确定桶的位置，根据哈希值按位计算数组索引。
3. 处理键值对，若桶为空，直接插入新节点。若桶不为空，判断当前位置第一个节点是否与新节点的 key 相同，如果相同则更新 value，如果不同说明发生哈希冲突，如果是链表，将新节点添加到链表的尾部；如果链表长度大于等于 8，则将链表转换为红黑树。
4. 检查容量并扩容，插入后若 size > threshold (capacity * loadFactor)，则扩容为原容量的两倍。并且重新计算每个节点的索引，数据将会重新分布。

11.1 只重写元素的 equals 方法没重写 hashCode，put 的时候会发生什么?

如果只重写 equals 方法，没有重写 hashCode 方法，那么会导致 equals 相等的两个对象，hashCode 不相等，这样的话，两个对象会被 put 到数组中不同的位置，size + 1，导致大量哈希冲突，退化成链表，查询效率降为 O(n)。

12、HashMap 怎么查找元素的呢？

通过哈希值定位索引 → 定位桶 → 检查第一个节点 → 遍历链表或红黑树查找 → 返回结果。

13、HashMap 的 hash 函数是怎么设计的?

先拿到 key 的哈希值，是一个 32 位的 int 类型数值，然后再让哈希值的高 16 位和低 16 位进行异或操作，这样能保证哈希分布均匀，减少哈希冲突。

14、为什么 hash 函数，能减少哈希冲突？

哈希函数通过异或操作将哈希值的高位引入低位，可以增加哈希值的随机性，从而减少哈希冲突。将哈希值无符号右移 16 位，意味着原哈希值的高 16 位被移到了低 16 位的位置。这样，原哈希值的高 16 位和低 16 位就可以参与到最终用于索引计算的低位中。选择 16 位是因为它是 32 位整数的一半，这样处理既考虑了高位的信息，又没有完全忽视低位的信息，从而达到了一种微妙的平衡状态。

15、为什么 HashMap 的容量是 2 的幂次方？

是为了快速定位元素在底层数组中的下标。HashMap 是通过 hash & (n - 1) 来定位元素下标的，n 为数组的大小，也就是 HashMap 底层数组的容量。数组长度 - 1 正好相当于一个低位掩码。掩码的低位最好全是 1，这样 & 运算才有意义，否则最后一位结果一定是 0。 2 的幂次方刚好是偶数，偶数 - 1 是奇数，奇数的二进制最后一位是 1，也就保证了 hash & (n - 1) 的最后一位可能为 0，也可能为 1（取决于 hash 的值），这样可以保证哈希值的均匀分布。

15.1 对数组长度取模定位数组下标，这块有没有优化策略？

HashMap 的策略是将取模运算优化为位运算 hash & (n - 1)。因为当数组的长度是 2 的 N 次幂时，hash & (n - 1) = hash % n。位运算的速度要远高于取余运算，因为计算机本质上是二进制的。

15.2 说说什么是取模运算？

在 Java 中，通常使用 % 运算符来表示取余，用 Math.floorMod() 来表示取模。当操作数都是正数的话，取模运算和取余运算的结果是一样的；只有操作数出现负数的情况下，结果才会不同。当数组的长度是 2 的 n 次幂时，取模运算/取余运算可以用位运算来代替，效率更高，因为计算机本质上二进制的。

16、如果初始化 HashMap，传一个 17 的容量，它会怎么处理？

HashMap 会将容量调整到大于等于 17 的最小的 2 的幂次方，也就是 32。这是因为哈希表的大小最好是 2 的 N 次幂，这样可以通过 hash & (n - 1) 高效计算出索引值。

17、你还知道哪些哈希函数的构造方法呢？

1. 除留取余法：取 key 除以一个不大于哈希表长度的正整数 p，所得余数为地址。
2. 直接定址法：取 key 映射到对应的数组位置，例如 12345 放到索引为 12345 的位置。
3. 数字分析法：取 key 的某些数字作为映射的位置。
4. 平方取中法：取 key 平方的中间几位作为映射的位置。
5. 折叠相加法：取 key 分割成位数相同的几段，然后把它们的叠加和作为映射的位置。
   

18、解决哈希冲突有哪些方法？

1. 链地址法：当发生哈希冲突的时候，使用链表将冲突的元素串起来。
2. 再哈希法：当发生哈希冲突的时候，使用另外一种哈希算法，直到找到空槽。
3. 开放寻址法：遇到哈希冲突的时候，就去寻找下一个空的槽：

• 线性探测：从冲突的位置开始，依次往后找，直到找到空槽。
• 二次探测：从冲突的位置开始，第一次增加 2 个位置，第二次增加 4，第三次增加 9 个，直到找到空槽。

19、为什么 HashMap 链表转红黑树的阈值为 8 呢？

树化发生在 table 数组的长度大于 64，且链表的长度大于 8 的时候。阈值选择 8 跟统计学有关，源码注释给出的回答是：理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为 8 的情况，发生概率仅为小数点后八位。至于红黑树转回链表的阈值为什么是 6，而不是 8？是因为如果这个阈值也设置成 8，假如发生碰撞，节点增减刚好在 8 附近，会发生链表和红黑树的不断转换，导致资源浪费。

20、HashMap扩容发生在什么时候呢？

当键值对数量超过阈值，也就是容量(默认：16) * 负载因子(默认：0.75)时。

20.1 为什么使用 1 << 4 而不是直接写 16？

首先是为了强调这个值是 2 的幂次方，而不是一个完全随机的选择。然后是为了通过位运算符快速计算索引。

20.2 为什么选择 0.75 作为 HashMap 的默认负载因子呢？

这是一个经验值。如果设置得太低，如 0.5，会浪费空间；如果设置得太高，如 0.9，会增加哈希冲突。0.75 是 JDK 作者经过大量验证后得出的最优解，能够最大限度减少 rehash 的次数。

21、HashMap的扩容机制了解吗？

扩容时，HashMap 会创建一个新数组，其容量是原来的两倍。然后遍历旧哈希表中的元素，将其重新分配到新的哈希表中。如果当前桶中只有一个元素，那么直接通过键的哈希值与新数组的大小取模锁定新的索引位置。如果当前桶是红黑树，那么会调用 split() 方法分裂树节点，以保证树的平衡。如果当前桶是链表，会通过旧键的哈希值与旧的数组大小取余 == 0 来判断，如果条件为真，元素保留在原索引的位置；否则元素移动到原索引 + 旧数组大小的位置。

21.1 JDK 7 扩容的时候有什么问题？

JDK 7 在扩容的时候使用头插法来重新插入链表节点，这样会导致链表无法保持原有的顺序。

21.2 JDK 8 是怎么解决这个问题的？

JDK 8 改用了尾插法，并且当 (e.hash & oldCap) == 0 时，元素保留在原索引的位置；否则元素移动到原索引 + 旧数组大小的位置。这样可以避免重新计算所有元素的哈希值，只需检查高位的某一位，就可以快速确定新位置。

22、JDK 8 对 HashMap 做了哪些优化呢？

1. 底层数据结构由数组 + 链表改成了数组 + 链表或红黑树的结构。
2. 链表的插入方式由头插法改为了尾插法。头插法在扩容后容易改变原来链表的顺序。
3. 扩容的时机由插入时判断改为插入后判断，这样可以避免在每次插入时都进行不必要的扩容检查，因为有可能插入后仍然不需要扩容。
4. 哈希扰动算法也进行了优化。JDK 7 是通过多次移位和异或运算来实现的。JDK 8 让 hash 值的高 16 位和低 16 位进行了异或运算，让高位的信息也能参与到低位的计算中，这样可以极大程度上减少哈希碰撞。

23、你能自己设计实现一个 HashMap 吗？

可以，我先说一下整体的设计思路：

1. 第一步，实现一个 hash 函数，对键的 hashCode 进行扰动。
2. 第二步，实现一个链地址法的方法来解决哈希冲突。
3. 第三步，扩容后，重新计算哈希值，将元素放到新的数组中。

24、HashMap 是线程安全的吗？

HashMap 不是线程安全的，主要有以下几个问题：

1. 多线程下扩容会死循环。JDK7 中的 HashMap 使用的是头插法来处理链表，在多线程环境下扩容会出现环形链表，造成死循环。不过，JDK 8 时通过尾插法修复了这个问题，扩容时会保持链表原来的顺序。
2. 多线程在进行 put 元素的时候，可能会导致元素丢失。因为计算出来的位置可能会被其他线程覆盖掉。
3. 多线程在进行 get 元素的时候，可能导致 get 为 null。因为其他线程可能先执行 put ，导致容量超出阈值从而扩容。

25、怎么解决 HashMap 线程不安全的问题呢？

1. 可以用 Hashtable 来保证线程安全。Hashtable 在方法上加了 synchronized 关键字。
2. 可以通过 Collections.synchronizedMap 方法返回一个线程安全的 Map，内部是通过 synchronized 对象锁来保证线程安全的，比在方法上直接加 synchronized 关键字更轻量级。
3. 可以使用并发工具包下的 ConcurrentHashMap，使用了CAS + synchronized 关键字来保证线程安全。

26、HashMap 内部节点是有序的吗？

无序的，根据 hash 值随机插入。

27、讲讲 LinkedHashMap 怎么实现有序的？

LinkedHashMap 在 HashMap 的基础上维护了一个双向链表，通过 before 和 after 标识前置节点和后置节点。实现了顺序读写。

28、讲讲 TreeMap 怎么实现有序的？

TreeMap 通过 key 的比较器来决定元素的顺序，如果没有指定比较器，那么 key 必须实现 Comparable 接口。TreeMap 的底层是红黑树，红黑树是一种自平衡的二叉查找树。插入或删除元素时通过旋转和染色来保持树的平衡。查找的时候从根节点开始，利用二叉查找树的特点，逐步向左子树或者右子树递归查找，直到找到目标元素。

29、TreeMap 和 HashMap 的区别？

1. HashMap 是基于数组 + 链表 + 红黑树实现的，put 元素的时候会先计算 key 的哈希值，然后通过哈希值计算出元素在数组中的存放下标，然后将元素插入到指定的位置，如果发生哈希冲突，会使用链表来解决，如果链表长度大于 8，会转换为红黑树。
2. TreeMap 是基于红黑树实现的，put 元素的时候会先判断根节点是否为空，如果为空，直接插入到根节点，如果不为空，会通过 key 的比较器来判断元素应该插入到左子树还是右子树。

在没有哈希冲突的情况下，HashMap 的查找效率是 O(1)。适用于查找操作比较频繁的场景。TreeMap 的查找效率是 O(logn)。并且保证了元素的顺序，因此适用于需要大范围查找或者有序遍历的场景。

30、讲讲 HashSet 的底层实现？

HashSet 的底层实际是一个 HashMap 实例，其中 key 是用户添加的元素（如 String、Integer）。value 是一个固定的静态 Object 类型 PRESENT 对象。HashSet 主要用于去重，HashMap 的 put() 方法会覆盖旧值，但 HashSet 的 add() 方法会返回 false，且集合内容不变。

30.1 HashSet 和 ArrayList 的区别？

1. ArrayList 是基于动态数组实现的，HashSet 是基于 HashMap 实现的。
2. ArrayList 可以有多个相同的元素；HashSet 不允许重复元素，通过 hashCode() 和 equals() 联合判定重复。
3. ArrayList 保持元素的插入顺序，可以通过索引访问元素；HashSet 不保证元素的顺序，元素的存储顺序依赖于哈希算法，并且可能随着元素的增删而改变。

30.2 HashSet 怎么判断元素重复，重复了是否 put ？

判断重复：通过 hashCode() 和 equals() 联合判定。
​重复处理：不覆盖，直接忽略，返回 false。若需要更新元素，需先删除旧元素再添加新元素。