93 lines
3.0 KiB
Markdown
93 lines
3.0 KiB
Markdown
|
## JAVA面试题（1）
|
|||
|
|
|
|||
|
|
### [说说 Java 中 HashMap 的原理？](https://www.mianshiya.com/bank/1860871861809897474/question/1834107117591187457)
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
**为什么引入红黑树:**
|
|||
|
|
当hash冲突较多的时候，链表中的元素会增多，插入、删除、查询的效率会变低，退化成O(n)使用红黑树可以优化插入、删除、查询的效率，logN级别。
|
|||
|
|
|
|||
|
|
转换时机:
|
|||
|
|
链表上的元素个数大于等于8 且 数组长度大于等于64；
|
|||
|
|
链表上的元素个数小于等于6的时候，红黑树退化成链表。
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
**链表插入方式变更：从"头插法"改为"尾插法"**
|
|||
|
|
|
|||
|
|
- **头插法特点**：
|
|||
|
|
- 插入时不需要遍历链表
|
|||
|
|
- 直接替换头结点
|
|||
|
|
- 扩容时会导致链表逆序
|
|||
|
|
- 多线程环境下可能产生**死循环**
|
|||
|
|
|
|||
|
|
- **尾插法改进**：
|
|||
|
|
- 避免扩容时的链表逆序
|
|||
|
|
- 解决多线程环境下的潜在死循环问题
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
### [Java 中 ConcurrentHashMap 1.7 和 1.8 之间有哪些区别？](https://www.mianshiya.com/bank/1860871861809897474/question/1780933294813114369)
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
#### ConcurrentHashMap 不同JDK版本的实现对比
|
|||
|
|
|
|||
|
|
1. **数据结构**
|
|||
|
|
|
|||
|
|
- JDK1.7：
|
|||
|
|
- 使用 `Segment（分段锁） + HashEntry数组 + 链表` 的数据结构
|
|||
|
|
|
|||
|
|
- JDK1.8及之后：
|
|||
|
|
- 使用 `数组 + 链表/红黑树` 的数据结构（与HashMap类似）
|
|||
|
|
|
|||
|
|
2. **锁的类型与宽度**
|
|||
|
|
|
|||
|
|
- JDK1.7：
|
|||
|
|
- 分段锁(Segment)继承了 `ReentrantLock`
|
|||
|
|
- Segment容量默认16，不会扩容 → 默认支持16个线程并发访问
|
|||
|
|
|
|||
|
|
- JDK1.8：
|
|||
|
|
- 使用 `synchronized + CAS` 保证线程安全
|
|||
|
|
- 空节点：通过CAS添加（**put操作**，多个线程可能同时想要将一个新的键值对插入到同一个桶中，这时它们会使用 CAS 来比较当前桶中的元素（或节点）是否已经被修改过。）
|
|||
|
|
- 非空节点：通过synchronized加锁，**只锁住该桶**，其他桶可以并行访问。
|
|||
|
|
|
|||
|
|
3. **渐进式扩容（JDK1.8+）**
|
|||
|
|
|
|||
|
|
- **触发条件**：元素数量 ≥ `数组容量 × 负载因子(默认0.75)`
|
|||
|
|
- **扩容过程**：
|
|||
|
|
1. 创建2倍大小的新数组
|
|||
|
|
2. 线程操作数据时，逐步迁移旧数组数据到新数组
|
|||
|
|
3. 使用 `transferIndex` 标记迁移进度
|
|||
|
|
4. 直到旧数组数据完全迁移完成
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
### [500. 什么是 Java 的 CAS（Compare-And-Swap）操作？](https://www.mianshiya.com/question/1780933295027023873)
|
|||
|
|
|
|||
|
|
CAS操作包含三个基本操作数：
|
|||
|
|
|
|||
|
|
1. **内存位置(V)**：要更新的变量
|
|||
|
|
2. **预期原值(A)**：认为变量当前应该具有的值
|
|||
|
|
3. **新值(B)**：想要更新为的值
|
|||
|
|
|
|||
|
|
CAS 工作原理：
|
|||
|
|
|
|||
|
|
1. 读取内存位置V的当前值为A
|
|||
|
|
2. 计算新值B
|
|||
|
|
3. 当且仅当V的值等于A时，将V的值设置为B
|
|||
|
|
4. 如果不等于A，则操作失败(通常重试)
|
|||
|
|
|
|||
|
|
```text
|
|||
|
|
伪代码表示：
|
|||
|
|
if (V == A) {
|
|||
|
|
V = B;
|
|||
|
|
return true;
|
|||
|
|
} else {
|
|||
|
|
return false;
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|