treemap 的 get() 时间复杂度为 o(log n)，因其基于红黑树实现，需沿树路径比较查找；不支持 o(1) 因需维持键有序性，适用于范围查询、排序遍历等场景。
TreeMap 的 get() 操作时间复杂度是 O(log n)
不是常数，也不是线性，就是标准的红黑树单次查找开销。它底层用的是自平衡二叉搜索树（红黑树），所有 get()、put()、remove() 都稳定在 O(log n) —— 前提是键的 compareTo() 或 compare() 实现本身不拖后腿。
常见错误现象：有人测出 get() 很慢，结果发现是自定义类的 compareTo() 里写了数据库查询或正则匹配；或者用了 String 但字符串超长（比如几 MB 的 JSON），导致每次比较都耗时严重。
- 键必须实现
Comparable，或传入外部Comparator；否则运行时报ClassCastException或NullPointerException - 如果键的比较逻辑有副作用（如修改状态、IO），不仅破坏排序语义，还会让查找行为不可预测
- 注意
null值：默认自然序下null会触发NullPointerException；用自定义Comparator可以处理，但必须显式定义null的位置（比如放在最前或最后）
为什么不是 O(1)？HashMap 不香吗
因为 TreeMap 要维持键的有序性，无法像 HashMap 那样靠哈希函数直接定位桶。它必须走树路径：从根开始，根据 compareTo() 结果决定往左还是右子节点走，最多比对 log₂(n) 次就能命中或确认不存在。
适用场景很明确：你需要按 key 排序遍历（firstKey()、subMap()、迭代器顺序）、范围查询（比如“查所有时间戳在 [t1, t2] 之间的记录”）、或者需要严格控制内存占用（HashMap 的负载因子和扩容机制可能多占 30%~50% 内存）。
立即学习“Java免费学习笔记（深入）”；
-
HashMap平均 O(1)，但 worst-case 是 O(n)（全哈希冲突）；TreeMap没有 worst-case 波动，始终 O(log n) - 如果只做随机查，且 key 类型支持高效哈希（如
Integer、String），HashMap几乎总更快；但如果还要tailMap(100)这种操作，TreeMap天然支持，HashMap得自己遍历过滤 - Java 8+ 的
HashMap在桶内链表过长时会转红黑树，但那只是为防哈希碰撞退化，和TreeMap的全局有序结构无关
实际性能差异有多大？别猜，得看 key 类型和数据量
小数据量（n TreeMap.get() 和 HashMap.get() 差距几乎感知不到；但到 n = 10⁵，log₂(10⁵) ≈ 17，而 HashMap 平均只需 1~2 次哈希 + 1 次 equals —— 实测吞吐量通常差 3~5 倍。
真正影响落地效果的，往往是 key 的比较成本。比如用 LocalDateTime 查找很快，但用自定义的 Version 类（内部解析 "1.2.3-beta" 字符串再逐段比）就会明显变慢。
- 测试时务必用真实 key 构造数据，别只用
Integer一测了事 - 用 JMH 做基准测试，避免 JVM 预热不足或 GC 干扰
- 如果业务中 90% 操作是范围查询，哪怕单次
get()慢一点，TreeMap整体更省事——别为了理论上的“快一点”硬切HashMap加排序层
容易被忽略的红黑树隐含约束
红黑树能保持 O(log n) 的前提是：插入/删除后的旋转和重着色必须在常数时间内完成。JDK 的 TreeMap 实现满足这点，但你不能破坏它的前提——比如在比较器里改写 key 对象的状态，或让 compareTo() 返回值随时间变化（如依赖系统时间、随机数）。
这类 bug 表现很隐蔽：有时查得到，有时查不到；map 大小明明是 1000，但 keySet().stream().count() 却是 999；甚至出现 ConcurrentModificationException（虽然没并发，但树结构已被非法修改）。
- key 对象必须是不可变的，或至少在放入
TreeMap后不再修改参与比较的字段 - 比较逻辑必须满足自反性（x.compare(x) == 0）、传递性（x
x），否则树结构会错乱 - 不要在
Comparator里抛异常（如IllegalArgumentException），TreeMap不会捕获，直接中断查找流程
红黑树的稳定性不来自魔法，而来自你对 key 和比较逻辑的克制。一旦放开这个口子，O(log n) 就只是纸面承诺。
