Java TreeMap 深度解析：从原理到实战

TreeMap 核心原理

TreeMap 是 Java 集合框架中基于红黑树实现的有序映射表，它通过 key 的自然排序或自定义 Comparator 维护键值对的顺序。与 HashMap 不同，TreeMap 不允许 null 键（会抛出 NullPointerException），但允许 null 值，其操作的时间复杂度为 O(log n)。

红黑树插入流程时序图

实际项目应用场景

在电商库存管理系统中，我们曾使用 TreeMap 实现商品价格区间查询功能。系统需要支持根据价格范围快速筛选商品，并按价格升序展示。采用 TreeMap<String, Product> 结构，key 设计为价格拼接唯一标识的字符串，通过自定义 Comparator 实现按价格优先排序。

当进行促销活动时，运营需要查询价格在 100-500 元之间的商品，利用 TreeMap 的 subMap() 方法可在 O(log n + k) 时间内完成范围查询（k 为结果数量）。相比使用 HashMap 后再排序的方案，性能提升约 40%，尤其在商品数量超过 10 万条时优势明显。

此外，通过 navigableKeySet() 实现的反向迭代器，轻松支持了价格从高到低的展示需求，无需额外排序操作。在高并发场景下，我们通过 Collections.synchronizedSortedMap() 包装 TreeMap，结合读写锁机制，平衡了线程安全与性能需求。

大厂面试深度追问

追问1：TreeMap 与 ConcurrentSkipListMap 的选型对比

在并发场景下选择 TreeMap 还是 ConcurrentSkipListMap 需要从多维度考量：

1. 线程安全特性：TreeMap 本身非线程安全，需额外同步机制（如 Collections.synchronizedSortedMap 或显式锁），而 ConcurrentSkipListMap 是并发安全的实现，内部通过 CAS 操作和分段锁保证线程安全。

2. 性能表现：在低并发场景，加锁的 TreeMap 性能可能更优，因为其红黑树结构的缓存局部性更好；高并发下，ConcurrentSkipListMap 的无锁设计能支持更高吞吐量，尤其读多写少场景优势明显。

3. 内存占用：SkipList（跳表）结构的内存开销高于红黑树，每个节点需维护多个索引指针，在数据量极大时，TreeMap 更节省内存。

4. 功能特性：两者都实现了 NavigableMap 接口，但 ConcurrentSkipListMap 额外支持原子性操作如 putIfAbsent()，适合分布式锁等场景。

解决方案：金融交易系统的订单簿实现中，我们采用分层设计：用 ConcurrentSkipListMap 存储活跃订单（高并发读写），用 TreeMap 存储历史订单（低频访问），通过定时任务异步同步数据，既保证了实时交易的高并发性能，又降低了整体内存占用。

追问2：红黑树与 AVL 树在 TreeMap 中的取舍原因

TreeMap 选择红黑树而非 AVL 树，核心原因在于平衡策略的效率差异：

1. 旋转操作次数：AVL 树是严格平衡树（左右子树高度差不超过1），插入和删除时可能需要 O(log n) 次旋转；红黑树是弱平衡（通过颜色规则保证最长路径不超过最短路径2倍），通常只需 2-3 次旋转。

2. 维护成本：AVL 树需存储高度信息，每个节点额外消耗内存，且更新时需频繁调整高度字段；红黑树仅需一个布尔字段存储颜色，维护成本更低。

3. 实际性能：在插入删除频繁的场景，红黑树的旋转操作更少，整体性能更优。虽然 AVL 树查询速度略快（更严格平衡），但 TreeMap 作为通用数据结构，需要在查询和更新性能间取得平衡。

解决方案：在搜索引擎的倒排索引实现中，我们针对不同场景优化：用红黑树（TreeMap）存储动态词频数据（频繁更新），用 AVL 树存储静态词典（极少更新，高频查询），通过这种混合结构兼顾了更新效率和查询性能。