一、先理解背景Map 家族已经有了 HashMap为什么还需要 TreeMap1.1 HashMap 的设计目标和局限HashMap 的设计目标是最快的随机访问。它底层是数组 链表/红黑树通过hashCode()把 key 分散到数组的不同位置上理想情况下get/put都是O(1)。但 HashMap 有一个根本性的设计取舍它完全不关心 key 的顺序。MapInteger, String map new HashMap(); map.put(3, C); map.put(1, A); map.put(2, B); // 遍历出来可能是2B, 3C, 1A 完全无序 for (Integer key : map.keySet()) { System.out.println(key map.get(key)); }没有 TreeMap 的弊端就出现了如果你写了一个配置系统用户按顺序添加了配置项但遍历的时候顺序全乱了用户就无法预测行为。如果你要做获取所有大于 10 的 key这种操作HashMap 只能遍历全部元素逐个判断时间复杂度是O(n)。1.2 所以 TreeMap 被设计出来解决什么问题TreeMap 的核心设计目标只有一个让 key 始终保持有序。有了这个特性以下操作就变得高效获取第一个/最后一个key → O(log n)获取比某个 key 大的下一个key → O(log n)获取某个范围内的所有 key如 10 到 20 之间→ O(log n k)k 是结果数量代价是get/put/remove从 O(1) 变成了O(log n)。这是一个经典的设计取舍用一点速度换取有序性带来的强大功能。二、TreeMap 底层为什么选择红黑树2.1 首先为什么不用普通数组或链表如果只是为了有序用数组排序行不行// 方案1用 ArrayList 每次插入时排序 ListEntry list new ArrayList(); list.add(new Entry(3, C)); Collections.sort(list); // 每次插入都要排序O(n log n)弊端很明显每次插入都要重新排序或者插入到正确位置需要 O(n) 移动元素。对于频繁增删的场景这个代价太高。链表呢查找需要 O(n)有序插入也要 O(n) 找位置。所以数组和链表都无法同时满足有序和高效增删查。2.2 二叉搜索树BST的出现为了同时满足有序和高效设计了二叉搜索树5 / \ 3 8 / \ \ 1 4 9规则很简单左子树所有节点 根节点 右子树所有节点。这样查找一个值时每次都能排除一半的可能性类似二分查找时间复杂度是O(log n)。插入也简单从根开始比较小就往左走大就往右走走到空位置就插入。但二叉搜索树有个致命缺陷如果插入的数据是有序的比如 1, 2, 3, 4, 51 \ 2 \ 3 \ 4 \ 5树退化成了链表查找变成 O(n)完全失去了设计意义。2.3 平衡二叉树的引入为了解决退化问题必须让树保持平衡左右子树的高度不能差太多。AVL 树是严格平衡的任意节点左右子树高度差 ≤ 1。但 AVL 树的设计弊端是维护严格平衡需要频繁旋转。插入一个节点可能需要从插入点一路旋转到根节点旋转次数不确定最坏情况下维护成本很高。红黑树的设计哲学是我不追求绝对平衡我只追求近似平衡。允许左右子树高度差最多一倍而不是 AVL 的 1这样旋转的次数大大减少维护成本更低。对比特性AVL 树红黑树平衡程度严格高度差≤1宽松高度≤2log n查找速度稍快树更矮稍慢树可能高一倍但仍是 O(log n)插入/删除旋转次数可能多次最多 2 次旋转 变色适用场景读多写少读写均衡工业首选TreeMap 选择红黑树的原因Map 是通用容器读写操作都很频繁。红黑树在查找效率和维护成本之间取得了更好的平衡实现也相对简单所以被 Java 选为 TreeMap 的底层结构。三、红黑树的五条规则TreeMap 的约束条件红黑树通过颜色约束来保证平衡所有操作都必须维护这五条规则每个节点要么是红色要么是黑色根节点是黑色所有叶子节点NIL空节点是黑色红色节点的两个子节点必须是黑色不能有两个连续红节点从任一节点到其每个叶子的所有路径上黑色节点数量相同黑高相同第 5 条是核心它保证了树不会偏向某一侧。即使某条路径上有红节点黑节点的数量也必须和其他路径一样所以最长路径最多是红黑红黑黑最短是黑黑黑最长不超过最短的两倍。这就确保了树高始终是O(log n)。四、TreeMap 的核心源码逻辑4.1 节点结构static final class EntryK,V implements Map.EntryK,V { K key; V value; EntryK,V left; // 左子节点 EntryK,V right; // 右子节点 EntryK,V parent; // 父节点 boolean color BLACK; // 默认黑色 }相比 HashMap 的 NodeTreeMap 的 Entry 多了parent和color因为红黑树需要双向关联和颜色标记来维护平衡。4.2 put() 方法的核心逻辑public V put(K key, V value) { EntryK,V t root; // 1. 树为空创建根节点 if (t null) { compare(key, key); // 检查 key 是否可比较 root new Entry(key, value, null); size 1; return null; } int cmp; EntryK,V parent; Comparator? super K cpr comparator; // 2. 找到插入位置二叉搜索树的查找逻辑 if (cpr ! null) { // 使用自定义比较器 do { parent t; cmp cpr.compare(key, t.key); if (cmp 0) t t.left; else if (cmp 0) t t.right; else return t.setValue(value); // key 已存在更新 value } while (t ! null); } else { // 使用自然排序Comparable Comparable? super K k (Comparable? super K) key; do { parent t; cmp k.compareTo(t.key); if (cmp 0) t t.left; else if (cmp 0) t t.right; else return t.setValue(value); } while (t ! null); } // 3. 创建新节点并挂上 EntryK,V e new Entry(key, value, parent); if (cmp 0) parent.left e; else parent.right e; // 4. 关键插入后修复红黑树平衡 fixAfterInsertion(e); size; return null; }设计要点TreeMap不允许 null key因为无法比较除非你用自定义 Comparator 处理了 null查找插入位置的过程就是标准 BST 的查找O(log n)插入后必须调用fixAfterInsertion()维护红黑树规则4.3 插入修复的核心思想新节点默认插入为红色插入黑色会破坏第 5 条规则导致黑高变化影响范围太大。插入红色后如果父节点是黑色没问题直接结束。如果父节点是红色违反第 4 条出现连续红节点需要分情况处理情况 1叔叔节点是红色黑(祖父) / \ 红(父) 红(叔) / 红(新)解决把父和叔变黑祖父变红然后把问题上移到祖父节点。情况 2叔叔节点是黑色或 null需要通过旋转解决。旋转又分为左旋和右旋目的是把新节点或父节点提上去同时保持 BST 的有序性。旋转后还要调整颜色确保不违反规则。为什么这样设计因为红黑树的规则是局部的只看父、叔、祖父所以修复只需要在插入点附近做有限次旋转和变色最多 2 次旋转就能恢复平衡。这比 AVL 树可能需要一路旋转到根的设计更高效。4.4 get() 方法public V get(Object key) { EntryK,V p getEntry(key); return (p null) ? null : p.value; } final EntryK,V getEntry(Object key) { if (comparator ! null) return getEntryUsingComparator(key); Comparable? super K k (Comparable? super K) key; EntryK,V p root; while (p ! null) { int cmp k.compareTo(p.key); if (cmp 0) p p.left; else if (cmp 0) p p.right; else return p; } return null; }就是标准的 BST 查找利用有序性每次排除一半O(log n)。五、TreeMap 特有的强大功能正因为底层是有序树TreeMap 提供了 HashMap 没有的方法TreeMapInteger, String map new TreeMap(); map.put(10, A); map.put(20, B); map.put(30, C); map.put(40, D); // 1. 获取第一个/最后一个 key map.firstKey(); // 10 map.lastKey(); // 40 // 2. 获取比 25 大的第一个 key map.ceilingKey(25); // 30 // 3. 获取比 25 小的第一个 key map.floorKey(25); // 20 // 4. 获取子视图10 key 35 SortedMapInteger, String sub map.subMap(10, 35); // {10A, 20B, 30C} // 5. 获取大于 20 的所有元素 SortedMapInteger, String tail map.tailMap(20); // {20B, 30C, 40D}这些操作在 HashMap 中要么做不到要么需要 O(n) 遍历。在 TreeMap 中全是 O(log n)。方法含义firstKey()最小 KeylastKey()最大 KeylowerKey(key)小于 key 的最大 KeyhigherKey(key)大于 key 的最小 KeyfloorKey(key)小于等于 key 的最大 KeyceilingKey(key)大于等于 key 的最小 Key六、总结TreeMap 的设计逻辑链问题解决方案设计原因HashMap 无序无法范围查询需要有序结构有序是某些场景的必要条件数组/链表无法高效维护有序性二叉搜索树BST 同时支持有序和 O(log n) 操作BST 会退化成链表自平衡树防止最坏情况AVL 树维护成本太高红黑树弱平衡读写均衡旋转次数少实现简单插入破坏平衡颜色约束 旋转修复局部修复最多 2 次旋转什么时候用 TreeMap需要 key 始终保持有序需要频繁做范围查询subMap, tailMap 等需要获取最近的更大/更小元素能接受 O(log n) 的增删查代价比 HashMap 的 O(1) 慢但比 O(n) 快得多什么时候不要用 TreeMap只关心快速存取不关心顺序 → 用 HashMap需要保持插入顺序 → 用 LinkedHashMap需要线程安全的有序 Map → 用 ConcurrentSkipListMap七、TreeMap 为什么能够自动排序这是理解 TreeMap 的核心。假设TreeMapInteger, String map new TreeMap(); map.put(30, A); map.put(10, B); map.put(20, C);TreeMap 内部并不是简单地把数据放进一个数组。它底层是一棵红黑树你现在先不要管红黑树的各种细节。先把它理解成30 / 10 \ 20当你插入20的时候它会不断比较20 和 30 比较 20 30 ↓ 往左边找然后20 和 10 比较 20 10 ↓ 往右边找最后找到应该放的位置。TreeMap 就是通过这种不断比较 Key的方式让 Key 始终保持有序。八、TreeMap 是按照什么规则排序的比如TreeMapInteger, String map new TreeMap();Integer可以比较大小所以10 20 30自然就能排序。但是如果Key 是你自己的对象TreeMapUser, String map new TreeMap();TreeMap 就会遇到一个问题两个 User 到底谁大谁小例如User user1 new User(张三, 20); User user2 new User(李四, 30);TreeMap 怎么知道user1 user2还是user1 user2所以 TreeMap 必须知道Key 的比较规则是什么。有两种方式。8-1、方式一Key 实现 Comparable例如public class User implements ComparableUser { private Integer age; Override public int compareTo(User o) { return this.age - o.age; } }意思就是User 按照 age 排序。然后TreeMapUser, String map new TreeMap();TreeMap 就知道怎么比较 User 了。8-2、方式二创建 TreeMap 的时候传 Comparator这个开发中其实更加常见。例如我们希望按照年龄排序TreeMapUser, String map new TreeMap((u1, u2) - u1.getAge() - u2.getAge());或者写得更安全一些TreeMapUser, String map new TreeMap(Comparator.comparing(User::getAge));这样 TreeMap 就知道User1.age User2.age那么 User1 就排在 User2 前面。九、TreeMap 最有价值的地方是什么TreeMap 不仅仅是“帮我排序。”它最大的价值其实是它可以在有序数据中进行各种范围查询。例如TreeMapInteger, String map new TreeMap(); map.put(10, A); map.put(20, B); map.put(30, C); map.put(40, D); map.put(50, E);现在我问你比 30 小的最大 Key 是多少TreeMapmap.lowerKey(30);结果20我问比 30 大的最小 Key 是多少map.higherKey(30);结果40我问小于等于35 的最大 Key 是多少map.floorKey(35);结果30我问大于等于35 的最小 Key 是多少map.ceilingKey(35);结果40这就是 TreeMap 非常重要的能力。十、TreeMap 还有一个非常重要的能力范围查询例如TreeMapInteger, String map new TreeMap(); map.put(10, A); map.put(20, B); map.put(30, C); map.put(40, D); map.put(50, E);我现在只想要20 ~ 40可以map.subMap(20, 40);得到20 30注意默认情况下subMap(20, 40)是20 key 40如果想包含40map.subMap(20, true, 40, true);还有map.headMap(30);表示Key 30以及map.tailMap(30);表示Key 30所以 TreeMap 很适合范围查询。十一、还有一个非常重要的坑TreeMap 的 Key 不能随便放比如TreeMapObject, String map new TreeMap(); map.put(10, A); map.put(hello, B);这就有问题。因为 TreeMap 需要比较10 和 hello但它们根本没法比较。所以TreeMap 的 Key 必须能够进行比较。一般就是Key 实现 Comparable或者TreeMap 提供 Comparator十二、TreeMap 允许 null Key 吗一般情况下TreeMapString, String map new TreeMap(); map.put(null, A);会抛出NullPointerException原因非常简单TreeMap 需要比较 Key。但是null 和 abc没办法进行自然排序。