前端码农

Appearance

Day11 Java 后端：集合体系（ArrayList、LinkedList、HashMap、ConcurrentHashMap 高频手撕） ​

📖 基础知识讲解【基础原理 + 高级深挖知识点】 ​

基础原理 ​

1. 集合体系全景：两大根接口 ​

Java 集合框架（java.util）只有两条根：Collection 单列集合（一个一个存元素）和 Map 双列集合（按 key-value 存）。Map 并不是 Collection 的子接口，这是面试里常被问倒的一个点。

text
Iterable（可迭代，提供 iterator()）
└── Collection
    ├── List          有序、可重复、有索引
    │     ├── ArrayList            动态数组   ★最常用
    │     ├── LinkedList           双向链表（同时是 Deque）
    │     ├── Vector               古老，方法级 synchronized（废弃）
    │     │     └── Stack          继承 Vector（废弃，用 ArrayDeque）
    │     └── CopyOnWriteArrayList 并发包，写时复制
    ├── Set           无序、不可重复（底层大多就是一个 Map）
    │     ├── HashSet              底层 HashMap
    │     │     └── LinkedHashSet  底层 LinkedHashMap，保留插入顺序
    │     ├── TreeSet              底层 TreeMap，红黑树，自动排序
    │     └── CopyOnWriteArraySet  并发包，底层 COWArrayList
    └── Queue         队列，先进先出
          ├── ArrayDeque           循环数组双端队列 ★栈/队列首选
          ├── PriorityQueue        二叉小顶堆，优先级队列
          └── BlockingQueue        并发包（ArrayBlockingQueue / LinkedBlockingQueue…）

Map（独立根接口，不属于 Collection）
├── HashMap                数组 + 链表 + 红黑树   ★最常用
│    └── LinkedHashMap    HashMap + 双向链表（可做 LRU）
├── TreeMap                红黑树，key 自动排序
├── Hashtable              全方法 synchronized（废弃）
│     └── Properties       读 .properties 配置
└── ConcurrentHashMap      并发包，CAS + synchronized 锁桶   ★并发首选
接口核心特征典型实现判重依据
List有序、可重复、有下标ArrayList不判重
Set不可重复、一般无序HashSethashCode() + equals()
Queue先进先出 / 按优先级出队ArrayDeque不判重
Mapkey 不重复、value 可重复HashMapkey 的 hashCode() + equals()

一句话结论： Set 和 Map 是一回事 —— HashSet 内部就是一个 HashMap，元素存在 key 上，value 统一塞一个固定的 PRESENT 占位对象。所以掌握了 HashMap，等于同时掌握了 HashSet，面试考 HashMap 的频率也远高于其他所有集合。

2. ArrayList：动态数组 ​

text
ArrayList 内部结构
  elementData ──► [ A ][ B ][ C ][ D ][  ][  ][  ][  ][  ][  ]
                    0    1    2    3                        9
  size = 4（实际元素个数）      capacity = 10（数组长度）

查询 get(2)：直接 elementData[2]              → O(1)
尾部 add(E)：elementData[size++] = e           → O(1) 均摊
中间 add(1, E)：System.arraycopy 整体后移      → O(n)
中间 remove(1)：后面元素整体前移                → O(n)
  • 底层是 Object[] elementData，不是泛型数组（泛型擦除，运行期就是 Object[]）。
  • 默认初始容量 10，但 JDK8 起是懒加载：new ArrayList<>() 时数组是空数组 {}，第一次 add 才扩到 10。
  • 扩容 1.5 倍：newCapacity = oldCapacity + (oldCapacity >> 1)，底层靠 Arrays.copyOf 整体拷贝到新数组。
  • 查询快、随机访问 O(1)；中间插入删除要移位，性能差。
  • 线程不安全，并发 add 会丢数据甚至数组下标越界。
  • 只会扩容，不会自动缩容，remove 掉大量元素后内存不会还给你，需要手动 trimToSize()。
java
List<String> list = new ArrayList<>();      // 此时 elementData 是空数组，容量 0
list.add("a");                              // 首次 add 才真正分配 capacity = 10
List<String> sized = new ArrayList<>(1000); // ✅ 已知数据量就一次给够，避免反复扩容拷贝

// 中间插入/删除的真实代价
list.add(0, "head");   // System.arraycopy 把后面全部元素往后挪一格
list.remove(0);        // 再挪回来

加粗要点： ArrayList 的性能优势不只是「下标寻址」，更重要的是内存连续带来的 CPU 缓存命中率。所以即使是遍历场景，ArrayList 也普遍比 LinkedList 快几倍 —— 这是回答「两者区别」时最能加分的一句。

3. LinkedList：双向链表 ​

text
LinkedList 内部结构（每个 Node 持有 prev / item / next 三个引用）
  first ──► ┌──────┐ ⇄ ┌──────┐ ⇄ ┌──────┐ ◄── last
            │ null │   │      │   │      │
            │  A   │   │  B   │   │  C   │
            └──────┘   └──────┘   └──────┘ null

addFirst / addLast / removeFirst / removeLast  → O(1)，只改指针
get(index)                                      → O(n)，从头或从尾遍历一半
  • 底层双向链表，Node 节点有 prev、item、next，没有容量概念，不需要扩容。
  • 头尾增删 O(1)；随机访问要遍历，get(i) 内部会判断 i 在前半还是后半，从近的一端开始走（仍是 O(n)）。
  • 实现了 Deque，所以它天然可以当栈、队列、双端队列使用。
  • 线程不安全。
  • 内存开销远大于 ArrayList：每个元素额外多两个引用 + 对象头，单个 Node 在 64 位 JVM 开启指针压缩下约 24 字节。
java
LinkedList<String> deque = new LinkedList<>();
deque.addFirst("a");            // 当栈/双端队列用
deque.addLast("b");
deque.pollFirst();

// ❌ 最经典的误用：用下标遍历 LinkedList，复杂度直接 O(n²)
for (int i = 0; i < list.size(); i++) { list.get(i); }
// ✅ 链表必须用迭代器 / 增强 for 遍历
for (String s : list) { }

加粗要点： 面试答「频繁增删用 LinkedList」只对了一半，完整答案是 「频繁在头尾增删才用，而且现实中更应该用 ArrayDeque」：ArrayDeque 基于循环数组，同样 O(1) 头尾操作，但内存连续、没有节点对象开销，实测比 LinkedList 快一个档次。真正非用 LinkedList 不可的场景极少。

4. 线程安全的 List：Vector、synchronizedList、CopyOnWriteArrayList ​

实现加锁方式读性能写性能结论
Vector每个方法 synchronized差（也要锁）差古老，已废弃
Collections.synchronizedList包装类，方法内 synchronized差（也要锁）差偶尔用于快速改造老代码
CopyOnWriteArrayList写时整个数组复制 + ReentrantLock极好（无锁）极差（O(n) 复制）读多写极少场景（白名单、监听器列表）
java
// Vector：连 get 都要抢锁，多线程读反而比加读写锁更慢
Vector<String> v = new Vector<>();

// 包装类：注意复合操作仍然不安全
List<String> sync = Collections.synchronizedList(new ArrayList<>());
if (!sync.contains("a")) { sync.add("a"); }   // ❌ 两步之间可能被插入，需要自己 synchronized (sync) {}

// CopyOnWriteArrayList：每次 add 都 Arrays.copyOf 一份新数组再替换引用
List<String> cow = new CopyOnWriteArrayList<>();
cow.add("a");  // 写：加锁 + 复制整个数组
cow.get(0);    // 读：直接读 volatile 数组，完全不加锁

加粗要点： CopyOnWriteArrayList 换来无锁读的代价是两份内存 + 写操作 O(n)，并且迭代器是弱一致性的（遍历的是开始迭代那一刻的快照，遍历期间别人的修改看不到，但也因此永远不会抛 ConcurrentModificationException）。写多的场景用它等于自杀。

5. Set 三兄弟：本质都是包了一层 Map ​

java
// HashSet 的真实实现（JDK 源码简化）
public class HashSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object(); // 固定占位 value

    public boolean add(E e) {
        return map.put(e, PRESENT) == null; // put 返回旧值，为 null 说明是新元素
    }
}
实现底层顺序判重依据额外要求
HashSetHashMap无序（哈希顺序）hashCode() + equals()元素必须正确重写这两个方法
LinkedHashSetLinkedHashMap插入顺序同上比 HashSet 多一条双向链表的开销
TreeSetTreeMap排序顺序compareTo / Comparator 返回 0元素必须可比较，否则 ClassCastException
java
// ⚠️ TreeSet 的判重用的是比较器而不是 equals，这会造成「看起来不重复却被去掉」
TreeSet<User> set = new TreeSet<>(Comparator.comparingInt(User::getAge));
set.add(new User("张三", 20));
set.add(new User("李四", 20));   // ❌ 被当成重复元素，加不进去！因为比较器只看 age

// ⚠️ HashSet 去重失效的典型原因：只重写了 equals 没重写 hashCode
Set<User> users = new HashSet<>();
users.add(new User("张三", 20));
users.add(new User("张三", 20));
System.out.println(users.size()); // 没重写 hashCode → 2（两条一样的数据）

加粗要点： Set 的「不可重复」完全依赖元素自己的判重实现 —— 哈希类看 hashCode+equals，树类看比较结果是否为 0。用自定义对象做 Set 元素或 Map 的 key 之前，必须先确认 equals/hashCode 是否成对重写（Lombok 的 @Data、IDEA 的 Generate、Objects.hash() 都能生成）。

6. Queue 与 Deque：栈、队列、优先级队列 ​

text
队列三套 API（这就是为什么同一件事有两个方法名）
            抛异常          返回特殊值
 入队        add(e)          offer(e)   → 队列满时返回 false
 出队        remove()        poll()     → 队列空时返回 null
 查看队首    element()       peek()     → 队列空时返回 null

ArrayDeque 的循环数组（head/tail 指针绕圈走，不需要搬移元素）
   ┌───┬───┬───┬───┬───┬───┬───┬───┐
   │ D │   │   │ A │ B │ C │   │   │
   └───┴───┴───┴───┴───┴───┴───┴───┘
     ↑tail        ↑head
   addFirst → head 往左绕；addLast → tail 往右走；容量不足则翻倍扩容
实现底层用途注意点
ArrayDeque循环数组栈 / 队列 / 双端队列不允许 null（null 被用作空标记）
LinkedList双向链表队列（可存 null）节点开销大，缓存不友好
PriorityQueue二叉堆（数组）TopK、任务优先级只保证堆顶最小，遍历顺序不是有序的
ArrayBlockingQueue定长数组 + 锁线程池工作队列必须指定容量，满了会阻塞
LinkedBlockingQueue链表 + 双锁生产者消费者默认容量是 Integer.MAX_VALUE，容易 OOM
java
// ✅ Java 里用栈，首选 ArrayDeque，不要用 Stack（继承 Vector，全方法加锁）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);          // 等价 addFirst
stack.pop();            // 等价 removeFirst

// PriorityQueue 求 TopK：维护一个大小为 k 的小顶堆
PriorityQueue<Integer> heap = new PriorityQueue<>();      // 默认小顶堆
for (int num : nums) {
    heap.offer(num);
    if (heap.size() > k) heap.poll();                     // 堆顶是最小的，弹掉
}
// 堆里剩下的就是最大的 k 个；heap.peek() 是第 k 大

// 大顶堆写法
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

加粗要点： 三个必记结论 —— ① 栈用 ArrayDeque，别用 Stack；② ArrayDeque 不能存 null；③ PriorityQueue 直接 toString() 或遍历出来不是有序的，想要有序必须不断 poll()。

7. HashMap：数组 + 链表 + 红黑树 ​

text
JDK8 HashMap 结构（table 数组长度恒为 2 的 n 次方）
table
 [0] → null
 [1] → Node(k1,v1) → Node(k9,v9) → null          ← 哈希冲突，链表（尾插）
 [2] → null
 [3] → TreeNode(红黑树根)                         ← 链表过长已树化
 ...        ├── TreeNode
 [15]→ null └── TreeNode

              JDK7                         JDK8
结构      数组 + 链表                  数组 + 链表 + 红黑树
插入      头插法（并发扩容会成环）      尾插法
冲突查询  O(n)                        链表 O(n) / 红黑树 O(log n)
扩容      重新计算 hash 定位           高低位拆分，e.hash & oldCap 判断

四个必须背下来的常量：

常量值含义
DEFAULT_INITIAL_CAPACITY16（1 << 4）默认数组长度，必须是 2 的 n 次方
DEFAULT_LOAD_FACTOR0.75f负载因子，阈值 = 容量 × 0.75，超过就扩容（翻倍）
TREEIFY_THRESHOLD8链表长度 ≥ 8 时尝试树化
UNTREEIFY_THRESHOLD6扩容拆分后树节点 ≤ 6 退化回链表
MIN_TREEIFY_CAPACITY64数组容量 < 64 时优先扩容而不是树化
java
// 树化的真实判断（putVal → treeifyBin 源码简化）
if (binCount >= TREEIFY_THRESHOLD - 1) {   // 链表长度达到 8
    treeifyBin(tab, hash);
}
void treeifyBin(Node<K,V>[] tab, int hash) {
    if (tab == null || tab.length < MIN_TREEIFY_CAPACITY) {
        resize();          // ⚠️ 容量不足 64，先扩容而不是树化
    } else {
        // 真正转成红黑树
    }
}

加粗要点： 树化条件是两个条件同时满足：链表长度 ≥ 8 且 数组容量 ≥ 64。只答前半句是最常见的扣分点。原因是容量小的时候冲突多是因为「桶太少」，扩容比树化更划算、代价也更低。

8. hash 扰动与寻址：为什么容量必须是 2 的 n 次方 ​

java
// ① 扰动函数：把 hashCode 的高 16 位异或到低 16 位
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// ② 寻址：用位与代替取模
int index = (table.length - 1) & hash;
text
为什么要扰动？（容量 16 时，取模只用到 hash 的低 4 位）
  hashCode : 1111 1111 1111 1111 0000 0000 0000 0101
  (n-1)    : 0000 0000 0000 0000 0000 0000 0000 1111
  直接相与 → 高 28 位全部被丢弃，高位的差异完全不参与寻址 → 冲突率高

  h ^ (h >>> 16) 先把高 16 位的特征混进低 16 位，再相与
  → 让 hash 的高位也能影响桶下标，分布更均匀，冲突更少

为什么 (n-1) & hash 能代替 hash % n？
  n = 16  → n-1 = 0000 1111（低位全 1）
  任意 hash & 0000 1111 的结果 ∈ [0, 15]，与 hash % 16 完全等价
  前提：n 必须是 2 的 n 次方，否则 n-1 的二进制有 0 位，
        那些位永远取不到 1 → 部分桶永远空着，另一些桶冲突翻倍
  收益：位运算比除法/取模快一个数量级（CPU 层面差几十倍）
设计目的
容量恒为 2 的 n 次方让 (n-1) & hash 等价于取模，用位运算提速
高 16 位异或扰动弥补「只用低位寻址」导致的高位信息丢失，降低冲突
扩容按 2 倍保持 2 的 n 次方，且让 rehash 可以用高低位拆分优化
负载因子 0.75空间利用率与冲突概率的折中（泊松分布下冲突概率最优）
java
// 即使你传入一个奇怪的初始容量，HashMap 也会向上取整到 2 的 n 次方
Map<String, String> map = new HashMap<>(13);
// tableSizeFor(13) = 16

// tableSizeFor 的位运算推导：把最高位的 1 向右「铺满」再 +1
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;  n |= n >>> 2;  n |= n >>> 4;
    n |= n >>> 8;  n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

加粗要点： 「容量 2 的 n 次方」不是为了好看，而是同时服务了三件事：寻址可用位运算、扩容可用高低位拆分免重算 hash、桶分布均匀。回答时把这三点串起来，比只说「为了取模快」深一个层次。

9. LinkedHashMap 与 TreeMap ​

text
LinkedHashMap = HashMap 的桶结构 + 一条贯穿所有节点的双向链表
 table: [0]→Entry(A)   [3]→Entry(B)   [7]→Entry(C)
          ╱                ╱                ╱
 head ──► A ⇄ B ⇄ C ◄── tail     ← 这条链表决定了遍历顺序

 accessOrder = false（默认）→ 按插入顺序
 accessOrder = true        → get/put 命中后把节点移到链表尾部 → 天然是 LRU
实现底层顺序时间复杂度典型用途
HashMap散列表无序O(1)绝大多数场景
LinkedHashMap散列表 + 双向链表插入序 / 访问序O(1)需要稳定顺序、LRU 缓存
TreeMap红黑树key 自然序 / 比较器序O(log n)排行榜、范围查询
java
// LinkedHashMap 做 LRU：三个参数 + 重写一个方法就够了
new LinkedHashMap<K, V>(capacity, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;   // 返回 true 时自动淘汰链表头（最久未访问）
    }
};

// TreeMap 的范围查询 API（NavigableMap），HashMap 完全做不到
TreeMap<Integer, String> tree = new TreeMap<>();
tree.firstKey();                  // 最小 key
tree.lastEntry();                 // 最大项
tree.floorKey(10);                // ≤ 10 的最大 key
tree.ceilingKey(10);              // ≥ 10 的最小 key
tree.subMap(5, true, 20, false);  // [5, 20) 的子视图
tree.descendingMap();             // 倒序视图

加粗要点： 选型只看两件事 —— 要不要顺序、要不要范围查询。不要顺序用 HashMap；要插入序/访问序用 LinkedHashMap；要按 key 排序或做区间检索用 TreeMap。TreeMap 的 key 不能为 null（要比较），而 HashMap、LinkedHashMap 允许一个 null key。

10. Hashtable 与 ConcurrentHashMap ​

text
Hashtable（已废弃）
  每个方法直接 synchronized 修饰整个对象 → 全表一把锁
  线程 A 在 get(k1)，线程 B 想 put(k2) 也要排队 → 并发度 = 1

ConcurrentHashMap JDK7：分段锁 Segment
  Segment[0] → HashEntry[] ← 锁 0
  Segment[1] → HashEntry[] ← 锁 1      并发度 = Segment 个数（默认 16）
  ...                                  缺点：两层结构、内存占用大、定位要两次 hash
  Segment[15]→ HashEntry[] ← 锁 15

ConcurrentHashMap JDK8：CAS + synchronized 锁单个桶
  table
   [0] 空桶     → CAS（casTabAt）写入，完全无锁
   [1] 有节点   → synchronized (f) 锁住这个桶的头节点 f，只阻塞落到同一桶的线程
   [3] 红黑树   → synchronized 锁 TreeBin
   [5] FWD 节点 → 说明正在扩容，当前线程去 helpTransfer() 协助迁移
                                       并发度 ≈ 桶的个数，远高于 16
维度HashtableCollections.synchronizedMapConcurrentHashMap（JDK8）
锁粒度整个对象整个对象（包装的 mutex）单个桶头节点 / 空桶 CAS
并发读要加锁要加锁不加锁（Node.val 为 volatile）
key/value 为 null都不允许取决于被包装的 Map都不允许
迭代器fail-fastfail-fast弱一致（不抛 CME）
size()精确精确估算值（baseCount + CounterCell）
推荐度❌ 淘汰⚠️ 低并发可用✅ 首选
java
// 并发场景唯一正确的选择
Map<String, Integer> cache = new ConcurrentHashMap<>();

// ⚠️ 注意：单个方法是原子的，但「组合起来」不是
if (!cache.containsKey(key)) {   // ❌ 两步之间可能被别的线程插入
    cache.put(key, compute(key));
}
// ✅ 用它自带的原子方法
cache.computeIfAbsent(key, k -> compute(k));
cache.putIfAbsent(key, 0);
cache.merge(key, 1, Integer::sum);   // 原子累加

加粗要点： JDK8 的 ConcurrentHashMap 放弃了分段锁，改为 「空桶 CAS + 非空桶 synchronized 锁头节点」，锁粒度从「16 段」细化到「每个桶」，并且读操作完全无锁。记住一句总结：锁的是桶，不是表。

11. equals 与 hashCode 契约 ​

text
HashMap 判断「两个 key 是否是同一个 key」的完整流程：
  1. 算 hash → 定位桶，桶里没节点 → 直接插入
  2. 桶里有节点，逐个比较：
       p.hash == hash                       ← 先比 hash（int 比较，极快）
       && (p.key == key || key.equals(p.key)) ← 再比引用，最后才 equals
  3. 全部不相等 → 作为新节点挂到链表尾

→ 只重写 equals 不重写 hashCode：两个「相等」的对象 hash 不同
   → 落到不同的桶 → 第 1 步就分道扬镳 → map 里出现两个相等的 key
→ 只重写 hashCode 不重写 equals：落到同一个桶但 equals 为 false
   → 同样被当成两个不同的 key
约定说明
a.equals(b) 为 true → hashCode 必须相等强制，违反则集合行为错乱
hashCode 相等 → equals 不一定为 true允许，这就是哈希冲突
同一对象多次调用 hashCode 结果一致所以参与 hashCode 的字段不能可变
equals 需满足自反、对称、传递、一致性不要在 equals 里做 instanceof 的父子混用
java
// ✅ 标准写法：用 IDE 生成或 Objects 工具类，别手写
public class User {
    private final Long id;      // ⚠️ 参与 hashCode 的字段用 final
    private final String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(id, user.id) && Objects.equals(name, user.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(id, name);   // 内部就是 31 * result + field
    }
}

// ❌ 经典事故：把可变对象当 key，改完字段再也取不出来
Map<User, String> map = new HashMap<>();
User u = new User(1L, "张三");
map.put(u, "value");
u.setName("李四");          // 如果 name 可变，hashCode 变了
map.get(u);                // → null！节点还躺在旧桶里，成了内存泄漏

加粗要点： 三句话 —— ① 重写 equals 必须同时重写 hashCode；② 作为 HashMap key 的对象应当不可变（字段 final）；③ 用 Objects.hash / IDE 生成，别自己拍脑袋算。Lombok 的 @Data 会自动生成两者，但继承场景下要小心 callSuper。

12. fail-fast 与迭代器 ​

text
modCount：集合结构性修改（add/remove/clear）的次数计数器
expectedModCount：迭代器创建时拍下的快照

for (String s : list) 的真实形态
   Iterator<String> it = list.iterator();   // expectedModCount = modCount
   while (it.hasNext()) {
       String s = it.next();                // checkForComodification()
       list.remove(s);                      // ❌ modCount++，但 expectedModCount 没变
   }                                        // → 下一次 next() 抛 ConcurrentModificationException

   it.remove() 做了什么？
       list.remove(index);
       expectedModCount = modCount;         // ✅ 把快照同步回来，所以安全
机制表现代表集合
fail-fast检测到并发修改立即抛 CMEArrayList、HashMap、LinkedList、Hashtable
fail-safe（弱一致）不抛异常，遍历的是旧快照或近似视图CopyOnWriteArrayList、ConcurrentHashMap
java
List<String> list = new ArrayList<>(List.of("a", "b", "c"));

// ❌ 写法 1：for-each 中删除 → CME
for (String s : list) { if ("b".equals(s)) list.remove(s); }

// ⚠️ 写法 2：倒数第二个元素时删除「恰好」不报错（hasNext 提前返回 false）
//    这是最阴险的坑：代码在测试数据下不报错，上线换数据就炸
for (String s : list) { if ("b".equals(s)) list.remove(s); }  // 3 元素删第 2 个时静默成功

// ✅ 写法 3：迭代器删除
Iterator<String> it = list.iterator();
while (it.hasNext()) { if ("b".equals(it.next())) it.remove(); }

// ✅ 写法 4：removeIf（JDK8+，最推荐，内部就是迭代器 + 位图标记）
list.removeIf("b"::equals);

// ✅ 写法 5：倒序下标遍历（删除后不影响未遍历的下标）
for (int i = list.size() - 1; i >= 0; i--) { if ("b".equals(list.get(i))) list.remove(i); }

加粗要点： CME 的本质是 modCount != expectedModCount，它是「快速失败的保护机制」而不是「并发检测的保证」—— 单线程 for-each 里删元素同样会抛。实际开发首选 removeIf，需要同时拿到前后元素时才用 Iterator。

✨ 高级深挖知识点 ​

1. ArrayList 扩容源码逐行拆解 ​

java
// JDK8 ArrayList 核心字段
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // ⚠️ 两个空数组
transient Object[] elementData;
private int size;

public boolean add(E e) {
    ensureCapacityInternal(size + 1);   // 确保容量够
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  // 首次 add 才真正开 10
    }
    ensureExplicitCapacity(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);   // ⭐ 1.5 倍（右移 1 位 = 除 2）
    if (newCapacity - minCapacity < 0) newCapacity = minCapacity;        // 一次加太多元素
    if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);  // ⭐ 新建数组 + 整体拷贝
}
text
扩容序列（无参构造）
  new ArrayList<>()      → elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA（长度 0，懒加载）
  第 1 次 add            → 10
  第 11 次 add           → 10 + 10>>1 = 15
  第 16 次               → 15 + 7  = 22
  第 23 次               → 22 + 11 = 33 → 49 → 73 → 109 ...

  new ArrayList<>(0)     → EMPTY_ELEMENTDATA，第 1 次 add 扩到 1 → 2 → 3 → 4 → 6 ...
  （所以这两个空数组不是冗余设计，用来区分「无参」和「显式传 0」）
细节结论
默认容量10，但是懒加载：构造时数组长度为 0，首次 add 才分配
扩容倍数oldCapacity + (oldCapacity >> 1) ≈ 1.5 倍（不是 2 倍）
扩容代价Arrays.copyOf → O(n) 内存拷贝（底层 System.arraycopy，JNI 实现）
是否自动缩容不会。remove 只是把元素前移、尾部置 null，数组长度不变
手动缩容trimToSize()
已知数据量的正确姿势new ArrayList<>(expectedSize)，避免多次扩容拷贝

加粗要点： 面试被问「ArrayList 扩容」时，把 oldCapacity + (oldCapacity >> 1) 这行源码背出来，再补一句「用位运算而不是 * 1.5，且不会自动缩容」，立刻区别于只会说「1.5 倍」的候选人。

2. subList 与 Arrays.asList 的两大陷阱 ​

java
// ⚠️ 坑 1：subList 返回的是「视图」，不是新集合
List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
List<Integer> sub = list.subList(1, 3);   // [2, 3]
sub.set(0, 99);
System.out.println(list);                 // [1, 99, 3, 4, 5] ← 原集合被改了！
list.add(6);                              // 原集合结构性修改
System.out.println(sub);                  // ❌ ConcurrentModificationException

// ✅ 正确：需要独立副本就显式拷贝
List<Integer> copy = new ArrayList<>(list.subList(1, 3));

// ⚠️ 坑 2：Arrays.asList 返回的是 Arrays 的内部类 ArrayList（不是 java.util.ArrayList）
List<String> fixed = Arrays.asList("a", "b");
fixed.set(0, "x");     // ✅ 可以改元素（底层就是那个数组）
fixed.add("c");        // ❌ UnsupportedOperationException（没有实现 add）
fixed.remove(0);       // ❌ UnsupportedOperationException

// ⚠️ 坑 2.1：基本类型数组会被当成「一个元素」
int[] arr = {1, 2, 3};
List<int[]> wrong = Arrays.asList(arr);        // size = 1！
List<Integer> right = Arrays.stream(arr).boxed().collect(Collectors.toList());

// ⚠️ 坑 3：List.of（JDK9+）是真正的不可变，连 set 都不行，而且不允许 null
List<String> immutable = List.of("a", "b");
immutable.set(0, "x");   // ❌ UnsupportedOperationException
List.of("a", null);      // ❌ NullPointerException
创建方式可改元素可增删允许 null与原数组联动
new ArrayList<>()✅✅✅—
Arrays.asList(arr)✅❌✅✅ 联动
List.of(...)❌❌❌—
Collections.unmodifiableList❌❌看原集合✅ 联动
list.subList(a, b)✅✅看原集合✅ 联动

加粗要点： 凡是「视图」类 API（subList、Arrays.asList、unmodifiableList、keySet、values、entrySet）都与源数据共享存储。要独立数据，就老老实实 new ArrayList<>(原集合) 做一次拷贝。

3. LinkedList 为什么实际上比 ArrayList 更慢 ​

text
理论：ArrayList 中间插入 O(n)，LinkedList 插入 O(1)
实际：绝大多数场景 ArrayList 都更快，为什么？

① LinkedList 的 O(1) 插入前提是「你已经持有那个节点的引用」
   list.add(index, e) 实际上要先 node(index) 遍历过去 → 仍是 O(n)
   而且这个 O(n) 是「指针跳转」，ArrayList 的 O(n) 是「连续内存拷贝」

② CPU 缓存行（Cache Line，通常 64 字节）
   ArrayList ：[e0][e1][e2][e3]...  内存连续 → 一次加载命中多个元素
   LinkedList：Node 散落在堆各处  → 每次跳转都可能 cache miss（慢 ~100 倍）

③ 内存开销
   ArrayList  每个元素 = 1 个引用（4/8 字节）
   LinkedList 每个元素 = 对象头 16 + prev 4 + next 4 + item 4 ≈ 40 字节
   → 同样 100 万个元素，LinkedList 多占近 10 倍内存，GC 压力更大

④ System.arraycopy 是 intrinsic（JVM 内建）方法，底层 memmove，极快
java
// 唯一值得用 LinkedList 的场景：频繁头部增删，且不随机访问
// 但这种场景 ArrayDeque 比 LinkedList 还快（循环数组，无节点对象开销）
Deque<Integer> deque = new ArrayDeque<>();   // ✅ 实际项目的正确选择

加粗要点： 结论直接记成一句话：「工程上 99% 的场景用 ArrayList，需要双端队列用 ArrayDeque，LinkedList 基本没有使用场景。」 这也是 LinkedList 作者 Josh Bloch 本人的公开说法。能把 CPU 缓存行和内存开销说出来，是这题的加分点。

4. HashMap put 全流程（面试必背） ​

text
put(key, value)
  │
  ├─ 1. hash = key.hashCode() ^ (hashCode >>> 16)        ← 扰动
  │
  ├─ 2. table == null 或 length == 0 ？ → resize() 初始化（容量 16，阈值 12）
  │
  ├─ 3. i = (n - 1) & hash，取 p = table[i]
  │      p == null ？ → 直接 new Node 放入  ────────────────┐
  │                                                        │
  ├─ 4. p != null，判断是否同一个 key：                      │
  │      p.hash == hash && (p.key == key || key.equals(p.key))│
  │        → 是：记下 e = p，准备覆盖 value                  │
  │        → 否：                                           │
  │            ├─ p 是 TreeNode ？ → 走红黑树 putTreeVal     │
  │            └─ 否则遍历链表：                             │
  │                 ├─ 找到相同 key → e = 该节点             │
  │                 └─ 到尾部还没找到 → 尾插新节点            │
  │                      链表长度 ≥ 8 → treeifyBin()         │
  │                        └─ 容量 < 64 → resize() 而非树化   │
  │                                                         │
  ├─ 5. e != null（key 已存在）→ oldValue = e.value          │
  │        onlyIfAbsent 为 false 时 e.value = value          │
  │        return oldValue   ⭐ 注意：这种情况 size 不变，不扩容 │
  │                                                         │
  └─ 6. ++size > threshold ？ → resize() 扩容 ◄──────────────┘
         afterNodeInsertion(evict)   ← LinkedHashMap 的 LRU 钩子
java
// 一个高频追问：put 返回值是什么？
Map<String, Integer> map = new HashMap<>();
Integer r1 = map.put("a", 1);   // null  ← key 不存在，返回 null
Integer r2 = map.put("a", 2);   // 1     ← 返回被覆盖的旧值

// 所以这段代码有歧义：返回 null 到底是「没有这个 key」还是「value 本来就是 null」？
if (map.get("k") == null) { ... }        // ❌ 二义性
if (!map.containsKey("k")) { ... }       // ✅ 明确

加粗要点： 这张流程图要能从「扰动」一路口述到「扩容」，关键节点有 5 个：扰动 hash → 位与寻址 → 空桶直插 → 链表/红黑树 → 判断是否超阈值扩容。再记住两个条件分支：树化要容量 ≥ 64、覆盖已有 key 不会触发扩容。

5. 扩容的高低位拆分：e.hash & oldCap ​

text
JDK8 最精妙的优化：扩容后节点的新下标只有两种可能
  旧容量 16 → 新容量 32
  旧下标 i = hash & 15（低 4 位）
  新下标     = hash & 31（低 5 位）
  → 差别仅在于「第 5 位（即 oldCap=16 这一位）」是 0 还是 1

  hash & oldCap == 0  →  新下标 = 原下标 i        （留在低位链 loHead）
  hash & oldCap != 0  →  新下标 = 原下标 i + 16   （搬到高位链 hiHead）

举例：oldCap = 16
  hash = ...0 0101  & 15 = 5    & 16 = 0  → 新下标仍是 5
  hash = ...1 0101  & 15 = 5    & 16 = 16 → 新下标 5 + 16 = 21

迁移示意
  旧 table[5] : A → B → C → D
                ↓ 按 e.hash & 16 拆成两条链（保持相对顺序）
  新 table[5] : A → C          （lo 链）
  新 table[21]: B → D          （hi 链）
java
// resize() 中链表拆分的源码（简化）
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {      // ⭐ 核心判断，不需要重算 hash，不需要重新取模
        if (loTail == null) loHead = e; else loTail.next = e;
        loTail = e;
    } else {
        if (hiTail == null) hiHead = e; else hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
维度JDK7JDK8
迁移方式遍历每个节点，indexFor 重新计算下标e.hash & oldCap 判断高低位
是否重算 hash要重新取模不用，只做一次位与
链表顺序头插 → 顺序反转尾插 → 保持原相对顺序
并发下的后果可能形成环形链表导致 CPU 100%不会成环（但仍可能丢数据，依旧不安全）

加粗要点： e.hash & oldCap 这一行是 JDK8 HashMap 的灵魂：把「重新取模」变成「一次位与」，把「全量 rehash」变成「链表二分」。它成立的前提依然是容量为 2 的 n 次方，和前面的寻址优化是同一套设计在呼应。

6. JDK7 并发扩容的死循环 ​

text
JDK7 transfer 用头插法，两个线程同时扩容时：
  初始 旧桶: A → B → null

  线程 1 执行到 e = A, next = B 后被挂起
  线程 2 完整执行完迁移，头插导致顺序反转 → 新桶: B → A → null

  线程 1 恢复，它手里的 e = A, next = B（旧快照）
    put A → 新桶: A → ...
    e = B，put B，头插 → B.next = A
    e = A（B.next 在线程 2 的结果里指向 A）
    put A，头插 → A.next = B

  最终:  A ⇄ B   形成环形链表
  后续任何 get() 落到这个桶 → while 死循环 → CPU 飙到 100%
java
// JDK7 的罪魁祸首（头插）
void transfer(Entry[] newTable) {
    for (Entry<K,V> e : table) {
        while (null != e) {
            Entry<K,V> next = e.next;
            int i = indexFor(e.hash, newTable.length);
            e.next = newTable[i];     // ⚠️ 头插：新节点指向原头节点
            newTable[i] = e;
            e = next;
        }
    }
}
问题JDK7JDK8
死循环（成环）会不会（改尾插 + 高低位拆分）
数据丢失会仍然会（两个线程同时写同一个空桶）
size 不准会仍然会（++size 非原子）
结论都不能在并发下用 HashMap，要用 ConcurrentHashMap

加粗要点： 「HashMap 线程不安全」的标准答案是分版本的：JDK7 的典型故障是扩容成环导致 CPU 100%，JDK8 修掉了成环，但数据覆盖丢失和 size 不准依然存在。千万不要说「JDK8 的 HashMap 已经安全了」。

7. 为什么树化阈值是 8，退化阈值是 6 ​

text
HashMap 源码注释里给出的泊松分布数据（负载因子 0.75 时，桶内节点数的概率）
  0:  0.60653066
  1:  0.30326533
  2:  0.07581633
  3:  0.01263606
  4:  0.00157653
  5:  0.00015757
  6:  0.00001316
  7:  0.00000094
  8:  0.00000006      ← 概率约为千万分之六，几乎不可能发生

结论：
  ① 选 8 → 正常情况下永远不会触发树化，树化只是「极端 hash 冲突」的兜底保险
  ② TreeNode 的体积约是普通 Node 的 2 倍，无脑树化纯属浪费内存
  ③ 链表长度小于 8 时，O(n) 遍历的实际开销并不比 O(log n) 的红黑树差
     （红黑树还有旋转、变色、比较器调用的额外成本）

为什么退化阈值是 6，而不是 8？
  如果树化和退化都用 8，那么节点数在 7 ⇄ 8 之间反复抖动时，
  会不停地「树化 → 退化 → 树化」，频繁结构转换代价极高。
  中间留一个 7 作为缓冲区 → 这就是「滞后/迟滞（hysteresis）」设计。
阈值值设计动机
TREEIFY_THRESHOLD8泊松分布下概率 ≈ 6e-8，作为兜底而非常态
UNTREEIFY_THRESHOLD6与 8 之间留缓冲，避免临界点反复抖动
MIN_TREEIFY_CAPACITY64小表冲突多是桶太少，扩容比树化更划算
java
// 一个有意思的追问：红黑树节点之间怎么比较大小？
// ① 先比 hash
// ② hash 相同且 key 实现了 Comparable → compareTo
// ③ 都不行 → tieBreakOrder：用 System.identityHashCode 兜底，保证有确定顺序
static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b)) ? -1 : 1;
    return d;
}

加粗要点： 这题考的是「是否读过源码注释」。答题公式：8 来自泊松分布的概率兜底，6 是为了防止临界抖动，两者之间留 7 作缓冲，再补一句树化还要求容量 ≥ 64。

8. 负载因子 0.75 与初始容量预估 ​

text
负载因子 = 阈值 / 容量，决定「多满就扩容」

  负载因子太小（如 0.5）→ 数组很空就扩容 → 空间浪费、扩容频繁
  负载因子太大（如 1.0）→ 冲突链变长    → 查询退化成 O(n)
  0.75 = 3/4 → 阈值 = capacity * 3 / 4，而容量是 2 的 n 次方
             → 这个乘法结果一定是整数，不会有浮点误差（设计上的小心思）

初始容量怎么算？目标是「放完所有元素都不触发扩容」
  需要 n 个元素 → 容量必须满足 容量 * 0.75 > n → 容量 > n / 0.75
  例：要放 1000 个元素
      1000 / 0.75 = 1333.3 → 向上取 2 的 n 次方 → 2048
      ❌ new HashMap<>(1000)  → tableSizeFor(1000)=1024，阈值 768，放到第 769 个就扩容
      ✅ new HashMap<>(2048)
      ✅ Maps.newHashMapWithExpectedSize(1000)   // Guava，内部已算好
java
// JDK 自带的正确算法（Guava 同思路）
int initialCapacity = (int) (expectedSize / 0.75F) + 1;
Map<String, Object> map = new HashMap<>(initialCapacity);

// 阿里规约：集合初始化时指定容量
// 原因：默认 16，放 1000 个元素要扩容 7 次（16→32→...→2048）
//       每次扩容都是 O(n) 的 rehash + 数组分配，还会产生大量垃圾对象

// 验证扩容次数的小技巧（反射看 table 长度）
Field f = HashMap.class.getDeclaredField("table");
f.setAccessible(true);
System.out.println(((Object[]) f.get(map)).length);
负载因子空间利用率冲突概率适用
0.5低很低内存充足、极致读性能
0.75均衡低默认，绝大多数场景
1.0高高内存极度紧张且数据量可控

加粗要点： 两个记忆点：① 0.75 是时间与空间的权衡，且能保证 容量 × 0.75 一定是整数；② 预估容量公式 expectedSize / 0.75 + 1，别直接把元素个数当容量传进去 —— 这是最常见的「以为自己优化了其实没有」。

9. ConcurrentHashMap JDK8 源码四个关键点 ​

java
// ① initTable：用 sizeCtl 的 CAS 实现「只有一个线程初始化」
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield();                       // 别的线程在初始化，让出 CPU 自旋等待
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {  // CAS 抢到初始化权
            try { /* 真正创建数组 */ } finally { sizeCtl = sc; }
        }
    }
    return tab;
}

// ② putVal：空桶 CAS，非空桶锁头节点
for (Node<K,V>[] tab = table;;) {
    if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        if (casTabAt(tab, i, null, new Node<>(hash, key, value, null)))
            break;                                // ⭐ 空桶：CAS 成功即结束，全程无锁
    } else if ((fh = f.hash) == MOVED) {
        tab = helpTransfer(tab, f);               // ⭐ 遇到 ForwardingNode，协助扩容
    } else {
        synchronized (f) {                        // ⭐ 只锁这一个桶的头节点
            // 链表尾插 / 红黑树插入
        }
    }
}

// ③ get 为什么不用加锁
static final class Node<K,V> {
    final int hash;
    final K key;
    volatile V val;              // ⭐ volatile 保证可见性
    volatile Node<K,V> next;     // ⭐ volatile
}
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>) U.getObjectVolatile(tab, ((long) i << ASHIFT) + ABASE);  // volatile 读
}
text
④ 多线程协助扩容：ForwardingNode + transferIndex
  扩容时把旧表按「步长 stride」切成多个区间，各线程各领一段
    transferIndex = n（从后往前分配）
    线程 A 领 [n-stride, n)   线程 B 领 [n-2*stride, n-stride) ...

  某个桶迁移完成后，旧表该位置放一个 ForwardingNode（hash = MOVED = -1）
    其他线程读到 FWD → 去新表查（find 方法）
    其他线程写到 FWD → helpTransfer() 加入协助迁移

  这就是 JDK8 CHM 相比 JDK7 的第二个大提升：
    JDK7 扩容是「单线程扩容，其他线程阻塞」
    JDK8 是「多线程并行迁移」
操作并发控制手段
初始化sizeCtl 的 CAS + Thread.yield() 自旋
写空桶casTabAt（Unsafe CAS），无锁
写非空桶synchronized (头节点 f)，锁粒度 = 单个桶
读volatile 读 + volatile 字段，完全无锁
扩容ForwardingNode 标记 + transferIndex 分段，多线程协助

加粗要点： 把这四句话背下来就足以应对绝大多数 CHM 面试：「空桶 CAS、非空桶 synchronized 锁头节点、读靠 volatile 完全无锁、扩容靠 ForwardingNode 让多线程协助迁移。」

10. ConcurrentHashMap 的 size() 为什么是估算值 ​

java
// CHM 没有用一个 volatile int size（那会成为并发瓶颈，所有线程都在抢同一个变量）
// 而是借鉴 LongAdder 的「分段累加」思想
private transient volatile long baseCount;        // 无竞争时累加到这里
private transient volatile CounterCell[] counterCells;  // 有竞争时分散到数组

final long sumCount() {
    CounterCell[] as = counterCells;
    long sum = baseCount;
    if (as != null)
        for (CounterCell a : as)
            if (a != null) sum += a.value;         // ⚠️ 遍历求和期间，别的线程还在改
    return sum;
}

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 : (n > Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) n);
}
public long mappingCount() { return Math.max(sumCount(), 0L); }  // ⭐ 推荐用这个，返回 long
text
分段累加示意
  线程 1 ─┐
  线程 2 ─┼─ CAS baseCount 失败 → 转而写入自己哈希到的 CounterCell
  线程 3 ─┘
            baseCount = 100
            counterCells = [ 12 | 7 | — | 23 | — ]
            size ≈ 100 + 12 + 7 + 23 = 142

  好处：把「一个热点变量」拆成「多个独立变量」→ 消除 CAS 竞争（伪共享用 @Contended 解决）
  代价：size() 是遍历求和，结果是某个时间点的「近似快照」，不保证精确

加粗要点： 答题要点：CHM 的 size() 用 baseCount + CounterCell[] 分段累加（同 LongAdder），目的是消除单一计数器的 CAS 热点，代价是结果只是估算值。所以绝对不要用 chm.size() 做精确的业务判断（比如「满 100 个就触发」），JDK8+ 还提供了返回 long 的 mappingCount()。

11. 为什么 ConcurrentHashMap 不允许 null ​

text
HashMap（单线程）：get(k) 返回 null 有二义性，但可以用 containsKey 消除
  map.get("k") == null
    ├─ 可能：没有这个 key
    └─ 可能：有这个 key，但 value 就是 null
  → 再调一次 map.containsKey("k") 就能区分  ✅

ConcurrentHashMap（并发）：containsKey 也救不了你
  线程 A: chm.get("k")        → null
  线程 A: chm.containsKey("k") → false
         ↑ 这两步之间，线程 B 可能刚好 put 或 remove 了 "k"
  → 两次调用的结果无法复合成一个可信结论 → 二义性「不可消除」

所以 Doug Lea 的选择是：从源头禁止 null，让 get 返回 null 有且只有一个含义 ——
  「这个 key 不存在」
java
// 源码直接抛 NPE
public V put(K key, V value) {
    if (key == null || value == null) throw new NullPointerException();
    // ...
}

// 各集合对 null 的态度，这是一张高频考题表
集合key / 元素为 nullvalue 为 null
HashMap✅ 允许一个（放在 table[0]，hash 固定为 0）✅ 允许
LinkedHashMap✅ 允许一个✅ 允许
TreeMap❌ NPE（要比较大小）✅ 允许
Hashtable❌ NPE❌ NPE
ConcurrentHashMap❌ NPE❌ NPE
ArrayList / LinkedList✅ 允许多个—
ArrayDeque❌ NPE（null 是队空标记）—
List.of / Map.of❌ NPE❌ NPE
HashSet✅ 允许一个—
TreeSet❌ NPE—

加粗要点： 标准答案一句话：「并发环境下 get 返回 null 的二义性无法通过 containsKey 消除（两次调用之间状态可能已变），所以干脆禁止 null。」 补充记忆：HashMap 的 null key 固定存在 table[0]，因为 hash(null) 直接返回 0。

12. 复合操作的原子性与弱一致迭代器 ​

java
ConcurrentHashMap<String, Integer> counter = new ConcurrentHashMap<>();

// ❌ 错误 1：check-then-act 不原子
if (!counter.containsKey(k)) counter.put(k, 1);

// ❌ 错误 2：read-modify-write 不原子（丢更新的经典案例）
counter.put(k, counter.get(k) + 1);

// ❌ 错误 3：以为加了 synchronized 就万事大吉（锁对了，但完全丧失并发性能）
synchronized (this) { counter.put(k, counter.get(k) + 1); }

// ✅ 正确：用 CHM 提供的原子复合方法
counter.merge(k, 1, Integer::sum);              // 最简洁的原子累加
counter.compute(k, (key, v) -> v == null ? 1 : v + 1);
counter.computeIfAbsent(k, key -> loadFromDb(key));
counter.putIfAbsent(k, 0);
counter.replace(k, oldVal, newVal);             // CAS 语义

// ✅ 高并发计数的更优解：value 用 LongAdder，避免每次都走 CHM 的桶锁
ConcurrentHashMap<String, LongAdder> fast = new ConcurrentHashMap<>();
fast.computeIfAbsent(k, key -> new LongAdder()).increment();
text
⚠️ computeIfAbsent 的两个致命坑

坑 1：mapping 函数里不能再操作同一个 map（JDK8 会死锁 / 死循环）
  map.computeIfAbsent("a", k -> {
      map.put("b", 1);        // ❌ 可能死锁：b 恰好 hash 到同一个桶，而该桶已被当前线程 synchronized
      return 1;
  });

坑 2：mapping 函数耗时很长（如远程调用）会把整个桶锁住
  map.computeIfAbsent(k, key -> rpcCall(key));   // ⚠️ 同桶的其他 key 全部阻塞
  → 缓存场景应改为「先 get，miss 再加载，最后 putIfAbsent」或用 Caffeine
迭代器类型行为代表
fail-fast结构变化立即抛 CMEArrayList、HashMap
弱一致（weakly consistent）不抛 CME；能看到创建后的部分修改，但不保证全部ConcurrentHashMap
快照（snapshot）完全基于创建时的数组副本，后续修改一概看不到CopyOnWriteArrayList

加粗要点： ConcurrentHashMap 只保证单个方法的原子性，不保证多个方法组合的原子性。遇到「判断再写」「读改写」一律换成 merge / compute / computeIfAbsent / putIfAbsent。另外记住 computeIfAbsent 的函数体里绝不能回头操作同一个 map。

13. CopyOnWriteArrayList 的适用边界 ​

java
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();                                  // 写操作加独占锁（JDK11 后改为 synchronized）
    try {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);          // ⭐ 每次写都复制整个数组
        es[len] = e;
        setArray(es);                             // ⭐ volatile 写，一次性切换引用
        return true;
    } finally { lock.unlock(); }
}

public E get(int index) {
    return elementAt(getArray(), index);          // ⭐ 读完全无锁，无 volatile 开销之外的成本
}
text
写时复制（Copy-On-Write）示意
  读线程持有的引用 ──► [a][b][c]       ← 老数组，读线程继续安全遍历
  写线程            ──► [a][b][c][d]   ← 复制一份加上 d，然后 array = 新数组

  ⇒ 读写不互斥，读永远不会被阻塞，也永远不会抛 CME
  ⇒ 但迭代器拿到的是「创建那一刻的快照」，看不到之后的写入
  ⇒ 写操作 O(n)：10 万元素的列表，每次 add 都复制 10 万个引用
维度CopyOnWriteArrayListCollections.synchronizedList
读性能极高（无锁）低（要抢锁）
写性能极低（O(n) 复制 + 独占锁）中（锁但不复制）
内存写时双倍占用正常
迭代器快照，不抛 CME，不支持 removefail-fast
数据实时性最终一致（读可能读到旧数据）强一致
适用读远多于写：配置、白名单、监听器列表写较频繁且并发不高
java
// ✅ 典型正确用法：事件监听器列表（注册少、遍历多）
private final List<Listener> listeners = new CopyOnWriteArrayList<>();
public void fire(Event e) {
    for (Listener l : listeners) l.onEvent(e);   // 遍历期间可安全注册/注销
}

// ❌ 典型误用：拿它当高并发写入的队列
List<Order> orders = new CopyOnWriteArrayList<>();
// 每秒上千次 add → 每次复制整个数组 → GC 爆炸、CPU 打满
// 这种场景应该用 ConcurrentLinkedQueue / LinkedBlockingQueue

加粗要点： CopyOnWriteArrayList 的定位非常窄：「读多写极少、能接受最终一致、数据量不大」。三个场景之外都不要用。它和 ConcurrentHashMap 的核心区别是 —— CHM 是细粒度锁换并发，COW 是牺牲写性能换读无锁。

14. Stream 转集合的四个坑 ​

java
List<User> users = List.of(new User(1L, "张三"), new User(2L, null), new User(1L, "李四"));

// ❌ 坑 1：key 重复直接抛 IllegalStateException: Duplicate key
Map<Long, String> m1 = users.stream()
        .collect(Collectors.toMap(User::getId, User::getName));
// ✅ 给第三个参数：合并函数
Map<Long, String> m2 = users.stream()
        .collect(Collectors.toMap(User::getId, User::getName, (a, b) -> b));  // 后者覆盖前者

// ❌ 坑 2：value 为 null 抛 NullPointerException（toMap 内部调 map.merge，不接受 null value）
//    注意：groupingBy 没这个问题，但它的 key 不能为 null
Map<Long, String> m3 = users.stream()
        .collect(Collectors.toMap(User::getId, u -> u.getName() == null ? "" : u.getName(), (a, b) -> b));

// ❌ 坑 3：Collectors.toList() 返回的实现类不保证是 ArrayList（规范未约定）
//    JDK16+ 的 stream().toList() 返回的是「不可变」List，add 会抛异常
List<String> l1 = users.stream().map(User::getName).collect(Collectors.toList());  // 可变
List<String> l2 = users.stream().map(User::getName).toList();                      // ⚠️ 不可变
// ✅ 想要确定的可变 ArrayList
List<String> l3 = users.stream().map(User::getName)
        .collect(Collectors.toCollection(ArrayList::new));

// ❌ 坑 4：toMap 默认返回 HashMap（无序），需要保序要显式指定
Map<Long, String> ordered = users.stream().collect(Collectors.toMap(
        User::getId, User::getName, (a, b) -> b, LinkedHashMap::new));
需求正确写法
key 可能重复toMap(k, v, (a, b) -> b) 指定合并策略
value 可能为 null在 valueMapper 里兜底，或改用 groupingBy
需要可变 Listcollect(Collectors.toCollection(ArrayList::new))
需要保持顺序的 MaptoMap(k, v, merge, LinkedHashMap::new)
分组groupingBy(User::getDeptId) → Map<Long, List<User>>
分组计数groupingBy(User::getDeptId, Collectors.counting())
并行流收集到线程安全容器collect(Collectors.toConcurrentMap(...))

加粗要点： Collectors.toMap 是线上事故高发区：key 重复抛 IllegalStateException、value 为 null 抛 NullPointerException。工程上永远传第三个合并参数。另外注意 JDK16 的 stream().toList() 是不可变的，和 collect(toList()) 不等价。

15. 不可变集合与防御性拷贝 ​

java
// ① Collections.unmodifiableXxx —— 只读「视图」，源集合改了它也跟着改
List<String> src = new ArrayList<>(List.of("a"));
List<String> view = Collections.unmodifiableList(src);
src.add("b");
System.out.println(view);        // [a, b] ← ⚠️ 并非真正不可变

// ② List.of / Map.of / Set.of（JDK9+）—— 真正不可变，但不允许 null
List<String> real = List.of("a", "b");
Map<String, Integer> m = Map.of("a", 1, "b", 2);          // 最多 10 对
Map<String, Integer> many = Map.ofEntries(Map.entry("a", 1), Map.entry("b", 2));

// ③ 浅不可变 ≠ 深不可变
List<User> list = List.of(new User(1L, "张三"));
list.get(0).setName("李四");     // ⚠️ 元素内部状态照样能改

// ✅ 防御性拷贝：getter 不要直接把内部集合引用交出去
public class Order {
    private final List<Item> items = new ArrayList<>();

    public List<Item> getItems() {
        return Collections.unmodifiableList(items);   // 或 new ArrayList<>(items)
    }
    // ❌ return items;  → 调用方可以 order.getItems().clear() 直接破坏内部状态
}
方式真不可变允许 null与源联动额外内存
Collections.unmodifiableList❌（视图）看源集合✅极小
List.of / Map.of✅❌❌小（紧凑实现）
new ArrayList<>(src)❌（可变副本）✅❌O(n)
Guava ImmutableList.copyOf✅❌❌O(n)

加粗要点： 三句话：① unmodifiableXxx 是只读视图不是不可变集合；② List.of 才是真不可变，但禁 null；③ 所有不可变集合都只是「浅」不可变，元素内部状态仍可改。类的 getter 返回集合时一定要做防御性拷贝或包只读视图。

16. 集合选型决策表与内存开销 ​

text
选型决策树
  需要键值对吗？
    ├─ 是 → 需要并发安全？
    │        ├─ 是 → ConcurrentHashMap
    │        └─ 否 → 需要顺序？
    │                 ├─ 插入序/访问序 → LinkedHashMap（LRU 用 accessOrder=true）
    │                 ├─ key 排序/范围查询 → TreeMap
    │                 └─ 不需要 → HashMap
    └─ 否 → 需要去重？
             ├─ 是 → 需要顺序？LinkedHashSet / TreeSet，否则 HashSet
             └─ 否 → 访问模式？
                      ├─ 随机访问为主 → ArrayList
                      ├─ 双端增删     → ArrayDeque
                      ├─ 取最大/最小   → PriorityQueue
                      ├─ 读多写极少且并发 → CopyOnWriteArrayList
                      └─ 生产者消费者  → LinkedBlockingQueue / ArrayBlockingQueue
容器单元素额外开销（64 位 JVM，开启指针压缩）说明
ArrayList≈ 4 字节（一个引用）+ 空余槽位最省内存的集合
LinkedList≈ 40 字节（Node 对象头 + 3 个引用）约 ArrayList 的 10 倍
HashMap≈ 36 字节（Node：头 16 + hash 4 + 3 引用）还要算上 table 数组的空槽
TreeMap≈ 40 字节（Entry 多了 color、parent）比 HashMap 略高
ConcurrentHashMap≈ 36 字节 + CounterCell 开销与 HashMap 接近
java
// 存大量基本类型时，自动装箱是隐形的内存杀手
List<Integer> boxed = new ArrayList<>();   // 每个 Integer 对象 16 字节 + 引用 4 字节 = 20
int[] raw = new int[n];                    // 每个 4 字节 → 省 5 倍内存
// 超大量基本类型建议直接用数组，或引入 Eclipse Collections / fastutil 的原始类型集合

// Integer 缓存池的坑（-128 ~ 127 复用同一对象）
Integer a = 127, b = 127;   System.out.println(a == b);  // true
Integer c = 128, d = 128;   System.out.println(c == d);  // false ← 必须用 equals
Map<Integer, String> map = new HashMap<>();
map.put(1000, "x");
System.out.println(map.get(1000));   // ✅ "x"，因为 HashMap 用 equals 比较，不是 ==

加粗要点： 选型先问三个问题：要不要键值对、要不要有序、要不要并发安全。性能优化层面记住两点：LinkedList 的内存是 ArrayList 的近 10 倍、大量基本类型别用包装类集合。

17. 遍历 Map 的五种方式与性能差异 ​

java
Map<String, Integer> map = new HashMap<>();

// ① keySet + get ——❌ 最差，每个 key 都要再查一次 hash（两次遍历成本）
for (String k : map.keySet()) { Integer v = map.get(k); }

// ② entrySet —— ✅ 推荐，一次遍历同时拿到 key 和 value
for (Map.Entry<String, Integer> e : map.entrySet()) {
    String k = e.getKey();  Integer v = e.getValue();
    e.setValue(v + 1);            // ⭐ 只有 entrySet 能原地改 value
}

// ③ 迭代器 —— ✅ 需要边遍历边删除时用
Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getValue() == null) it.remove();
}

// ④ forEach（JDK8）—— ✅ 代码最简洁，但不能 break、不能删除
map.forEach((k, v) -> System.out.println(k + "=" + v));

// ⑤ Stream —— 适合「遍历 + 过滤 + 转换」一气呵成，单纯遍历反而更慢
map.entrySet().stream()
   .filter(e -> e.getValue() > 10)
   .forEach(e -> System.out.println(e.getKey()));

// ✅ 批量删除的最佳写法
map.entrySet().removeIf(e -> e.getValue() == null);
map.values().removeIf(Objects::isNull);           // keySet/values/entrySet 都是视图，删除会反映到源 map
方式需要 value可改 value可删除可 break评价
keySet + get❌ 低效间接❌✅不要用
entrySet✅✅❌✅默认选择
Iterator✅✅✅✅要删除时用
forEach✅✅❌❌简洁场景
removeIf✅❌✅—批量删除首选

加粗要点： 遍历 Map 默认用 entrySet（keySet + get 等于查两遍哈希表），边遍历边删用 Iterator 或 removeIf。顺带记住 keySet() / values() / entrySet() 返回的都是视图，对它们的删除会直接作用在源 Map 上。

18. 比较器契约与 Comparison method violates its general contract! ​

这是 Java 集合里**最典型的「本地测不出、上量才炸」**的异常，根因不是 JDK 的 bug，而是自己写的 Comparator 违反了契约。

三条契约（必须同时满足）：

契约形式化表述最常见的违反写法
反对称性sgn(compare(a,b)) == -sgn(compare(b,a))漏掉「相等返回 0」，相等时两边都返回 -1
传递性compare(a,b)>0 && compare(b,c)>0 ⇒ compare(a,c)>0多字段比较时分支写漏、互相覆盖
等价传递compare(a,b)==0 ⇒ sgn(compare(a,c)) == sgn(compare(b,c))相等判定依据和排序依据不是同一个字段
java
// ❌ 违约写法 1：漏掉「相等返回 0」—— 直接违反反对称性
list.sort((a, b) -> a.getScore() > b.getScore() ? 1 : -1);
// 当 a.score == b.score 时，compare(a,b) = -1，compare(b,a) 也 = -1
// 两个元素互相认为「我比你小」，TimSort 归并时发现 run 不单调 → 抛异常

// ❌ 违约写法 2：整数相减溢出
list.sort((a, b) -> a.getBalance() - b.getBalance());
// balance 是 int 且跨正负大数时，相减溢出符号翻转：
// 2_000_000_000 - (-2_000_000_000) = -294_967_296 → 结果变成「大的更小」

// ❌ 违约写法 3：比较依据不稳定（随机数 / 当前时间 / 可变字段）
list.sort((a, b) -> Double.compare(Math.random(), 0.5));          // 每次比较结果都不同
list.sort((a, b) -> Long.compare(a.refreshAt(), b.refreshAt()));  // 排序过程中字段被别的线程改了

// ❌ 违约写法 4：null 字段直接 NPE 或被当成最小值随意处理
list.sort((a, b) -> a.getName().compareTo(b.getName()));          // name 为 null 直接炸

// ✅ 正确写法：全部交给 Comparator 工厂方法，杜绝手写分支
list.sort(Comparator
        .comparingInt(User::getAge)                               // 不会溢出（内部用 Integer.compare）
        .thenComparing(User::getName, Comparator.nullsLast(Comparator.naturalOrder()))
        .thenComparing(User::getId));                             // ⭐ 兜底加一个唯一字段，保证全序

为什么「小数据量不报、上量才报」：

text
Arrays.sort(Object[])  →  TimSort
   ├─ 数组长度 < 32（MIN_MERGE）→ 走 binarySort（二分插入排序）
   │                             不做 run 合并，不校验契约 → 违约也不报错，只是结果顺序乱
   └─ 数组长度 ≥ 32              → 切分 run + 归并
                                   mergeLo / mergeHi 里依赖「run 内单调」这一前提
                                   发现越界 → throw IllegalArgumentException
                                              ("Comparison method violates its general contract!")

所以这个异常的本质是：违约一直存在，只是数据量小的时候表现为「排序结果不对」，数据量大了才表现为「抛异常」。线上报这个错，不要去查 JDK 版本，直接去审 Comparator。

-Djava.util.Arrays.useLegacyMergeSort=true 能让异常消失，但这是掩盖问题：它只是退回 JDK6 的归并排序（不校验契约），排序结果依然是错的，而且多占一倍临时内存。只应作为「线上紧急止血 + 当天修比较器」的手段。

另一个隐蔽后果：比较器与 equals 不一致

java
TreeSet<User> set = new TreeSet<>(Comparator.comparingInt(User::getAge));
set.add(new User(1, "张三", 20));
set.add(new User(2, "李四", 20));     // ⚠️ 加不进去！size 仍为 1
// TreeMap / TreeSet 判重用的是 compare(a,b) == 0，完全不看 equals
// 两个 equals 不等的对象，只要年龄相同就被认为是「同一个元素」

set.contains(new User(99, "王五", 20));  // → true，但 HashSet 下会是 false
容器判重依据不一致时的症状
HashSet / HashMaphashCode + equals—
TreeSet / TreeMapcompare() == 0元素被误去重、contains 结果反直觉
List.containsequals和 TreeSet.contains 结论可能相反

排序稳定性也要记住：Arrays.sort(int[]) 等基本类型用双轴快排（不稳定，但基本类型没有「相等但不同」的概念，无影响）；Arrays.sort(Object[]) 和 List.sort 用 TimSort（稳定），这是「先按 A 排再按 B 排」能叠加生效的前提。

加粗要点： Comparison method violates its general contract! 是自己的比较器违约，不是 JDK 问题。三条铁律：绝不用 a - b 相减（用 Integer.compare）、绝不漏掉相等返回 0（用 Comparator.comparing 系列工厂方法而不是手写三元）、多字段链末尾补一个唯一字段保证全序。另外记住 TreeSet/TreeMap 判重只看 compare()==0，完全不看 equals，比较器只比一个字段就会把不同对象误去重。

19. 三个特种 Map：EnumMap、IdentityHashMap、WeakHashMap ​

这三个平时用得少，但它们各自解决一类「普通 HashMap 解决不了」的问题，面试问到能答出场景就很加分。

实现底层key 判等依据典型场景
EnumMap数组，下标 = ordinal()枚举身份（==）枚举做 key 的所有场景
IdentityHashMap线性探测的平坦数组== 引用相等对象图遍历去重、序列化/深拷贝防循环引用
WeakHashMap数组 + 链表，key 是弱引用equalskey 生命周期由外部决定的旁路缓存
java
// ① EnumMap：没有 hash、没有冲突、没有扩容，就是一个数组
EnumMap<Status, Integer> counter = new EnumMap<>(Status.class);
counter.put(Status.PAID, 10);
// 内部：vals[Status.PAID.ordinal()] = 10
// 优势：O(1) 且常数极小、迭代顺序天然按枚举声明顺序、内存只有 HashMap 的几分之一
// ⚠️ 不接受 null key；ordinal 依赖枚举声明顺序，但它不会被持久化，所以改枚举顺序是安全的

// ② IdentityHashMap：故意不用 equals
Map<Object, Object> visited = new IdentityHashMap<>();
void deepCopy(Object node) {
    if (visited.containsKey(node)) return;   // 只有「同一个对象」才算访问过
    visited.put(node, Boolean.TRUE);
    // ...
}
// 为什么不能用 HashMap：两个 equals 相等但不同的节点会被误判为「已访问」，
// 导致对象图被错误折叠。JDK 的序列化、Jackson 的循环引用检测都用它。
// ⚠️ 它故意违反 Map 接口契约（Map 规定用 equals），别当通用 Map 用

// ③ WeakHashMap：key 没人引用了，整个 entry 自动消失
Map<ClassLoader, Config> cache = new WeakHashMap<>();
cache.put(loader, config);
loader = null;        // 外部不再引用 key
System.gc();          // GC 后这个 entry 会被自动清掉（下次访问 map 时清理队列）

WeakHashMap 的两个致命误解：

java
// ❌ 误解 1：以为「value 没人用了也会被回收」—— 弱的是 key，不是 value
Map<String, byte[]> cache = new WeakHashMap<>();
cache.put(key, new byte[10 * 1024 * 1024]);
// 如果 value 内部直接或间接引用了 key，就形成「强引用环」：
// Entry.value → key，而 Entry 被 table 强引用 → key 永远不会被回收 → 永不失效的泄漏

// ❌ 误解 2：用字符串常量当 key
cache.put("userConfig", config);     // 字面量在常量池里被永久强引用 → 这个 entry 永远不会回收

// ✅ 正确姿势：key 必须是「生命周期由外部明确控制」的对象
// 典型：ClassLoader、Thread、Class、框架里的组件实例

顺带讲清 ThreadLocal 内存泄漏的真正机制（面试高频，很多人答错）：

text
Thread 对象
  └─ threadLocals: ThreadLocalMap
       └─ Entry[]           ← Entry extends WeakReference<ThreadLocal<?>>
            ├─ key   : 弱引用指向 ThreadLocal 实例   ← ThreadLocal 没人引用时会被回收 → key = null
            └─ value : 强引用指向你放进去的值         ← ⚠️ 没人清，就一直在

泄漏链：线程池的核心线程不死 → Thread 一直活
       → ThreadLocalMap 一直活 → key=null 但 value 还被强引用
       → value（可能是一个大对象 / 持有上下文的整条引用链）永远回收不掉
  • 为什么 key 设计成弱引用：避免「ThreadLocal 变量本身」成为泄漏源，这是减轻泄漏而不是解决泄漏
  • get / set 时会顺手清理一部分 key == null 的槽位（expungeStaleEntry），但不保证清完
  • 真正的解法只有一个：try { ... } finally { threadLocal.remove(); }，在线程池场景下这是硬性要求
  • InheritableThreadLocal 在线程池里还会错传上下文（线程复用时继承的是创建时的快照），要用 TransmittableThreadLocal 这类方案

加粗要点： 枚举做 key 一律用 EnumMap（就是个数组，没 hash 没扩容）；对象图去重、防循环引用用 IdentityHashMap（按 == 判等，故意不走 equals）；WeakHashMap 弱的是 key 不是 value，value 若引用了 key 就是永不失效的泄漏，且字符串字面量当 key 永远不会被回收。ThreadLocal 泄漏的根源是 Entry.value 是强引用（key 才是弱引用），线程池里必须 finally { remove(); }。

20. 集合拷贝的三个层次，以及 toArray 的三个坑 ​

「把集合复制一份」这句话在 Java 里有三种完全不同的语义，混淆它们是线上数据被意外改动的常见原因。

java
List<User> src = new ArrayList<>(List.of(new User(1, "张三")));

// 层次 ①：视图（View）—— 没有新容器，共享同一份底层数据
List<User> view1 = Collections.unmodifiableList(src);   // 只读视图，src 改了它也变
List<User> view2 = src.subList(0, 1);                   // 子视图，改它会写回 src
Set<String> view3 = map.keySet();                       // keySet/values/entrySet 都是视图

// 层次 ②：浅拷贝（Shallow Copy）—— 新容器，但装的是同一批对象引用
List<User> shallow1 = new ArrayList<>(src);             // ⭐ 最常用，是浅拷贝
List<User> shallow2 = (List<User>) ((ArrayList<User>) src).clone();
List<User> shallow3 = src.stream().collect(Collectors.toList());
List<User> shallow4 = List.copyOf(src);                 // 不可变 + 浅拷贝
User[] arr = src.toArray(new User[0]);                  // 也是浅拷贝

shallow1.add(new User(2, "李四"));   // ✅ 不影响 src —— 容器是独立的
shallow1.get(0).setName("王五");     // ⚠️ src.get(0).getName() 也变成了"王五"！

// 层次 ③：深拷贝（Deep Copy）—— 容器和元素都是新的
List<User> deep = src.stream().map(User::copy).collect(Collectors.toList());
操作新容器新元素源集合改动会影响它吗它的改动会影响源集合吗
unmodifiableList / subList❌❌✅ 会✅ 会（subList 可写回）
new ArrayList<>(src)✅❌结构不影响，元素内部会结构不影响，元素内部会
List.copyOf / ImmutableList✅❌同上不可改（但元素内部仍可改）
map(::copy) 深拷贝✅✅❌❌

关键认知：Java 里没有任何一个 API 会帮你做深拷贝。clone()、拷贝构造、Collectors.toList()、List.copyOf 全是浅拷贝。只要元素是可变对象，「拷贝一份再改」就会穿透到源集合。防御性拷贝要生效，必须要么元素本身不可变（全 final 字段），要么手写元素级的 copy。

Collections.copy 不是你想的那个 copy：

java
List<User> dest = new ArrayList<>(src.size());   // ⚠️ size 是 0，capacity 才是 10
Collections.copy(dest, src);                     // → IndexOutOfBoundsException: Source does not fit in dest
// 它要求 dest.size() >= src.size()，是「按下标覆盖已有元素」，不是「填充空集合」
// 想复制一份：直接 new ArrayList<>(src)

toArray 的三个坑：

java
List<String> list = List.of("a", "b");

// 坑 1：无参 toArray() 返回 Object[]，强转会抛 ClassCastException
String[] bad = (String[]) list.toArray();        // ❌ ClassCastException
// 原因：底层数组的「运行时类型」就是 Object[]，泛型擦除后 JDK 没法知道你要什么类型

// ✅ 正确：传入类型化数组
String[] ok1 = list.toArray(new String[0]);      // ⭐ 推荐，传长度 0 最快（JIT 对 0 长度有优化）
String[] ok2 = list.toArray(String[]::new);      // JDK11+，等价且更直观

// 坑 2：Arrays.asList 包装数组后结构不可变
List<String> fixed = Arrays.asList(ok1);
fixed.add("c");                                  // ❌ UnsupportedOperationException
fixed.set(0, "z");                               // ✅ set 可以，而且会写回原数组 ok1！

// 坑 3：基本类型数组被当成单个元素
int[] nums = {1, 2, 3};
List<int[]> wrong = Arrays.asList(nums);         // ⚠️ size = 1，装的是整个数组对象
List<Integer> right = Arrays.stream(nums).boxed().collect(Collectors.toList());

并行流写入非线程安全集合（高频事故）：

java
// ❌ 看起来很美，实际会丢数据、甚至抛 ArrayIndexOutOfBoundsException
List<String> result = new ArrayList<>();
data.parallelStream().forEach(result::add);       // ArrayList 的 add 没有任何同步

// ✅ 方案 A：用 collect，Stream 框架自己负责分段合并
List<String> r1 = data.parallelStream().collect(Collectors.toList());
// ✅ 方案 B：确实要 forEach 就用线程安全容器
List<String> r2 = Collections.synchronizedList(new ArrayList<>());
// ✅ 方案 C：收集到 Map 时用并发版本，避免 merge 阶段的额外拷贝
Map<String, Long> r3 = data.parallelStream()
        .collect(Collectors.groupingByConcurrent(Function.identity(), Collectors.counting()));

加粗要点： 分清三个层次：视图共享底层数据（subList、unmodifiableList、keySet）、new ArrayList<>(src) 是浅拷贝（容器独立但元素共享）、深拷贝必须自己写，JDK 没有任何 API 帮你做。toArray 一律用 toArray(new T[0])，无参版本返回 Object[] 强转必崩。并行流绝不能 forEach(list::add)，要用 collect。

❓ 高频面试题【基础简答 + 连环追问链 + 精简口述答案 + 项目关联话术】 ​

题 1：ArrayList 和 LinkedList 的区别？你平时怎么选？ ​

精简口述答案：

底层结构不同：ArrayList 是动态数组，内存连续，支持下标随机访问，get(i) 是 O(1)；LinkedList 是双向链表，get(i) 要从头或尾遍历，是 O(n)，但它同时实现了 Deque，头尾增删是 O(1)。

扩容上 ArrayList 用 oldCapacity + (oldCapacity >> 1)，也就是 1.5 倍，底层是 Arrays.copyOf 整体拷贝；LinkedList 不需要扩容，但每个元素要多包一个 Node 对象。

但工程上我基本只用 ArrayList。理由有三个：① LinkedList 的 O(1) 插入前提是你已经持有节点引用，add(index, e) 本身还是要先 O(n) 遍历定位；② ArrayList 内存连续，CPU 缓存行命中率高，而链表节点散落在堆上每跳一次都可能 cache miss；③ LinkedList 每个元素的额外开销约 40 字节，是 ArrayList 的近 10 倍，GC 压力大。真的需要双端操作时我用 ArrayDeque，它是循环数组，比 LinkedList 更快也更省内存。

连环追问链：

  1. 追问：ArrayList 的默认容量是 10，是在什么时候分配的？

    • 答：不是构造的时候，是第一次 add 的时候。无参构造只是把 elementData 指向一个静态空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，ensureCapacityInternal 发现是这个数组时才把 minCapacity 提升到 10。这是个懒加载优化 —— 很多 ArrayList 创建出来可能一个元素都不放，提前开 10 个槽位纯属浪费。顺带一提，源码里有两个空数组，EMPTY_ELEMENTDATA 对应「显式传了容量 0」，这种情况第一次 add 只扩到 1，不会扩到 10。

  2. 追问：ArrayList 删除元素后，底层数组会变小吗？

    • 答：不会。remove 只做两件事：System.arraycopy 把后面的元素整体前移一位，然后把最后一个槽位置 null 帮助 GC，elementData.length 完全不变。所以一个曾经放过 100 万元素的 ArrayList，即使清空了也还占着 100 万个引用的内存。需要释放得手动调 trimToSize()。这也是一类隐蔽的内存占用问题 —— 长生命周期的 ArrayList 被当缓冲区反复填充清空，内存只升不降。

  3. 追问：list.remove(1) 和 list.remove(Integer.valueOf(1)) 有什么区别？

    • 答：这是重载的坑。remove(int index) 按下标删，remove(Object o) 按对象删。写 list.remove(1) 会优先匹配 int 版本，删的是第 2 个元素，而不是值为 1 的元素。List<Integer> 场景下想按值删必须写 remove(Integer.valueOf(1)) 或 remove((Integer) 1)。我代码评审时专门盯这一行。

  4. 追问：既然 ArrayList 查询是 O(1)、插入是 O(n)，那中间插入 1 万次会很慢吧？

    • 答：理论上慢，实际上通常不慢。因为 System.arraycopy 是 JVM 的 intrinsic 内建方法，底层直接走 memmove，是按字节块批量搬运的，比「逐个节点跳指针」快得多。实测在几万量级，ArrayList 的中间插入经常还是比 LinkedList 快。只有在元素数量非常大（十万以上）且插入位置集中在头部时，链表才可能占优 —— 而那种场景更应该换数据结构，比如 ArrayDeque 或跳表。

  5. 追问：ArrayList 怎么做到线程安全？

    • 答：三个档位。① Collections.synchronizedList：方法级加锁，但复合操作（如「判断不存在再 add」）仍然不安全，且遍历时必须手动在外层加同一把锁；② CopyOnWriteArrayList：写时复制，读无锁、迭代器是快照不抛 CME，适合读多写极少（监听器列表、白名单），写是 O(n) 复制；③ 干脆不共享 —— 用局部变量，或并发收集后再合并。我们项目里真正用 COW 的只有事件监听器那一处。

✅ 项目关联话术（按真实经历替换）：

我之前排查过一个接口 P99 从 80ms 飙到 1.2s 的问题，最后定位到是一段用 LinkedList 存明细、然后用 for (int i = 0; i < list.size(); i++) list.get(i) 遍历的代码。数据量从几百涨到两万后，这个写法实际是 O(n²)，每次 get 都从头遍历。改成 ArrayList 之后 P99 直接回到 90ms。那之后我在团队的代码规范里加了两条：集合声明统一用 ArrayList 并预估初始容量、禁止对 List 接口用下标 for 循环遍历，统一用 for-each 或迭代器，并且在 CI 的静态扫描里加了规则。

题 2：HashMap 的底层结构？JDK7 和 JDK8 有什么区别？为什么负载因子是 0.75？ ​

精简口述答案：

JDK8 的 HashMap 是数组 + 链表 + 红黑树。数组叫 table，长度恒为 2 的 n 次方；冲突的节点挂成链表，当链表长度达到 8 且数组容量 ≥ 64 时转成红黑树，查询从 O(n) 变 O(log n)；扩容拆分后树节点 ≤ 6 时退化回链表。

和 JDK7 的区别主要三点：① JDK7 只有数组 + 链表，没有红黑树；② JDK7 插入用头插法，并发扩容时可能形成环形链表导致 get 死循环、CPU 100%，JDK8 改成尾插法；③ JDK7 扩容要对每个节点重新计算下标，JDK8 利用容量是 2 的 n 次方这个性质，用 e.hash & oldCap 把一条链直接拆成「低位链留在原下标」和「高位链放到原下标 + oldCap」，不需要重算 hash。

负载因子 0.75 是时间和空间的折中：太小（0.5）会导致数组很空就扩容，浪费内存且扩容频繁；太大（1.0）会让冲突链变长，查询退化。另外 0.75 等于 3/4，而容量是 2 的 n 次方，容量 × 3 / 4 一定是整数，不会有浮点误差，这也是选它而不是 0.7、0.8 的工程原因。

连环追问链：

  1. 追问：为什么树化阈值是 8，退化阈值是 6，不设成一样？

    • 答：8 这个数字来自源码注释里的泊松分布计算 —— 负载因子 0.75 时，一个桶里出现 8 个节点的概率约是 0.00000006，千万分之六。也就是说在 hash 分布正常的情况下永远不会触发树化，树化只是对「hash 被恶意攻击或 hashCode 实现很差」的兜底。TreeNode 的体积大约是普通 Node 的两倍，无脑树化是浪费。退化设成 6 而不是 8，是为了在 6 和 8 之间留一个 7 作缓冲区，避免节点数在临界点抖动时反复树化、退化，这是典型的滞后设计。

  2. 追问：你刚才说树化还要容量 ≥ 64，为什么？

    • 答：因为容量小的时候，冲突多的根本原因是桶太少，不是 hash 分布差。treeifyBin 里先判断 tab.length < MIN_TREEIFY_CAPACITY（64），如果成立就调 resize() 扩容而不是树化 —— 扩容把桶数翻倍，冲突链自然就短了，代价还比建红黑树低。只有数组已经够大（≥ 64）、链表还是那么长，才说明是 hash 分布本身有问题，这时候树化才值得。

  3. 追问：为什么容量必须是 2 的 n 次方？

    • 答：服务了三件事，不只是一件。① 寻址：n 是 2 的 n 次方时，n-1 的二进制低位全是 1，(n-1) & hash 完全等价于 hash % n，但位运算比取模快一个数量级；② 分布均匀：如果容量不是 2 的 n 次方，n-1 的二进制里有 0 位，那些位永远与不出 1，导致一部分桶永远取不到，另一部分冲突翻倍；③ 扩容优化：正因为是 2 倍关系，新旧下标只差 oldCap 这一个 bit，才能用 e.hash & oldCap 做高低位拆分。另外即使你 new HashMap<>(13)，tableSizeFor 也会用一串右移或运算把它向上取整到 16。

  4. 追问：hash 扰动函数在做什么？不做扰动会怎样？

    • 答：扰动就是 h ^ (h >>> 16)，把 hashCode 的高 16 位异或到低 16 位。原因是寻址只用到 hash 的低位 —— 容量 16 的时候只用低 4 位，高 28 位的差异被完全丢弃。假设两个对象 hashCode 分别是 0x0000_0005 和 0xFFFF_0005，不扰动的话它们会落到同一个桶。做一次异或后高位特征被混入低位，分布明显更均匀。这个优化成本只有一次移位加一次异或，收益很高。

  5. 追问：知道初始容量要怎么估算吗？new HashMap<>(1000) 放 1000 个元素会扩容吗？

    • 答：会扩容。tableSizeFor(1000) 得到 1024，阈值是 1024 × 0.75 = 768，放到第 769 个就触发扩容了。正确公式是 expectedSize / 0.75 + 1，1000 个元素要传 1334，tableSizeFor 后是 2048。工程上直接用 Guava 的 Maps.newHashMapWithExpectedSize(1000) 更省心。阿里规约要求集合初始化指定容量，就是因为默认 16 放 1000 个元素要扩容 7 次，每次都是 O(n) 的 rehash 加一次数组分配。

  6. 追问：HashMap 能存 null 吗？存在哪里？

    • 答：可以，而且只能存一个 null key，value 可以有多个 null。源码里 hash(null) 直接返回 0，所以 null key 恒定落在 table[0]。但要注意这带来了 get 返回 null 的二义性 —— 分不清「key 不存在」还是「value 本身是 null」，所以判断存在性要用 containsKey。Hashtable 和 ConcurrentHashMap 则是 key、value 都不允许 null，TreeMap 的 key 也不行（要比较大小）。

✅ 项目关联话术（按真实经历替换）：

我们有个批量导入的接口，一次处理 5 万条数据，里面用 HashMap 做 ID 到对象的索引，原来是 new HashMap<>() 默认 16。压测时发现这个接口的 GC 频率明显偏高，用 JFR 抓下来看，HashMap.resize 和 Arrays.copyOf 占了可观的分配量 —— 5 万条数据要扩容 12 次，中间产生了一堆废弃的 table 数组。改成 Maps.newHashMapWithExpectedSize(50000) 之后，Young GC 次数降了约三分之一，接口 P99 快了 15% 左右。这件事之后我们在代码规范里明确：只要数据量可预估，集合必须指定初始容量，且用 expectedSize / 0.75 + 1 计算。

题 3：HashMap 为什么线程不安全？具体会出什么问题？ ​

精简口述答案：

要分版本回答。JDK7 最严重的问题是扩容形成环形链表：transfer 用头插法迁移，两个线程同时扩容时，一个线程手里拿着旧的 next 快照，另一个线程已经把链表顺序反转了，交错执行后两个节点会互相指向，形成环。之后任何 get 落到这个桶就是 while 死循环，CPU 直接打满 100%，而且是那种重启才能恢复的故障。

JDK8 改成尾插法 + 高低位拆分，不会再成环了，但依然线程不安全，还有三个问题：① 数据覆盖丢失 —— 两个线程同时判断同一个空桶为 null，都执行写入，后者覆盖前者；② size 不准 —— ++size 不是原子操作；③ 扩容期间读到中间状态，可能拿到 null。

所以结论是：任何版本的 HashMap 都不能在多线程写入的场景使用，并发场景用 ConcurrentHashMap。

连环追问链：

  1. 追问：能把 JDK7 成环的过程讲细一点吗？

    • 答：假设旧桶是 A → B → null。线程 1 执行到 Entry next = e.next（此时 e = A，next = B）后被挂起。线程 2 完整跑完迁移，头插导致新桶变成 B → A → null。线程 1 恢复，它用的还是旧快照：先头插 A，然后 e = B，头插 B 时 B.next = A；接着 e = B.next，而在线程 2 的结果里 B.next 是 A，于是又处理 A，头插时 A.next = B —— A 和 B 互相指向，环就形成了。关键点是「头插法会反转顺序」和「线程 1 持有过期的 next 快照」这两个因素叠加。

  2. 追问：JDK8 的数据丢失具体是哪一行代码导致的？

    • 答：putVal 里这一段：
      java
      if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
      判断为 null 和赋值之间没有任何同步。线程 A 和线程 B 同时判断 tab[5] == null 成立，A 写入 k1，B 紧接着写入 k2 覆盖掉，k1 就凭空消失了。ConcurrentHashMap 对应的位置用的是 casTabAt(tab, i, null, newNode) —— CAS 保证「判断 + 写入」是一步原子操作，失败就重试。

  3. 追问：既然不安全，Collections.synchronizedMap 够用吗？

    • 答：它能保证单个方法线程安全，但有三个明显短板：① 锁的是整个 map 对象，并发度等于 1，所有读写互相阻塞；② 复合操作仍不安全，「containsKey 再 put」这种还是要自己在外面加同一把锁；③ 遍历必须手动 synchronized (map) 包起来，否则照样抛 CME。它存在的意义主要是把已有的非线程安全 Map 临时包一下，正式的并发场景应该直接用 ConcurrentHashMap。

  4. 追问：那 Hashtable 呢？它和 ConcurrentHashMap 比差在哪？

    • 答：Hashtable 是把 synchronized 直接加在每个方法上，和 synchronizedMap 本质一样，全表一把锁，读也要抢锁。ConcurrentHashMap（JDK8）是空桶 CAS、非空桶 synchronized 锁头节点，并发度约等于桶的数量，而且读完全不加锁，靠 Node.val 和 next 的 volatile 以及 tabAt 的 volatile 读保证可见性。另外 Hashtable 的默认容量是 11、扩容是 2n+1、取模用的是除法，性能也更差。Hashtable 现在只在很老的代码里能见到，属于被淘汰的类。

  5. 追问：JDK8 的 HashMap 在并发下还会死循环吗？

    • 答：不会死循环，但会死在别的地方。有个真实案例：并发 put 时如果恰好触发树化，TreeNode 的 root 和 parent 指针在没有同步保护的情况下可能被改成互相引用，导致 treeify 或 balanceInsertion 里的循环出不来，表现同样是 CPU 100%。所以更稳妥的说法是：「JDK8 修掉了链表成环这一类死循环，但在并发下行为完全未定义，照样可能出现 CPU 打满」。面试时这么说比简单答「JDK8 不会死循环」要准确。

✅ 项目关联话术（按真实经历替换）：

我们有过一次线上事故就是这个。一个本地缓存用的是 static HashMap，初版是单线程定时任务刷新，后来有人加了个接口可以手动触发刷新，就变成了多线程写。某天运营连点了几次刷新按钮，那台机器的 CPU 直接 100%，接口全部超时。用 jstack 抓线程栈，看到好几个线程卡在 HashMap.getNode 里，基本就确定是哈希表的环。当时紧急重启恢复，后面做了两件事：把 HashMap 换成 ConcurrentHashMap，并且把「刷新」改成单线程执行器串行化加去重。复盘时我们还在静态扫描里加了规则：static 修饰的集合字段禁止使用非线程安全实现。

题 4：ConcurrentHashMap 在 JDK8 是怎么实现的？和 JDK7 比有什么改进？ ​

精简口述答案：

JDK7 用的是分段锁：把整个表切成默认 16 个 Segment，每个 Segment 自己是一个 ReentrantLock 加一张小哈希表，不同段的写互不影响，所以并发度是段的个数，默认 16。缺点是两层结构内存占用大、定位要算两次 hash、并发度写死在初始化时。

JDK8 彻底重构，抛弃了 Segment，结构变回和 HashMap 一样的「数组 + 链表 + 红黑树」，用三个手段保证并发安全：① 桶为空时用 casTabAt 做 CAS 写入，完全无锁；② 桶不为空时 synchronized 锁住该桶的头节点，只阻塞落到同一个桶的线程；③ 读操作完全不加锁，靠 Node 的 val、next 是 volatile 以及 tabAt 的 volatile 读保证可见性。

另外扩容也优化了：迁移时把旧表按步长切成多个区间，多个线程可以并行迁移；某个桶迁移完就在旧表该位置放一个 ForwardingNode，其他线程读到它就去新表查，写到它就调 helpTransfer 加入协助。所以 JDK8 的并发度从「16 段」提升到了「桶的数量」，一句话总结就是 锁的是桶，不是表。

连环追问链：

  1. 追问：为什么 JDK8 敢用 synchronized 而不是 ReentrantLock？

    • 答：因为 JDK6 之后 synchronized 有了锁升级：偏向锁 → 轻量级锁（CAS 自旋）→ 重量级锁。ConcurrentHashMap 里锁桶头节点的竞争通常非常短、非常低，绝大多数情况停在轻量级锁阶段，性能和 CAS 接近，而且 synchronized 由 JVM 原生支持，不需要像 ReentrantLock 那样维护 AQS 队列对象，内存开销更小。再加上 synchronized 的代码更简洁、不会忘记 unlock，Doug Lea 在注释里也说明了这个选择。

  2. 追问：sizeCtl 这个字段是干什么的？

    • 答：它是一个 volatile int，用不同的取值复用了多种状态：0 表示还没初始化；-1 表示某个线程正在初始化（通过 CAS 抢到这个值，其他线程 Thread.yield() 自旋等待）；小于 -1 时，低 16 位记录的是正在参与扩容的线程数（-(1 + 扩容线程数)）；大于 0 时表示下一次扩容的阈值。用一个变量承载这么多语义，是为了让状态切换可以用一次 CAS 完成，这是 Doug Lea 典型的写法。

  3. 追问：size() 为什么是估算的？

    • 答：因为它没有用一个 volatile int size —— 那会变成所有写线程争抢的热点，CAS 失败率极高。它借鉴 LongAdder 的分段累加：无竞争时 CAS 累加到 baseCount，一旦 CAS 失败说明有竞争，就改为累加到 CounterCell[] 数组里线程各自哈希到的槽位。size() 是 baseCount 加上所有 CounterCell 的求和，遍历求和的过程中其他线程还在改，所以结果只是某个时间点的近似值。工程上千万不要用 chm.size() 做精确的业务判断，另外 JDK8 还提供了返回 long 的 mappingCount()，比 size() 更推荐。

  4. 追问：ConcurrentHashMap 用了它就一定线程安全了吗？

    • 答：不是。它只保证单个方法的原子性，不保证多个方法组合的原子性。像「containsKey 不存在则 put」、「get 出来加一再 put 回去」这种 check-then-act、read-modify-write 都会丢更新。正确做法是用它自带的原子复合方法：putIfAbsent、computeIfAbsent、compute、merge、replace(k, old, new)。高并发计数我更倾向于 ConcurrentHashMap<String, LongAdder> 配 computeIfAbsent(k, x -> new LongAdder()).increment()，这样连桶锁都不用反复抢。

  5. 追问：computeIfAbsent 有什么坑？

    • 答：两个。① mapping 函数里不能再操作同一个 map —— 当前线程已经 synchronized 住了这个桶，如果函数体里 put 的 key 恰好 hash 到同一个桶，JDK8 下会直接死锁或死循环（JDK9 之后会抛 IllegalStateException 提示递归更新）；② mapping 函数不要做耗时操作，比如远程调用或查库 —— 整个桶在这期间都被锁住，落到同桶的其他 key 全部阻塞。缓存场景更安全的写法是「先 get，miss 了在锁外加载，最后 putIfAbsent」，或者直接用 Caffeine 这类专业缓存。

  6. 追问：它的迭代器是什么行为？遍历时别人在改会怎样？

    • 答：是**弱一致（weakly consistent）**迭代器 —— 不会抛 ConcurrentModificationException，也不会像 CopyOnWriteArrayList 那样是完整快照。它能保证遍历到创建迭代器时已存在的元素，对于之后的修改则「可能看到也可能看不到」。所以它适合做监控统计、批量导出这种对实时性要求不高的遍历；如果需要「遍历期间数据不变」的强一致语义，ConcurrentHashMap 给不了，得在业务层加锁或者先拷贝一份。

✅ 项目关联话术（按真实经历替换）：

我们做过一个接口限流的本地计数器，最早的实现是 ConcurrentHashMap<String, Integer> 加 map.put(key, map.get(key) + 1)。灰度的时候就发现统计值明显偏小 —— 典型的 read-modify-write 丢更新。第一版修复用了 merge(key, 1, Integer::sum)，正确了但压测时发现热点 key 上有锁竞争。最终版改成 ConcurrentHashMap<String, LongAdder>，用 computeIfAbsent 初始化、increment() 累加，热点 key 的竞争被 LongAdder 内部的 Cell 分散掉，QPS 提升了一倍多。这件事让我记住了一个原则：ConcurrentHashMap 保证的是单方法原子性，组合操作必须用它提供的原子 API，而高并发计数要进一步把热点拆散。

题 5：为什么重写 equals 必须重写 hashCode？ ​

精简口述答案：

因为 HashMap、HashSet 判断「是不是同一个 key」是两步：先用 hash 定位桶，再在桶内用 == 或 equals 比较。

如果只重写 equals 不重写 hashCode，两个业务上「相等」的对象会因为继承了 Object 的 hashCode（基于对象地址）而算出不同的 hash，落到不同的桶里，第一步就分道扬镳了，equals 根本没机会被调用。结果就是：HashSet 里出现两个相等的元素、用一个「相等」的新对象去 map.get 拿不到值。

反过来只重写 hashCode 不重写 equals，两个对象会落到同一个桶，但 equals 返回 false，照样被当成两个不同的 key —— 只是退化成了哈希冲突。

所以 JDK 的契约是：a.equals(b) 为 true，则 a.hashCode() 必须等于 b.hashCode()；反之不要求。实际写代码我一律用 IDE 生成或者 Objects.equals / Objects.hash，不手写。

连环追问链：

  1. 追问：为什么 hashCode 相等不要求 equals 相等？

    • 答：因为 hashCode 返回的是 int，只有约 43 亿个取值，而对象的可能状态是无限的 —— 鸽笼原理决定了冲突不可避免。所以哈希表的设计前提就是「hash 相等只是候选，还要 equals 确认」。顺带说一个经典例子："Aa".hashCode() 和 "BB".hashCode() 都是 2112，可以无限拼接构造出大量 hash 相同的字符串 —— 这就是**哈希碰撞攻击（Hash DoS）**的原理，往请求参数里塞大量这种 key，能把 HashMap 退化成链表打满 CPU。Java 8 用红黑树树化缓解了这个问题。

  2. 追问：用可变对象当 HashMap 的 key 会有什么问题？

    • 答：放进去之后就再也取不出来。因为节点是按放入时的 hash 挂在某个桶上的，之后你改了参与 hashCode 的字段，再用这个对象去 get，算出的新 hash 指向另一个桶，那里什么都没有，返回 null。而旧桶里的节点谁也访问不到，但它和 value 的引用还在，GC 回收不了，就是内存泄漏。所以作为 key 的类应该设计成不可变：字段加 final、不提供 setter。这也是 String 为什么是完美的 key —— 不可变而且缓存了 hash 值。

  3. 追问：Objects.hash(a, b, c) 内部是怎么算的？为什么用 31？

    • 答：内部就是 result = 31 * result + element.hashCode() 的循环（Arrays.hashCode 的实现）。选 31 有两个原因：① 31 是奇素数，奇数能避免乘法丢失信息（偶数相当于左移，会把高位丢掉），素数则让散列分布更均匀；② 31 * i 可以被 JVM 优化成 (i << 5) - i，一次移位加一次减法，比乘法快。顺便一提，Objects.hash 内部要创建可变参数数组，在超高频路径上有装箱和数组分配开销，极致性能场景会手写展开。

  4. 追问：Lombok 的 @Data 生成的 equals 有什么坑？

    • 答：主要是继承场景。@Data 默认生成的 equals 不比较父类字段，而且默认 callSuper = false，父类字段不参与比较会导致「两个父类字段不同的子类对象被判为相等」；如果加了 @EqualsAndHashCode(callSuper = true) 但父类没有正确实现 equals，又会退化成 Object 的地址比较。另外 @Data 会把所有字段纳入比较，包括那些你其实不希望参与身份判断的字段（比如 updateTime、懒加载的关联集合 —— 后者还可能触发 N+1 查询）。我们团队的做法是：实体类只用 @Getter/@Setter，equals/hashCode 显式写、只基于业务主键。

  5. 追问：JPA / Hibernate 实体的 equals 该怎么写？

    • 答：这是个经典难题。不能只用自增主键 —— 实体在持久化之前 id 是 null，放进 HashSet 后再 persist，id 变了 hash 也变了，就取不出来了。常见的三种做法：① 用业务唯一键（如订单号、UUID）而不是数据库自增 id；② 在构造时就生成一个 UUID 作为标识；③ hashCode 返回一个常量（比如类名的 hash），equals 比 id —— 牺牲哈希分布换正确性，适用于集合规模很小的关联场景。我倾向第一种，顺带还解决了幂等的问题。

✅ 项目关联话术（按真实经历替换）：

我们做商品去重时遇过一次。原来的逻辑是把 SkuDTO 丢进 HashSet 去重，SkuDTO 只重写了 equals（比较 skuId），没重写 hashCode。测试环境数据少恰好没暴露，上线后发现同一个 sku 在列表里出现了两次。排查出来后我做了三件事：补上 hashCode 并把参与比较的字段改成 final；在单元测试里加了一条「equals 为 true 的两个对象 hashCode 必须相等」的断言；最后在 CI 里接了静态扫描规则，只重写 equals 不重写 hashCode 直接卡住构建。后来我们干脆把去重改成了 Collectors.toMap(SkuDTO::getSkuId, Function.identity(), (a, b) -> a)，用明确的业务主键去重，不再依赖对象的 equals。

题 6：遍历集合时删除元素为什么会抛异常？有几种正确写法？ ​

精简口述答案：

因为 ArrayList 这类集合有一个 modCount 字段，记录结构性修改（add / remove / clear）的次数。创建迭代器时会把当前 modCount 存成 expectedModCount，之后每次 next() 都会调 checkForComodification() 比较两者 —— 一旦不等就抛 ConcurrentModificationException。

for-each 本质就是迭代器的语法糖，你在循环体里调 list.remove(e) 只会让 modCount 自增，expectedModCount 没同步，下一次 next() 就炸了。而 iterator.remove() 在删除之后会执行 expectedModCount = modCount 把快照同步回来，所以它是安全的。

正确写法主要四种：iterator.remove()、removeIf()（JDK8+，最推荐）、倒序下标遍历、遍历时收集待删元素最后 removeAll。另外还有一个阴险的点：用 for-each 删除「倒数第二个」元素时恰好不会抛异常，因为删完 size 减一，hasNext() 里 cursor != size 直接为 false 就结束了 —— 这种代码在测试数据下是「正常」的，换批数据就暴雷。

连环追问链：

  1. 追问：为什么说 CME 不是「并发」异常？

    • 答：名字有误导性。它的触发条件只是 modCount != expectedModCount，单线程里自己边遍历边删同样会抛。它的设计目的是「快速失败」—— 让错误在第一次出现时就暴露，而不是留下一个行为未定义的集合继续跑下去。反过来说，它也不能作为并发检测的保证：多线程修改时它只是「尽力而为」地抛，modCount 本身不是 volatile，完全可能漏检。

  2. 追问：removeIf 的实现和 Iterator.remove 有什么不同？

    • 答：Iterator.remove 是一次删一个，每次删除都要 System.arraycopy 把后面的元素前移，删 n 个元素是 O(n·m) 的拷贝量。ArrayList.removeIf 聪明得多：先用一个 BitSet 标记所有要删的位置（这一轮只读不改），然后一次性批量压缩数组，整体是 O(n)。所以删除比例高的时候 removeIf 明显更快，而且代码更短、不会写错。它内部也会做 modCount 校验，遍历过程中如果 predicate 里改了集合同样会抛 CME。

  3. 追问：Map 怎么安全地边遍历边删？

    • 答：Map 本身没有迭代器，要通过它的三个视图来操作：entrySet().iterator() 然后 it.remove()，或者更简洁的 map.entrySet().removeIf(e -> 条件)、map.values().removeIf(...)、map.keySet().removeIf(...)。关键是要理解 keySet、values、entrySet 都是视图而不是副本，在视图上删除会直接作用到源 Map。反过来要小心：拿到 keySet 后不要随便当独立集合传出去。

  4. 追问：CopyOnWriteArrayList 和 ConcurrentHashMap 为什么不抛 CME？

    • 答：机制不同。CopyOnWriteArrayList 的迭代器基于创建那一刻的数组快照，之后的写操作换的是新数组，老数组不会变，所以遍历永远安全 —— 代价是看不到新数据，而且它的迭代器不支持 remove（会抛 UnsupportedOperationException）。ConcurrentHashMap 是弱一致迭代器，它直接遍历当前的桶数组，能看到部分新修改，但不保证完整性，也不做 modCount 校验。所以这两个类遍历时删除不会异常，但语义是「最终一致」而不是「强一致」。

  5. 追问：实际项目里你怎么写？

    • 答：优先级是 removeIf > Iterator > 新建集合收集保留项。能用一行 list.removeIf(条件) 表达的绝不写循环；需要同时访问上下文、或者删除时还要做别的事（记日志、发事件）才用 Iterator；如果是函数式风格的数据流处理，我更倾向于不删除原集合，直接 stream().filter(...).collect(...) 生成新集合 —— 不改原数据在并发和可读性上都更安全。另外绝对禁止在 for-each 里调 list.remove，这条写进了团队规范。

✅ 项目关联话术（按真实经历替换）：

我们有个过滤下架商品的逻辑，最初写的是 for-each 里 list.remove(item)。测试用的是三条数据，刚好删的是第二条 —— 倒数第二个，hasNext() 提前返回 false，一次异常都没抛，就这么上线了。结果真实数据下 CME 直接把接口打成 500。修复时我没有简单换成 Iterator，而是改成了 list.removeIf(SkuVO::isOffline)，一行解决。复盘之后我们把「禁止在 for-each 中对被遍历集合做结构性修改」写进了规范，并加了静态扫描规则。这个坑给我的最大教训是：「测试没报错」不等于「写法正确」，边界恰好掩盖 bug 的情况比直接报错危险得多。

题 7：线上突然报 Comparison method violates its general contract!，怎么定位和修？ ​

精简口述答案：

这个异常不是 JDK 的 bug，是自己写的 Comparator 违反了比较契约。List.sort / Arrays.sort(Object[]) 用的是 TimSort，它会先把数组切成一段段单调的 run 再归并，归并时依赖「run 内严格单调」这个前提；一旦比较器自相矛盾，mergeLo / mergeHi 里的指针会越界，JDK 检测到就直接抛这个 IllegalArgumentException。

它典型的表现是**「测试环境一直好的，上线一段时间后突然报」**，原因是 TimSort 对长度小于 32（MIN_MERGE）的数组走的是二分插入排序，根本不做 run 合并，也就不校验契约 —— 违约一直存在，只是数据量小的时候表现为「排序结果不对」，数据量涨上去才表现为抛异常。

定位就看栈顶是哪个 sort 调用，然后去审对应的比较器，九成是这三种写法之一：漏掉相等返回 0（a.x > b.x ? 1 : -1）、用 a - b 相减导致 int 溢出、比较依据不稳定（排序过程中字段被别的线程改了，或者比较里用了 Math.random() / 当前时间）。修法是一律改用 Comparator.comparingInt / comparing + thenComparing 这套工厂方法，不手写三元分支。

连环追问链：

  1. 追问：为什么漏掉「相等返回 0」就一定违约？

    • 答：违反的是反对称性：契约要求 sgn(compare(a,b)) == -sgn(compare(b,a))。写成 a.x > b.x ? 1 : -1 时，如果 a.x == b.x，那么 compare(a,b) 返回 -1，compare(b,a) 也返回 -1 —— 两个元素互相认为「对方比我大」，这在数学上就不是一个序关系了。TimSort 归并时会据此一直往前推指针，最后越界。顺带一提，这种写法即使不抛异常，排序结果也是不确定的，而且会破坏稳定性。

  2. 追问：a - b 为什么不安全？不是都这么写吗？

    • 答：只有在能确定两个值都是非负且差值不溢出 int 的情况下才安全，这个前提在业务代码里基本不成立。比如余额、时间戳差、带符号的分数，2_000_000_000 - (-2_000_000_000) 的结果是 -294_967_296，符号直接翻转，「大的变成了小的」。long 字段更危险，强转 int 还会截断。正确写法是 Integer.compare(a, b) / Long.compare(a, b)，或者直接用 Comparator.comparingInt，它内部就是调 Integer.compare。

  3. 追问：-Djava.util.Arrays.useLegacyMergeSort=true 能解决问题吗？

    • 答：只能让异常消失，不能解决问题。它退回 JDK6 的归并排序实现，那个实现不校验契约，所以不报错 —— 但排序结果依然是错的，而且归并排序要额外开一倍的临时数组，内存开销更大。我只会把它当成「线上凌晨紧急止血」的手段，且必须当天把比较器修掉、把参数摘掉，不然就是埋了个「排序结果随机错」的雷。

  4. 追问：多字段排序怎么写才稳？reversed() 放在哪？

    • 答：用链式 comparing(...).thenComparing(...)，并且末尾一定补一个唯一字段（主键、ID），保证是全序 —— 否则相等元素的相对顺序虽然由 TimSort 的稳定性保证，但一旦上游数据顺序变了，结果就会跟着变，排查起来很痛苦。reversed() 的陷阱在于它作用于前面整条链：comparing(A).thenComparing(B).reversed() 是「A 和 B 都倒序」，如果只想倒 A，要写 comparing(A, Comparator.reverseOrder()).thenComparing(B)。另外 null 字段必须显式处理，用 Comparator.nullsFirst/nullsLast 包一层，不能靠 compareTo 碰运气。

  5. 追问：TreeMap 传了比较器之后，判重还看 equals 吗？

    • 答：完全不看。TreeMap / TreeSet 的所有判等逻辑（put 覆盖、contains、去重）都只看 compare(a, b) == 0。所以 new TreeSet<>(Comparator.comparingInt(User::getAge)) 会把所有同龄用户当成同一个人，第二个加不进去。这就是 SortedSet 文档里那句「应当与 equals 一致」的实际含义 —— 不一致不会报错，但会静默丢数据，这类 Bug 极难发现。要排序又要按业务主键判重，就必须把主键加到比较链末尾。

✅ 项目关联话术（按真实经历替换）：

我们有个运营后台的列表接口，支持按多字段排序，上线半年一直正常。后来某个类目的商品数涨到几千条之后，这个接口开始间歇性报 500，日志里就是 Comparison method violates its general contract!。一开始以为是 JDK 版本问题，后来看栈顶定位到排序那行，发现比较器写的是 (a, b) -> a.getWeight() > b.getWeight() ? 1 : -1 —— 权重相等时两边都返回 -1，违反反对称性。数据量小的时候走二分插入排序不校验，所以一直没暴露。我把它改成 Comparator.comparingInt(Item::getWeight).reversed().thenComparing(Item::getId)，顺手在团队规范里加了两条硬性要求：禁止在比较器里用减法、禁止手写三元比较，并在静态扫描里加了对应规则，之后又扫出来四处同样的写法。

题 8：WeakHashMap 什么时候用？ThreadLocal的内存泄漏到底泄漏在哪？ ​

精简口述答案：

WeakHashMap 的 key 是弱引用，当某个 key 除了这个 map 之外再没有强引用时，GC 就会回收它，对应的 entry 也会被自动清掉（下次访问 map 时从 ReferenceQueue 里批量清理）。它适合的场景是**「缓存的生命周期应该跟随 key 对象，而不是由缓存自己决定」**，典型是以 ClassLoader、Class、Thread、框架组件实例为 key 的元数据缓存。

最关键的一点是：弱的是 key，不是 value。Entry.value 是强引用。所以如果 value 直接或间接引用了 key，就形成了一条「table → Entry → value → key」的强引用链，key 永远不会被回收，这个 entry 就成了永不失效的泄漏。另外用字符串字面量当 key 也没用 —— 常量池会永久强引用它。

ThreadLocal 的泄漏是同一个机制的经典案例：ThreadLocalMap.Entry 继承 WeakReference<ThreadLocal<?>>，key 是弱引用、value 是强引用。ThreadLocal 实例被回收后 key 变成 null，但 value 还被 Entry 强引用着。在线程池里核心线程不会销毁，Thread → ThreadLocalMap → Entry → value 这条链一直活着，value 就永远回收不掉。get / set 会顺手清理一部分 stale entry，但不保证清完。唯一可靠的解法就是 try { ... } finally { tl.remove(); }。

连环追问链：

  1. 追问：既然 value 是强引用才泄漏，为什么 JDK 还要把 key 设成弱引用？

    • 答：这是减轻泄漏而不是解决泄漏。如果 key 也是强引用，那么只要线程活着，ThreadLocal 实例本身就永远回收不掉 —— 连「这个 ThreadLocal 已经没人用了」这个信息都拿不到。设成弱引用之后，至少 JDK 能通过「key == null」识别出哪些槽位是废弃的，从而在 get / set / remove 时调 expungeStaleEntry 做启发式清理。value 之所以不能设成弱引用，是因为很多场景下 value 就只有这一处引用（比如 ThreadLocal<SimpleDateFormat>），设成弱引用的话随时会被回收，功能就废了。

  2. 追问：ThreadLocalMap 为什么用线性探测而不是链表解决冲突？

    • 答：因为它的使用场景决定了元素数量极少（一个线程通常只有几个 ThreadLocal），线性探测的平坦数组比「数组 + 链表」更省内存、缓存局部性更好，而且不需要为每个节点额外分配 Node 对象。代价是删除时不能简单置 null（会断开探测链），必须做 rehash 式的整理，这就是 expungeStaleEntry 里那段「向后扫描并重新定位」的逻辑。另外它的 hash 用的是 threadLocalHashCode，按黄金分割数 0x61c88647 递增，能让连续创建的 ThreadLocal 在数组里均匀散开。

  3. 追问：InheritableThreadLocal 在线程池里能用吗？

    • 答：不能。它的继承发生在 Thread 创建的那一刻（init 里从父线程拷贝 inheritableThreadLocals）。线程池的线程是复用的，创建时继承的是「第一次提交任务那个线程」的上下文，后面所有任务拿到的都是这个过期快照，表现为「traceId 串了」「用户身份串了」，而且是概率性的，极难排查。要在线程池里透传上下文，得用阿里开源的 TransmittableThreadLocal，它在任务提交时抓快照、执行前后做 replay 和还原。

  4. 追问：WeakHashMap 是线程安全的吗？能当并发缓存用吗？

    • 答：不是线程安全的，而且它比普通 HashMap 更危险 —— 因为它的「清理 stale entry」动作发生在 size()、get()、put() 这些看起来是读操作的方法里，也就是说连 get 都会修改内部结构。并发访问时不仅可能丢数据，还可能像 JDK7 的 HashMap 那样出现结构错乱。要并发用必须 Collections.synchronizedMap 包一层。但说实话，需要「带自动回收的并发缓存」时，直接用 Caffeine（支持 weakKeys / softValues / 容量与时间淘汰）比自己拼 WeakHashMap 靠谱得多。

  5. 追问：软引用和弱引用做缓存，该选哪个？

    • 答：都不该选。软引用（SoftReference）的回收时机由 JVM 根据内存压力决定，不可控 —— 实测表现往往是「内存快满了才回收」，这意味着它在回收前会加剧 GC 压力、拉长 Full GC 时间，而且回收策略在不同 JDK / 不同 GC 下差异很大，缓存命中率完全不可预期。弱引用则是「下次 GC 就没了」，作为缓存几乎没有命中率。生产上做本地缓存，正确答案是显式容量上限 + 显式过期时间 + 明确的淘汰算法，也就是 Caffeine 这类方案。软弱引用的真实用途是「旁路元数据」而不是「缓存热数据」。

✅ 项目关联话术（按真实经历替换）：

我排查过一次线上老年代缓慢上涨、大约三天一次 Full GC 的问题。用 MAT 看堆 dump，支配树里最大的一块是线程池里几十个核心线程的 ThreadLocalMap，每个 Entry 的 key 都是 null、value 是一个几 MB 的上下文对象，里面还挂着整个请求的参数和中间结果。根因是一个工具类用 ThreadLocal 存请求上下文，但只在拦截器的 preHandle 里 set，没有在 afterCompletion 里 remove —— 线程池的线程不死，这些 value 就一直在。加上 finally { CONTEXT.remove(); } 之后老年代曲线立刻变平。这件事之后我们做了两件事：在统一的拦截器基类里强制做 remove，业务方不允许自己裸用 ThreadLocal；以及在 code review checklist 里加了「ThreadLocal.set 必须有配对的 remove」这一条。

✍️ 手撕代码【核心实现 + 边界 Case 自测清单 + 变种拓展题】 ​

题 1：集合安全删除 —— CME 复现与五种正确写法 ​

核心实现：

java
import java.util.*;
import java.util.concurrent.*;
import java.util.function.Predicate;
import java.util.stream.Collectors;

public class SafeRemoveDemo {

    /* ---------- ① 复现 CME ---------- */
    static void reproduceCme() {
        List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
        try {
            for (String s : list) {
                if ("b".equals(s)) list.remove(s);   // modCount++ 但 expectedModCount 没动
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("① 抛出 CME ✅");
        }
    }

    /* ---------- ② 最阴险的「静默成功」---------- */
    static void silentSuccess() {
        List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
        for (String s : list) {
            if ("b".equals(s)) list.remove(s);   // 删倒数第二个：hasNext() 里 cursor(2) != size(2) 为 false
        }
        System.out.println("② 居然没报错，结果 = " + list);   // [a, c]
    }

    /* ---------- ③ Iterator.remove ---------- */
    static void byIterator() {
        List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            if (it.next().startsWith("b")) it.remove();   // 内部同步 expectedModCount
        }
        System.out.println("③ Iterator  = " + list);
    }

    /* ---------- ④ removeIf：首选 ---------- */
    static void byRemoveIf() {
        List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
        list.removeIf(s -> s.startsWith("b"));           // 内部 BitSet 标记 + 一次性压缩，O(n)
        System.out.println("④ removeIf  = " + list);
    }

    /* ---------- ⑤ 倒序下标：删除不影响未遍历区间 ---------- */
    static void byReverseIndex() {
        List<String> list = new ArrayList<>(Arrays.asList("a", "b", "b", "d"));
        for (int i = list.size() - 1; i >= 0; i--) {
            if ("b".equals(list.get(i))) list.remove(i);
        }
        System.out.println("⑤ 倒序下标  = " + list);
    }

    /* ---------- ⑥ Stream：不改原集合，生成新集合 ---------- */
    static void byStream() {
        List<String> src = List.of("a", "b", "c", "d");
        List<String> result = src.stream()
                .filter(s -> !s.startsWith("b"))
                .collect(Collectors.toCollection(ArrayList::new));
        System.out.println("⑥ Stream    = " + result);
    }

    /* ---------- ⑦ Map 的三个视图删除 ---------- */
    static void mapRemove() {
        Map<String, Integer> map = new HashMap<>();
        map.put("a", 1); map.put("b", 2); map.put("c", 3);

        map.entrySet().removeIf(e -> e.getValue() % 2 == 0);   // 按 value 删
        map.keySet().removeIf(k -> k.equals("c"));             // 按 key 删
        System.out.println("⑦ Map       = " + map);            // {a=1}

        // 需要边删边做别的事时用迭代器
        Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, Integer> e = it.next();
            if (e.getValue() < 0) { log(e.getKey()); it.remove(); }
        }
    }

    /* ---------- ⑧ 并发集合不抛 CME，但语义不同 ---------- */
    static void concurrentCollections() {
        List<String> cow = new CopyOnWriteArrayList<>(List.of("a", "b"));
        for (String s : cow) {
            cow.add("x");        // ✅ 不抛异常，但迭代器是快照，看不到 x，不会死循环
            break;
        }
        // cow.iterator().remove();  // ❌ UnsupportedOperationException

        Map<String, Integer> chm = new ConcurrentHashMap<>(Map.of("a", 1, "b", 2));
        for (String k : chm.keySet()) {
            chm.remove(k);           // ✅ 弱一致迭代器，不抛 CME
        }
        System.out.println("⑧ CHM 清空后 = " + chm);
    }

    private static void log(String k) { /* ... */ }

    public static void main(String[] args) {
        reproduceCme(); silentSuccess(); byIterator();
        byRemoveIf(); byReverseIndex(); byStream();
        mapRemove(); concurrentCollections();
    }
}

三个必须记住的点：

  1. CME 的本质是 modCount != expectedModCount，它是单线程也会触发的「快速失败」机制，不是并发检测保证。
  2. 删倒数第二个元素时 for-each 恰好不报错，这是最危险的情况 —— 代码在测试数据下「正常」，真实数据直接 500。
  3. 工程优先级：removeIf > Iterator.remove > 倒序下标 > stream().filter() 生成新集合；永远不要在 for-each 里调 remove。

✅ 边界 Case 自测：

场景期望行为
for-each 中删除最后一个元素抛 CME（cursor 已是旧 size，hasNext 仍为 true，下一次 next() 校验失败）
for-each 中删除倒数第二个元素静默成功，不抛异常（最大的坑）
for-each 中删除第一个元素（长度 ≥ 3）抛 CME
for-each 中 add 元素抛 CME（add 同样修改 modCount）
Iterator.remove() 在 next() 之前调用抛 IllegalStateException（lastRet == -1）
连续调两次 it.remove()第二次抛 IllegalStateException
removeIf 的 predicate 里修改集合抛 CME
Arrays.asList(...) 上调 removeIf抛 UnsupportedOperationException
List.of(...) 上调 removeIf抛 UnsupportedOperationException
subList 上删除，再访问原 list原 list 被修改；反之改原 list 后访问 subList 抛 CME
CopyOnWriteArrayList 迭代器 remove抛 UnsupportedOperationException
ConcurrentHashMap 遍历中 remove正常，不抛异常（弱一致）
空集合调 removeIf返回 false，无异常

🔁 变种拓展题：

  1. 不用 removeIf，手写一个 O(n) 的原地删除（双指针压缩，只遍历一次）：

    java
    static <T> void removeAll(List<T> list, Predicate<? super T> p) {
    int w = 0;                               // write 指针
    for (int r = 0; r < list.size(); r++) {      // read 指针
        T e = list.get(r);
        if (!p.test(e)) list.set(w++, e);
    }
    list.subList(w, list.size()).clear();        // 一次性砍掉尾部
}

  2. 写一个「遍历中可安全删除」的自定义 fail-safe 迭代器：构造时 Arrays.copyOf 拍快照，remove 作用到源集合 —— 说明这正是 CopyOnWriteArrayList 的思路以及它的代价。

  3. 解释为什么 ArrayList 的 modCount 不是 volatile：它只用于单线程的快速失败，加 volatile 会给每次 add/remove 带来内存屏障开销，而并发安全本来就不是它的承诺。

  4. 用 List.removeAll(otherList) 删除 1 万个元素为什么很慢？ 因为 removeAll 对每个元素都要调一次 otherList.contains，是 O(n·m)。把 otherList 先转成 HashSet 可以降到 O(n)。

题 2：手写 LRU 缓存（LinkedHashMap 版 + 双向链表版 + 线程安全版） ​

核心实现：

text
LRU = Least Recently Used，容量满时淘汰「最久未被访问」的数据

HashMap + 双向链表的组合拳
  HashMap：key → 节点引用，保证 get 定位是 O(1)
  双向链表：维护访问顺序，head 侧是最近访问，tail 侧是最久未访问
  为什么要「双向」？删除一个节点需要知道它的前驱 —— 单链表拿不到，必须 O(n) 找

  get(k)   : map 找到 node → 把 node 移到 head → 返回 value          O(1)
  put(k,v) : 命中 → 更新 value + 移到 head
             未命中 → 新建 node 插到 head；若 size > cap → 删 tail    O(1)

  哨兵节点（dummy head / dummy tail）的作用：
    让「插入」「删除」不需要判断 null，代码从 20 行缩到 8 行
    head ⇄ [最近] ⇄ ... ⇄ [最久] ⇄ tail
java
/* ========== 方案一：LinkedHashMap，面试写这个最快（10 行） ========== */
public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LruCache(int capacity) {
        // 第三个参数 accessOrder = true → get/put 命中后把节点移到链表尾部
        super((int) (capacity / 0.75f) + 1, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;   // 返回 true 时自动删除链表头（最久未访问的）
    }
}
java
/* ========== 方案二：手写双向链表 + HashMap，考察真实功底 ========== */
public class LruCacheManual<K, V> {

    private static class Node<K, V> {
        K key; V value;
        Node<K, V> prev, next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> map;
    private final Node<K, V> head;   // 哨兵：head.next 是最近使用
    private final Node<K, V> tail;   // 哨兵：tail.prev 是最久未使用

    public LruCacheManual(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        this.capacity = capacity;
        this.map = new HashMap<>((int) (capacity / 0.75f) + 1);
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToHead(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {                 // 命中：更新值 + 提到最前
            node.value = value;
            moveToHead(node);
            return;
        }
        node = new Node<>(key, value);
        map.put(key, node);
        addToHead(node);
        if (map.size() > capacity) {        // ⚠️ 先插入再判断，顺序不能反
            Node<K, V> eldest = tail.prev;
            remove(eldest);
            map.remove(eldest.key);         // ⚠️ 必须同时清 map，否则内存泄漏
        }
    }

    public V remove(K key) {
        Node<K, V> node = map.remove(key);
        if (node == null) return null;
        remove(node);
        return node.value;
    }

    public int size() { return map.size(); }

    /* ---- 三个链表基本操作，全部 O(1) ---- */
    private void addToHead(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void remove(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = node.next = null;      // 断开引用，帮助 GC
    }

    private void moveToHead(Node<K, V> node) {
        remove(node);
        addToHead(node);
    }
}
java
/* ========== 方案三：线程安全版 ========== */
// 做法 A：读写锁包装（读多写少时优于全 synchronized）
public class ConcurrentLruCache<K, V> {
    private final LruCacheManual<K, V> delegate;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

    public ConcurrentLruCache(int capacity) { this.delegate = new LruCacheManual<>(capacity); }

    public V get(K key) {
        // ⚠️ 注意：LRU 的 get 会移动节点，是「写」操作，不能用读锁！
        lock.writeLock().lock();
        try { return delegate.get(key); } finally { lock.writeLock().unlock(); }
    }
    public void put(K key, V value) {
        lock.writeLock().lock();
        try { delegate.put(key, value); } finally { lock.writeLock().unlock(); }
    }
}

// 做法 B：用 Collections.synchronizedMap 包 LinkedHashMap（最省事）
Map<String, Object> lru = Collections.synchronizedMap(new LruCache<>(100));

// 做法 C：生产环境的正确答案 —— 用 Caffeine（W-TinyLFU，分段锁 + 异步淘汰）
Cache<String, Object> cache = Caffeine.newBuilder()
        .maximumSize(10_000)
        .expireAfterWrite(Duration.ofMinutes(10))
        .recordStats()
        .build();

三个必须记住的点：

  1. 必须是双向链表：删除节点要改前驱的 next，单链表拿不到前驱就得 O(n) 遍历，整体就不是 O(1) 了。
  2. 哨兵节点（dummy head / tail） 能消掉所有 null 判断，是链表题的通用技巧；淘汰时 map.remove 和链表删除必须成对执行，漏一个就是内存泄漏。
  3. LRU 的 get 是写操作（要移动节点），所以线程安全版不能用读锁；LinkedHashMap 的 accessOrder=true 本质就是在 afterNodeAccess 里做了 moveToHead。

✅ 边界 Case 自测：

场景期望行为
capacity = 0 或负数构造时抛 IllegalArgumentException
capacity = 1，put 两个不同 key只保留后一个
get 不存在的 key返回 null，不改变任何顺序
put 已存在的 key更新 value 且提到最前，size 不变、不触发淘汰
淘汰后再 get 被淘汰的 key返回 null
先 put A B C（cap=3），get(A) 后 put D淘汰 B（A 刚被访问过，不是最久未用）
反复 get 同一个 key顺序稳定，不重复插入
remove 后链表前后指针相邻节点正确连上，size 减一
全部 remove 后head.next == tail，map 为空
value 允许为 null 吗手写版允许，但 get 返回 null 产生二义性 → 建议禁止
并发 put 同一个 key无锁版会出现链表指针错乱 / 丢数据，必须加锁
大量 put 后内存map.size() 恒 ≤ capacity，链表长度与 map 一致（强校验点）

🔁 变种拓展题：

  1. LFU 缓存（LeetCode 460）：按「访问频次」淘汰，频次相同时淘汰最久未用。实现是 HashMap<K, Node> + HashMap<freq, DoubleLinkedList> + minFreq 指针，全部 O(1)。
  2. 带过期时间的 LRU：节点加 expireAt 字段，get 时懒删除；再配一个 ScheduledExecutorService 定期清扫，或用小顶堆按过期时间排序做主动淘汰。
  3. LRU-K：记录最近 K 次访问，只有被访问 K 次以上的数据才进主缓存，能有效防止偶发的批量扫描把热点数据冲掉（缓存污染）。
  4. 分段 LRU 提升并发度：按 key.hashCode() 把缓存分成 N 个 LruCache 分片，每片一把锁 —— 这正是 ConcurrentHashMap JDK7 分段锁的思路。
  5. 用 LinkedHashMap 实现 FIFO 缓存：accessOrder 保持默认 false，只按插入顺序淘汰，代码完全一样。
  6. 为什么 Redis 的 LRU 是「近似 LRU」？ 因为维护完整链表的内存和 CPU 成本太高，Redis 改为随机采样若干 key（maxmemory-samples，默认 5）淘汰其中最久未用的，用精度换性能 —— 这是工程上典型的权衡。

题 3：手写一个简易 ArrayList（泛型 + 1.5 倍扩容 + fail-fast 迭代器） ​

核心实现：

java
import java.util.*;

public class MyArrayList<E> implements Iterable<E> {

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

    private Object[] elementData;
    private int size;
    private int modCount;            // ⭐ 结构性修改计数，fail-fast 的核心

    public MyArrayList() { this.elementData = EMPTY; }

    public MyArrayList(int initialCapacity) {
        if (initialCapacity < 0) throw new IllegalArgumentException("capacity < 0");
        this.elementData = initialCapacity == 0 ? EMPTY : new Object[initialCapacity];
    }

    /* ---------- 增 ---------- */
    public boolean add(E e) {
        ensureCapacity(size + 1);
        elementData[size++] = e;
        return true;
    }

    public void add(int index, E e) {
        checkPositionIndex(index);                 // 插入允许 index == size
        ensureCapacity(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = e;
        size++;
    }

    /* ---------- 删 ---------- */
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        checkElementIndex(index);
        modCount++;                                // ⭐ 结构变了
        E old = (E) elementData[index];
        int moved = size - index - 1;
        if (moved > 0) System.arraycopy(elementData, index + 1, elementData, index, moved);
        elementData[--size] = null;                // ⭐ 置 null 帮助 GC，但数组长度不变（不缩容）
        return old;
    }

    public boolean remove(Object o) {              // ⚠️ 与 remove(int) 构成重载陷阱
        int i = indexOf(o);
        if (i < 0) return false;
        remove(i);
        return true;
    }

    public void clear() {
        modCount++;
        for (int i = 0; i < size; i++) elementData[i] = null;
        size = 0;
    }

    /* ---------- 查改 ---------- */
    @SuppressWarnings("unchecked")
    public E get(int index) { checkElementIndex(index); return (E) elementData[index]; }

    @SuppressWarnings("unchecked")
    public E set(int index, E e) {
        checkElementIndex(index);
        E old = (E) elementData[index];
        elementData[index] = e;                    // ⭐ set 不是结构性修改，modCount 不变
        return old;
    }

    public int indexOf(Object o) {
        for (int i = 0; i < size; i++) {
            if (o == null ? elementData[i] == null : o.equals(elementData[i])) return i;
        }
        return -1;
    }

    public boolean contains(Object o) { return indexOf(o) >= 0; }
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }

    /* ---------- 扩容：核心考点 ---------- */
    private void ensureCapacity(int minCapacity) {
        if (elementData == EMPTY) {
            elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];  // 懒加载
            modCount++;
            return;
        }
        if (minCapacity - elementData.length > 0) grow(minCapacity);
    }

    private void grow(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);          // ⭐ 1.5 倍
        if (newCapacity - minCapacity < 0) newCapacity = minCapacity;        // 一次加太多
        if (newCapacity - Integer.MAX_VALUE + 8 > 0) newCapacity = Integer.MAX_VALUE - 8;
        elementData = Arrays.copyOf(elementData, newCapacity);       // ⭐ O(n) 拷贝
    }

    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = size == 0 ? EMPTY : Arrays.copyOf(elementData, size);
        }
    }

    /* ---------- 越界校验：区分「访问」和「插入」 ---------- */
    private void checkElementIndex(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    private void checkPositionIndex(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    /* ---------- fail-fast 迭代器 ---------- */
    @Override
    public Iterator<E> iterator() { return new Itr(); }

    private class Itr implements Iterator<E> {
        int cursor;                       // 下一个要返回的下标
        int lastRet = -1;                 // 上一个返回的下标，-1 表示不可删除
        int expectedModCount = modCount;  // ⭐ 创建时拍快照

        @Override public boolean hasNext() { return cursor != size; }

        @Override
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            if (cursor >= size) throw new NoSuchElementException();
            lastRet = cursor;
            return (E) elementData[cursor++];
        }

        @Override
        public void remove() {
            if (lastRet < 0) throw new IllegalStateException();   // next() 之前不能删
            checkForComodification();
            MyArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;    // ⭐ 关键：把快照同步回来，所以 it.remove 安全
        }

        private void checkForComodification() {
            if (modCount != expectedModCount) throw new ConcurrentModificationException();
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(elementData[i]);
            if (i < size - 1) sb.append(", ");
        }
        return sb.append(']').toString();
    }

    /* ---------- 自测 ---------- */
    public static void main(String[] args) {
        MyArrayList<String> list = new MyArrayList<>();
        for (int i = 0; i < 12; i++) list.add("e" + i);   // 触发一次扩容 10 → 15
        System.out.println(list + " size=" + list.size());

        list.add(0, "head");
        System.out.println(list.get(0) + " / " + list.remove(0));

        Iterator<String> it = list.iterator();
        while (it.hasNext()) if (it.next().endsWith("1")) it.remove();   // ✅ 安全
        System.out.println(list);

        try {
            for (String s : list) list.remove(s);          // ❌ 预期抛 CME
        } catch (ConcurrentModificationException e) {
            System.out.println("CME 触发 ✅");
        }
    }
}

三个必须记住的点：

  1. 扩容写成 oldCapacity + (oldCapacity >> 1)，并且要处理「一次加入很多元素」时 newCapacity < minCapacity 的分支，以及接近 Integer.MAX_VALUE 的溢出分支。
  2. modCount 只在结构性修改时自增（add / remove / clear / grow），set 不算；Iterator.remove 删除后必须把 expectedModCount = modCount 同步回来。
  3. 越界校验要区分两套：get/set/remove 用 index >= size，而 add(index, e) 允许 index == size（尾部追加），面试写错这点是常见扣分项。

✅ 边界 Case 自测：

场景期望行为
new MyArrayList<>() 后 size()0，且底层数组长度为 0（懒加载未分配）
第 1 次 add数组长度变成 10
第 11 次 add扩容到 15（10 + 10>>1）
new MyArrayList<>(-1)抛 IllegalArgumentException
get(-1) / get(size)抛 IndexOutOfBoundsException
add(size, e)✅ 合法，等价于尾部追加
add(size + 1, e)抛 IndexOutOfBoundsException
remove(0) 后末尾槽位被置为 null，elementData.length 不变
存入 null 再 indexOf(null)能正确找到（indexOf 做了 null 分支）
remove(1) 与 remove(Integer...)前者按下标，后者按对象 —— 验证重载行为
it.remove() 未调 next() 先调抛 IllegalStateException
连续两次 it.remove()第二次抛 IllegalStateException
迭代中调 list.add下一次 next() 抛 CME
迭代中调 list.set不抛异常（set 不改 modCount）
clear() 后再迭代hasNext() 直接 false
trimToSize() 后数组长度等于 size

🔁 变种拓展题：

  1. 加上 subList(from, to) 返回视图：内部持有父 list 引用和偏移量，并共享 modCount —— 由此解释为什么改了父 list 之后访问 subList 会抛 CME。
  2. 实现 ListIterator：支持 previous()、add()、set()，注意 lastRet 在反向遍历时的语义变化。
  3. 把扩容改成 2 倍，压测对比：1.5 倍的优势是更容易复用之前释放的内存块（内存碎片更少），2 倍的优势是扩容次数少；JDK 选 1.5 是空间友好的折中。
  4. 手写 MyLinkedList：双向链表 + node(int index) 的「下标小于 size/2 从头找，否则从尾找」优化，对比两者在中间插入的实测性能。
  5. 让它线程安全：分别用 synchronized 方法、ReentrantReadWriteLock、CopyOnWrite 三种方式实现，并说明各自的适用场景与代价。
  6. 实现 Serializable：为什么 elementData 要声明为 transient？因为数组里通常有大量空槽位，JDK 通过自定义 writeObject 只序列化前 size 个有效元素，节省空间。

题 4：手写一个简易 HashMap（扰动 + 位与寻址 + 扩容高低位拆分） ​

核心实现：

java
import java.util.*;

public class MyHashMap<K, V> {

    static final int DEFAULT_CAPACITY = 16;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int MAXIMUM_CAPACITY = 1 << 30;

    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;
        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash; this.key = key; this.value = value; this.next = next;
        }
    }

    private Node<K, V>[] table;
    private int size;
    private int threshold;
    private final float loadFactor;

    public MyHashMap() { this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); }

    public MyHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }

    public MyHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) throw new IllegalArgumentException("capacity < 0");
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("illegal loadFactor");
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);   // ⭐ 与 JDK 一致：先存到 threshold
    }

    /* ---------- 向上取整到 2 的 n 次方：把最高位的 1 向右铺满再 +1 ---------- */
    static int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;  n |= n >>> 2;  n |= n >>> 4;
        n |= n >>> 8;  n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    /* ---------- 扰动函数：高 16 位异或到低 16 位 ---------- */
    static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /* ---------- put ---------- */
    public V put(K key, V value) {
        if (table == null) resize();
        int hash = hash(key);
        int i = (table.length - 1) & hash;        // ⭐ 位与代替取模
        Node<K, V> first = table[i];

        if (first == null) {                      // 空桶，直接放
            table[i] = new Node<>(hash, key, value, null);
        } else {
            Node<K, V> e = first, prev = null;
            while (e != null) {
                // ⭐ 先比 hash（快），再比引用，最后才 equals
                if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                    V old = e.value;
                    e.value = value;
                    return old;                   // ⭐ 覆盖已有 key：size 不变，不扩容
                }
                prev = e; e = e.next;
            }
            prev.next = new Node<>(hash, key, value, null);   // ⭐ 尾插（JDK8 行为）
        }
        if (++size > threshold) resize();
        return null;
    }

    /* ---------- get / containsKey / remove ---------- */
    public V get(Object key) {
        Node<K, V> e = getNode(key);
        return e == null ? null : e.value;
    }

    public boolean containsKey(Object key) { return getNode(key) != null; }

    private Node<K, V> getNode(Object key) {
        if (table == null || size == 0) return null;
        int hash = hash(key);
        for (Node<K, V> e = table[(table.length - 1) & hash]; e != null; e = e.next) {
            if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) return e;
        }
        return null;
    }

    public V remove(Object key) {
        if (table == null) return null;
        int hash = hash(key);
        int i = (table.length - 1) & hash;
        Node<K, V> e = table[i], prev = null;
        while (e != null) {
            if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                if (prev == null) table[i] = e.next;    // 删的是头节点
                else prev.next = e.next;
                size--;
                return e.value;
            }
            prev = e; e = e.next;
        }
        return null;
    }

    /* ---------- 扩容：高低位拆分，不重算 hash ---------- */
    @SuppressWarnings("unchecked")
    private void resize() {
        Node<K, V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int newCap, newThr;

        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; }
            newCap = oldCap << 1;                       // ⭐ 2 倍，保持 2 的 n 次方
            newThr = (int) (newCap * loadFactor);
        } else if (threshold > 0) {                     // 构造时传了初始容量
            newCap = threshold;
            newThr = (int) (newCap * loadFactor);
        } else {
            newCap = DEFAULT_CAPACITY;
            newThr = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR);
        }
        threshold = newThr;
        Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
        table = newTab;
        if (oldTab == null) return;

        for (int j = 0; j < oldCap; j++) {
            Node<K, V> e = oldTab[j];
            if (e == null) continue;
            oldTab[j] = null;
            if (e.next == null) {                       // 只有一个节点，直接定位
                newTab[e.hash & (newCap - 1)] = e;
                continue;
            }
            // ⭐ 链表拆成「低位链」和「高位链」，保持相对顺序
            Node<K, V> loHead = null, loTail = null, hiHead = null, hiTail = null;
            while (e != null) {
                Node<K, V> next = e.next;
                if ((e.hash & oldCap) == 0) {           // ⭐ 核心：一次位与定去向
                    if (loTail == null) loHead = e; else loTail.next = e;
                    loTail = e;
                } else {
                    if (hiTail == null) hiHead = e; else hiTail.next = e;
                    hiTail = e;
                }
                e = next;
            }
            if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
            if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
        }
    }

    public int size() { return size; }
    public int capacity() { return table == null ? 0 : table.length; }

    /* ---------- 调试用：打印桶分布，直观看冲突 ---------- */
    public void printDistribution() {
        if (table == null) { System.out.println("table 未初始化"); return; }
        for (int i = 0; i < table.length; i++) {
            int len = 0;
            for (Node<K, V> e = table[i]; e != null; e = e.next) len++;
            if (len > 0) System.out.println("bucket[" + i + "] 链长 = " + len);
        }
    }

    public static void main(String[] args) {
        MyHashMap<String, Integer> map = new MyHashMap<>();
        for (int i = 0; i < 20; i++) map.put("key" + i, i);
        System.out.println("size=" + map.size() + " capacity=" + map.capacity());  // 20 / 32
        System.out.println(map.get("key7") + " " + map.get("none"));
        System.out.println(map.put("key7", 700) + " → " + map.get("key7"));        // 7 → 700
        System.out.println(map.remove("key7") + " " + map.containsKey("key7"));    // 700 false

        map.put(null, -1);                       // null key 固定落在 table[0]
        System.out.println("null key = " + map.get(null));
        System.out.println("tableSizeFor(13) = " + tableSizeFor(13));              // 16
        map.printDistribution();
    }
}

三个必须记住的点：

  1. 三件套必须一字不差：扰动 (h = key.hashCode()) ^ (h >>> 16)、寻址 (n - 1) & hash、扩容拆分 (e.hash & oldCap) == 0。
  2. 覆盖已有 key 时 size 不变、不触发扩容，而且要返回旧值 —— 这是 put 的语义，写漏了直接判错。
  3. 链表比较顺序是 hash → == → equals，先比 int 极快，能挡掉绝大多数不相等的情况；同时 key 为 null 时要走单独分支，不能直接调 key.equals。

✅ 边界 Case 自测：

场景期望行为
new MyHashMap<>() 后立刻 get返回 null，不抛 NPE（table 还是 null）
tableSizeFor(0) / (1) / (13) / (17)1 / 1 / 16 / 32
put 20 个元素（默认 16）容量变成 32，阈值 24
put 已存在的 key返回旧值，size 不变
put(null, v)成功，hash(null) == 0，落在 table[0]
get(null)能正确取到
两个 hashCode 相同但 equals 不同的 key挂成链表，各自独立存储
两个 equals 相同的 key后者覆盖前者
只重写 equals 不重写 hashCode 的 key取不到值（能验证契约的重要性）
删除桶内头节点 / 中间节点 / 尾节点三种情况链表都要正确连上
删除不存在的 key返回 null，size 不变
扩容后所有 key 仍可查到遍历校验 get(k) == v（最关键的一条）
扩容后链表相对顺序与扩容前一致（尾插 + 高低位拆分的性质）
把 key 设计成可变对象，put 后改字段get 返回 null（复现内存泄漏场景）
loadFactor = 0 或 NaN构造抛 IllegalArgumentException

🔁 变种拓展题：

  1. 加上树化：链表长度 ≥ 8 且容量 ≥ 64 时转红黑树，并实现 UNTREEIFY_THRESHOLD = 6 的退化 —— 这是完整版 HashMap 最复杂的部分，面试通常只要求说清条件。
  2. 实现 entrySet() 视图 + fail-fast 迭代器：加 modCount，并让 keySet、values、entrySet 都是视图而非副本。
  3. 改成 LinkedHashMap：给 Node 加 before/after 指针维护一条贯穿所有节点的双向链表，再提供 accessOrder 开关和 removeEldestEntry 钩子，就能直接当 LRU 用。
  4. 改成线程安全：对照 ConcurrentHashMap 的思路 —— 空桶用 AtomicReferenceArray 的 CAS 写入、非空桶 synchronized 锁头节点，体会「锁桶不锁表」。
  5. 实现开放寻址法版本：用线性探测 / 二次探测代替链表，分析删除时为什么需要「墓碑标记（tombstone）」，以及它在 CPU 缓存上的优势。
  6. 故意写一个坏 hashCode（恒返回 1），用 printDistribution() 观察所有元素挤进一个桶、查询退化成 O(n) 的现象，再解释哈希碰撞攻击与树化的意义。

题 5：并发场景综合题 —— 线程安全计数器、本地缓存与 TopK ​

核心实现：

java
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.LongAdder;
import java.util.function.Function;
import java.util.stream.Collectors;

public class ConcurrentCollectionDemo {

    /* ========== ① 并发词频统计：三种写法对比 ========== */
    static void wordCount() throws Exception {
        List<String> words = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) words.add("w" + (i % 100));

        // ❌ 错误：read-modify-write 不原子，统计值会偏小
        Map<String, Integer> wrong = new ConcurrentHashMap<>();
        // wrong.put(w, wrong.getOrDefault(w, 0) + 1);

        // ✅ 写法 A：merge，最简洁的原子累加
        Map<String, Integer> byMerge = new ConcurrentHashMap<>();
        runParallel(words, w -> byMerge.merge(w, 1, Integer::sum));

        // ✅ 写法 B：LongAdder，热点 key 下性能最好
        Map<String, LongAdder> byAdder = new ConcurrentHashMap<>();
        runParallel(words, w -> byAdder.computeIfAbsent(w, k -> new LongAdder()).increment());

        // ✅ 写法 C：并行流 + groupingByConcurrent
        Map<String, Long> byStream = words.parallelStream()
                .collect(Collectors.groupingByConcurrent(Function.identity(), Collectors.counting()));

        System.out.println("merge  w0 = " + byMerge.get("w0"));         // 1000
        System.out.println("adder  w0 = " + byAdder.get("w0").sum());   // 1000
        System.out.println("stream w0 = " + byStream.get("w0"));        // 1000
    }

    /* ========== ② 并发安全的本地缓存 ========== */
    static class LocalCache<K, V> {
        private final ConcurrentHashMap<K, V> map = new ConcurrentHashMap<>();
        private final Function<K, V> loader;

        LocalCache(Function<K, V> loader) { this.loader = loader; }

        /* ⚠️ 看着没问题，但 loader 是远程调用时会把整个桶锁住 */
        V getBad(K key) { return map.computeIfAbsent(key, loader); }

        /* ✅ 推荐：锁外加载 + putIfAbsent，牺牲「可能重复加载」换取不阻塞同桶的其他 key */
        V get(K key) {
            V v = map.get(key);
            if (v != null) return v;
            v = loader.apply(key);                  // 在锁外执行耗时加载
            if (v == null) return null;             // ⚠️ CHM 不允许 null value
            V prev = map.putIfAbsent(key, v);       // 原子写入，输掉竞争就用别人的
            return prev != null ? prev : v;
        }

        /* ✅ 要求「只加载一次」时用 Future 占位，这是 Guava/Caffeine 的核心思路 */
        private final ConcurrentHashMap<K, Future<V>> futures = new ConcurrentHashMap<>();

        V getOnce(K key) throws Exception {
            Future<V> f = futures.get(key);
            if (f == null) {
                FutureTask<V> task = new FutureTask<>(() -> loader.apply(key));
                f = futures.putIfAbsent(key, task);   // ⭐ 原子占位
                if (f == null) { f = task; task.run(); }  // 抢到的线程负责真正加载
            }
            try {
                return f.get();                       // 其他线程在这里等结果，不阻塞别的 key
            } catch (ExecutionException e) {
                futures.remove(key, f);               // ⚠️ 失败要移除，否则缓存了异常
                throw e;
            }
        }
    }

    /* ========== ③ TopK：小顶堆，O(n log k) ========== */
    static List<Map.Entry<String, Integer>> topK(Map<String, Integer> counts, int k) {
        // 小顶堆：堆顶是「当前 K 个中最小的」，比它大就替换掉
        PriorityQueue<Map.Entry<String, Integer>> heap =
                new PriorityQueue<>(k, Map.Entry.comparingByValue());
        for (Map.Entry<String, Integer> e : counts.entrySet()) {
            if (heap.size() < k) {
                heap.offer(e);
            } else if (e.getValue() > heap.peek().getValue()) {
                heap.poll();
                heap.offer(e);
            }
        }
        // ⚠️ 堆本身不是有序的，要全量 poll 出来再反转
        List<Map.Entry<String, Integer>> result = new ArrayList<>(k);
        while (!heap.isEmpty()) result.add(heap.poll());
        Collections.reverse(result);
        return result;
    }

    /* 对照：Stream 版 TopK，代码短但是 O(n log n) 全排序 */
    static List<Map.Entry<String, Integer>> topKByStream(Map<String, Integer> counts, int k) {
        return counts.entrySet().stream()
                .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
                .limit(k)
                .collect(Collectors.toList());
    }

    /* ========== ④ 生产者消费者：阻塞队列 ========== */
    static void producerConsumer() throws Exception {
        BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(100);   // ⭐ 必须有界
        ExecutorService pool = Executors.newFixedThreadPool(3);
        final Integer POISON = Integer.MIN_VALUE;                       // 毒丸，优雅停机

        pool.submit(() -> {
            try {
                for (int i = 0; i < 1000; i++) queue.put(i);            // 满了自动阻塞
                queue.put(POISON);
            } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        });
        pool.submit(() -> {
            try {
                while (true) {
                    Integer v = queue.take();                           // 空了自动阻塞
                    if (POISON.equals(v)) break;
                }
            } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        });
        pool.shutdown();
        pool.awaitTermination(10, TimeUnit.SECONDS);
        System.out.println("生产者消费者结束，剩余 = " + queue.size());
    }

    private static void runParallel(List<String> data, java.util.function.Consumer<String> action)
            throws Exception {
        ExecutorService pool = Executors.newFixedThreadPool(8);
        int chunk = data.size() / 8;
        List<Future<?>> futures = new ArrayList<>();
        for (int i = 0; i < 8; i++) {
            List<String> sub = data.subList(i * chunk, (i + 1) * chunk);
            futures.add(pool.submit(() -> sub.forEach(action)));
        }
        for (Future<?> f : futures) f.get();
        pool.shutdown();
    }

    public static void main(String[] args) throws Exception {
        wordCount();
        LocalCache<String, String> cache = new LocalCache<>(k -> "value-" + k);
        System.out.println(cache.get("a") + " " + cache.getOnce("b"));
        Map<String, Integer> counts = Map.of("a", 5, "b", 9, "c", 1, "d", 7);
        System.out.println(topK(new HashMap<>(counts), 2));
        producerConsumer();
    }
}

三个必须记住的点：

  1. ConcurrentHashMap 只保证单方法原子性：计数一律用 merge / compute，热点 key 进一步用 LongAdder 把竞争打散。
  2. computeIfAbsent 的函数体里不能做耗时操作、不能回头操作同一个 map；要「只加载一次」就用 Future 占位（Guava/Caffeine 的做法），要「不阻塞」就锁外加载 + putIfAbsent。
  3. TopK 用小顶堆是 O(n log k)，远优于全排序的 O(n log n)；注意 PriorityQueue 本身遍历无序，必须靠 poll() 才能拿到有序结果。

✅ 边界 Case 自测：

场景期望行为
8 线程各累加 12500 次总数恰好 100000（验证原子性，这是核心断言）
map.put(k, map.get(k) + 1) 版本结果小于 100000，复现丢更新
merge 的 value 为 null等价于 remove（merge 的 remapping 返回 null 会删除该 key）
computeIfAbsent 的函数返回 null不会放入 map，下次还会再次调用
computeIfAbsent 里 put 同一个 map 的 keyJDK8 可能死锁/死循环，JDK9+ 抛 IllegalStateException
putIfAbsent 竞争失败返回已存在的值，调用方要使用返回值而不是自己那份
getOnce 加载抛异常必须 futures.remove(key, f)，否则异常被永久缓存
topK(map, 0)返回空列表，不抛异常
topK(map, k > map.size())返回全部元素
存在相同 value 的 TopK结果顺序不确定但数量正确（需明确 tie 的处理策略）
PriorityQueue 直接 toString()不是有序的（只保证堆顶最小）
ArrayBlockingQueue 满了调 put / addput 阻塞；add 抛 IllegalStateException；offer 返回 false
消费者线程被中断恢复中断标志 Thread.currentThread().interrupt() 后退出
用无界队列且生产快于消费内存持续增长直至 OOM —— 所以必须用有界队列

🔁 变种拓展题：

  1. 统计 10GB 日志的 TopK IP：内存放不下 → 先按 hash(ip) % 1024 分片写到 1024 个小文件（相同 IP 必落同一文件），每个文件内用 HashMap 统计后取 TopK，最后对 1024 组结果做归并 —— 这就是 MapReduce 的雏形。
  2. 实时 TopK：数据流持续到来，要求随时能查当前 TopK。方案是 HashMap 记频次 + 一个大小为 K 的小顶堆，或者直接用 Count-Min Sketch 做近似统计（牺牲精度换内存）。
  3. 把 LocalCache 补上过期和刷新：加 expireAfterWrite、refreshAfterWrite，并说明「缓存击穿」（热点 key 失效瞬间大量请求打到 DB）为什么必须用 Future 占位或分布式锁解决。
  4. 用 ConcurrentSkipListMap 实现带排序的并发 Map：对比它和「TreeMap + 读写锁」的性能差异，理解跳表为什么适合无锁并发。
  5. Collections.synchronizedList 的遍历为什么还要手动加锁：写出正确的 synchronized (list) { for (...) } 代码，解释包装类只同步了方法而迭代器是跨多次方法调用的。
  6. 用 CountDownLatch 改写 runParallel：对比 Future.get() 等待和 latch.await() 的语义区别，以及为什么不能用 Thread.sleep 等并发任务结束。

题 6：手写比较器契约自测器 + 动态多字段排序构建器 ​

这题是深挖 #18 的动手版。前半部分能让你在单元测试里就把违约的比较器抓出来，而不是等上线后看到 Comparison method violates its general contract!；后半部分是后台列表接口「按任意字段排序」的标准解法。

核心实现：

java
import java.util.*;
import java.util.function.Function;

/** ① 比较器契约自测器：O(n³) 暴力校验，只在单元测试里用 */
public final class ComparatorContract {

    public static <T> void verify(List<T> samples, Comparator<T> cmp) {
        int n = samples.size();

        // 契约 1：反对称性 sgn(c(a,b)) == -sgn(c(b,a))
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                T a = samples.get(i), b = samples.get(j);
                int ab = sgn(cmp.compare(a, b));
                int ba = sgn(cmp.compare(b, a));
                if (ab != -ba) {
                    throw new AssertionError(String.format(
                            "违反反对称性: compare(%s,%s)=%d, compare(%s,%s)=%d", a, b, ab, b, a, ba));
                }
            }
        }

        // 契约 2：自反性 compare(a, a) == 0（反对称性的特例，单独报错更好定位）
        for (T a : samples) {
            if (cmp.compare(a, a) != 0) {
                throw new AssertionError("compare(a, a) != 0: " + a);
            }
        }

        // 契约 3：传递性 a>b && b>c ⇒ a>c
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    T a = samples.get(i), b = samples.get(j), c = samples.get(k);
                    if (sgn(cmp.compare(a, b)) > 0 && sgn(cmp.compare(b, c)) > 0
                            && sgn(cmp.compare(a, c)) <= 0) {
                        throw new AssertionError(String.format(
                                "违反传递性: %s > %s > %s 但 compare(%s,%s)=%d",
                                a, b, c, a, c, cmp.compare(a, c)));
                    }
                }
            }
        }

        // 契约 4：等价传递 c(a,b)==0 ⇒ sgn(c(a,x)) == sgn(c(b,x))
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                T a = samples.get(i), b = samples.get(j);
                if (cmp.compare(a, b) != 0) continue;
                for (T x : samples) {
                    if (sgn(cmp.compare(a, x)) != sgn(cmp.compare(b, x))) {
                        throw new AssertionError(String.format(
                                "违反等价传递: %s == %s 但对 %s 的比较结果不同", a, b, x));
                    }
                }
            }
        }
    }

    /** 稳定性与「结果是否真的有序」双重校验 */
    public static <T> void verifySorted(List<T> src, Comparator<T> cmp) {
        List<T> sorted = new ArrayList<>(src);
        sorted.sort(cmp);
        for (int i = 1; i < sorted.size(); i++) {
            if (cmp.compare(sorted.get(i - 1), sorted.get(i)) > 0) {
                throw new AssertionError("排序结果并非有序，位置 " + i);
            }
        }
    }

    private static int sgn(int v) { return Integer.compare(v, 0); }

    private ComparatorContract() {}
}
java
/** ② 动态多字段排序构建器：把前端传的 "age,desc;name,asc" 变成安全的 Comparator */
public final class SortBuilder<T> {

    /** ⭐ 白名单：绝不能直接把前端字符串当字段名反射取值（SQL/反射注入 + 性能黑洞） */
    private final Map<String, Comparator<T>> allowed = new LinkedHashMap<>();

    public <U extends Comparable<? super U>> SortBuilder<T> field(String name, Function<T, U> getter) {
        // nullsLast 包一层，彻底杜绝字段为 null 时的 NPE
        allowed.put(name, Comparator.comparing(getter, Comparator.nullsLast(Comparator.naturalOrder())));
        return this;
    }

    /** 基本类型专用，避免装箱 */
    public SortBuilder<T> intField(String name, java.util.function.ToIntFunction<T> getter) {
        allowed.put(name, Comparator.comparingInt(getter));   // 内部用 Integer.compare，不会溢出
        return this;
    }

    /**
     * @param expr      形如 "age,desc;name,asc"，非法字段直接忽略（也可以选择抛 400）
     * @param tieBreak  ⭐ 兜底唯一字段比较器，保证全序与结果可复现
     */
    public Comparator<T> build(String expr, Comparator<T> tieBreak) {
        Comparator<T> result = null;
        if (expr != null && !expr.isBlank()) {
            for (String seg : expr.split(";")) {
                String[] kv = seg.trim().split(",");
                if (kv.length == 0) continue;
                Comparator<T> one = allowed.get(kv[0].trim());
                if (one == null) continue;                              // 不在白名单，静默忽略
                if (kv.length > 1 && "desc".equalsIgnoreCase(kv[1].trim())) {
                    one = one.reversed();                               // ⭐ 只反转当前这一个字段
                }
                result = (result == null) ? one : result.thenComparing(one);
            }
        }
        // 没有任何合法字段时，也必须返回一个确定的顺序，不能返回 null
        return result == null ? tieBreak : result.thenComparing(tieBreak);
    }

    private SortBuilder() {}
    public static <T> SortBuilder<T> of(Class<T> type) { return new SortBuilder<>(); }
}

// 用法
Comparator<User> cmp = SortBuilder.of(User.class)
        .intField("age", User::getAge)
        .field("name", User::getName)
        .field("createdAt", User::getCreatedAt)
        .build(req.getSort(), Comparator.comparing(User::getId));   // id 兜底
users.sort(cmp);

✅ 边界 Case 自测：

  • 把 (a, b) -> a.getScore() > b.getScore() ? 1 : -1 丢给 verify，确认在样本里有两个相等元素时就报违反反对称性（这是最有价值的一条）
  • 构造 balance = Integer.MAX_VALUE 和 Integer.MIN_VALUE 的两个对象，验证 a - b 写法被 verify 抓出来、而 comparingInt 能通过
  • 样本里放 name == null 的对象，确认 nullsLast 生效且不抛 NPE
  • 同一组数据用 build("age,desc", ...) 排两次，结果必须完全一致（验证 tieBreak 保证了可复现性）
  • 传入 "password,asc" 这种不在白名单的字段，确认被忽略且不会反射到任何字段
  • 传入 null、空串、";;;"、"age"（缺方向）这几种畸形输入，确认都返回可用的比较器而不是 NPE
  • 用 comparing(A).thenComparing(B).reversed() 和 comparing(A, reverseOrder()).thenComparing(B) 各排一次，亲手对比两者结果的差异
  • 准备 40 个以上的元素（跨过 MIN_MERGE = 32）再用违约比较器排序，复现 IllegalArgumentException；再把元素减到 10 个，确认不报错但顺序是错的

🔁 变种拓展题：

  • 把 verify 的 O(n³) 降成抽样：传入 maxSamples，超过阈值就随机抽样 + 固定随机种子，保证失败可复现；这样可以把它挂到 CI 里跑真实数据
  • 支持中文按拼音排序：Comparator.comparing(User::getName, Collator.getInstance(Locale.CHINA))，注意 Collator 不是线程安全的，必须每次新建或用 ThreadLocal（并配 remove）
  • 支持「自定义枚举顺序」：业务要求状态按「待支付 → 已支付 → 已取消」而不是枚举声明序，用 Comparator.comparingInt(u -> ORDER.indexOf(u.getStatus()))，ORDER 用 List.of 固化
  • 排序下推到数据库：白名单模式天然可以复用成 ORDER BY 的字段白名单 —— 内存排序只适合「已经全量加载」的小数据集，上了分页就必须下推，否则会出现「每页内部有序、跨页乱序」的经典 Bug
  • TopK 场景不要全排序：只要前 N 条时用 PriorityQueue 维护大小为 N 的堆，复杂度从 O(n log n) 降到 O(n log N)

⚠️ 当日踩坑实录 ​

❌ 坑✅ 解决方案
for-each 里 list.remove(e) 抛 ConcurrentModificationException用 list.removeIf(条件) 或 Iterator.remove()；绝不在 for-each 里改结构
删「倒数第二个」元素时不报错，换数据后才炸不要依赖「测试没报错」，统一用 removeIf，并加静态扫描规则拦截
list.remove(1) 删的是下标不是值List<Integer> 按值删要写 remove(Integer.valueOf(1)) 或 remove((Integer) 1)
Arrays.asList(...) 上 add / remove 抛 UnsupportedOperationException需要可变集合就 new ArrayList<>(Arrays.asList(...))
Arrays.asList(intArray) 得到 size == 1基本类型数组用 Arrays.stream(arr).boxed().collect(toList())
List.of(...) 传 null 抛 NPE、set 也抛异常List.of 是真不可变且禁 null，要可变/可含 null 用 ArrayList
JDK16 的 stream().toList() 返回不可变 List，add 抛异常需要可变就用 collect(Collectors.toCollection(ArrayList::new))
subList 改元素影响了原集合，原集合 add 后访问 subList 抛 CMEsubList 是视图；要独立副本必须 new ArrayList<>(list.subList(a, b))
Collections.unmodifiableList 包装后源集合改了它也变它只是只读视图；要真不可变用 List.of 或 Guava ImmutableList.copyOf
getter 直接 return items 被外部 clear() 破坏内部状态getter 做防御性拷贝或返回只读视图
new HashMap<>(1000) 放 1000 个元素依然扩容容量按 expectedSize / 0.75 + 1 算，或用 Maps.newHashMapWithExpectedSize
默认容量放 5 万条数据，GC 频繁、接口变慢数据量可预估时一律指定初始容量，减少 resize 的 O(n) 拷贝与垃圾
清空 ArrayList 后内存没降remove/clear 不缩容，需要释放调 trimToSize()，或干脆换新对象
LinkedList 用 for (i...) list.get(i) 遍历，接口 P99 飙升实际是 O(n²)；改用 ArrayList，或用迭代器/for-each 遍历链表
用 LinkedList 当「高性能队列」，内存翻 10 倍双端队列用 ArrayDeque，阻塞队列用 ArrayBlockingQueue
ArrayDeque.push(null) 抛 NPEArrayDeque 把 null 当队空标记，禁止存 null；需要 null 换 LinkedList
用 Stack / Vector 被代码评审打回栈用 ArrayDeque，列表用 ArrayList，两者都是遗留的全同步类
PriorityQueue 直接遍历输出不是有序的它只保证堆顶最小；要有序必须反复 poll()，或用 TreeSet / 排序
只重写 equals 不重写 hashCode，HashSet 去重失效两者必须同时重写，用 IDE 生成或 Objects.equals + Objects.hash
可变对象当 key，改完字段 get 返回 null 且内存泄漏key 必须不可变（字段 final、无 setter），或直接用业务主键做 key
Lombok @Data 在继承场景下 equals 行为意外实体类显式写 equals/hashCode 只基于业务主键，或指定 callSuper
TreeMap / TreeSet 存 null key 抛 NPE排序容器必须能比较，null 一律先过滤
TreeSet 把两个不同对象判成重复它用比较器结果是否为 0 判重，不是 equals；比较器要包含完整业务主键
ConcurrentHashMap.put(k, null) 抛 NPECHM key/value 都禁 null；用空对象或常量占位，查询用 containsKey
static HashMap 被多线程写，CPU 100%换 ConcurrentHashMap；静态集合字段禁止使用非线程安全实现
用了 CHM 但 map.put(k, map.get(k) + 1) 仍丢数据组合操作要用 merge / compute / putIfAbsent，热点用 LongAdder
computeIfAbsent 里做远程调用，同桶 key 全部阻塞锁外加载 + putIfAbsent，或用 Future 占位，或直接用 Caffeine
computeIfAbsent 的函数里操作同一个 map 导致死锁函数体保持纯粹，不碰外部同一个 map
用 chm.size() 做「满 N 条就落库」的判断，结果偏差size() 是估算值（baseCount + CounterCell），精确计数用 LongAdder 单独维护
CopyOnWriteArrayList 当高频写入容器，GC 爆炸它只适合读多写极少；高频写用 ConcurrentLinkedQueue / 阻塞队列
Collections.synchronizedList 遍历仍抛 CME遍历要手动 synchronized (list) { ... } 包住整个循环
Collectors.toMap 抛 Duplicate key永远传第三个合并参数：toMap(k, v, (a, b) -> b)
Collectors.toMap 的 value 为 null 抛 NPE在 valueMapper 里兜底，或改用 groupingBy
toMap 结果顺序和源数据不一致默认是 HashMap，要保序传第四个参数 LinkedHashMap::new
map.keySet() 当独立集合传出去，调用方删除后源 map 也少了数据keySet/values/entrySet 都是视图，要副本就 new HashSet<>(map.keySet())
用 keySet() + get() 遍历，性能白损失一半统一用 entrySet() 遍历
Integer 做 key，== 比较在大于 127 时失效包装类一律用 equals；HashMap.get 内部用 equals 所以不受影响
存几百万个 Integer，内存远超预期大量基本类型用数组，或引入 Eclipse Collections / fastutil 这类原始类型集合
list.removeAll(otherList) 在大数据量下极慢先把 otherList 转成 HashSet，把 O(n·m) 降到 O(n)
嵌套集合 Map<String, List<X>> 用 getOrDefault 后 add 丢数据getOrDefault 返回的默认值没放进 map，要用 computeIfAbsent(k, x -> new ArrayList<>())
比较器写 (a, b) -> a.getW() > b.getW() ? 1 : -1，线上抛 Comparison method violates its general contract!相等时必须返回 0；统一用 Comparator.comparingInt / comparing，禁止手写三元
比较器写 a.getCount() - b.getCount()，大数值时顺序错乱减法会整型溢出；一律用 Integer.compare(a, b) 或 comparingInt
比较器里漏了 return 0 分支（只写了大于和小于）三条分支必须齐全，用 ComparatorContract.verify 在单测里兜一遍
本地 20 条数据不报错，线上几千条才抛违约异常TimSort 元素数 < MIN_MERGE = 32 走二分插入排序不校验；测试数据必须 > 32
加 -Djava.util.Arrays.useLegacyMergeSort=true 后异常消失，就当修好了那只是关掉校验，顺序依旧是错的；必须改比较器本身
comparing(A).thenComparing(B).reversed() 把整条链都反转了reversed() 作用于「它之前的整条链」；只反单字段写 comparing(A, reverseOrder())
排序字段为 null 抛 NPE包一层 Comparator.nullsFirst(...) / nullsLast(...)
TreeSet 的比较器只比了一个字段，不同对象被静默去重排序容器只看 compare() == 0，比较器末尾必须补唯一键（如 id）
同一份数据两次排序结果不同，分页出现重复/漏数据比较器没有全序；末尾加 tieBreak 唯一字段，分页排序尽量下推到数据库
把前端传的排序字段直接反射取值，被安全扫描报注入风险排序字段必须走白名单 Map<String, Comparator<T>>，非法字段忽略或报 400
new ArrayList<>(src) 以为是深拷贝，改副本元素的字段影响了原集合构造拷贝只复制引用；要互不影响必须逐个 new 新对象（Java 无内置深拷贝 API）
Collections.copy(new ArrayList<>(n), src) 抛 IndexOutOfBoundsException它要求目标 size() >= src.size()，不是容量；正常场景直接用 new ArrayList<>(src)
(String[]) list.toArray() 抛 ClassCastException无参 toArray 返回 Object[]；用 toArray(new String[0])
list.toArray(new String[0]) 以为比给准长度慢实测给 0 更快（JVM 对零长度数组有优化），统一写 new String[0]
Arrays.asList(arr) 返回的 List 上 set 后，原数组也变了它是数组的视图，不是副本；要独立副本再包一层 new ArrayList<>(...)
list.parallelStream().forEach(result::add) 偶发丢数据/下标越界并行流写非线程安全集合必错；改用 collect(toList()) / Collectors.toConcurrentMap / 同步容器
WeakHashMap 的 value 里引用了 key，条目永远不回收弱的只是 key；value 持有 key 会形成强引用环路，value 里存 id 而非 key 对象
用字符串字面量 "abc" 当 WeakHashMap 的 key，永不过期字面量在常量池里被强引用；key 必须是业务上会被回收的对象
ThreadLocal 用完没 remove()，线程池里老年代持续上涨必须 try { ... } finally { tl.remove(); }；只清 key 不清 value 仍泄漏
InheritableThreadLocal 在线程池里串了上下文（traceId 错乱）它只在创建线程时传递；线程池场景用 TransmittableThreadLocal（TTL）
WeakHashMap 当多线程缓存用，偶发死循环/数据错乱它非线程安全，且 get 也会清理过期条目改结构；缓存一律用 Caffeine

📌 当日复盘任务 ​

  • [ ] 画出 Collection / Map 的完整继承体系图，标注每个实现类的底层数据结构
  • [ ] 默写 ArrayList 的 grow 方法，说清 1.5 倍、Arrays.copyOf、不缩容三个结论
  • [ ] 解释 ArrayList 的两个空数组常量分别对应什么构造场景
  • [ ] 用一句话说清为什么工程上几乎不用 LinkedList（提到 CPU 缓存行和内存开销）
  • [ ] 对比 Vector / Collections.synchronizedList / CopyOnWriteArrayList 三者的锁策略和适用场景
  • [ ] 说明 HashSet 为什么就是 HashMap，PRESENT 占位对象的作用是什么
  • [ ] 列出 ArrayDeque 的两套 API（抛异常 vs 返回特殊值），说明它为什么禁止 null
  • [ ] 默写 HashMap 的四个关键常量及其含义（16 / 0.75 / 8 / 6 / 64）
  • [ ] 完整口述 put 流程：从扰动 hash 到判断扩容，不漏任何分支
  • [ ] 默写扰动函数 h ^ (h >>> 16)，解释不扰动会带来什么后果
  • [ ] 解释容量为 2 的 n 次方同时服务了「寻址、分布、扩容」三件事
  • [ ] 默写 tableSizeFor，手算 tableSizeFor(13) 和 tableSizeFor(17)
  • [ ] 解释 e.hash & oldCap 做高低位拆分的原理，举一个具体的二进制例子
  • [ ] 完整讲一遍 JDK7 头插法并发扩容成环的过程
  • [ ] 说明 JDK8 为什么仍然线程不安全（数据覆盖、size 不准、树化指针错乱）
  • [ ] 解释树化阈值 8 的泊松分布依据，以及退化阈值为什么是 6
  • [ ] 解释树化为什么还要求容量 ≥ 64
  • [ ] 推导初始容量公式 expectedSize / 0.75 + 1，验证 new HashMap<>(1000) 会扩容
  • [ ] 对比 HashMap / LinkedHashMap / TreeMap 的结构、顺序、复杂度与适用场景
  • [ ] 列出 TreeMap 的六个 NavigableMap 范围查询 API
  • [ ] 对比 Hashtable / synchronizedMap / ConcurrentHashMap 的锁粒度与并发度
  • [ ] 口述 JDK8 CHM 的四个关键点：空桶 CAS、桶锁、读无锁、ForwardingNode 协助扩容
  • [ ] 解释 sizeCtl 的多种取值分别代表什么状态
  • [ ] 解释 CHM 的 size() 为什么是估算值，baseCount 和 CounterCell 各自的角色
  • [ ] 解释 CHM 为什么 key 和 value 都禁止 null（二义性不可消除）
  • [ ] 整理一张「各集合对 null 的支持情况」表并默写一遍
  • [ ] 列出 CHM 的所有原子复合方法，说明 computeIfAbsent 的两个坑
  • [ ] 解释 fail-fast 的实现原理，说清 modCount 和 expectedModCount 的同步时机
  • [ ] 对比 fail-fast、弱一致、快照三类迭代器及其代表集合
  • [ ] 不看答案手写 LRU：LinkedHashMap 版和双向链表版各一遍，验证 10 条边界 Case
  • [ ] 不看答案手写 MyArrayList，必须包含 1.5 倍扩容和 fail-fast 迭代器
  • [ ] 不看答案手写 MyHashMap，必须包含扰动、位与寻址、高低位拆分扩容
  • [ ] 写一个 8 线程并发计数的程序，分别用错误写法和 merge/LongAdder 对比结果差异
  • [ ] 用小顶堆实现 TopK，分析为什么是 O(n log k) 而不是 O(n log n)
  • [ ] 总结 equals / hashCode 的完整契约，并解释可变 key 导致内存泄漏的机制
  • [ ] 整理 Collectors.toMap 的四个坑，并写出一行「永远安全」的标准写法
  • [ ] 画一张集合选型决策树，覆盖「键值对 / 去重 / 有序 / 并发 / 阻塞」五个维度
  • [ ] 在自己项目里搜一遍 new HashMap<>() 和 for-each 中的 remove，列出需要整改的位置
  • [ ] 默写比较器的三条契约（反对称、传递、等价传递），各举一个违约的真实写法
  • [ ] 解释为什么「相等时返回 -1」会导致 Comparison method violates its general contract!
  • [ ] 说清 TimSort 的 MIN_MERGE = 32 如何造成「小数据不报、上量才报」
  • [ ] 解释 useLegacyMergeSort 为什么只是止血而不是修复
  • [ ] 亲手对比 comparing(A).thenComparing(B).reversed() 与 comparing(A, reverseOrder()).thenComparing(B) 的结果差异
  • [ ] 写一个 nullsLast + 末尾补唯一键的多字段比较器，并用契约自测器验证
  • [ ] 解释 TreeSet/TreeMap 判重为什么不看 equals，以及由此引发的静默丢数据
  • [ ] 不看答案手写 ComparatorContract.verify（反对称 + 传递 + 等价传递三重校验）
  • [ ] 实现一个带白名单的动态排序构建器，说明为什么不能反射前端传的字段名
  • [ ] 对比 EnumMap / IdentityHashMap / WeakHashMap 的底层结构与适用场景
  • [ ] 解释 EnumMap 为什么比 HashMap 快（数组下标 vs hash 寻址）
  • [ ] 说清 WeakHashMap 的两个致命误解：弱的是 key 不是 value、字面量当 key
  • [ ] 完整画出 ThreadLocal 的泄漏链，指出弱引用在哪一环、强引用在哪一环
  • [ ] 解释 ThreadLocalMap 为什么用线性探测而非链表，0x61c88647 的作用是什么
  • [ ] 说明 InheritableThreadLocal 在线程池下为什么失效，TTL 是怎么解决的
  • [ ] 整理集合拷贝的三个层次（视图 / 浅拷贝 / 深拷贝），各写一行代码示例
  • [ ] 解释为什么说「Java 没有任何 API 能做深拷贝」，列出三种可行的深拷贝手段
  • [ ] 整理 toArray 的三个坑，并记住 toArray(new T[0]) 这一行标准写法
  • [ ] 写一段并行流写入集合的错误代码，复现丢数据，再用三种正确方案各改一遍