八股-Java 基础
Java 基础相关面试题
======= Java 集合 =======
ArrayList 源码
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
@java.io.Serial
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认的初始容量。
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默认容量的空实例的共享空数组实例。
* 我们将其与 EMPTY_ELEMENTDATA 区分开来，
* 以便在添加第一个元素时知道要扩容多少。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 用于存储 ArrayList 元素的数组缓冲区。
* ArrayList 的容量就是这个数组缓冲区的长度。
* 任何 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList，
* 在添加第一个元素时都会扩容到 DEFAULT_CAPACITY。
*/
transient Object[] elementData; // 非 private 以简化嵌套类的访问
/**
* ArrayList 的大小（包含的元素数量）。
*
* @serial
*/
private int size;
}
📒 transient
transient 是 Java 中的一个 关键字，用于标记 不希望被序列化的字段
🧠 什么是序列化？
序列化（Serialization）是指将对象的状态转换为字节流，以便：
- 保存到磁盘
- 通过网络传输
反序列化（Deserialization）是指从字节流中恢复出对象
Java 中支持序列化的类通常实现 java.io.Serializable 接口
🧩 transient 是干什么的？
当一个字段被标记为 transient，在序列化时，它的值不会被保存
也就是说，它不会被写入字节流中，在反序列化时这个字段会变成默认值（如 null 或 0）
✅ 示例：
class User implements Serializable { private String username; private transient String password; // 不想被序列化 // 构造函数 + getter/setter }当你把 User 实例序列化时：
- username 会被写入
- password 不会被写入（反序列化后它是 null）
🧠 为什么使用 transient ？
常见原因如下：
场景 原因 安全性 不希望将敏感信息（如密码、身份证号）序列化保存 无意义 字段是临时用的，序列化后也没用（如缓存数据、连接池、日志等） 不可序列化 字段类型本身不可序列化，比如Thread,Socket,InputStream等 性能优化 避免序列化体积变大 🔎 ArrayList 中的 transient Object[] elementData
transient Object[] elementData;这是为了：
- 防止 elementData 被直接序列化（因为它可能比实际大小要大）
- 在 ArrayList 自定义了 writeObject() 和 readObject() 方法，它会只序列化有效数据（size 个元素），而不是整个数组
- 这样可以 节省空间、提高性能
✅ 总结
特性 含义 transient关键字 表示该字段不参与序列化 序列化时会忽略 字段不会写入字节流 反序列化后为默认值 null、0、false等 常用于 安全、临时变量、不可序列化对象
ArrayList 构造函数
带初始化容量的构造函数
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
无参构造函数，默认创建空集合
public ArrayList() {
this.elementData = DEFAULT_CAPACITY_EMPTY_ELEMENTDATA;
}说明：无参构造函数，默认创建空集合
将 collection 对象转换成数组，然后将数组的地址的赋给 elementData
public ArrayList(Collection<?> extends E c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}说明：将 collection 对象转换成数组，然后将数组的地址的赋给 elementData
ArrayList 添加和扩容操作(第1次添加数据)
添加操作
public boolean add(E e)：添加元素到ArrayList中-
ensureCapacityInternal(size + 1);：确保内部容量 -
elementData[size++] = e;：将元素添加到数组中 -
return true;：返回添加成功
-
确保内部容量
private void ensureCapacityInternal(int minCapacity)：确保内部容量-
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));：计算容量
-
计算容量
DEFAULT_CAPACITY=10：默认容量为10
private static int calculateCapacity(Object[] elementData, int minCapacity)：计算容量-
if (elementData == DEFAULT_CAPACITY_EMPTY_ELEMENTDATA)：如果elementData为默认空数组，则返回最大值和minCapacity的较大者 -
return minCapacity;：返回minCapacity
-
扩容方法
private void grow(int minCapacity)：扩容方法-
int oldCapacity = elementData.length;：获取当前容量 -
int newCapacity = oldCapacity + (oldCapacity >> 1);：增加原来容量的1.5倍 -
newCapacity - minCapacity < 0：如果新容量小于minCapacity，则设置为minCapacity -
if (newCapacity - MAX_ARRAY_SIZE > 0)：如果新容量超过最大数组大小，则设置为hugeCapacity(minCapacity) -
elementData = Arrays.copyOf(elementData, newCapacity);：数组拷贝
-
ArrayList 底层的实现原理
ArrayList底层是用动态的数组实现的
ArrayList初始容量为0，当第一次添加数据的时候才会初始化容量为10
ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组
ArrayList在添加数据的时候
- 确保数组已使用长度（size）加1之后足够存下下一个数据
- 计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容（原来的1.5倍）
- 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上
- 返回添加成功布尔值
ArrayList list = new ArrayList(10)中的list扩容几次
0 次
该语句只是声明和实例了一个ArrayList，指定了容量为10，未扩容
如何实现数组和 List 之间的转换
- 数组转List，使用JDK中java.util.Arrays工具类的asList方法
- List转数组，使用List的toArray方法。无参toArray方法返回Object数组，传入初始化长度的数组对象，返回该对象数组
用Arrays.asList转换List后，如果修改了数组的内容，list受影响吗
- Arrays.asList转换list之后，如果修改了数组的内容，list会受影响，因为它的底层使用的是Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址
List用toArray转数组后，如果修改了List内容，数组受影响吗
- list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响
数组转List
public static void testArray2List(){
String[] strs = {"aaa","bbb","ccc"};
List<String> list = Arrays.asList(strs);
for (String s : list) {
System.out.println(s);
}
}
public static void testArray2List(){
String[] strs = {"aaa","bbb","ccc"};
List<String> list = Arrays.asList(strs);
for (String s : list) {
System.out.println(s);
}
strs[1]="ddd";
System.out.println("=================");
for (String s : list) {
System.out.println(s);
}
}
aaa
ddd
ccc
List转数组
public static void testList2Array(){
List<String> list = new ArrayList<String>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
String[] array = list.toArray(new String[list.size()]);
for (String s : array) {
System.out.println(s);
}
}
public static void testList2Array(){
List<String> list = new ArrayList<String>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
String[] array = list.toArray(new String[list.size()]);
for (String s : array) {
System.out.println(s);
}
list.add("ddd");
System.out.println("=================");
for (String s : array) {
System.out.println(s);
}
}
aaa
bbb
ccc
二叉树
满二叉树
完全二叉树
二叉搜索树（BST）
红黑树
- 什么是二叉树
二叉树中，每个节点最多拥有两个“叉”，即左子节点和右子节点。不强制要求每个节点都必须有两个子节点，有的节点可能仅有左子节点，有的节点可能仅有右子节点。二叉树的每个节点的左子树和右子树也各自满足二叉树的定义 - 什么是二叉搜索树
二叉搜索树（Binary Search Tree，BST），又称二叉查找树或有序二叉树。在树中的任意节点，其左子树中所有节点的值均小于该节点的值，而右子树中所有节点的值均大于该节点的值。二叉搜索树中不存在键值相等的节点。通常情况下，二叉搜索树搜索的时间复杂度为O(logn)
红黑树 （自平衡的二叉搜索树）
红黑树（Red-Black Tree）：这是一种自平衡的二叉搜索树（BST），之前被称为平衡二叉B树（Symmetric Binary B-Tree）
好的，下面是对 红黑树（Red-Black Tree） 的详细讲解，适合系统学习和面试准备
🌳 什么是红黑树？
红黑树是一种 自平衡的二叉查找树（BST） ，它通过在每个节点添加一个“颜色位”（红或黑）并定义一组规则来保持平衡，确保最坏情况下的操作时间复杂度为 O(log n)
🧩 红黑树的特点
红黑树满足以下 5 个性质（核心）：
- 每个节点是红色或黑色
- 根节点是黑色
- 所有叶子节点（NIL）是黑色（注意：红黑树中的 NIL 是逻辑上的 null，不是真正的节点）
- 红色节点不能有红色子节点（即不能连续两个红色节点）
- 从任一节点到其所有后代叶子节点的路径都包含相同数目的黑色节点
🎯 红黑树的目的
- 保证树的 高度不会过高，从而提高查找效率
- 在最坏情况下，红黑树的高度为 2 * log(n+1)，相比 AVL 树更“宽松”，因此插入/删除效率更高
📏 红黑树 vs AVL 树
| 对比项 | 红黑树 | AVL 树 |
|---|---|---|
| 平衡度 | 相对平衡（黑高差距 ≤ 1） | 严格平衡（左右子树高度差 ≤ 1） |
| 查询效率 | 一般略低 | 更高 |
| 插入/删除效率 | 更高（旋转次数更少） | 较低（更频繁的旋转） |
| 应用场景 | 插入/删除频繁（如 TreeMap） | 查找频繁但修改少 |
🔄 红黑树的核心操作
1. 插入（Insert）
步骤：
新节点初始为红色
插入后可能违反红黑树的性质，需要通过：
- 颜色变换（recolor）
- 旋转（rotate）
来修复
可能需要多次修复，直到满足所有红黑性质
👉 常见的修复场景如下：
- 父亲是黑色：不需要处理
- 父亲是红色，叔叔是红色：变色
- 父亲是红色，叔叔是黑色或 null：旋转 + 变色
2. 删除（Delete）
删除更复杂，核心点在于：
删除黑色节点后可能会破坏黑高（路径黑色数量相等）的性质
需要使用“双重黑”的概念来修复平衡
修复操作包括：
- 兄弟是红色 → 旋转 + 变色
- 兄弟是黑色，子节点也是黑 → 兄弟变红，向上递归修复
- 兄弟是黑色，有红色子节点 → 合理旋转/变色解决双重黑
🔧 常见操作时间复杂度
| 操作 | 时间复杂度 |
|---|---|
| 查找（Search） | O(log n) |
| 插入（Insert） | O(log n) |
| 删除（Delete） | O(log n) |
📚 应用场景
红黑树被广泛应用于各种需要有序存储、快速增删查的场景：
- TreeMap（有序键值对）
- TreeSet（有序集合）
- Linux 的 CFS 调度器（红黑树用于进程调度）
- Java 的 HashMap 在链表过长后也会转换为红黑树（提高查询效率）
🟩 一、插入过程（Red-Black Tree Insertion）
我们依次插入以下数字：10, 20, 30, 15, 25, 23
✅ 步骤 1：插入 10（根节点）
10(B)- 红黑树要求根节点是黑色
✅ 步骤 2：插入 20（红）
10(B)
\
20(R)- 父节点是黑色，插入红色，✅ 无需调整
✅ 步骤 3：插入 30（红）
10(B)
\
20(R)
\
30(R)❌ 违反规则：红色节点 20 有红色子节点 30
- 父（20）是红，叔叔为空（黑）
- 属于「右右」结构 → 左旋 + 父子变色
修复后：
20(B)
/ \
10(R) 30(R)✅ 步骤 4：插入 15（红）
20(B)
/ \
10(R) 30(R)
\
15(R)❌ 再次违反规则（10 和 15 都是红色）
- 父（10）红，叔叔（30）红 → 变色处理
修复后：
20(B)
/ \
10(B) 30(B)
\
15(R)✅ 步骤 5：插入 25（红）
20(B)
/ \
10(B) 30(B)
\ /
15(R)25(R)- 插入在黑色节点 30 下，父红叔叔红 ❌ → 变色
修复后：
20(B)
/ \
10(B) 30(B)
\ /
15(R)25(R)✅ 仍然符合红黑树规则
✅ 步骤 6：插入 23（红）
20(B)
/ \
10(B) 30(B)
\ /
15(R)25(R)
/
23(R)❌ 25 是红色，其子节点 23 也是红色 → 违反规则（红红冲突）
- 属于「左右」结构 → 先右旋成右右，再左旋 + 变色
修复后结构如下：
20(B)
/ \
10(B) 25(B)
\ / \
15(R)23(R)30(R)✅ 插入修复完毕，红黑树仍平衡
🟥 二、删除过程（Red-Black Tree Deletion）
我们现在从上一步的树中 删除节点 25（黑色） ，它是内部节点，有两个子节点（23 和 30）
🪓 步骤 1：删除 25，找到中序后继 30 替代
20(B)
/ \
10(B) 30(B)
\ /
15(R)23(R)- 30 替代 25，原本 30 的子节点 23 是红色
- 删除了一个黑色节点，需要修复
🔄 步骤 2：修复「双黑」问题
我们会根据兄弟节点的颜色进行如下操作：
- 兄弟（23）是红色 → 旋转 + 变色
- 或兄弟为黑 + 无红子 → 变色并向上传递
- 最终恢复平衡
修复过程较复杂，但关键是通过旋转 + 变色使路径黑色节点数重新一致
散列表
散列函数的基本要求：
- 散列函数计算得到的散列值必须为大于等于0的正整数，因为hashValue需作为数组的下标
- 若key1等于key2，则经过散列后得到的哈希值也应相同，即：hash(key1) == hash(key2)
散列冲突
在实际情况下，寻找一个散列函数，使其对于不同的ky计算所得的散列值皆不相同，几乎是不可能实现的。即便如著名的MD5、SHA等哈希算法，也无法避免这种情况。这种现象被称为散列冲突，或称哈希冲突、哈希碰撞，即指多个ky映射到同一个数组下标位置
在散列表中，数组的每个下标位置可称为“桶”（bucket）或“槽”（slot）。每个桶（槽）都对应一条链表，所有散列值相同的元素均被放置于相同槽位对应的链表中
当查找或删除一个元素时，通过散列函数计算出的槽，用于遍历链表查找或删除
平均情况下，基于链表法解决冲突时，查询的时间复杂度为O(1)
散列表可能会退化为链表，此时查询的时间复杂度将从O(1)退化为O(n)
将链表法中的链表改造为其他高效的动态数据结构，如红黑树，查询的时间复杂度将降至O(log n)
将链表法中的链表改造红黑树还有一个非常重要的原因，可以防止DDos攻击
HashMap 实现原理
HashMap的数据结构：底层使用hash表数据结构，即数组和链表或红黑树
- 当向HashMap中插入元素时，利用key的hashCode方法重新hash计算出当前对象在数组中的下标
- 存储时，若出现hash值相同的key，存在以下两种情况：
a. 若key相同，则覆盖原始值；
b. 若key不同（出现冲突），则将当前的key-value对放入链表或红黑树中 - 获取时，直接定位到hash值对应的下标，进一步判断key是否相同，从而找到对应值
jdk1.7 和 jdk1.8的 HashMap 有什么区别
JDK1.8之前采用拉链法。拉链法：将链表与数组相结合。即创建一个链表数组，其中每一格代表一个链表。若遇哈希冲突，则将冲突的值添加至链表中即可
JDK1.8在解决哈希冲突方面有所变化，当链表长度超过阈值（默认为8）且数组长度达到64时，将链表转化为红黑树，以减少搜索时间。在扩容resiz()过程中，若红黑树拆分后的节点数不超过临界值6个，则退化成链表
HashMap 的 put 方法
判断键值对数组table是否为空或为null，否则执行resize()进行扩容（初始化）
根据键值key计算hash值得到数组索引
判断table[i] == null，条件成立，直接新建节点添加
如果table[i] != null，不成立
- 4.1 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value
- 4.2 判断table[i] 是否为TreeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
- 4.3 遍历table[i]，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现key已经存在直接覆盖value
插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold（数组长度*0.75），如果超过，进行扩容
🌟 一、源码结构入口
在 HashMap.java 中，调用 put(K key, V value) 实际会触发以下核心逻辑：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}🔢 二、hash() 方法 — 计算键的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}🧠 解析：
- 使用 key.hashCode() 生成原始哈希值
- 与高 16 位右移做异或，提高哈希分布均匀性
- 结果作为 putVal 的 hash 入参
🚪 三、putVal 方法解析入口
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)按步骤解读其主要逻辑
✅ 1. 初始化 table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;- 如果当前数组为空，则执行 resize() 创建初始容量（默认 16）
✅ 2. 计算索引位置
int i = (n - 1) & hash;- 通过 hash 值与 (n - 1) 做与运算，快速求模定位数组下标
- & 替代 %，效率更高
✅ 3. 没有碰撞，直接插入
if ((p = tab[i]) == null)
tab[i] = newNode(hash, key, value, null);- 目标桶位为空，直接插入新节点
✅ 4. 发生哈希冲突
else {
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;情况分类处理：
| 情况 | 描述 | 处理方式 |
|---|---|---|
| ✅ Key 相同 | 用新 value 替换旧值 | e = p; |
| ❌ Key 不同，链表结构 | 遍历链表末尾添加 | for (Node<K,V> e = p; e != null; e = e.next) |
| ❌ Key 不同，红黑树结构 | 插入红黑树 | ((TreeNode<K,V>)p).putTreeVal(...) |
✅ 5. 链表长度超限转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD = 8
treeifyBin(tab, hash);- 如果链表长度超过 8 且数组长度大于 64 → 转红黑树
✅ 6. 插入完成后处理返回值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
return oldValue;
}- 如果已存在键，则替换值，并返回旧值
- 否则返回 null
📈 四、自动扩容机制（resize）
当实际元素个数 > 阈值（threshold = 容量 * 负载因子）时触发：
if (++size > threshold)
resize();resize() 过程：
- 扩容为原来的 2 倍
- 对原数据重新计算 hash
- 低位不变，高位迁移：保证高效分布
📌 五、时间复杂度总结
| 操作 | 时间复杂度 |
|---|---|
| 插入 put | O(1) 平均，O(n) 最坏（hash 冲突极多） |
| 查找 get | O(1) 平均，O(logn) 最坏（红黑树） |
| 删除 remove | O(1) 平均 |
📋 六、完整流程图简述：
put(key, value)
↓
计算 hash
↓
hash & (n - 1) 定位索引
↓
[ ] 空桶 ——> 直接插入
[ ] 冲突 ——> 比较 key：
↓
[=] 相同 ——> 替换值
[≠] 不同 ——> 链表 / 红黑树插入
↓
检查链表长度 ——> 超 8 转红黑树
↓
检查 size 是否超过 threshold
↓
是 ——> resize 扩容
HashMap 的扩容机制
🧩 HashMap 的基本结构
- HashMap 底层是一个数组 + 链表/红黑树的结构
- 当发生哈希冲突时，会将相同哈希值的键值对存储在同一个桶的链表（或红黑树）中
🚀 触发扩容的条件
当 HashMap 中的元素数量超过 负载因子（load factor） × 当前数组容量（capacity） 时，会触发扩容
- 默认初始容量：16
- 默认负载因子：0.75
- 即当 size > 16 × 0.75 = 12 时触发扩容
🔄 扩容机制过程详解
1. 创建新数组
- 新数组容量是原来的两倍（capacity × 2）
2. 重新计算位置（Rehashing）
- 将原数组中的每个元素重新计算在新数组中的位置
- 新位置要么是原位置 index，要么是 index + oldCap
- 原因：HashMap 中使用的是 (n - 1) & hash 计算位置，扩容后 n 翻倍，导致高位发生变化
int newIndex = (oldHash & oldCap) == 0 ? oldIndex : oldIndex + oldCap;3. 链表拆分重分布
- 每个链表不会重新计算每个节点的 hash，而是直接分成两个链表放到新数组的不同位置
- 如果原链表长度超过树化阈值，在新数组中如果仍然超过阈值，保留为红黑树；否则退化为链表
📌 为什么扩容是 2 倍？
因为 2 的幂次方可以简化 hash 定位逻辑 (n - 1) & hash，大大提高效率，避免使用取模 % 运算
⚠️ 扩容代价高
- 扩容是一个 O(n) 的操作（需要遍历旧数组中所有元素）
- 所以建议在已知数据量时提前设定初始容量，减少扩容次数
int expectedSize = 1000;
Map<String, String> map = new HashMap<>((int) (expectedSize / 0.75f) + 1);🧠 Rehashing 基本背景
- HashMap 使用 (n - 1) & hash 计算数组下标（即 bucket index）
- 这是因为容量 n 通常是 2 的幂，所以 (n - 1) & hash 等价于 hash % n 的高效实现
- 扩容时，n 变成原来的 2 倍，假设原容量为 oldCap，扩容后就是 newCap = oldCap * 2
🧮 关键点：位运算分析
扩容前后的 index 如何变化
扩容前
oldIndex = hash & (oldCap - 1);扩容后
newIndex = hash & (newCap - 1); // newCap = 2 * oldCap
= hash & (2 * oldCap - 1)
= hash & (oldCap * 2 - 1)由于 newCap = oldCap << 1，那么 (newCap - 1) 的二进制会多一位：
- 假设 oldCap = 16 (0b10000)，oldCap - 1 = 0b01111
- 扩容后 newCap = 32 (0b100000)，newCap - 1 = 0b11111
所以：
hash & 0b01111 -> 旧索引 oldIndex
hash & 0b11111 -> 新索引 newIndex观察：
- newIndex 与 oldIndex 的差别就在于 多了高一位的判断（hash & oldCap）
✅ 核心结论：
- 如果 (hash & oldCap) == 0，说明新高位是 0，newIndex = oldIndex
- 否则，新高位是 1，newIndex = oldIndex + oldCap
🔁 举个例子：
假设：
- oldCap = 16，oldCap - 1 = 0b01111
- 某个键的 hash = 0b10011（十进制 19）
则：
- oldIndex = 0b10011 & 0b01111 = 0b00011 = 3
- hash & oldCap = 0b10011 & 0b10000 = 0b10000 != 0 ⇒ 高位是 1
- 所以 newIndex = oldIndex + oldCap = 3 + 16 = 19
🌲 好处
- 不需要重新计算 hash 值，只判断 hash & oldCap，即可得出元素应该留在原位置，还是移动到新位置（+oldCap）
- 保证 hash 分布的均匀性，避免过多冲突
- 极大提高了扩容过程的效率
总结
| 阶段 | 操作 |
|---|---|
| 触发扩容 | size > capacity × loadFactor |
| 扩容策略 | 新容量 = 原容量 × 2 |
| 重定位元素 | 根据 hash & newCapacity 重新分布 |
| 性能建议 | 尽量减少扩容次数，预估大小提前设定 |
HashMap 的寻址算法
计算对象的hashCode()，随后调用hash0方法进行二次哈希
将hashCode值右移16位后进行异或运算，以使哈希分布更加均匀
最终通过(capacity-1) & hash获取索引
为何HashMap的数组长度一定是2的次幂？
- 计算索引时效率更高：如果是2的次幂，可以使用位与运算代替取模
- 扩容时重新计算索引的效率更高：当hash & oldCap == 0时，元素留在原位置；否则，新位置 = 旧位置 + oldCap
HashMap 在 1.7 下的多线程死循环问题
😨 问题描述
在 Java 1.7 中，如果多个线程在并发 put()，并且触发了 扩容（resize） 操作，可能会导致 链表成环（形成自引用），从而导致死循环（死链表） ，最终：
- CPU 占用飙升（死循环）
- 程序卡死甚至宕机
- HashMap.get() 永远得不到返回值
🧩 背景知识：1.7 中
HashMap
扩容过程
Java 1.7 中 HashMap 的底层结构是 数组 + 链表（无红黑树）
当发生扩容时，主要步骤是：
- 创建一个新数组，容量为原来的 2 倍
- 遍历旧数组，把旧链表中的元素复制到新数组中
- 复制链表时是头插法（头部插入） ，不是尾插！
❗ 问题出现的原因
并发 put() 时多个线程同时触发 resize()
例如：
- 线程 A 和 线程 B 同时触发扩容
- 线程 A 正在遍历并迁移某个桶里的链表
- 线程 B 把链表头部插入到了新数组中（因为是头插法）
- 两个线程交叉修改链表指针，最终可能导致环形链表（A -> B -> C -> A）！
这就出现了链表的自引用，即 循环引用（loop）
📉 死循环具体表现
当你之后使用 .get() 遍历这个链表时：
while (entry != null) {
if (entry.key.equals(key)) {
return entry.value;
}
entry = entry.next;
}由于链表变成了一个“环”，entry.next 永远不为 null，导致程序进入无限循环，CPU 飙高
🛠️ Java 1.8 的修复方式
Java 1.8 做了两件关键改进：
- 迁移链表节点时改为尾插法（保持原顺序）
- 引入了 synchronized 控制线程安全的迁移过程
- 之后还引入了 红黑树优化链表性能
这些改动使得 HashMap 在多线程下虽然依旧不是线程安全，但至少 不会出现结构性损坏（如链表成环）
✅ 正确建议
在多线程环境下，绝对不要使用非线程安全的 HashMap
应该使用以下替代方案：
- ConcurrentHashMap
- Collections.synchronizedMap(new HashMap<>())（加外部锁）
- Hashtable（已过时，不推荐）
🧪 真实案例模拟（简略版）
以下代码在高并发下可能会复现死循环问题：
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
final int key = i;
new Thread(() -> map.put(key, key)).start();
}运行后，有概率程序 hang 住、CPU 飙升
📌 总结
| 版本 | 是否会死循环 | 原因 |
|---|---|---|
| Java 1.7 | ✅ 有概率 | 多线程扩容 + 头插法导致链表成环 |
| Java 1.8+ | ❌ 不会 | 尾插法 + 同步控制，结构更安全 |
======= Java 异常 =======
✅ 一、Java 异常的整体分类
Java 中所有异常都继承自 java.lang.Throwable。
Throwable
/ \
Error Exception
/ \
CheckedException UncheckedException📚 二、详细解释
1.
Error
（错误）❗不可恢复，不需要处理
系统级严重问题，开发者 不应尝试捕获
典型代表：
- OutOfMemoryError：内存溢出
- StackOverflowError：栈溢出
- NoClassDefFoundError：类找不到
2.
Exception
（异常）✅ 需要/可以处理
✅ 2.1.
Checked Exception（受检查异常）
- 编译时必须处理（要么 try-catch，要么 throws）
- 不处理编译就报错
典型例子：
| 异常类型 | 描述 |
|---|---|
| IOException | IO 错误 |
| SQLException | 数据库错误 |
| ClassNotFoundException | 找不到类 |
❗2.2.
Unchecked Exception（运行时异常）
- 编译时 不强制处理
- 程序逻辑出错，运行时抛出
典型例子：
| 异常类型 | 描述 |
|---|---|
| NullPointerException | 空指针异常 |
| ArrayIndexOutOfBoundsException | 数组越界 |
| ArithmeticException | 除以 0 |
| IllegalArgumentException | 参数非法 |
🎯 三、为什么要分 Checked 和 Unchecked？
- Checked 异常：编译器要求你必须考虑和处理 → 更稳健
- Unchecked 异常：太常见，强制处理会让代码臃肿 → 自己负责逻辑合理性
✍️ 四、代码示例
public void readFile(String path) throws IOException {
FileReader reader = new FileReader(path); // Checked Exception
}
public void divide(int a, int b) {
int result = a / b; // Unchecked Exception，b=0 会报错
}🧠 五、异常分类顺口溜
异常顶层 Throwable，分成错误与异常；
Error 致命不捕捉，OOM 栈爆很常见；
Exception 再细看，Checked 编译需处理；
运行异常不强求，空指针越界打头炮；
IOException 要捕捉，数据库错别放掉；
逻辑漏洞靠你写，捕获抛出要分明！✅ 六、面试重点小结
| 问题 | 答案概要 |
|---|---|
| Java 异常分哪几类？ | Throwable → Error / Exception |
| Checked 和 Unchecked 区别？ | 编译是否强制处理 |
| RuntimeException 是哪类异常？ | Unchecked 异常 |
| 什么异常必须 try-catch？ | Checked 异常 |