【八股战神篇】Java集合高频面试题

专栏简介

八股战神篇专栏是基于各平台共上千篇面经，上万道面试题，进行综合排序提炼出排序前百的高频面试题，并对这些高频八股进行关联分析，将每个高频面试题可能进行延伸的题目再次进行排序选出高频延伸八股题。面试官都是以点破面从一个面试题不断深入，目的是测试你的理解程度。本专栏将解决你的痛点，助你从容面对。本专栏已更新Java基础高频面试题、Java集合高频面试题，后续会更新JUC、JVM、MySQL、JVM、Redis、操作系统、计算机网络、设计模式、场景题等，计划在七月前更新完毕（赶在大家高频面试前）点此链接订阅专栏“八股战神篇”

一 常见的集合类型有哪些？

Java 集合框架分为单列集合和双列集合两大类。

首先是单列集合，它以 Collection 为核心接口，主要分为三种：

第一种是 List，用于存储有序且可重复的元素，比如 ArrayList 基于动态数组，访问快但插入删除慢；LinkedList 基于双向链表，插入删除快但访问慢；Vector 是线程安全的老版本实现。

第二种是 Set，用于存储无序且不可重复的元素，比如 HashSet 基于哈希表，查找快但无序；LinkedHashSet 保留插入顺序；TreeSet 基于红黑树，按顺序存储。

第三种是 Queue，用于队列操作，比如 PriorityQueue 基于堆实现按优先级处理，ArrayDeque 是双端队列支持栈和队列操作。

接下来是双列集合，它以 Map 为核心接口，用于存储键值对，比如：HashMap 基于哈希表，键无序且查找快；LinkedHashMap 保留插入顺序；TreeMap 基于红黑树，按键的自然顺序排序；Hashtable 是线程安全的老版本实现。

延伸

1，集合体系结构图

为了更好理解，可以参考以下简单的结构：

Collection|-- List|     |-- ArrayList|     |-- LinkedList|-- Set|     |-- HashSet|     |-- TreeSet|-- Queue|-- LinkedList|-- PriorityQueue
Map|-- HashMap|-- TreeMap|-- LinkedHashMap

2，集合的选择

• 如果需要快速查询：使用 HashSet 或 HashMap。

• 如果需要排序：使用 TreeSet 或 TreeMap。

• 如果需要保证插入顺序：使用 LinkedHashSet 或 LinkedHashMap。

• 如果需要动态大小的数组：使用 ArrayList。

• 如果需要频繁插入删除：使用 LinkedList。

3，如果只有单列集合，没有双列集合，会发生什么？

双列集合最核心的特性是以键值对形式存储数据，每个键唯一且对应一个值。如果没有双列集合，会导致：

需要手动管理键值关系： 开发者需要用单列集合（如List）分别存储键和值，自己维护它们的对应关系，增加了开发复杂度。

效率低下： 查找某个键对应的值需要遍历整个键的集合，而不是像Map一样通过哈希或排序快速定位。

二 ArrayList和LinkedList的区别？

ArrayList 和 LinkedList 是 Java 中常用的两个 List 接口实现类。它们在底层数据结构和性能上有很大的区别，各有优缺点，适用于不同的场景。以下是它们详细的区别。

第一点是底层实现不同

ArrayList：基于 动态数组 实现，元素连续存储，支持通过索引直接访问元素（随机访问），数组容量不足时会进行 动态扩容。

LinkedList：基于 双向链表 实现，每个节点包含一个数据部分和两个指针，分别指向前一个和后一个节点，不支持通过索引直接访问，需要通过遍历找到对应位置的元素。

第二点是访问性能不同

ArrayList：随机访问性能优越，时间复杂度为 O(1)，因为可以直接通过索引访问，适合频繁读取元素的场景，例如：根据索引获取数据。

LinkedList：随机访问性能较差，时间复杂度为 O(n)，需要从头或尾部开始遍历才能找到对应的元素，不适合频繁读取或按索引访问元素的场景。

第三点是插入和删除性能不同

ArrayList：插入或删除操作（非尾部）可能涉及大量数据的移动，时间复杂度为 O(n)，删除或插入元素时，所有后续元素都需要移动，尤其是在列表中间插入或删除元素时，在 尾部插入 元素的时间复杂度通常是 O(1)，但当数组容量不足时会触发 扩容，导致性能下降。

LinkedList：插入或删除操作性能更优（非索引访问场景），时间复杂度为 O(1)，只需调整链表指针即可，但如果通过索引访问位置后再插入或删除，则时间复杂度为 O(n)，适合频繁在列表头部或中间插入和删除元素的场景。

第四点是扩容效率的不同

ArrayList：插入时，如果空间不足需要扩容，扩容会新建一个更大的数组，并将旧数据复制过去，影响性能。

LinkedList：没有容量的概念，插入时只需更新节点指针，不涉及扩容操作。

第五点是内存使用效率的不同

ArrayList：内存利用率较高，仅存储实际数据，数组容量不足时会扩容（默认扩容为原容量的 1.5 倍），可能导致一定的内存浪费，扩容操作需要复制整个数组，会消耗时间和内存。

LinkedList：内存开销较大，每个节点需要额外存储两个指针（prev 和 next），不会发生扩容问题，因为它是基于链表实现的，当数据量较大时，链表的额外指针开销可能显著增加内存使用。

第六点是使用场景的不同

场景	选择
需要频繁按索引访问元素	ArrayList
需要频繁在中间或两端插入、删除元素	LinkedList
数据量较大，内存效率要求高	ArrayList
数据量不大，频繁插入删除	LinkedList

代码示例

1. 随机访问性能对比

import java.util.*;
​
public class AccessPerformanceTest {public static void main(String[] args) {List<Integer> arrayList = new ArrayList<>();List<Integer> linkedList = new LinkedList<>();
​// 初始化数据for (int i = 0; i < 100000; i++) {arrayList.add(i);linkedList.add(i);}
​// 测试 ArrayList 的随机访问性能long start = System.nanoTime();arrayList.get(50000);long end = System.nanoTime();System.out.println("ArrayList 随机访问时间: " + (end - start) + " ns");
​// 测试 LinkedList 的随机访问性能start = System.nanoTime();linkedList.get(50000);end = System.nanoTime();System.out.println("LinkedList 随机访问时间: " + (end - start) + " ns");}
}
输出示例：ArrayList 随机访问时间: 100 ns
LinkedList 随机访问时间: 20000 ns

2. 插入和删除性能对比

import java.util.*;
​
public class InsertPerformanceTest {public static void main(String[] args) {List<Integer> arrayList = new ArrayList<>();List<Integer> linkedList = new LinkedList<>();
​// 测试在头部插入性能long start = System.nanoTime();for (int i = 0; i < 10000; i++) {arrayList.add(0, i);}long end = System.nanoTime();System.out.println("ArrayList 头部插入时间: " + (end - start) + " ns");
​start = System.nanoTime();for (int i = 0; i < 10000; i++) {linkedList.add(0, i);}end = System.nanoTime();System.out.println("LinkedList 头部插入时间: " + (end - start) + " ns");}
}
输出示例：ArrayList 头部插入时间: 50000000 ns
LinkedList 头部插入时间: 2000000 ns

延伸

1，说一下ArrayList的默认大小？它是如何进行扩容的？
在 Java 中，ArrayList 的初始默认容量为 10。

当通过无参构造函数创建一个 ArrayList 时：

ArrayList list = new ArrayList<>();
此时 ArrayList 的容量并未真正分配。

当第一次向 ArrayList 添加元素时（如 list.add(1)），它会分配默认大小为 10 的数组。
当 ArrayList 中的元素数量超过当前容量时，ArrayList 会自动扩容。当数组容量不足时，ArrayList 会将容量扩展为 原容量的 1.5 倍，创建一个新的更大的数组。将原数组中的元素拷贝到新数组中。

示例：

新容量计算公式：

newCapacity = oldCapacity + (oldCapacity >> 1);

初始容量为 10，当元素数量超过 10 时：

第一次扩容：容量从 10 扩展为 15。

第二次扩容：容量从 15 扩展为 22。

依此类推。

2，ArrayList是线程安全的吗？为什么？

ArrayList 不是线程安全的。这是因为 ArrayList 的设计目标是为了在单线程环境下提供高性能，而没有对多线程环境提供内置的线程同步机制。

因为 ArrayList 的底层结构是基于动态数组实现的，它的底层是一个 Object[] 数组，用来存储元素。当需要添加、删除或修改元素时，ArrayList 会直接操作这个数组。

• 在单线程环境下，这种设计性能高效。
• 但在多线程环境下，如果多个线程同时操作同一个 ArrayList 实例，可能会引发数据不一致或异常。

3，ArrayList是否有容量限制？

ArrayList 是 Java 中基于动态数组实现的列表。理论上，ArrayList 的容量限制取决于 JVM 所能分配的最大内存，具体限制与可用的堆内存大小和数组的实现有关。

理论限制：

• 最大容量为 Integer.MAX_VALUE - 8（即约 2^31 – 1 个元素，约 2.1 billion 个），这是由数组在 JVM 中的实现所决定的。
• 实际限制：受到可用内存的约束，通常在大量数据时可能会触发 OutOfMemoryError。

三 HashMap的原理是什么？

HashMap 是一种基于哈希表的键值对存储数据结构，它的查找很高效，存储性能较好，被广泛用于高效管理和访问数据。HashMap 的实现基于数组和链表或红黑树，JDK 8之前是数组+链表，JDK 8及之后是数组+链表+红⿊树。接下来我会讲述put方法和get方法的核心逻辑。

put方法：在 HashMap 中，put 方法的核心逻辑是将一个键值对插入到 HashMap 中。其执行流程主要包括以下步骤：

1. 计算键的哈希值 根据 hashCode() 方法计算键的哈希值，然后通过哈希值定位键值对应该存储的桶（bucket）。

2. 定位桶位置 使用哈希值对数组的长度取模，确定键值对存储的位置。

3. 检查冲突（是否有相同哈希值的键）

   • 如果桶为空，直接插入键值对。

   • 如果桶中已有元素（发生哈希冲突），遍历桶中的链表或树结构：

     • 如果找到相同的键（通过 equals 方法判断），则替换旧值为新值。

     • 如果未找到相同的键，则将键值对插入到链表末尾或树中。

4. 树化检查 如果链表长度超过阈值（默认 8），链表会转换为红黑树以提高性能。

5. 扩容检查 如果插入新键值对后，HashMap 的实际元素数量超过了负载因子阈值（loadFactor），会触发扩容（默认将容量翻倍）。

get方法：HashMap 的 get(Object key) 方法用于根据键（key）获取对应的值（value）。其核心逻辑是：

1. 根据键的 hashCode() 计算哈希值，确定该键所在的桶（bucket）。

2. 遍历该桶中的链表（或红黑树）来查找目标键。

3. 如果找到对应的键，返回其对应的值；否则返回 null。

延伸

1，链表到红黑树的转换条件是什么？

默认链表长度超过 8 时转换为红黑树，减少链表查找时间复杂度（从 O(n) 降到 O(log n)）。

2，HashMap为什么采用红黑树而不是采用B+树？

在 HashMap 的实现中，链表长度超过一定阈值（默认 8）时会转换为红黑树，而不是 B+ 树，主要原因如下：

时间复杂度：红黑树是一种平衡二叉搜索树，查找、插入、删除的时间复杂度是 O(log n)。B+ 树虽然在数据库中有优势，但其设计更适合磁盘存储和范围查询，不适合频繁的动态操作。

内存占用：红黑树的内存使用率较低，而 B+ 树由于每个节点存储更多指针，内存开销较大，且不必要。

HashMap 的设计目标：HashMap 的目标是高效查找，而红黑树能很好地满足这一点，并且它与内存结构更契合。B+ 树则更适合大规模外存数据管理。

3，哈希冲突的解决办法有哪些？

拉链法（Chaining）：将所有映射到同一哈希桶中的元素存储为链表（或红黑树）。当冲突较少时，链表的查找复杂度为 O(n)，当链表转为红黑树后复杂度降为 O(log n)。

开放地址法（Open Addressing）：如果一个位置已经被占用，尝试探查其他位置存储冲突的元素。线性探测，依次检查下一个位置。二次探测，按平方步长检查下一个位置。双哈希，使用第二个哈希函数计算探测步长。

再哈希（Rehashing）：当哈希表负载因子过高时，扩容并重新计算所有键的哈希值，减少冲突。

四 HashMap如何扩容？

HashMap 在存储过程中可能会遇到哈希冲突，因此需要使用链表或红黑树来解决这些冲突。然而，随着数据量的增加，冲突可能会加剧，导致访问的时间复杂度无法维持在 O(1) 的水平。此时，就需要进行扩容。扩容的过程包括分配新的数组和重新哈希旧数组中的键值对。

HashMap 扩容主要有下面四个核心步骤：

1. 触发条件 扩容发生在插入新元素时，如果当前元素数量超过了 阈值，则触发扩容。

2. 容量翻倍 扩容时HashMap 会先新建一个数组，新数组的大小是老数组的两倍。

3. 重新哈希（Rehashing） 将旧数组中的键值对重新分配到新数组中，重新计算每个键值对在新数组中的位置。在JDK 1.8 及之后对扩容进行了改进，通过位运算判断新下标位置，而不需要每个节点都重新计算哈希值，提高了效率。

4. 性能影响 扩容是一种代价较高的操作，需要分配新内存并重新计算所有键值对的位置，因此应尽量避免频繁扩容。

延伸

1.为什么采用2倍扩容，而不是1.5倍或者3倍扩容？

HashMap 采用 2 倍扩容，是为了性能优化、空间利用率和实现简单性的综合平衡，避免了 1.5 倍或 3 倍扩容带来的复杂性和资源浪费问题。

（1）保持哈希分布均匀性

HashMap 扩容后需要重新计算键值对的位置。如果新数组大小是 2 的幂，则通过位运算（key.hash & (newCapacity - 1)）来定位数组索引。这种位运算是非常高效的，避免了取模运算（%）的性能开销。如果选择其他扩容倍数（如 1.5 倍或 3 倍），就无法简单通过位运算完成定位，计算索引的效率会降低。

（2）节约内存碎片，防止浪费空间

1.5 倍扩容：扩容后的数组大小无法保证是 2 的幂。这样 HashMap 的存储空间利用率可能下降，影响键值对的哈希分布，增加哈希冲突。

3 倍扩容：虽然可以减少扩容的频率，但扩容时占用内存会瞬间大幅增加，浪费内存空间。尤其在数据量大的情况下，内存分配的压力会显著增加。

（3）减少扩容频率与内存占用的平衡

扩容过小（如 1.5 倍）会导致频繁扩容，而扩容过大（如 3 倍）会导致一次性占用过多内存。2 倍扩容在扩容频率和扩容成本之间取得了一个平衡：扩容后内存增长速度适中，只需重新分配内存并搬移数据，避免了频繁扩容的性能开销。

（4） 兼容性与实现简单性

Java 中 HashMap 的容量始终是 2 的幂次方。2 倍扩容后，容量仍然是 2 的幂，哈希计算和分布规则无需额外调整。如果使用 1.5 倍或 3 倍扩容，则数组长度不再是 2 的幂，导致实现变得复杂。比如，哈希计算的规则需要调整，哈希分布也可能变得不均匀。

五 Java 8中，HashMap有哪些重要的改进？

在 Java 8 中，HashMap 的实现进行了重要的优化，主要集中在性能提升和处理哈希冲突的改进。以下是关键的改进点：

1，数据结构的改进

在 JDK 1.7 及之前，HashMap 的数据结构是“数组+链表”。当发生哈希冲突时，多个键值对以链表形式存储在同一个“桶”中。 在 JDK 1.8 中，引入了红黑树优化。当链表长度超过 8 时，会自动转换为红黑树，这将时间复杂度从 O(n) 降低到 O(logN)，大幅提高查找效率。

2，哈希算法的改进

在JDK 1.7时直接使用 hashCode 的低位进行哈希运算，这样当 table 长度较小时，高位没有参与计算，导致哈希分布不均。Java 8 使用了一种新的哈希函数实现（基于 MurmurHash 的思想），以减少哈希冲突的概率。这个优化使键的分布更加均匀，即使是质量较差的哈希码也能避免集中到某些桶中。

3，扩容位置改进

在 Java 7 中，扩容时需要重新计算每个元素的哈希值。 在 Java 8 中，扩容优化为利用位运算快速判断新位置：每个元素的哈希值只需要检查高位变化即可决定分配到新桶或保留在原桶中。例如，当容量从 16 扩展到 32 时，桶的数量翻倍，每个元素的位置只需要通过 (hash & (newCapacity - 1)) 判断是否需要迁移。这种优化减少了扩容时的计算开销。

4，扩容触发机制改进

在JDK 1.7中扩容是“先扩容后插入”，无论是否发生哈希冲突，都会执行扩容操作，可能导致无效扩容。在JDK 1.8中扩容变为“先插入再扩容”，仅在插入后元素总量超过阈值，或某条链表因哈希冲突长度超过 8 且当前数组容量未达到 64 时，才会触发扩容，减少了不必要的操作。

延伸

1，改进的哈希算法详解

在 Java 8 中，HashMap 的哈希函数对键的哈希码做了更多处理，以减少冲突。它通过高位和低位的混合（h ^ (h >>> 16)）来避免低质量的哈希函数导致的冲突。

示例：

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这种设计使得高位和低位都能参与哈希桶的定位，减少了哈希冲突的概率，尤其是对于哈希值分布不均的键。

2，与 Java 7 HashMap 的对比

特性	Java 7	Java 8
冲突处理	链表	链表 + 红黑树
时间复杂度（最坏情况）	O(n)	O(log n)（链表转红黑树后）
哈希算法	哈希码简单混合	哈希码高位与低位的混合
扩容机制	重新计算哈希值	基于高位判断新桶位置

示例对比

Java 7 性能退化示例：

import java.util.HashMap;
​
public class HashMapTest {public static void main(String[] args) {HashMap<Integer, String> map = new HashMap<>();for (int i = 0; i < 1000; i++) {map.put(i * 16, "value" + i); // 强制让哈希冲突}System.out.println(map); // 性能会退化为 O(n)}
}

Java 8 的改进： 在相同情况下，Java 8 中链表会转化为红黑树，从而避免退化问题。

3，HashMap能不能无限扩容？

HashMap 的扩容最终受限于 JVM 所能提供的内存。当 HashMap 的容量增长到超过 JVM 可用的堆内存大小时，扩容操作将无法成功，可能会导致 OutOfMemoryError。适用于中小规模的数据存储，实际开发中，由于 HashMap 的扩容和 rehashing 都是相对昂贵的操作，大量的元素插入可能会导致系统性能的显著下降。

4，树化后删除元素能不能回退成链表？

当红黑树中的元素数量减少到 6 时，HashMap 会将红黑树退化回链表，红黑树的结构维护成本较高，涉及复杂的旋转和调整操作。如果元素数量较少，链表反而更加高效。

六 HashMap是否是线程安全的？

HashMap 是非线程安全的。HashMap 是 Java 中的一个常用集合类，用于存储键值对。由于它在设计时没有考虑线程安全问题，所以在多线程环境中，多个线程同时对 HashMap 进行读写操作可能导致数据不一致、死循环等问题。

延伸

1. 为什么 HashMap 不是线程安全的

HashMap 的非线程安全性主要体现在以下几个方面：

1. 并发修改导致数据不一致：

   • 多个线程同时对 HashMap 进行修改（如 put()、remove() 等），可能导致数据被覆盖或丢失，最终状态不可预测。

   • 示例问题：线程 A 和线程 B 同时向 HashMap 中插入数据，线程 A 可能会覆盖线程 B 的修改，导致丢失线程 B 的数据。

2. 扩容操作的线程安全问题：

   • 当 HashMap 的容量达到阈值时，会触发扩容（rehash），即将元素重新分布到新的数组中。

   • 如果在多线程环境中发生扩容操作，可能导致死循环或数据丢失。

   • 原因：扩容过程中，HashMap 会通过链表的遍历重新分配元素。如果多个线程同时执行扩容操作，链表的结构可能被破坏，导致循环引用。

3. 无同步机制：

   • HashMap 的方法（如 put()、get() 等）没有任何同步措施，不会主动加锁，因此多个线程同时访问共享的 HashMap 会导致线程安全问题。

2.如何使HashMap变得线程安全？

HashMap 本身不是线程安全的，如果在多线程环境下使用可能会出现数据不一致、死循环等问题。要使 HashMap 线程安全，可以采用以下几种方法：

1. 使用 Collections.synchronizedMap

• 将HashMap包装成线程安全的同步Map。

• 示例代码：

  Map<String, String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

• 这种方式会为所有操作加锁，适合简单的多线程访问，但性能较低。

2.使用 ConcurrentHashMap

• ConcurrentHashMap 是 Java 提供的线程安全实现，采用分段锁机制（Java 8 后基于 CAS 和分段锁结合）。

• 示例代码：

  Map<String, String> concurrentMap = new ConcurrentHashMap<>();

• ConcurrentHashMap 提供更高的并发性能，是线程安全的推荐选择。

3.手动加锁

• 可以使用 synchronized 或 ReentrantLock 在关键代码块上加锁。

• 示例代码：

  Map<String, String> map = new HashMap<>();
  synchronized (map) {
  map.put("key", "value");
  }

• 这种方式适合特定场景，但需要自行管理锁，代码复杂且容易出错。