【009】建立了复杂度直觉，知道了「HashMap.get() 是 O(1)、ArrayList.get(index) 是 O(1)、LinkedList.get(index) 是 O(n)」。但为什么？这篇想把「为什么」讲清楚——从内存模型出发，理解数据结构的本质，而不是死记结论。

理解了底层原理，你才能在面对「用 ArrayList 还是 LinkedList」「HashMap 为什么要重写 hashCode」「ConcurrentHashMap 为什么比 Hashtable 快」这类问题时，不靠背答案，而是推导出来。下面我按「数组 → 链表 → 哈希表 → Java 集合对照 → 选型决策」的顺序往下聊。

---

1. 数组：连续内存，随机访问的基础 📦

1.1 内存模型

数组在内存里是一块连续的空间，每个元素占固定大小：

内存地址：  1000  1004  1008  1012  1016
数组内容：  [  1  ][  2  ][  3  ][  4  ][  5  ]
下标：        [0]   [1]   [2]   [3]   [4]

假设 int 占 4 字节，数组起始地址是 1000，那么：

arr[0] 的地址 = 1000 + 0 × 4 = 1000
arr[3] 的地址 = 1000 + 3 × 4 = 1012
arr[i] 的地址 = 起始地址 + i × 元素大小

这就是 O(1) 随机访问的原因：不管 i 是多少，一次乘法加法就能算出地址，直接读取。

1.2 数组的优缺点

操作	复杂度	原因
按下标读/写	O(1)	直接计算地址
末尾追加（有空间）	O(1)	直接写最后位置
中间插入/删除	O(n)	需要移动后面所有元素
按值查找	O(n)	需要逐个比较

中间插入为什么是 O(n)：

插入前：[1][2][3][4][5]
在下标 2 插入 99：
  先把 [3][4][5] 向右移一位：[1][2][_][3][4][5]
  再写入 99：[1][2][99][3][4][5]
移动了 n-2 个元素，O(n)

缓存局部性：连续内存对 CPU 缓存非常友好。CPU 读取数据时会把附近的内存一起加载到缓存（Cache Line，通常 64 字节）。遍历数组时，大部分数据已经在缓存里了，速度极快。

1.3 Java 数组

// 基本类型数组：连续内存，元素直接存值
int[] arr = new int[5];  // 分配 5 × 4 = 20 字节连续内存

// 对象数组：连续内存，但存的是引用（指针），对象本身在堆上
String[] strs = new String[5];  // 分配 5 × 8 = 40 字节（64位JVM，引用8字节）
// strs[0] 存的是指向 String 对象的地址，不是 String 本身

// 数组长度固定，创建后不能改变
// 这是 ArrayList 存在的原因：它在数组基础上提供了动态扩容

Java 对象数组的内存布局：

strs 数组（连续内存）：
[ref→"hello"][ref→"world"][null][null][null]
      ↓              ↓
  堆上的 String   堆上的 String

遍历对象数组时，虽然引用是连续的，但对象本身在堆上分散——这比基本类型数组的缓存局部性差一些。

---

2. ArrayList：数组的动态封装 📋

2.1 内部结构

// ArrayList 的核心字段（简化）
public class ArrayList<E> {
    Object[] elementData;  // 底层数组
    int size;              // 实际元素数量（≤ elementData.length）
}

ArrayList 就是一个可自动扩容的数组。elementData.length 是容量（capacity），size 是实际元素数量。

2.2 扩容机制

// 默认初始容量 10
List<String> list = new ArrayList<>();  // elementData.length = 0（懒初始化）
list.add("a");  // 第一次 add，扩容到 10

// 当 size == capacity 时，触发扩容
// 新容量 = 旧容量 + 旧容量 >> 1 = 旧容量 × 1.5
// 10 → 15 → 22 → 33 → 49 → ...

扩容的代价：

// 扩容时调用 Arrays.copyOf，底层是 System.arraycopy（native 方法）
// 把旧数组的所有元素复制到新数组
// 时间：O(n)，空间：需要同时持有新旧两个数组

摊还 O(1) 的推导：

假设从容量 1 开始，每次扩容 × 2（简化）：
  插入第 1 个：无扩容，1 次操作
  插入第 2 个：扩容复制 1 个，2 次操作
  插入第 3 个：扩容复制 2 个，3 次操作
  插入第 4 个：无扩容，1 次操作
  插入第 5 个：扩容复制 4 个，5 次操作
  ...
  插入 n 个元素的总操作数 ≈ n + n/2 + n/4 + ... ≈ 2n
  平均每次插入 ≈ 2 次操作 → 摊还 O(1)

2.3 初始容量的优化

如果你知道大概要放多少元素，指定初始容量可以避免多次扩容：

// ❌ 不知道大小，可能扩容多次
List<User> users = new ArrayList<>();
for (User u : queryResult) users.add(u);

// ✅ 已知大小，一次分配到位
List<User> users = new ArrayList<>(queryResult.size());
for (User u : queryResult) users.add(u);

// 或直接
List<User> users = new ArrayList<>(queryResult);

什么时候指定初始容量：

• 已知元素数量（如从数据库查出 N 条记录）
• 预期元素数量很大（如批量处理几万条数据）
• 性能敏感的热点路径

2.4 ArrayList vs 原生数组

// 原生数组：类型安全，无装箱，性能最好
int[] scores = new int[100];

// ArrayList<Integer>：有装箱开销（int → Integer），有额外对象头
List<Integer> scoreList = new ArrayList<>(100);

// 大量数值计算时，原生数组比 ArrayList<Integer> 快很多
// 业务代码里通常无所谓，但批量数值处理时要注意

装箱（Boxing）的代价：int 是 4 字节栈上的值，Integer 是堆上的对象（16 字节对象头 + 4 字节值）。ArrayList<Integer> 里每个元素都是一个 Integer 对象，内存占用是原生数组的 4～5 倍，且有 GC 压力。

---

3. 链表：指针串起来的节点 🔗

3.1 内存模型

链表的每个节点包含数据和指向下一个节点的指针：

单向链表：
[data=1 | next→] → [data=2 | next→] → [data=3 | next=null]

双向链表：
null ← [prev | data=1 | next→] ↔ [prev | data=2 | next→] ↔ [prev | data=3 | next=null]

关键特点：节点在内存里不连续，靠指针串联。

3.2 链表的优缺点

操作	复杂度	原因
按下标访问	O(n)	必须从头遍历
头部插入/删除	O(1)	只改指针
尾部插入（有尾指针）	O(1)	直接改尾节点指针
中间插入（已知位置）	O(1)	只改前后节点的指针
中间插入（不知位置）	O(n)	先找位置 O(n)，再插入 O(1)
按值查找	O(n)	必须遍历

插入/删除只改指针：

在节点 B 和 C 之间插入节点 X：
  原来：A → B → C
  新建节点 X，设 X.next = C，B.next = X
  结果：A → B → X → C
  只改了两个指针，O(1)

但找到「B 和 C 之间」需要 O(n)——这是链表中间插入实际上也是 O(n) 的原因。

3.3 缓存局部性劣势

数组遍历：
  内存：[1][2][3][4][5]（连续）
  CPU 读 arr[0] 时，把 arr[0]~arr[15] 都加载到缓存
  读 arr[1] 时，已经在缓存里了 → 极快

链表遍历：
  内存：[1|→0x5000][2|→0x1200][3|→0x8800]（分散）
  CPU 读节点 1 时，加载节点 1 附近的内存到缓存
  读节点 2 时，节点 2 在 0x5000，不在缓存 → 缓存未命中 → 慢

实测：遍历 100 万个元素，ArrayList 比 LinkedList 快 3～10 倍，即使两者都是 O(n)。

3.4 LinkedList 的实现

// LinkedList 的节点（简化）
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

// LinkedList 的核心字段
public class LinkedList<E> {
    int size;
    Node<E> first;  // 头节点
    Node<E> last;   // 尾节点
}

LinkedList 实现了 Deque 接口，可以当双端队列用：

LinkedList<String> deque = new LinkedList<>();
deque.addFirst("a");   // O(1)，改 first 指针
deque.addLast("b");    // O(1)，改 last 指针
deque.removeFirst();   // O(1)
deque.removeLast();    // O(1)
deque.get(5);          // O(n)，从头遍历到第 5 个

3.5 什么时候真的该用 LinkedList

几乎没有。LinkedList 的 O(1) 头部操作优势，ArrayDeque 也能做到（且更快，因为缓存局部性好）。

// 需要双端队列：用 ArrayDeque，不用 LinkedList
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("a");   // O(1)，摊还
deque.addLast("b");    // O(1)，摊还
deque.removeFirst();   // O(1)，摊还

LinkedList 唯一的优势：在已知节点引用的情况下，O(1) 删除（不需要查找）。但 Java 的 LinkedList 没有暴露节点引用，所以这个优势在 Java 里用不上。

结论：Java 里几乎所有场景都用 ArrayList 或 ArrayDeque，LinkedList 基本可以忘掉。

---

4. 哈希表：用空间换 O(1) 查找 🗂️

4.1 核心思想

哈希表的目标：O(1) 时间内找到任意 key 对应的 value。

实现思路：

1. 准备一个数组（桶数组，bucket array）
2. 对 key 做哈希运算，得到一个整数（哈希值）
3. 用哈希值对数组长度取模，得到下标
4. 把 value 存到该下标的位置

查找时：
  对 key 做同样的哈希运算 → 得到下标 → 直接读取
  整个过程：O(1)（哈希计算 + 数组访问）

key="zhang" → hash("zhang") = 12345 → 12345 % 16 = 9 → 存到 bucket[9]
key="li"    → hash("li")    = 67890 → 67890 % 16 = 2 → 存到 bucket[2]

查找 "zhang"：hash("zhang") % 16 = 9 → 直接读 bucket[9]

4.2 哈希函数

好的哈希函数要满足：

• 均匀分布：不同 key 尽量映射到不同下标，减少冲突
• 计算快：O(1) 时间
• 确定性：同一个 key 每次哈希值相同

Java 的 hashCode()：

// String 的 hashCode（Java 实现）
// s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
"hello".hashCode()  // 99162322

// Integer 的 hashCode 就是值本身
Integer.valueOf(42).hashCode()  // 42

// 自定义类必须重写 hashCode
public class User {
    private Long id;
    private String username;

    @Override
    public int hashCode() {
        return Objects.hash(id, username);  // 推荐用 Objects.hash
    }
}

HashMap 对 hashCode 的二次处理（Java 8）：

// HashMap 内部会对 hashCode 做扰动，让高位也参与运算
// 减少低位相同时的冲突
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

4.3 哈希冲突

不同的 key 可能映射到同一个下标——这叫哈希冲突（Hash Collision）。

解决方案 1：链地址法（Chaining）——Java HashMap 使用

bucket[2] → [("li", 25)] → [("wang", 30)] → null

每个桶存一个链表，冲突的元素都挂在同一个桶的链表上。

解决方案 2：开放寻址法（Open Addressing）

冲突时，找下一个空桶（线性探测、二次探测等）。ThreadLocal 的 ThreadLocalMap 使用这种方式。

冲突对性能的影响：

理想情况（无冲突）：每个桶最多 1 个元素 → O(1) 查找
最坏情况（全冲突）：所有元素在同一个桶的链表 → O(n) 查找
平均情况（均匀分布）：每个桶约 n/capacity 个元素 → O(1) 查找

4.4 负载因子与扩容

负载因子（Load Factor） = 元素数量 / 桶数量

负载因子越高，冲突越多，查找越慢；负载因子越低，内存浪费越多。

Java HashMap 的默认值：

// 默认初始容量 16，默认负载因子 0.75
Map<String, Integer> map = new HashMap<>();

// 当 size > capacity × loadFactor 时触发扩容
// 16 × 0.75 = 12，即元素超过 12 个时扩容
// 扩容：容量翻倍（16 → 32），重新哈希所有元素（rehash）

扩容的代价：O(n)，需要重新计算所有元素的桶位置。和 ArrayList 扩容类似，摊还后每次 put 仍是 O(1)。

指定初始容量避免扩容：

// 如果知道要放 100 个元素
// 需要容量 = 100 / 0.75 ≈ 134，取 2 的幂次方 = 256
Map<String, User> map = new HashMap<>(256);

// 或者直接用 Maps.newHashMapWithExpectedSize（Guava）
Map<String, User> map = Maps.newHashMapWithExpectedSize(100);

4.5 Java 8 的链表转红黑树优化

Java 8 之前，HashMap 的桶里只有链表。极端情况下（大量哈希冲突），链表很长，查找退化到 O(n)。

Java 8 引入了优化：当同一个桶的链表长度超过 8，且总容量 ≥ 64 时，链表转为红黑树：

链表（长度 ≤ 8）：O(n) 查找
红黑树（长度 > 8）：O(log n) 查找

当红黑树节点数 ≤ 6 时，退化回链表

为什么是 8：泊松分布计算，在负载因子 0.75 时，一个桶里有 8 个元素的概率约为 0.00000006，极小。正常情况下不会触发树化，树化是极端情况的兜底。

Java 8 HashMap 的桶结构：
  正常：数组 + 链表
  极端：数组 + 红黑树（链表过长时）

---

5. HashMap.put() 完整流程 🔄

把前面的知识串起来，走一遍 put(key, value) 的完整路径：

put("zhang", user)
    │
    ▼
① 计算 hash：hash = key.hashCode() ^ (hashCode >>> 16)
    │
    ▼
② 计算桶下标：index = hash & (capacity - 1)
   （等价于 hash % capacity，但位运算更快；capacity 必须是 2 的幂次方）
    │
    ▼
③ 桶是否为空？
    ├─ 是 → 直接创建节点放入，结束
    └─ 否 ↓
    ▼
④ 桶里第一个节点的 key 是否相等？
   （先比 hash，再用 == 或 equals 比 key）
    ├─ 是 → 更新 value，结束
    └─ 否 ↓
    ▼
⑤ 桶里是链表还是红黑树？
    ├─ 红黑树 → 按红黑树方式插入/更新
    └─ 链表 → 遍历链表
              ├─ 找到相同 key → 更新 value，结束
              └─ 没找到 → 追加到链表末尾
                          链表长度 ≥ 8 且 capacity ≥ 64？
                          ├─ 是 → 链表转红黑树
                          └─ 否 → 保持链表
    ▼
⑥ size++，是否超过阈值（capacity × loadFactor）？
    ├─ 是 → 扩容（capacity × 2，rehash 所有元素）
    └─ 否 → 结束

代码对照（简化版，理解流程用）：

// 步骤 ② 的位运算技巧
// capacity 是 2 的幂次方（如 16 = 0b10000）
// capacity - 1 = 0b01111（低位全 1）
// hash & (capacity - 1) 等价于 hash % capacity，但快得多
int index = hash & (capacity - 1);

// 步骤 ④ 的 key 比较
// 先比 hash（整数比较，快），再比 equals（可能慢）
// 两者都相等才认为是同一个 key
if (p.hash == hash && (p.key == key || (key != null && key.equals(p.key))))

为什么 capacity 必须是 2 的幂次方：让 hash & (capacity - 1) 等价于取模，且分布均匀。如果 capacity 不是 2 的幂次方，这个位运算就不等价于取模了。

---

6. equals 和 hashCode 契约：必须同时重写 ⚖️

6.1 契约规则

Java 规范要求：

1. equals 相等 → hashCode 必须相等
2. hashCode 相等 → equals 不一定相等（哈希冲突是允许的）
3. equals 不等 → hashCode 最好不等（减少冲突，提升性能）

违反契约的后果：

// ❌ 只重写 equals，不重写 hashCode
public class User {
    private Long id;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        return Objects.equals(id, ((User) o).id);
    }
    // 没有重写 hashCode！
}

User u1 = new User(1L);
User u2 = new User(1L);

System.out.println(u1.equals(u2));  // true（equals 相等）
System.out.println(u1.hashCode() == u2.hashCode());  // false！（用的 Object.hashCode，基于内存地址）

Set<User> set = new HashSet<>();
set.add(u1);
set.contains(u2);  // false！明明 equals 相等，却找不到
// 原因：u2.hashCode() 不同 → 找到不同的桶 → 桶里没有 u2 → 返回 false

6.2 正确的重写方式

public class User {
    private Long id;
    private String username;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User other)) return false;
        return Objects.equals(id, other.id)
            && Objects.equals(username, other.username);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, username);  // 和 equals 用同样的字段
    }
}

用 record 自动获得正确实现（Java 16+）：

// record 自动生成 equals 和 hashCode，基于所有字段
public record UserId(Long id, String username) {}

UserId u1 = new UserId(1L, "zhang");
UserId u2 = new UserId(1L, "zhang");
u1.equals(u2);  // true
u1.hashCode() == u2.hashCode();  // true

6.3 hashCode 的设计原则

// 好的 hashCode：
// 1. 用 equals 里用到的所有字段
// 2. 用 Objects.hash() 或 31 倍数法
// 3. 不要用可变字段（对象放入 HashMap 后改了字段，hashCode 变了，找不到了）

// ❌ 用可变字段做 hashCode
public class Order {
    private Long id;
    private String status;  // 可变！

    @Override
    public int hashCode() {
        return Objects.hash(id, status);  // status 变了，hashCode 变了
    }
}

Order order = new Order(1L, "CREATED");
Map<Order, String> map = new HashMap<>();
map.put(order, "value");

order.setStatus("PAID");  // 修改了 status
map.get(order);  // null！hashCode 变了，找不到了

// ✅ 只用不可变字段（通常是 id）
@Override
public int hashCode() {
    return Objects.hash(id);  // id 不会变
}

6.4 null key 的处理

HashMap 允许 null key（存在 bucket[0]），HashSet 允许 null 元素：

Map<String, Integer> map = new HashMap<>();
map.put(null, 100);  // 合法，存在 bucket[0]
map.get(null);       // 100

// TreeMap 不允许 null key（需要比较大小，null 无法比较）
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put(null, 100);  // NullPointerException

---

7. 线程安全的集合：从 Hashtable 到 ConcurrentHashMap 🔐

7.1 HashMap 不是线程安全的

// ❌ 多线程并发 put，可能导致：
// - 数据丢失（两个线程同时写同一个桶）
// - 死循环（Java 7 的扩容 bug，Java 8 已修复但仍不安全）
// - 数据不一致
Map<String, Integer> map = new HashMap<>();
// 多线程并发操作 → 未定义行为

7.2 Hashtable：全方法加锁，性能差

// Hashtable 的每个方法都加了 synchronized
public synchronized V put(K key, V value) { ... }
public synchronized V get(Object key) { ... }

问题：整个 Hashtable 只有一把锁，所有线程串行执行，并发性能极差。现代代码不应该使用 Hashtable。

7.3 Collections.synchronizedMap：包装器，同样粗粒度

Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
// 底层也是对整个 map 加锁，和 Hashtable 一样粗粒度
// 遍历时还需要手动加锁：
synchronized (syncMap) {
    for (Map.Entry<String, Integer> entry : syncMap.entrySet()) { ... }
}

7.4 ConcurrentHashMap：分段锁 → CAS + synchronized

Java 7：分段锁（Segment）

把 HashMap 分成 16 个 Segment，每个 Segment 有自己的锁。不同 Segment 的操作可以并发，同一 Segment 内串行。并发度 = Segment 数量（默认 16）。

Java 8：CAS + synchronized（更细粒度）

put 操作：
  桶为空 → CAS 直接写入（无锁）
  桶不为空 → synchronized 锁住桶的头节点（只锁一个桶）

get 操作：
  完全无锁（volatile 保证可见性）

并发度：Java 8 的 ConcurrentHashMap 理论上可以有 capacity 个线程同时写（每个线程写不同的桶），远高于 Java 7 的 16。

// 线程安全的 Map，高并发场景使用
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// 原子操作（避免先 get 再 put 的竞态条件）
map.putIfAbsent("key", 1);
map.computeIfAbsent("key", k -> expensiveCompute(k));
map.merge("key", 1, Integer::sum);  // 原子地累加

// ❌ 这样写不是原子的，有竞态条件
if (!map.containsKey("key")) {
    map.put("key", compute());  // 两步操作，中间可能被其他线程插入
}
// ✅ 用 computeIfAbsent
map.computeIfAbsent("key", k -> compute());

7.5 线程安全集合速查

集合	线程安全	推荐场景
HashMap	❌	单线程或局部变量
Hashtable	✅（粗粒度）	不推荐，历史遗留
Collections.synchronizedMap	✅（粗粒度）	简单场景，不推荐
ConcurrentHashMap	✅（细粒度）	多线程共享 Map
ArrayList	❌	单线程或局部变量
Vector	✅（粗粒度）	不推荐，历史遗留
Collections.synchronizedList	✅（粗粒度）	简单场景
CopyOnWriteArrayList	✅（写时复制）	读多写少（如配置列表）
ConcurrentLinkedQueue	✅（无锁）	高并发队列
LinkedBlockingQueue	✅（锁）	生产者-消费者

CopyOnWriteArrayList 的原理：每次写操作（add/remove）都复制整个数组，写完后替换引用。读操作完全无锁。适合读多写少的场景（如缓存的配置列表），不适合频繁写入。

---

8. 集合选型决策树 🌳

8.1 选 List

需要有序、可重复的集合？
    │
    ▼
需要频繁按下标随机访问？
    ├─ 是 → ArrayList（O(1) 随机访问）
    └─ 否 → 需要频繁在头部插入/删除？
                ├─ 是 → ArrayDeque（比 LinkedList 快）
                └─ 否 → ArrayList（默认选择）

多线程共享？
    ├─ 读多写少 → CopyOnWriteArrayList
    └─ 读写均衡 → Collections.synchronizedList 或换设计

8.2 选 Map

需要 key-value 映射？
    │
    ▼
需要按 key 排序？
    ├─ 是 → TreeMap（O(log n)，红黑树）
    └─ 否 → 需要保持插入顺序？
                ├─ 是 → LinkedHashMap（O(1)，有序）
                └─ 否 → HashMap（O(1)，最快）

多线程共享？
    └─ 是 → ConcurrentHashMap

8.3 选 Set

需要去重集合？
    │
    ▼
需要按元素排序？
    ├─ 是 → TreeSet（O(log n)）
    └─ 否 → 需要保持插入顺序？
                ├─ 是 → LinkedHashSet（O(1)）
                └─ 否 → HashSet（O(1)，最快）

8.4 选队列/栈

需要队列（FIFO）或栈（LIFO）？
    │
    ▼
需要优先级排序？
    ├─ 是 → PriorityQueue（O(log n) 插入/删除）
    └─ 否 → ArrayDeque（O(1) 摊还，双端）

多线程生产者-消费者？
    ├─ 有界 → ArrayBlockingQueue
    └─ 无界 → LinkedBlockingQueue 或 ConcurrentLinkedQueue

8.5 一张表总结

需求	推荐集合	不推荐
有序列表，随机访问	ArrayList	LinkedList
栈或双端队列	ArrayDeque	Stack、LinkedList
key-value，快速查找	HashMap	Hashtable
key-value，按 key 排序	TreeMap	—
key-value，保持插入顺序	LinkedHashMap	—
去重，快速判断存在	HashSet	—
去重，有序	TreeSet	—
优先级队列	PriorityQueue	—
多线程 Map	ConcurrentHashMap	Hashtable、synchronizedMap
多线程读多写少 List	CopyOnWriteArrayList	Vector
多线程队列	LinkedBlockingQueue	—

---

9. 常见面试题背后的工程意义 💡

面试题不是为了考你背没背，而是考你理不理解原理。这里把几道高频题和工程意义对应起来：

9.1 「HashMap 为什么线程不安全？」

工程意义：理解这个，才知道什么时候必须用 ConcurrentHashMap，什么时候 HashMap 就够了（局部变量、单线程）。

答案要点：多线程并发 put 时，可能同时操作同一个桶，导致数据丢失或链表结构破坏。Java 8 修复了 Java 7 的死循环 bug，但仍然不是线程安全的。

9.2 「HashMap 的初始容量为什么是 16？为什么是 2 的幂次方？」

工程意义：理解这个，才知道为什么要指定初始容量，以及指定多少合适。

答案要点：2 的幂次方让 hash & (capacity - 1) 等价于取模，且分布均匀。16 是经验值，不大不小。如果知道元素数量，应该指定 expectedSize / 0.75 向上取 2 的幂次方。

9.3 「HashMap 和 HashSet 的关系？」

工程意义：理解底层共享，避免重复学习。

答案要点：HashSet 底层就是 HashMap，key 是元素，value 是一个固定的 PRESENT 对象。add(e) 就是 map.put(e, PRESENT)，contains(e) 就是 map.containsKey(e)。

9.4 「为什么重写 equals 必须重写 hashCode？」

工程意义：这是实际 bug 的来源，不是纯理论。

答案要点：HashMap/HashSet 先用 hashCode 定位桶，再用 equals 比较 key。如果两个「相等」的对象 hashCode 不同，会落在不同的桶，HashMap 就找不到了。

9.5 「ConcurrentHashMap 的 size() 是精确的吗？」

工程意义：在并发场景下，size() 可能不精确，不要依赖它做业务判断。

答案要点：Java 8 的 ConcurrentHashMap.size() 返回的是一个估算值（通过 baseCount + counterCells 累加），在高并发下可能不精确。如果需要精确计数，用 LongAdder 或 AtomicLong 单独维护。

9.6 「ArrayList 和数组的区别？」

工程意义：知道什么时候用原生数组（性能敏感、基本类型），什么时候用 ArrayList（需要动态大小、泛型）。

答案要点：ArrayList 底层是 Object[]，支持动态扩容和泛型，但有装箱开销（基本类型）。原生数组固定大小，基本类型无装箱，性能更好，但不灵活。

---

10. 综合示例：一个用户权限缓存的集合选型 💻

场景：Spring Boot 应用需要一个「用户权限缓存」，满足：

1. 按用户 ID 快速查找权限列表
2. 判断某个权限是否存在（高频操作）
3. 多线程并发读（接口处理线程），偶尔写（权限变更时刷新）
4. 需要知道缓存里有多少用户

10.1 选型分析

需求 1：按 userId 查找 → Map（O(1) 查找）
需求 2：判断权限存在 → 权限列表用 Set（O(1) contains）而不是 List（O(n)）
需求 3：多线程读多写少 → ConcurrentHashMap（读无锁，写细粒度锁）
需求 4：size() 不精确 → 单独维护计数器

10.2 实现

@Component
public class PermissionCache {

    // ConcurrentHashMap：线程安全，读无锁
    // value 用 Set：O(1) 判断权限存在
    private final ConcurrentHashMap<Long, Set<String>> cache = new ConcurrentHashMap<>();

    // 精确计数（ConcurrentHashMap.size() 不精确）
    private final LongAdder userCount = new LongAdder();

    /**
     * 加载用户权限（写操作，偶尔触发）
     */
    public void load(Long userId, Collection<String> permissions) {
        // 用不可变 Set，防止外部修改
        Set<String> permSet = Set.copyOf(permissions);  // Java 10+，不可变

        Set<String> old = cache.put(userId, permSet);
        if (old == null) {
            userCount.increment();  // 新用户，计数 +1
        }
    }

    /**
     * 判断用户是否有某个权限（高频读操作）
     */
    public boolean hasPermission(Long userId, String permission) {
        Set<String> perms = cache.get(userId);  // O(1)，无锁
        return perms != null && perms.contains(permission);  // O(1)
    }

    /**
     * 获取用户所有权限
     */
    public Set<String> getPermissions(Long userId) {
        return cache.getOrDefault(userId, Set.of());
    }

    /**
     * 移除用户权限（权限变更时）
     */
    public void evict(Long userId) {
        if (cache.remove(userId) != null) {
            userCount.decrement();
        }
    }

    /**
     * 缓存用户数（精确）
     */
    public long cachedUserCount() {
        return userCount.sum();
    }

    /**
     * 批量加载（启动时或全量刷新）
     */
    public void loadAll(Map<Long, List<String>> userPermissions) {
        // 先构建新 Map，再原子替换（避免中间状态）
        userPermissions.forEach((userId, perms) -> load(userId, perms));
    }
}

10.3 使用

@Service
public class OrderService {

    private final PermissionCache permissionCache;

    public void createOrder(Long userId, CreateOrderRequest req) {
        // O(1) 权限检查
        if (!permissionCache.hasPermission(userId, "ORDER_CREATE")) {
            throw new BusinessException(403, "FORBIDDEN", "无权创建订单");
        }
        // ... 业务逻辑
    }
}

选型总结：

需求	选型	原因
userId → 权限集合	ConcurrentHashMap	线程安全，O(1) 查找
权限集合	Set.copyOf()	O(1) contains，不可变防并发修改
精确计数	LongAdder	比 AtomicLong 在高并发下更快
批量加载	forEach + put	ConcurrentHashMap 的 putAll 不是原子的

---

11. 内存占用对比：选型时别忽略空间 💾

不同集合的内存开销差异很大，大数据量时需要考虑：

集合	每个元素的额外开销	说明
int[]	0	纯数据，无对象头
ArrayList<Integer>	~20 字节	Integer 对象头(16) + 引用(8) - 值(4)
LinkedList<Integer>	~48 字节	Node 对象头(16) + prev(8) + next(8) + item 引用(8) + Integer(16)
HashMap<K,V>	~48 字节/条目	Entry 对象头(16) + hash(4) + key 引用(8) + value 引用(8) + next 引用(8) + 对齐
HashSet<E>	~48 字节/元素	底层 HashMap，同上

实际影响：

100 万个 int 值：
  int[]：4 MB
  ArrayList<Integer>：~24 MB（6 倍）
  LinkedList<Integer>：~52 MB（13 倍）

业务场景：处理大量数值数据（如统计、计算）时，考虑用原生数组或 IntStream，而不是 List<Integer>。

---

小结 💡

• 数组：连续内存，O(1) 随机访问，O(n) 中间插入。ArrayList 是动态数组，扩容策略是 × 1.5，摊还 O(1) 追加。已知大小时指定初始容量避免扩容。
• 链表：节点分散在内存各处，O(1) 头尾操作，O(n) 随机访问。缓存局部性差，遍历比数组慢 3～10 倍。Java 里几乎不用 LinkedList，用 ArrayDeque 代替。
• 哈希表：哈希函数 + 桶数组，O(1) 平均查找。冲突用链地址法解决，Java 8 链表超过 8 个节点转红黑树。负载因子 0.75，超过阈值扩容（容量翻倍，rehash）。
• equals/hashCode 契约：必须同时重写，用相同的字段。违反契约会导致 HashMap/HashSet 找不到元素。不要用可变字段做 hashCode。
• ConcurrentHashMap：Java 8 用 CAS + synchronized（桶级别锁），读无锁，并发度远高于 Hashtable。size() 不精确，需要精确计数用 LongAdder。
• 选型原则：默认 ArrayList + HashMap + HashSet；需要排序用 TreeMap/TreeSet；需要顺序用 LinkedHashMap；需要线程安全用 ConcurrentHashMap/CopyOnWriteArrayList；需要队列用 ArrayDeque/PriorityQueue。

下一篇（011）预告 🌲：树与排序——二叉搜索树、红黑树、B+ 树（数据库索引的底层）、堆排序与 TopK，以及业务里哪些地方真的会碰到树结构。