Java TreeMap有序存储原理详解

Java TreeMap 的核心魅力在于其底层红黑树结构带来的天然有序性——它不依赖额外排序，就能在 O(log n) 时间内完成插入、删除和查找，并支持按 key 自然顺序或任意自定义规则（如忽略大小写、按长度排序、倒序、复合条件等）动态维护键值对的逻辑顺序；但这也意味着 key 不能为 null、必须可比较，且非线程安全，多线程场景下需谨慎选用 ConcurrentSkipListMap 替代；与仅保持插入顺序的 LinkedHashMap 不同，TreeMap 真正赋能的是范围查询、首尾键获取等有序操作，是需要“逻辑排序”而非“物理记录”的业务场景不可替代的选择。

TreeMap 为什么能自动排序

TreeMap 底层用的是红黑树（Red-Black Tree），不是哈希表，所以它天然按 key 的自然顺序（或自定义 Comparator）维护节点位置。插入、删除、查找都保持有序，不需要额外排序操作。

注意：key 类型必须实现 Comparable 接口（如 Integer、String），否则运行时抛 ClassCastException；或者构造时传入 Comparator 显式指定比较逻辑。

如何自定义 TreeMap 的排序规则

默认按 key 自然序升序，但多数实际场景需要定制，比如忽略大小写、按长度排序、或倒序。

• 倒序：用 Collections.reverseOrder()，如 new TreeMap(Collections.reverseOrder())
• 忽略大小写：用 String.CASE_INSENSITIVE_ORDER
• 按字符串长度：写匿名 Comparator，例如 (s1, s2) -> Integer.compare(s1.length(), s2.length())
• 复合条件：先按长度，长度相同时按字典序，用 thenComparing 链式调用

TreeMap 和 LinkedHashMap 选哪个

两者都保持“某种顺序”，但语义完全不同：

• TreeMap 是按 key 值大小排序（逻辑序），get/put 时间复杂度是 O(log n)
• LinkedHashMap 是按插入/访问顺序（物理序），get/put 是 O(1)，但不提供基于值的范围查询（比如 “所有 key > 100 的项”）
• 如果只需要遍历时“和插入顺序一致”，选 LinkedHashMap；如果要二分查找、子映射（subMap）、首尾键（firstKey()/lastKey()），必须用 TreeMap

常见陷阱：null key 和并发修改

TreeMap 不允许 null 作为 key（会抛 NullPointerException），哪怕你传了 Comparator —— 因为红黑树在比较时仍需调用 compare(null, x) 或 x.compareTo(null)，而多数 Comparator 并未处理 null。

另外，TreeMap 不是线程安全的。多线程读写时，不能只靠 Collections.synchronizedMap() 包一层就完事——它的迭代器仍可能抛 ConcurrentModificationException。真要并发使用，优先考虑 ConcurrentSkipListMap，它也是有序的，且支持高并发。

真正容易被忽略的是：TreeMap 的 entrySet() 迭代器返回的 Map.Entry 是可变的（setValue() 有效），但改 value 不影响树结构；而改 key 就会破坏排序，所以没有 setKey() 方法。

好了，本文到此结束，带大家了解了《Java TreeMap有序存储原理详解》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！