Java 集合学习 02：HashMap、红黑树与并发容器

哈希表最有价值的地方不是“查找很快”，而是把大量键稳定地分散到可管理的桶里。HashMap 的实现细节之所以值得理解，是因为它把几个工程取舍放在了一起：内存利用率、冲突分布和扩容成本。

HashMap 的容量为什么是 2 的幂

HashMap 使用 (n - 1) & hash 计算桶位置。容量为 2 的幂时，这个掩码运算可以等价地取代取模，并且让 hash 的低位参与得更直接。扩容到两倍后，旧桶中的元素不需要重新完整计算位置：要么留在原索引，要么移动到 原索引 + oldCap。

这套设计依赖一个前提：键的 hashCode() 和 equals() 契约必须一致。把可变字段放进 key、或只重写其中一个方法，都会让“找得快”的承诺失效。

HashMap 的链表为什么要树化

JDK 8 中，桶链表足够长且表容量足够大时，桶可能树化为红黑树；删除后又可能退回链表。这里的阈值是为极端碰撞准备的保护机制，不是普通业务需要主动追求的优化。

更常见的动作反而是：预估容量、避免低质量 hash、不要把同一张 HashMap 交给多个写线程。树化解决的是单桶退化，并不把非线程安全集合变成并发容器。

ConcurrentHashMap 在 JDK 8 中如何保证并发安全

JDK 8 的 ConcurrentHashMap 不再采用 JDK 7 的 Segment 结构，而是结合 CAS、桶级同步和协作式扩容。空桶写入可以先尝试 CAS；发生冲突时，只锁住相关桶的头节点，而不是锁整张表。

扩容同样不是单线程搬家。参与线程领取不同区间迁移；已迁移桶会被放置一个 ForwardingNode，后续操作据此转向新表。迁移链表时按 hash & oldCap 拆为两段并保持顺序，避免旧实现中头插迁移带来的并发链表成环风险。

ConcurrentHashMap 的复合操作为什么仍然要注意原子性

ConcurrentHashMap 解决的是容器内部并发访问，不等于一段复合业务逻辑天然原子：

// 仍可能出现“读到旧值后再写回”的竞争
if (!map.containsKey(key)) {
  map.put(key, value);
}

// 把判断与更新收敛到容器提供的原子操作
map.putIfAbsent(key, value);

容器选择只是第一层。第二层是把读—改—写的业务不变量收敛为原子 API，或明确交给锁、事务和消息顺序来维护。

HashMap 和 Hashtable 的区别

Hashtable 通过对方法整体加锁提供早期的线程安全语义，代价是竞争粒度粗，也不接受 null 键和值。新代码通常不应因为“它线程安全”就使用它：并发 map 的常见选择是 ConcurrentHashMap，而排序需求则应该交给 TreeMap 或在读取后排序。

TreeMap 的价值不是比 HashMap 更“稳定”，而是它可以按比较器定义 key 的顺序，并支持范围视图。若业务只需要最终展示排序，先用哈希表聚合、最后再排序，往往比让每一次写入都维护树结构更划算。

红黑树是什么，为什么 HashMap 不使用 AVL 树

红黑树并不追求绝对平衡，而是在查询、插入和删除之间给出稳定的 O(log n) 上界。它比 AVL 树少一些旋转约束，因此更适合频繁更新的场景。HashMap 桶树化正是用这种折中防御极端 hash 碰撞；实际业务更该关注 key 的散列质量与容量预估。

使用 HashMap 时要检查什么

key 是否不可变，equals 与 hashCode 是否一起实现；
是否能预估数量并设置初始容量，降低扩容复制；
是否真的要求排序或插入顺序，而非偶然依赖遍历结果；
并发写入时，复合操作是否已经收敛到原子方法；
扩容、缓存淘汰和异常重试是否会把同一个 key 重复计算。

这张清单比记住某个阈值更耐用。集合在大部分时候不是性能瓶颈，但当它成为共享状态的入口时，边界必须被写清楚。

HashMap 的 put 过程

一次 put 并不是“算出 hash 后塞进数组”这么简单。实现首先会处理表是否初始化、将原始 hash 的高低位混合、用容量掩码定位桶；若桶为空则直接放入，若首节点 hash 与 key 相等则替换 value，否则沿链表或树节点继续比较。插入后还要维护 size，并在超过阈值时触发扩容。

哈希扰动的目标是让高位信息也参与桶定位。因为容量是 2 的幂，索引主要使用 hash 的低位；如果只拿原始低位，某些类型糟糕的 hashCode 会让碰撞集中。扰动不能修复违反契约的 key，却能降低正常 key 因位分布不均造成的风险。

默认负载因子常被记作 0.75。它不是神奇常数，而是查找冲突与空间利用率之间的折中。负载越高，内存越省但桶更容易变长；负载越低，碰撞少但更多槽位空置。需要装载大量数据时，正确做法是根据预计元素数和负载因子估算初始容量，并让容量归到 2 的幂，而不是事后频繁触发 resize。

HashMap 的树化、退化和扩容阈值

JDK 8 的桶在满足长度与表容量条件后可以树化。这里有三个必须一起理解的点：链表长度很长只是条件之一；表容量过小时，优先扩容而不是立即树化；树节点减少到较低阈值后可以退回链表。树化与退化之间留出间隔，是为了避免元素数量在边界附近反复增删时来回转换。

红黑树通过颜色约束把高度控制在对数级别。它不像 AVL 那样追求严格平衡，因此插入、删除时旋转的代价更温和。对 HashMap 而言，树化是一道针对极端碰撞的防线，不是常态性能路径。绝大多数性能问题仍应从不合理的 key、没有预分配容量或错误的并发访问开始查。

Hashtable 和 ConcurrentHashMap 如何选择

Hashtable 的公开方法带有同步控制，因此历史上被视为线程安全容器；它不允许 null key 和 null value，默认容量与扩容策略也不同。HashMap 允许一个 null key 和多个 null value，但不保证并发写安全。

今天遇到共享 map 时，不应该在二者之间做二选一。真正的问题是：读写是否并发？是否需要复合操作原子化？是否需要排序？普通并发键值访问选 ConcurrentHashMap；按 key 排序与范围查询选 ConcurrentSkipListMap 或在单线程语义下使用 TreeMap；需要整个操作序列隔离时，再考虑外层锁或更高层事务。

HashMap 和 TreeMap 的区别

TreeMap 基于红黑树，按 key 的自然顺序或比较器维持顺序。它的强项是 subMap、headMap、tailMap 等范围视图，而不是替代所有 HashMap。若只需要在响应返回前排序一次，常见做法是哈希聚合后再排序；若每次更新都需要立即按范围查询，维护树结构才有意义。

比较器要满足稳定且可传递的排序关系。尤其要注意：compare(a, b) == 0 会让 TreeMap 把 key 视作同一位置，即便 equals 返回 false。日期、金额或自定义 ID 的排序规则若只比较部分字段，可能无意中覆盖数据。

ConcurrentHashMap 在 JDK 7 和 JDK 8 中的区别

JDK 7 的 ConcurrentHashMap 使用 Segment 分段，每段近似独立哈希表并有自己的锁。分段降低了整表锁竞争，但并发粒度固定，结构与扩容也相对复杂。

JDK 8 重写了这套结构：底层同样由数组、链表和树节点组成，但空桶优先用 CAS 放入，发生冲突时只在相关桶上同步；扩容由多个线程协作完成。迁移线程会按区间领取任务，桶迁移完成后放入 ForwardingNode，让随后到来的操作知道应该转向新表。

对于链表桶，元素会按 hash 的一个高位拆为低位与高位两条链，分别留在原位置与 原位置 + oldCap，并保持原有相对顺序。这个细节使扩容不必重新计算完整索引，也避免了并发迁移里因改变链接顺序带来的危险。

ConcurrentHashMap 的 computeIfAbsent 有什么边界

ConcurrentHashMap 能保证容器单次操作的并发安全，却不能自动把多行代码变成事务。下面两段代码的差别来自原子边界，而不是 map 的类型：

// 非原子：两个线程都可能先看到 key 不存在
if (!cache.containsKey(key)) {
  cache.put(key, load(key));
}

// 将“缺失时计算”交给容器；计算函数仍应避免副作用
cache.computeIfAbsent(key, this::load);

当业务涉及库存扣减、状态流转、跨服务幂等或消息顺序时，map 只能保存状态，不能取代锁、数据库条件更新、版本号或消息协议。理解到这一层，才能避免“已经换成 ConcurrentHashMap，为什么还是重复执行”的困惑。