HashMap 数组+链表+红黑树（8树化/6退化/0.75推导）、ConcurrentHashMap CAS+synchronized、ArrayList 扩容、泛型擦除、动态代理（JDK vs CGLIB）。

Java 基础与集合底层深度

校招考察频度：★ 高频（核心必考·高频生死线） 一句话速记：HashMap 借位运算取模、泊松分布定 8 树化、0.75 折中时空；ConcurrentHashMap 在 1.8 抛弃分段锁，以 CAS + Synchronized 锁细化至桶头节点；动态代理在接口用 JDK 反射生成代理类，无接口用 CGLIB 继承子类重写。

集合与面向对象基础是 Java 一面最坚硬的试金石。面试官通过对 HashMap 每一个常数设定的底层推导，快速判断候选人是“死记硬背”还是真正理解了“算法工程落地”。

一、HashMap 底层结构与常数数学推导

1. 底层存储模型

JDK 1.7：Entry<K, V>[] 数组 + 单向链表（头插法，并发扩容易产生环形死循环）。
JDK 1.8+：Node<K, V>[] 数组 + 单向链表 + 红黑树（尾插法，保持原有先后顺序）。
- 当单链表长度达到阈值（TREEIFY_THRESHOLD = 8）且数组总长度达到（MIN_TREEIFY_CAPACITY = 64）时，链表自动树化为红黑树。
- 若数组长度小于 64，优先通过 resize() 数组扩容而不是树化。

Node[] 散列桶数组
 0:  [ null ]
 1:  [ Node ] -> [ Node ] -> [ Node ] (链表，长度 < 8)
 2:  [ TreeNode (红黑树根) ]           (树化，长度 >= 8 且总容量 >= 64)
     /      \
  [TreeNode] [TreeNode]
 3:  [ null ]

2. 为什么数组容量必须是 2 的幂次方？

位运算极速取模：当容量 n 为 2 的整数次幂时，二进制表示恰为高位 1 其余全 0，此时 n - 1 的低位全部为 1。
```
index = hash & (n - 1)  // 等价于 hash % n
```
CPU 执行与运算（AND）仅需 1 个时钟周期，比传统的求模除法指令（DIV 几十个时钟周期）快一个数量级。
散列均匀：若容量为奇数或非 2 的幂，n - 1 的二进制低位会出现 0，导致部分哈希槽永远无法被命中，大幅加剧碰撞。

3. 为什么树化阈值是 8？为什么退化阈值是 6？

泊松分布（Poisson Distribution）数学推导：在理想的随机哈希算法下，每个桶中发生碰撞的元素数量服从泊松分布：
```
P(X = k) = (λ^k * e^(-λ)) / k!
```
在默认负载因子 0.75 时，参数 λ ≈ 0.5。根据源码注释计算概率：
- 碰撞 1 次的概率：0.6065
- 碰撞 3 次的概率：0.0126
- 碰撞 8 次的概率：0.00000006（千万分之六）！
结论：单链表长度达到 8 是几乎不可能发生的极端哈希倾斜事件。红黑树单个节点（TreeNode）所占用的内存是普通单链表节点（Node）的两倍，且旋转平衡需消耗 CPU。定为 8 是空间换时间开销的最优防守界限。
为什么退化是 6 而不是 8？ 如果退化阈值也是 8，当链表在长度 7 和 8 之间频繁增删时，会导致桶在“链表 ⇄ 红黑树”之间剧烈震荡，带来巨大的树化和拆解性能损耗。预留差值 2 作为防抖缓冲层。

4. 为什么负载因子默认选 0.75？

时空权衡（Time-Space Tradeoff）：
- 若过大（如 1.0）：空间利用率高，但哈希碰撞概率飙升，链表过长，查询退化至 O(N)。
- 若过小（如 0.5）：碰撞极低，但数组空间浪费一半，且极其频繁触发 resize() 扩容，严重影响写入吞吐。
- 0.75 在泊松分布概率、平均查找长度（ASL）与内存开销之间取得了最佳的工程折中。

5. JDK 1.8 的高低位扩容链表优化

扩容时（容量翻倍为原来的 2 倍），由于高位新增了一个二进制 1，原节点的新索引只有两种可能：

若 (e.hash & oldCap) == 0：留在原索引位置（低位链表 lowHead）。
若 (e.hash & oldCap) != 0：移动到 原索引 + oldCap 位置（高位链表 highHead）。无需像 1.7 那样对所有键值重新计算哈希取模，仅通过一次按位与判断即可完成平滑迁移。

二、ConcurrentHashMap 并发安全机制

1. JDK 1.7 分段锁 vs JDK 1.8 锁细化

对比维度	JDK 1.7 ConcurrentHashMap	JDK 1.8+ ConcurrentHashMap
底层结构	`Segment<K,V>[]` 数组 + `HashEntry<K,V>[]` + 链表	`Node<K,V>[]` 数组 + 链表 + 红黑树
并发粒度	分段锁（Segment）：继承 `ReentrantLock`，锁整个 Segment 槽	节点级锁：CAS + `synchronized` 仅锁定单个桶的头节点（Node）
并发度	固定为 Segment 数组大小（默认 16，不可扩容）	理论上等于数组容量大小（可达数千上万），并发度大幅提升
查询性能	不加锁，依赖 `volatile` 保证跨线程可见性	不加锁，Node 的 `val` 和 `next` 均为 `volatile` 保证可见性

2. 为什么 JDK 1.8 用 `synchronized` 替换了 `ReentrantLock`？

JVM 官方底层持续优化：从 JDK 1.6 开始，JVM 对 synchronized 引入了偏向锁、轻量级锁、自旋锁与适应性自旋等大量优化，在低冲突或单线程下开销极低。
节约内存空间：每个 ReentrantLock 都需要维护一个 AQS 同步队列对象及其状态，若每个桶槽都绑定一个 Lock，内存占用成倍增加；而 synchronized 是 JVM 原生关键字，仅依赖对象头部的 Mark Word 即可完成加锁，零额外内存开销。

3. 高并发计数机制（`size()` 与 `mappingCount()`）

在超高并发写入下，单变量 CAS 计数（如 AtomicLong）会因为多核总线缓存一致性流量（MESI 协议）导致 CPU 满载假死。 ConcurrentHashMap 借鉴了 LongAdder 的槽分化思想：

内部维护 baseCount 和一个动态伸缩的 CounterCell[] 数组。
线程无竞争时直接 CAS 修改 baseCount；一旦 CAS 失败（冲突），根据线程的哈希探针分配到 CounterCell[i] 进行局部累加。
统计总数时：total = baseCount + Σ(CounterCell[i])。化整为零，将单点竞争转化为分布式并行累加。

三、ArrayList vs LinkedList 底层与硬件缓存亲和性

特性	ArrayList	LinkedList
底层结构	连续物理内存 `Object[]` 动态数组	离散物理内存双向链表（`Node` 含 `item`, `prev`, `next`）
随机访问	O(1)，直接通过基址 + 偏移量计算地址	O(N)，需从头或尾二分遍历查找指针
插入/删除	尾部 O(1)，中间位置需 O(N) 移动数组元素	头部/尾部 O(1)，指定位置需 O(N) 遍历找到节点后修改指针
扩容机制	初始 10（初次 add 触发），扩容为原来的 1.5 倍（`old + (old >> 1)`）	无需扩容，每个元素按需动态分配节点内存
CPU Cache 亲和性	极高（连续物理内存，一次 Cache Line 加载 64 字节击中多个元素）	极差（各节点堆内存离散分布，指针跳跃导致高 Cache Miss）

面试加分项：即使是频繁在中间插入删除的场景，如果数据量在几千以内，ArrayList 的综合实测性能依然往往优于 LinkedList！因为现代 CPU 的 L1/L2 缓存机制使得连续内存的拷贝速度极快，而 LinkedList 大量的堆内存离散分配与指针解引用不仅带来巨大的内存开销，还会造成频繁的 CPU 缓存行失效。

四、泛型擦除与动态代理（JDK vs CGLIB）

1. 泛型类型擦除（Type Erasure）

实现本质：Java 的泛型属于“编译期伪泛型”。编译器在前端对泛型类型进行语法检查，编译成 .class 字节码后，所有类型参数会被擦除替换为原始类型（Object 或其上限类如 Comparable），并在调用处自动生成类型强转指令（checkcast）。
为什么不能 new T()？：因为在运行时运行时（Runtime），具体的泛型类型 T 已经被擦除为 Object，JVM 根本无法知道要为其分配多少字节的内存空间与调用哪个构造器。
桥接方法（Bridge Method）：当子类重写父类的泛型方法时，编译器会自动在字节码中生成一个参数为 Object 的桥接方法，内部调用子类精确类型的方法，以维护面向对象的多态性。

2. 动态代理两大流派

JDK 动态代理与 CGLIB 选型与生成流程

维度	JDK 动态代理	CGLIB 动态代理
前置条件	目标类必须实现至少一个接口	目标类与方法不能被 `final` 修饰
底层原理	反射机制，生成实现该接口的 `$Proxy0` 字节码	ASM 字节码操作框架，动态生成目标类的子类
增强入口	实现 `InvocationHandler` 接口，调用 `invoke()`	实现 `MethodInterceptor` 接口，调用 `intercept()`
性能表现	历史版本反射较慢，高版本已高度优化；类加载极快	运行时首次生成子类较耗时，但后续方法调用性能略优
Spring 默认选型	Spring 4.x 之前有接口用 JDK，无接口用 CGLIB	Spring Boot 2.x 起全量默认开启 CGLIB（避免类型强转异常）

五、校招高频面试追问

HashMap 为什么线程不安全？会发生什么？
- JDK 1.7 在多线程并发扩容时，头插法会导致链表节点倒序，多线程竞争下产生环形死循环链表，造成 CPU 100% 飙死。
- JDK 1.8 虽改为尾插法消除了死循环，但在并发 put 时仍然存在数据覆盖丢失问题（两个线程同时判断哈希桶为空，同时写入同一槽位，后者覆盖前者），并发计数 size++ 也非原子操作。高并发必须使用 ConcurrentHashMap。
解决哈希冲突的常见方法有哪些？
- 链地址法（Separate Chaining，如 HashMap 采用）
- 开放寻址法（Open Addressing，如线性探测、二次探测，ThreadLocal 采用线性探测）
- 再哈希法（Re-hashing）
- 建立公共溢出区
equals() 与 hashCode() 为什么必须同时重写？
- 依据 Java 契约：若两个对象 equals() 为 true，则它们的 hashCode() 必须相同；若两个对象的 hashCode() 相同，equals() 不一定为 true（哈希碰撞）。
- 如果只重写 equals 而不重写 hashCode，把该对象作为键放入 HashMap 时，两个逻辑相等的对象计算出不同的哈希桶索引，导致无法查到存入的值，打破映射唯一性。
ArrayList 在遍历时调用 list.remove() 为什么抛出 ConcurrentModificationException？
- foreach 本质是调用迭代器（Iterator）。ArrayList 内部维护一个 modCount（结构修改次数），迭代器创建时会保存一个 expectedModCount = modCount。在遍历过程中调用 list.remove() 导致 modCount 自增，迭代器调用 next() 时校验发现两者不相等，触发**快速失败（Fail-Fast）**机制。
- 正确做法：使用迭代器自身的 iterator.remove()，或者使用 Java 8+ 的 list.removeIf()。
CGLIB 为什么不能代理 final 方法或类？
- 因为 CGLIB 的代理机制是通过生成目标类的子类并重写（Override）父类方法来植入增强逻辑的。在 Java 语法规范中，final 类禁止被继承，final 方法禁止被子类重写，因此 CGLIB 对此无能为力。