---

---

Java集合

前言

已经找到工作了，分享秋招时的笔记。祝大家都能顺利找到自己心仪的工作。

---

面试题

Java 集合？

• 集合框架主要有两大接口：Collection 接口、Map 接口
• Collection 接口用于存储一组对象，Map 接口用于存储键值对
• Collection 接口有三个主要子接口：List Set Queue

说说 List、Set、Queue、Map 四者的区别？

• List: 有序集合，允许重复存储元素
• Set：无序集合，元素不可以重复
• Queue：队列集合，按照先入先出的顺序操作元素，元素有序可重复
• Map：键值对集合，存储不重复的键值对

集合框架底层数据结构总结？

• ArrayList：数组
• LinkedList：双向链表
• Hashset：哈希表
• HashMap：哈希表
• TreeSet：红黑树
• TreeMap：红黑树
• PriorityQueue：堆
• ConcurrentHashMap：分段锁的哈希表

ArrayList 和 Vector 的区别?

• ArrayList 是 List 的主要实现类，使用于频繁查找的工作，线程不安全
• Vector 是 List 的古老实现，是线程安全的，在每个方法调用都进行同步，有很大的性能损失，推荐使用并发包的 CopyOnWriteArrayList，在副本修改，不会有并发问题

ArrayList 与 LinkedList 区别?

• 数据结构不同：
  ArrayList 基于数组实现，LinkedList 基于双向链表实现
• 功能上：
  ArrayList 适合查找，LinkedList 适合增删
• 是否支持随机访问：
  ArrayList 支持随机访问；LinkedList 不支持随机访问
• 内存占用：
  ArraryList 占用连续的内存空间；LinkedList 内存空间不连续

ArrayList 核心扩容机制？

1. 向 ArrayList 添加元素时，元素数量等于容量，会触发扩容操作
2. 扩容后的新容量大小一般为原容量大小的 1.5 倍
3. 如果计算的新容量小于所需的容量。就会直接使用最小容量来扩容
4. 确定好新的容量大小后，会创建一个新的数组，将原有元素复制到新数组中，同时释放原数组的空间

ArrayList 怎么序列化的知道吗？

• ArrayList 使用自定义的序列化机制，数组使用 transient 修饰，在序列化的时候只序列化实际存储的元素，而不是整个数组

为什么 ArrayList 用 transient 修饰数组？

• 当对象序列化时，Java 会默认将对象所有字段都进行序列化
• transient 关键字修饰数组就是告诉 Java 序列化机制不要对数组进行默认的序列化
• 数组的长度可能远大于当前实际存储的元素数量，序列化整个数组会占用大量的空间和时间

快速失败和安全失败了解吗？

• 快速失败：
  一种错误检测机制，用于在多线程环境下，当多个线程同时修改同一个集合时，能够抛出异常

• 安全失败：
  一种容错机制，在迭代操作时不会直接在原集合上操作，而是在原集合的副本上进行遍历操作，用于在遍历集合的同时，不会因为集合的修改而异常

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

• 使用 Vector 代替 ArrayList
• 使用 Collection.synchronizedList() 方法
• 使用 Reentrantlock 实现同步
• 使用 CopyOnWriteArrayList

CopyOnWriteArrayList 了解多少？

• CopyOnwriteArrayList 是 Java 并发包中提供的一个线程安全的集合类
• 实现 List 接口
• 通过在写操作时创建一个新的数组来实现线程安全。读操作不需要加锁，所以适用于读多写少的场景。

Comparable 和 Comparator 的区别？

• Comparable 接口：是类内部的接口，用于定义对象自身的默认排序方式
  通过类实现 Comparable 接口的 compareTo() 方法，可以实现排序
• Comparator 接口：是比较器接口，可以在类外部定义多种不同的排序方式
  通过实现 Comparator 接口，可以创建不同的比较规则，而不需要修改原始类的代码

无序性和不可重复性的含义是什么？

• 无序性：元素没有明确的顺序关系，不一定按照特定的顺序存储或返回
• 不可重复性：集合中的元素是不重复的

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同？

HashSet:

• 底层数据结构：哈希表
• 无序性
• 不可重复性
• 查找效率：平均查找时间复杂度是 O(1)
• 适用场景：适用于快速查找无序元素的情况

LinkedHashSet:

• 底层数据结构：哈希表 + 链表
• 有序性：元素按照插入顺序存储
• 不可重复性
• 查找效率：平均查找时间复杂度是 O(1)
• 适用场景：适用于保持插入顺序且不允许重复元素的情况

TreeSet:

• 底层数据结构：红黑树
• 有序性：元素按照自然顺序存储
• 不可重复性
• 查找效率：平均查找时间复杂度是 O(logN)
• 适用场景：适用于有序且不重复的元素的情况

Queue 与 Deque 的区别？

• Queue：单端队列，元素按照先进先出的顺序排序
• Deque：双端队列，在队列的两端都可以插入删除元素

ArrayDeque 与 LinkedList 的区别？

• 底层实现不同：ArrayDeque 是双端队列，底层实现是循环数组，LinkedList 是双向链表
• 随机访问：ArrayDeque 支持随机访问，LinkedList 不支持随机访问
• 使用场景：
  如果在双端进行频繁的插入和删除操作，通常选择 ArrayDeque
  如果在中间进行插入和删除操作，通常选择 LinkedList

说一说 PriorityQueue？

• PriorityQueue 是 Java 集合中的类，用于实现优先队列，基于二叉堆实现
• PriorityQueue 内部使用可变长数组来存储数据，通过堆的上浮和下沉操作，保证堆的特性
• 插入和删除堆顶元素的时间复杂度是 O(logn)
• PriorityQueue 默认是小顶堆，可以通过自定义的比较器创建大顶堆

HashMap

讲讲 HashMap？

• HashMap 是 Java 集合中的类，是键值对存储的数据结构，基于哈希表实现
• 允许存储任意类型的键值对，其中键唯一，值可以重复
• HashMap 内部使用哈希函数将键映射到桶，每个桶存储了一组键值对
• HashMap 是非线程安全的，多线程中，通常使用 ConcurrentHashMap

HashMap 底层数据结构？

• 在 JDK7 中，HashMap 使用的是数组 + 链表的数据结构来存储键值对。具体来说，数组的每个元素是一个链表，用于存储具有相同哈希值的键值对
• 在 JDK8 中，HashMap 对于链表长度过长的情况（默认超过 8 个元素）会将链表转换为红黑树，从而提高查询效率

你对红黑树了解多少？为什么不用二叉树/平衡树呢？

• 红黑树是自平衡的二叉查找树，在每个节点增加额外的颜色信息来满足平衡性质，插入、删除、查找的时间复杂度是 O(logn)
• 平衡二叉树是比红黑树更严格的平衡树，为了保持平衡，需要旋转的次数更多，保持平衡的效率比红黑树低

红黑树怎么保持平衡的知道吗？

• 节点颜色：每个节点都被标记为红色或者黑色
• 根节点：根节点是黑色的
• 叶节点：每个叶节点都是黑色的
• 红色子节点：如果一个节点是红色的，则其子节点必须是黑色的
• 黑色高度：任意节点到子树的每个叶子节点的路径，必须包含相同数量的黑色节点

HashMap 的 put 流程知道吗？

1. 计算存储位置：HashMap 会根据键的 hashcode 值计算出键值对对应的存储位置
2. 检查存储位置：如果该位置没有元素，则直接将键值对存储在该位置
3. 位置已经有元素：如果该位置已经存在其他键值对，需要进行更多操作：
   • 键存在：使用 hashcode 值和 equals() 方法判断该键是否存在，如果存在，则替换原有值
   • 键不存在：将新的键值对添加到链表或红黑树中
   • 链表转换为红黑树：当链表的长度超过 8 个节点时，HashMap 会将该链表转换为红黑树
4. 扩容：当存储键值对的数量超过容量的 0.75 倍时，HashMap 会进行扩容操作

HashMap 怎么查找元素的呢？

1. 使用扰动函数获取新的哈希值
2. 计算数组下标，获取节点
3. 如果当前节点和 key 匹配，直接返回该节点的 value 值，查找完成
4. 如果当前节点是树节点，则在红黑树中查找 key 值
5. 如果不是树节点，遍历链表查找
6. 如果遍历完链表或红黑树仍然没找到 key 值，返回 null。

HashMap 的哈希/扰动函数是怎么设计的?

• HashMap 将 key 的 hashCode 右移 16 位，然后将结果和原 hashCode 进行异或操作

为什么哈希/扰动函数能降 hash 碰撞？

• 通过哈希函数的设计，使相同哈希值的键值对能够分散到不同的桶中

为什么 HashMap 的容量是 2 的倍数呢？

• 容量为 2 的倍数，可以使用位运算，哈希计算的效率更高
• 容量为 2 的倍数可以保证元素在哈希表中均匀分布，减少哈希碰撞

如果初始化 HashMap，传一个 17 的值 new HashMap<>，它会怎么处理？

hashMap 会向上寻找离最近的 2 的倍数，即 32，作为 HashMap 的实际容量

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

• 直接定址法：直接根据 key 值映射到数组的位置
• 数字分析法：取 key 的某些位置作为映射的位置
• 平方取中法：取 key 平方的中间几位作为映射的位置

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

• 链地址法：(HashMap) 在冲突的位置上设置链表，把冲突的元素放进去
• 开放定址法：从冲突的位置往下找，直到找到空位
• 公共溢出区法：在哈希表中建立一个公共溢出区，将冲突元素放进去

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

• 根据统计学，链表长度为 8 时，将链表转换为红黑树的效率值最大
• 选择 6 是为了避免频繁的链表和红黑树之间的转换

扩容在什么时候呢？为什么扩容因子是 0.75？

• 扩容通常发生在数据结构的存储空间快要到达容量上限的时候进行
• 扩容因子一般是 0.75，主要是考虑时间和空间的平衡性，是一个经验值

HashMap 扩容机制了解吗？

1. 触发扩容机制：当 HashMap 中的元素超过负载因子和数组长度乘积时，触发扩容操作
2. 创建新数组：需要扩容时会创建新的数组，长度为原来的2 倍
3. 移动元素：HashMap 会重新计算原数组元素的哈希值，然后将原数组中的所有元素移动到新数组中对应的位置
   JDK1.8 进行优化，不需要重新计算每个元素的哈希值，元素的位置只可能在原位置，或者原位置向右移动 2 的次幂

JDK1.8 对 HashMap 主要做了哪些优化呢？为什么？

• 数据结构变化：数组 + 链表变成数组 + 链表 + 红黑树
  在链表过长时转为红黑树，将时间复杂度从 O(n) 降为 O(logn)
• 链表插入方式变化：链表的插入方式从头插法改成了尾插法
  头插法扩容时，会使链表发生反转，多线程环境下会产生环
• 扩容后数组位置优化：1.7 需要对原数组的元素重新计算哈希值，1.8 进行优化，元素位置不变或者移动 2 的次幂，提高扩容的效率

HashMap 是线程安全的吗？多线程下会有什么问题？

• HashMap 不是线程安全的
• 多线程的问题：
  • 扩容死循环：JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容可能导致环形链表
  • 元素丢失：多线程的 put 会导致元素的丢失，当计算的索引位置相同，新的 key 值会覆盖之前存储的值
  • 并发的 put 和 get：线程的 put 和 get 并发时，可能会导致 get 操作读取的值为过时的数据或者空值

有什么办法能解决 HashMap 线程不安全的问题呢？

1. 使用 ConcurrentHashMap
   在内部使用了分段锁来对不同的部分进行并发控制，从而允许多个线程同时进行读取和写入操作，而不需要全局锁定整个数据结构
2. 使用 Collections.synchronizedMap 方法
   将普通的 HashMap 包装成线程安全的 Map

HashMap 和 Hashtable 的区别？

• 线程安全：Hashtable 是线程安全的，HashMap 不是线程安全的
• 允许空键值：HashTable 不允许键值为 null，而 HashMap 允许键值为 null
• 性能：Hashtable 是线程安全的，需要进行线程同步，所以在高并发的环境中，Hashtable 的性能相对较差
• 底层数据结构：HashTable 的底层数据结构是数组和链表，而 HashMap 在 JDK1.8 以后为数据 + 链表 + 红黑树

HashMap 和 HashSet 区别？

• 底层实现：HashSet 底层实现是基于 HashMap 实现的
• 接口实现：HashMap 实现 Map 接口，HashSet 实现 Set 接口
• 元素存储：HashMap 存储键值对，其中 key 值唯一，value 值可以重复；HashSet 用来存储唯一元素，重复的元素会自动去重
• 元素添加：HashMap 调用 put() 方法向 map 中添加元素，HashSet 调用 add() 方法向 Set 添加元素

HashMap 和 TreeMap 区别？

• 底层实现：HashMap 基于哈希表实现，TreeMap 基于红黑树实现
• 存储顺序：HashMap 不保证存储顺序，TreeMap 可以保证存储顺序，
• 时间复杂度：HashMap 的查找的平均时间复杂度是 O(1)，TreeMap 的时间复杂度为 O(logn)
• 空间复杂度：TreeMap 需要额外的空间存储红黑树结构，具有更高的空间复杂度

HashMap 有哪几种常见的遍历方式?

• 迭代器遍历：使用 Iterator 遍历 HashMap，获取键和值

Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, String> entry = iterator.next();
    Integer key = entry.getKey();
    String value = entry.getValue();
    // 处理 key 和 value
}

• foreach 遍历：遍历键的集合

for (Integer key : map.keySet()) {
    String value = map.get(key);
    // 处理 key 和 value
}

• keySet 遍历：通过 keySet() 方法获取 HashMap 的键集合，然后通过 get() 方法获取对应的值

for (Integer key : map.keySet()) {
    String value = map.get(key);
    // 处理 key 和 value
}

HashSet 如何检查重复?

• 比较对象 hashcode 值：检查是否有其他元素具有相同的 hashcode 值
  • 如果没有相同的 hashcode 值，HashSet 会假设元素没有重复出现
  • 如果有相同的 hashcode 值，会调用 equals() 方法比较，如果返回 true，HashSet 会认为元素重复

HashMap 多线程操作导致死循环问题？

• JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容可能导致环形链表

HashMap 内部节点是有序的吗？

• 不是有序的，元素的存储顺序是根据哈希值决定的，而不是插入的顺序
• 如果想使用有序的 Map，可以使用 LinkedHashMap 或者 TreeMap

讲讲 LinkedHashMap 怎么实现有序的？

• LinkedHashMap 内部维护一个双向链表，有头尾节点

讲讲 TreeMap 怎么实现有序的？

• TreeMap 的底层数据结构是红黑树
• 红黑树是一种自平衡的二叉查找树，通过旋转和改变节点颜色来保持树的平衡
• TreeMap 内部基于红黑树的自平衡性保证了其中元素的有序性

JDK1.7 和 JDK1.8 的 ConcurrentHashMap 的底层具体实现？

JDK1.7：

• JDK1.7 的 ConcurrentHashMap 使用分段锁技术，将整个 HashMap 分成若干个段，并为每个段分配一个独立的锁

JDK1.8：

• JDK1.8 的 ConcurrentHashMap 使用 CAS 和 synchronized 块实现线程安全，避免了锁的竞争，提高了并发的性能
• JDK1.8 的 ConcurrentHashMap 使用链表和红黑树的结构来存储哈希碰撞的元素，提高了查找性能

ConcurrentHashMap 和 Hashtable 的区别？

• 底层数据结构：
  • JDK1.7 的 ConcurrentHashMap 底层使用分段的数组 + 链表实现
  • JDK1.8 的 ConcurrentHashMap 底层使用数组 + 链表 + 红黑树实现
  • Hashtable 使用数组 + 链表
• 实现线程的方式
  • HashTable 使用 sychronized 来保证线程安全，效率偏低
  • JDK1.7 的 ConcurrentHashMap 使用分段锁技术，将整个 HashMap 分成若干个段，并为每个段分配一个独立的锁
  • JDK1.8 的 ConcurrentHashMap 使用 CAS 和 synchronized 技术保证线程安全，避免了锁的竞争，提高了并发的性能

秋招后端开发面试题系列目录
一、Java
1.1 Java基础上
1.2 Java基础下
1.3 Java集合
1.4 JavaIO
1.5 Java多线程上
1.6Java多线程下
二、JVM
2.1 JVM底层原理
2.2 垃圾回收器
2.3 垃圾回收算法
2.4 类加载机制
2.5 运行时数据区
三、MySQL
3.1 MySQL基础
3.2 事务
3.3 索引
3.4 锁机制
3.5 MVCC
四、Redis
4.1 Redis基础
4.2 缓存原理
五、中间件
5.1 RabbitMQ
六、Spring开源框架
6.1 Spring
6.2 Spring MVC
6.3 Spring Boot
6.4 MyBatis
七、操作系统
八、计算机网络
九、设计模式
十、微服务架构
十一、Spring Cloud分布式
11.1 分布式基础
11.2 Spring Cloud
11.3 GateWay
11.4 Nacos
11.5 OpenFeign
11.6 Ribbon
十二、算法
十三、项目