Java · 集合框架选型与 HashMap 底层

💡 一句话理解

集合选型的本质是"数据布局决定复杂度": ArrayList 是数组, 随机访问 O(1) 但中间插删要整体搬家; HashMap 是"数组 + 链表 + 红黑树"的三层结构 — hash 位运算定位桶 O(1), 冲突了沿链表逐个 equals, 链太长树化封底到 O(log n)。看懂"桶下标 = 扰动后的 hash 与上 (n-1)"这一行, 容量为什么必须是 2 的幂、扰动函数为什么存在、resize 为什么按高位拆两条链, 全部连成一条线。

并发维度上答案只有一个: 任何会被多个线程写的集合, 都必须换成并发容器。HashMap 并发写的结局是 JDK 7 的链表成环死循环或 JDK 8 的无声丢数据; synchronizedMap 是一把全表锁形同虚设; ConcurrentHashMap 用"CAS 插空桶 + synchronized 锁桶首节点"把锁粒度压到单个桶。选型时先问访问模式 (读多写少? 要有序? 键是枚举?), 再问并发度, 答案基本就出来了。

🧠 必知必会 必考 & 必会

ArrayList 扩容

add 时若满: 新容量 = 旧容量 + (旧容量 >> 1) 即 1.5 倍, Arrays.copyOf 整体搬迁; 默认容量 10 是懒分配 (首次 add 才建数组); 均摊后 add 仍是 O(1)。

ArrayList<Integer> a = new ArrayList<>();   // 懒分配: 首 add 才建 10 长数组
for (int i = 1; i <= 11; i++) a.add(i); // 第 11 次 add 触发扩容
// 关键: 10 → 10 + (10 >> 1) = 15 → 22 → 33, 均摊后 add 仍 O(1)

LinkedList 真实定位

双向链表: 头尾插删 O(1), 但"按下标插入"要先走 O(n) 定位; 理论 O(1) 插入被遍历成本吃掉。真实用途是当 Deque (队列/栈), 列表场景几乎全被 ArrayList + ArrayDeque 替代。

Deque<Integer> dq = new LinkedList<>(); // 真实定位: 当 Deque 用
dq.offerFirst(1); dq.offerLast(2);    // 头尾插删 O(1) → [1, 2]
dq.pollFirst();                          // → 1 出队, 剩 [2]
// 关键: get(i) 要从头部逐节点走 O(n), 按下标访问别用它

hash 扰动函数

(h = key.hashCode()) ^ (h >>> 16): 高 16 位异或进低 16 位。桶下标只取低 log2(n) 位, 小表时不扰动会让高位信息全部丢失, 冲突暴增。

static int hash(Object key) {
    int h;
    return (h = key.hashCode()) ^ (h >>> 16); // 关键: 高 16 位混进低 16 位
}
// n=16 时下标只取低 4 位, 不扰动 → 高位信息全丢, 冲突暴增

容量 2 的幂

hash & (n-1) 等价 hash % n 但免除法; n-1 二进制全 1 才能均匀取到每个桶。传 10 会被 tableSizeFor 规整到 16, 默认 16, 上限 2^30。

int hash = 0x25, n = 16;        // n 必须是 2 的幂
int idx = hash & (n - 1);       // → 5, 等价 hash % n 但免除了除法
// 关键: n-1 = 0b1111 全 1 → 均匀盖住每个桶; 传 10 会规整到 16

树化 8/64 退化 6

链长 ≥ 8 且 table ≥ 64 才 treeify, 容量不足优先扩容 (冲突多半是容量问题); 删除到 ≤ 6 退化回链表, 6 = 8 - 2 防止阈值附近反复横跳。理想 hash 下链到 8 的概率约千万分之六 — 树化是兜底不是常态。

// putVal 源码: 同一桶链长到 8 才尝试树化
if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, h);
// treeifyBin 先查容量: n < 64 → 只扩容不树化 (冲突多半是表太小)
// 关键: 删到 ≤ 6 退化回链表, 6 = 8 - 2 防阈值附近反复横跳

负载因子与 resize

0.75 是空间利用率与冲突率的折中; 超过阈值容量翻倍, 单次 O(n) 均摊 O(1); JDK 8 拆高低两条链, 不重算 hash, 只看新增那一个 bit。

Map<String, Integer> m = new HashMap<>(4); // 阈值 = 4 × 0.75 = 3
m.put("a", 1); m.put("b", 2); m.put("c", 3); m.put("d", 4);
// 第 4 次 put: ++size(4) > 3 → resize 到 8, 单次 O(n) 均摊 O(1)
// 关键: 拆链只看 (hash & oldCap)==0 ? 原桶 : idx+oldCap, 不重算 hash

equals/hashCode 契约

equals 相等 → hashCode 必须相等 (反向不要求); 违反 → "存得进取不出"。hashCode 相同只是同桶候选, 再用 equals 精筛。重写其中一个必须重写另一个。

// Bad 类只重写了 equals: 两个 new Bad("A") 是 equals 相等的
map.put(new Bad("A"), 1);
map.get(new Bad("A"));  // → null: hashCode 不同落进不同桶
// 关键: equals 涉及的字段必须全部进 hashCode (Objects.hash(...))

fail-fast

迭代器创建时记下 modCount, next() 每次校验, 不一致抛 ConcurrentModificationException; 目的是尽快暴露 bug 而非保证安全, 单线程删错照样中招。

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : list)
    if (x == 2) list.remove(Integer.valueOf(2)); // → CME
// 关键: next() 校验 modCount, 单线程删错照样中招

fail-safe 与弱一致

CopyOnWriteArrayList 迭代的是写入瞬间的不可变快照; ConcurrentHashMap 迭代器弱一致 — 不抛 CME 但可能看不到迭代期间的修改, 语义要自己兜。

List<Integer> cow = new CopyOnWriteArrayList<>(List.of(1, 2));
for (Integer x : cow) cow.add(3); // 不抛 CME, 迭代仍是 [1, 2] 快照
// 关键: CHM 迭代器同理弱一致 — 不抛 CME 但可能漏看迭代中的修改

CHM 的 JDK 8 实现

空桶 CAS 无锁插入; 有节点 synchronized 锁首节点 (粒度=单桶); size 用 baseCount + CounterCell 分段累加 (LongAdder 思路); 扩容时多线程还能协助搬桶; key/value 均禁 null。

ConcurrentHashMap<String, Integer> m = new ConcurrentHashMap<>();
m.put("k", null); // → NullPointerException: key/value 均禁 null
// 关键: 空桶 CAS 无锁插入; 有节点 synchronized 锁首节点 (粒度=单桶)
// size = baseCount + CounterCell[] 分段累加 (LongAdder 思路)

LinkedHashMap

在 HashMap 之上多维护一条双向链表: accessOrder=false 插入序, true 访问序; 重写 removeEldestEntry 即成 LRU。accessOrder 模式连 get 都改结构, 并发风险更大。

Map<String, Integer> m = new LinkedHashMap<>(16, 0.75f, true);
m.put("a", 1); m.put("b", 2); m.get("a"); // 访问序: get 也算访问
m.keySet();             // → [b, a]: a 被访问后移到链尾 (最新)
// 关键: accessOrder=true + 重写 removeEldestEntry 即成 LRU

TreeMap / TreeSet

红黑树按键有序: 增删查 O(log n); floorKey/ceilingKey/subMap 天然支持范围查询; key 必须 Comparable 或构造时给 Comparator。

TreeMap<Integer, String> m = new TreeMap<>();
m.put(10, "a"); m.put(20, "b"); m.put(30, "c");
m.floorKey(25);            // → 20: ≤ 25 的最大 key, O(log n)
m.subMap(10, true, 20, true); // → {10=a, 20=b} 范围视图

EnumSet / EnumMap

按 ordinal 用位向量/数组实现: 无 hash 计算、无冲突、缓存友好, 比 HashSet/HashMap 又快又省; 限定 key 是同一枚举类 — 状态机/标志位的最佳载体。

enum Perm { READ, WRITE, ADMIN }
EnumSet<Perm> rw = EnumSet.of(Perm.READ, Perm.WRITE); // 位向量
EnumMap<Perm, String> label = new EnumMap<>(Perm.class);
label.put(Perm.ADMIN, "管理员"); // 关键: 无 hash 无冲突, 数组直取

不可变集合

List.of/Map.of (JDK 9+) 真不可变且省内存, 元素禁 null; Arrays.asList 是定长视图 (可 set 不可 add); unmodifiableList 只是只读视图, 包装的原表仍可被改。

List<String> a = List.of("x", "y");
a.set(0, "z");           // → UnsupportedOperationException
List<Integer> b = Arrays.asList(1, 2);
b.set(0, 9); b.add(3);     // set → [9, 2]; add 抛异常 (定长)
// 关键: unmodifiableList 只是只读视图, 原表仍可被改

🏭 生产实战 real world

// 热点数据本地缓存: LRU 上限 1000, 防穿透/防雪崩的第一道闸
private static final int MAX = 1000;
private final Map<String, UserVO> cache =
    new LinkedHashMap<>(16, 0.75f, true) {  // true = accessOrder, LRU 语义
      @Override protected boolean removeEldestEntry(Map.Entry<String, UserVO> e) {
        return size() > MAX;             // 插入后自动淘汰"最久未访问"那条
      }
    };

public UserVO get(String uid, Function<String, UserVO> loader) {
  return cache.computeIfAbsent(uid, loader); // 单线程读; 多线程要包 synchronizedMap
}

// 写频率极低 + 读极多: COW 每次读只是拿引用, 无锁无快照拷贝
private final List<Pattern> whitelist = new CopyOnWriteArrayList<>();

public boolean allowed(String url) {
  for (Pattern p : whitelist) {          // 迭代的是写入瞬间的不可变快照
    if (p.matcher(url).find()) return true;  // 迭代中刷新也不会抛 CME
  }
  return false;
}

public void refresh(List<String> patterns) {
  List<Pattern> next = patterns.stream().map(Pattern::compile).toList();
  whitelist.clear();                    // 注意: 每次写都整表复制, 表必须小 (百级以内)
  whitelist.addAll(next);
}

// 网关按 API 计数: 每 key 独立 LongAdder, 单 key 内部再 Cell 分散竞争
private final ConcurrentHashMap<String, LongAdder> counters = new ConcurrentHashMap<>();

public void record(String api) {
  counters.computeIfAbsent(api, k -> new LongAdder()).increment();
}

public long snapshot() {
  long total = 0;
  for (LongAdder v : counters.values()) total += v.sum(); // sum 弱一致, 监控足够
  return total;
}
// 压测对比: 32 线程打同一计数点, AtomicLong ~4M ops/s → LongAdder ~31M ops/s

// IP 段归属: 网段起点转 long 存 TreeMap, floorEntry 找 <= ip 的最大起点
private final TreeMap<Long, String> ranges = new TreeMap<>();

public void load(Map<Long, String> cidrs) { ranges.putAll(cidrs); }

public String locate(long ip) {
  Map.Entry<Long, String> e = ranges.floorEntry(ip);  // O(log n), 不用全表扫
  return e == null ? "unknown" : e.getValue();
}
// 版本灰度同款: floorEntry(当前版本) 命中"最近的已发布"配置, 上线即生效

// 已知总量就直接给足: 一次分配到位, 中途零拷贝
List<Order> orders = new ArrayList<>(rows.size());

// 量化 (100k 对象, JFR): 懒分配多产生 ~1.4MB 临时数组, young GC 6 次 → 0 次
// 更优是流式: 边查边写出, 根本别把全表堆在堆里
try (PreparedStatement ps = conn.prepareStatement(SQL)) {
  ResultSet rs = ps.executeQuery();
  while (rs.next()) {
    orders.add(mapRow(rs));
  }
}

// EnumMap 底层是按 ordinal 索引的数组: 无 hash 计算, 无冲突, 缓存友好
enum State { NEW, PAID, SHIPPED, DONE, CLOSED }

private final Map<State, Map<Event, State> transitions = new EnumMap<>(State.class);

private void put(State s, Event e, State next) {
  transitions.computeIfAbsent(s, k -> new EnumMap<>(Event.class)).put(e, next);
}

public State next(State cur, Event ev) {
  State s = transitions.getOrDefault(cur, Map.of()).get(ev);
  if (s == null) throw new IllegalStateTransition(cur, ev); // 非法流转直接拒绝
  return s;
}

// 用 record: equals/hashCode 按全部字段自动生成, 契约不会漏
public record TaxNo(String code, String region) {}

Set<TaxNo> seen = ConcurrentHashMap.newKeySet();
boolean first = seen.add(new TaxNo(code, region));  // false = 重复申报, 直接拒

// 手写时的底线: equals 涉及的字段必须全部进 hash
// Objects.hash(code, region) 一行生成, 别自己造魔数 hash

// 同 key 的写入在同一桶上串行化: 别的线程等结果, 不再重复打 DB
private final ConcurrentHashMap<String, Product> cache = new ConcurrentHashMap<>();

public Product get(String sku) {
  return cache.computeIfAbsent(sku, this::loadFromDb);
  // 注意: loadFromDb 里绝不能再写这个 cache — 递归 compute 会卡死/抛 ISE
  // 加载慢的 key 要过期: 换 Caffeine (expireAfterWrite + 同 key 单飞)
}

// 正确 1: removeIf, 内部用迭代器删除, 一行搞定
users.removeIf(u -> u.lastActive().isBefore(cutoff));

// 正确 2: 迭代器 remove — 每轮 next() 只能配一次 remove()
for (Iterator<User> it = users.iterator(); it.hasNext(); ) {
  if (it.next().lastActive().isBefore(cutoff)) it.remove();
}

// Map 同理: map.keySet().removeIf(k -> stale(k))

// 任何 add/put 直接 UnsupportedOperationException — 越早炸越好
private static final Set<String> BLOCKED_IPS = Set.of("10.1.3.4", "10.1.3.9");
private static final Map<Integer, String> CODES =
    Map.of(400, "BAD_REQUEST", 404, "NOT_FOUND", 500, "SERVER_ERROR");

// 超过 10 对会编译不过 → Map.ofEntries(Map.entry(k, v), ...)
// 元素禁 null; JDK 9 前用 Collections.unmodifiableMap 包一层只读视图

⚠️ 编码注意与常见坑 pitfalls

// 错: Map<String,Integer> m = new HashMap<>();  多线程并发 put
//     → JDK 7 resize 成环 get() 死循环; JDK 8 无声丢 key
// 对: Map<String,Integer> m = new ConcurrentHashMap<>();

// 错: class Point 只重写 equals → map.get(new Point(1,2)) → null
//     set.add(p1); set.add(p2); → size()==2, "相等"却重复
// 对: record Point(int x, int y) {} 或手写 Objects.hash(x, y)

// 错: map.put(user, v); user.setLevel(9); → hash 漂移, entry 永久取不出
// 对: key 用 String/Integer/record 等不可变类型;
//     状态必须变 → 先 remove 旧 key, 改完再 put 回去

// 错: for (User u : users) if (stale(u)) users.remove(u);
//     → ConcurrentModificationException, 单线程也中招
// 对: users.removeIf(u -> stale(u));  或迭代器 it.remove()

// 错: Arrays.asList("a","b").add("c"); → UnsupportedOperationException
//     Arrays.asList(new int[]{1,2}) → List<int[]>, 整个数组当一个元素
// 对: new ArrayList<>(Arrays.asList("a","b"));
//     基本类型: Arrays.stream(arr).boxed().toList()

// 错: List<Integer> v = list.subList(0, 2); list.add(9); v.get(0);
//     → ConcurrentModificationException (视图依赖原表的 modCount)
// 对: List<Integer> copy = new ArrayList<>(list.subList(0, 2));

// 错: list.remove(null) 在 ArrayList 能跑, 换 chm.put("k", v) 遇 null → NPE
//     map.get(k) == null 分不清"不存在"还是"值就是 null"
// 对: Objects.requireNonNull(v) 入集合前挡掉; 判存在用 containsKey(k)

// 错: Iterator<User> it = users.iterator(); 迭代中 users.add(x);
//     → 下一次 it.next() 照样抛 CME
// 对: 先收集 List<User> toAdd, 迭代完统一 users.addAll(toAdd)

// 错: chm.put("k", null); → NullPointerException (刻意设计)
//     否则 get 返回 null 分不清"不存在"与"值是 null"
// 对: chm.put("k", Optional.empty()); 判存在用 containsKey(k)

// 错: if (!m.containsKey(k)) m.put(k, v);
//     两步之间别人已经 put, 竞态依旧存在
// 对: m.putIfAbsent(k, v); / m.computeIfAbsent(k, key -> load(key));

// 错: LinkedList<User> l = ...; l.get(i) 从头逐节点走 O(n)
//     万级元素随机访问/排序的遍历成本先爆
// 对: 排序/随机访问换 ArrayList; 栈/队列用 ArrayDeque

// 错: 依赖 new HashSet<>(List.of("b","a")) 的迭代顺序
//     → 今天碰巧有序, 换 JDK 版本/数据分布就变
// 对: 插入序 LinkedHashSet; 排序序 TreeSet — 显式声明

// 错: new HashMap<>(1000);  1000 是 table 大小, 装到 750 就 resize
// 对: new HashMap<>(2048);  // 1000/0.75≈1334 → 规整到 2048
//     或 Guava Maps.newHashMapWithExpectedSize(1000)

// 错: 万级大表用 COW 且每秒写百次
//     → 每次写全量复制一个新数组, CPU 与 GC 起飞
// 对: COW 只用于小表+读多写极少; 写多换 CHM 聚合

// 错: new TreeMap<>().put(t1, "a"); .put(t2, "b");
//     → ClassCastException: TaxNo cannot be cast to Comparable
// 对: new TreeMap<>(Comparator.comparing(TaxNo::code));

// 错: it.next(); it.remove(); it.remove();
//     → IllegalStateException: 一次 next() 只配一次 remove()
// 对: 删完让下一轮 next() 先行; 批量删直接 removeIf

// 错: users.stream().collect(Collectors.toMap(User::id, User::name));
//     遇重复 id → IllegalStateException: Duplicate key
// 对: Collectors.toMap(User::id, User::name, (a, b) -> b);

Long a = 127L, b = 127L; a == b;  // → true (缓存池内同一对象)
Long x = 128L, y = 128L; x == y;  // → false, 缓存只到 127
// 对: x.equals(y); 或拆箱 x.longValue() == y.longValue()

// 错: for (V v : chm.values()) 期间并发 put 看不到 → 误判"丢数据"
// 对: List<V> snap = new ArrayList<>(chm.values()); 拷贝快照再处理

// 错: for (K k : map.keySet()) if (stale(k)) map.remove(k);
//     → 同样改 modCount, 抛 ConcurrentModificationException
// 对: map.keySet().removeIf(k -> stale(k));  或 entrySet().removeIf(...)