面试八股文-java常见集合篇-EW帮帮网

一.能谈谈你对ArrayList的理解吗？

1. 底层数据结构

ArrayList 底层是通过 Object[] 动态数组 来存储元素的。
由于数组是连续存储的，所以 ArrayList 支持 随机访问（通过索引查找元素），时间复杂度是 O(1)。

2. 初始化

ArrayList 默认构造方法并不会立刻创建数组，而是初始化一个 空数组（长度为0）。
当第一次添加元素时，会分配一个 默认容量为 10 的数组。

源码片段（JDK 8）：

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

3. 扩容机制

当数组空间不足时，ArrayList 会进行扩容：
- 扩容大小 = 原来容量的 1.5 倍（即 newCapacity = oldCapacity + (oldCapacity >> 1)）。
- 扩容时会调用 Arrays.copyOf()，将旧数组元素复制到新数组中。
扩容代价较高，因为需要 拷贝所有元素。

4. 元素的添加

在末尾添加元素：O(1)（摊销后，偶尔需要扩容 O(n)）。
在指定位置插入元素：O(n)，因为需要将插入点后的元素整体向后移动。

5. 元素的删除

按索引删除：需要把删除点后的元素整体向前移动，时间复杂度 O(n)。
按值删除：需要先查找（O(n)），再移动元素（O(n)）。
但删除最后一个元素是 O(1) 的。

6. 线程安全性

ArrayList 不是线程安全的。
多线程环境下建议使用：
- Collections.synchronizedList(new ArrayList<>())
- 或者使用 CopyOnWriteArrayList。

二.如何实现数组和List之间的转换？

在 Java 里，数组和 List 之间的转换是非常常见的操作，主要有以下几种方式👇

1. 数组 → List

(1) 使用 `Arrays.asList()`

String[] array = {"A", "B", "C"};
List<String> list = Arrays.asList(array);

特点：返回的 list 是 定长的，不能增删，只能改值（会直接修改原数组），修改原来的数组数据会直接影响到列表数据，二者是相互绑定的。

(2) 使用 `new ArrayList<>(Arrays.asList())`

String[] array = {"A", "B", "C"};
List<String> list = new ArrayList<>(Arrays.asList(array));

特点：得到的 ArrayList 是可变的，支持增删改查，因为是新new出来的对象，所以修改不会影响到原来数组。

(3) 使用 `Collections.addAll()`

String[] array = {"A", "B", "C"};
List<String> list = new ArrayList<>();
Collections.addAll(list, array);

特点：性能优于 Arrays.asList()，推荐。

(4) Java 8 Stream

String[] array = {"A", "B", "C"};
List<String> list = Arrays.stream(array).collect(Collectors.toList());

特点：灵活，可以加过滤、映射等操作。

2. List → 数组

(1) 使用 `toArray()`

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");

// 转换成 Object[]
Object[] array1 = list.toArray();

// 转换成指定类型的数组
String[] array2 = list.toArray(new String[0]);

推荐写法：new String[0]，JVM 会自动优化为合适大小。

(2) Java 8 Stream

List<String> list = Arrays.asList("A", "B", "C");
String[] array = list.stream().toArray(String[]::new);

更简洁，特别适合需要操作后再转数组的场景。

二.ArrayList和LinkedList的区别是什么？

特性	ArrayList	LinkedList
底层结构	动态数组	双向链表
内存占用	少（连续存储）	大（节点+指针开销）
随机访问	O(1)	O(n)
插入/删除（中间）	O(n)	O(1)（已知节点引用时）
插入/删除（尾部）	O(1)（摊销）	O(1)
扩容机制	需要，1.5倍扩容	不需要
适合场景	读多写少，随机访问多	写多读少，频繁插入/删除

三.红黑树的性质有什么?

红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在插入和删除时通过颜色标记和旋转保持平衡，保证了最坏情况下的时间复杂度为 O(log n)。

红黑树有 5 大性质：

🌳 红黑树的性质

每个节点要么是红色，要么是黑色。
根节点是黑色。
所有叶子节点（NIL 空节点）都是黑色。

这里的叶子节点指的是树中的 NIL 空节点，不是普通数据节点。
红色节点的子节点必须是黑色。

即：不能有两个连续的红色节点（不允许出现 “红红相连”）。
从任一节点到其所有后代叶子节点的路径上，黑色节点数必须相同。

这个黑色节点数称为 黑高（black-height）。

四.红黑树的增删查复杂度是什么?

红黑树作为一种 自平衡二叉查找树，核心目标就是保证操作的时间复杂度稳定在 O(log n)。我们分三类操作来看：

🔍 1. 查找（Search）

和普通二叉搜索树一样，查找只需比较左右子树。
树的高度最多是 2 * log2(n+1)，因此查找复杂度：
O(log n)

➕ 2. 插入（Insert）

按照二叉搜索树的规则找到插入位置，先插入为 红色节点。
如果违反了红黑树性质（比如出现了两个连续的红色节点），则需要旋转（左旋 / 右旋）+ 颜色变换 来修复。
修复操作最多需要 2 次旋转 和 若干次颜色变换。

👉 插入的复杂度：O(log n)（查找位置 O(log n) + 调整 O(1)）。

➖ 3. 删除（Delete）

按照二叉搜索树的规则删除节点（可能需要找前驱/后继替换）。
如果删除的是 黑色节点，可能会破坏红黑树的平衡性，这时需要 旋转 + 颜色调整 来修复。
修复的次数依然是 常数次（≤ 3 次旋转）。

👉 删除的复杂度：O(log n)（查找待删节点 O(log n) + 调整 O(1)）。

📊 总结表

操作	红黑树复杂度	说明
查找	O(log n)	树高 ≤ 2log(n+1)
插入	O(log n)	最多 2 次旋转，若干次染色
删除	O(log n)	最多 3 次旋转，若干次染色

五.什么是散列表，什么是哈希冲突，什么是链表法处理hash冲突?

1. 散列表（Hash Table）

定义：散列表是一种根据 关键码（Key） 直接访问数据的存储结构。
核心思想：通过 哈希函数（Hash Function） 把 Key 映射到数组下标，然后在该位置存储对应的 Value。
优势：查找、插入、删除的平均时间复杂度都可以做到 O(1)。

👉 举例：

Key: "Tom" → Hash 函数 → 位置 5
Key: "Jerry" → Hash 函数 → 位置 2

2. 哈希冲突（Hash Collision）

定义：不同的 Key，经过哈希函数计算后，可能得到 相同的数组下标，这种情况就是 哈希冲突。
原因：数组长度有限，而 Key 可能无限 → 鸽巢原理，必然会有冲突。

👉 举例：

Key1 = "abc" → Hash = 5
Key2 = "xyz" → Hash = 5

两者都映射到位置 5，就发生了冲突。

3. 链表法（Separate Chaining）

定义：链表法是一种常见的解决哈希冲突的办法，也叫 拉链法。
做法：当多个元素冲突到同一个位置时，在该数组槽（bucket）上维护一个 链表（或红黑树，JDK 1.8+ 优化） 来存储这些元素。
特点：
- 插入新元素 → 直接挂到对应槽的链表上。
- 查找元素 → 先通过哈希函数找到槽，再遍历链表查找。

👉 举例：

数组下标 5:
   [Key1: abc, Value1] → [Key2: xyz, Value2] → [Key3: pqr, Value3]

4. 总结

散列表：用哈希函数把 Key 映射到数组位置，实现快速访问。
哈希冲突：不同的 Key 可能映射到同一个数组下标。
链表法：在冲突位置使用链表（或树）存储多个元素，解决冲突问题。

六.HashMap的put方法的具体流程

在这里插入图片描述

具体流程

在这里插入图片描述

七.HashMap的扩容机制是什么？

在这里插入图片描述

具体流程

在这里插入图片描述

八.HashMap的寻址算法是什么，为什么HashMap数组长度一定为2的次幂?

1. HashMap 的寻址算法

HashMap 底层是一个数组，存储元素的位置需要通过 哈希值计算索引。
寻址算法是：

index = (n - 1) & hash

hash = key 的 hashCode 经过扰动函数处理后的值
n = 数组长度（table.length）
& 位运算，比取模 % 更快

👉 举例：

n = 16 (10000b)
hash = 59 (111011b)
index = (16 - 1) & 59 = 15 & 59 = 11

这样就能快速定位到数组下标 11。

2. 为什么数组长度必须是 2 的次幂？

(1) 高效寻址

如果数组长度是 2 的次幂，比如 16（10000b），那么 n-1 = 15 (01111b)，
这样 (n - 1) & hash 的效果就是 取 hash 的低几位。
取低位比取模运算 % 高效很多。

(2) 保证散列均匀

如果长度不是 2 的次幂，比如 n = 10：

n-1 = 9 (1001b)，只保留了低几位，导致 hash 分布不均匀，冲突严重。

👉 举个例子：

n = 16 → (n-1)&hash 等价于对 16 取模，均匀分布在 0~15
n = 10 → (n-1)&hash = 9 (1001b)，只能保留第 1 和第 4 位，结果分布不均，容易集中在少数槽位

(3) 扩容时元素迁移高效

扩容后数组长度翻倍，例如从 16 → 32。
那么 (n-1)&hash 的结果要么在原位置，要么在原位置 + n。
因此扩容迁移时，只需要判断 hash 的新增高位 是 0 还是 1，而不用重新计算 hash。
- 高位 = 0 → 索引不变
- 高位 = 1 → 新索引 = 旧索引 + n

九.hashmap在1.7情况下的多线程死循环问题是什么?

参考回答

在这里插入图片描述

面试八股文-java常见集合篇

一.能谈谈你对ArrayList的理解吗？

1. 底层数据结构

2. 初始化

3. 扩容机制

4. 元素的添加

5. 元素的删除

6. 线程安全性

二.如何实现数组和List之间的转换？

1. 数组 → List

(1) 使用 Arrays.asList()

(2) 使用 new ArrayList<>(Arrays.asList())

(3) 使用 Collections.addAll()

(4) Java 8 Stream

2. List → 数组

(1) 使用 toArray()

(2) Java 8 Stream

二.ArrayList和LinkedList的区别是什么？

三.红黑树的性质有什么?

🌳 红黑树的性质

四.红黑树的增删查复杂度是什么?

🔍 1. 查找（Search）

➕ 2. 插入（Insert）

➖ 3. 删除（Delete）

📊 总结表

五.什么是散列表，什么是哈希冲突，什么是链表法处理hash冲突?

1. 散列表（Hash Table）

2. 哈希冲突（Hash Collision）

3. 链表法（Separate Chaining）

4. 总结

六.HashMap的put方法的具体流程

具体流程

七.HashMap的扩容机制是什么？

具体流程

八.HashMap的寻址算法是什么，为什么HashMap数组长度一定为2的次幂?

1. HashMap 的寻址算法

2. 为什么数组长度必须是 2 的次幂？

(1) 高效寻址

(2) 保证散列均匀

(3) 扩容时元素迁移高效

九.hashmap在1.7情况下的多线程死循环问题是什么?

参考回答

网站公告

今日签到

热门文章

最新发布

(1) 使用 `Arrays.asList()`

(2) 使用 `new ArrayList<>(Arrays.asList())`

(3) 使用 `Collections.addAll()`

(1) 使用 `toArray()`