HashMap的底层实现原理大部分Java工程师都能聊上几句数组加链表链表长度到8再转红黑树。可一旦话题换成TreeMap与TreeSet的实现原理能讲清楚的人就少了一半。我在刚开始啃这两个类源码时也有同样的困惑——明明都是Map凭什么TreeMap的遍历天然有序排序的代价又在哪里TreeSet去重到底靠什么这些问题如果不把底层数据结构摸透用起来总会踩到几个不痛不痒但很坑的错误。今天这篇就系统地把TreeMap和TreeSet的底裤扒干净从红黑树讲起一路看到put、get、删除的源码路径再落到实战里真正值得注意的陷阱。无论你是准备面试还是要在一堆有序数据里做区间查询都能从这里拿到可以直接用的东西。1. 先从“凭什么有序”说起TreeMap的底层契约1.1 TreeMap与HashMap的本质差异HashMap大家都知道核心是哈希表通过数组加链表/红黑树来存储键值对。哈希定位最大的特点是快平均O(1)但代价是无序——哈希函数打散了元素在内存里的物理顺序遍历的时候你根本不知道下一个出来的键是谁。TreeMap走的完全是另一条路。它不哈希而是维护一棵排序二叉树。所有键按照“左小右大”的规则存放在树里任何时刻对这棵树做中序遍历得到的序列都是严格升序的。这个“有序”不是在遍历时才临时排序而是在每次插入、删除时就已经通过树的自平衡机制维护好了。TreeMap的puts、gets、deletes全部落在从根到叶子的路径上时间复杂度稳定在O(logN)树的高度就是log级别的。也就是说TreeMap和HashMap的差异不是“快慢”这么简单而是数据组织方式不同一个靠哈希桶定位一个靠排序树定位。理解了这一点后面看它的所有API行为都会很顺。1.2 排序的物理载体红黑树到底是一棵什么样的树先复习一下二叉搜索树BST左子树所有节点小于根右子树所有节点大于根中序遍历天然有序。BST最大的问题在于退化——如果你按顺序插入1、2、3、4、5树会变成一根链表查询复杂度退化成O(N)。红黑树就是加了五条颜色规则的BST目标是把树的高度控制在log级别。它不像AVL树那样严格追求左右子树高度差不超过1而是通过颜色约束做到“近似平衡”。红黑树允许最长路径是最短路径的两倍但因为有这个上界任何操作路径都不会超过2log2(N1)所以所有操作都能保证O(logN)。TreeMap为什么选红黑树而不是AVL因为红黑树的平衡代价更小。AVL为了追求绝对平衡插入删除时频繁旋转写操作慢红黑树放宽了平衡条件牺牲一点查询常数换来更少的结构调整。对TreeMap这种偏写、偏范围操作的场景是更务实的选择。1.3 TreeSet只是“只用了Key的TreeMap”很多人以为TreeSet是另一套数据结构其实它就是一棵只关心“键”的TreeMap。TreeSet内部持有一个NavigableMapE,Object的引用默认就是TreeMap实例。你把元素add进TreeSet它干的事情就是把元素当作TreeMap的key放进去value统一用一个固定的Object占位符。这个设计在源码里表现得特别直白public class TreeSetE extends AbstractSetE implements NavigableSetE, Cloneable, java.io.Serializable { private static final Object PRESENT new Object(); private transient NavigableMapE,Object m; public TreeSet() { this(new TreeMap()); } public boolean add(E e) { return m.put(e, PRESENT) null; } public boolean remove(Object o) { return m.remove(o) ! null; } public boolean contains(Object o) { return m.containsKey(o); } }所以TreeSet的排序、去重、范围查询等行为全部继承自TreeMap。把TreeMap的红黑树机制弄明白TreeSet就只剩下“适配器模式”这一层皮了。这也是为什么JDK源码设计里复用性可以做到这么极致——一个底层数据结构换个接口包装就成了另一个集合类。2. 红黑树的五条铁律与TreeMap的平衡艺术2.1 五条规则从哪儿来红黑树对每个节点涂上黑或红并遵守五条规则每个节点不是红色就是黑色。根节点是黑色。每个叶子节点NIL是黑色。红色节点的两个子节点必须都是黑色也就是说红节点不能挨着红节点。从任意节点到其每个叶子节点的路径上黑色节点的数量必须相同。这五条规则的核心作用是把树的高度限定在O(logN)内。直觉是这样因为规则5任何一条路径上的黑节点数相同因为规则4一条路径上不能连续出现两个红节点。所以最长路径是“黑红黑红”交替最多只是最短路径全黑的两倍。有了这个上界TreeMap的查找、插入、删除就都能保证对数级复杂度。我在刚接触的时候一直觉得规则5是最难理解的其实它就是在保证“每条路一样沉”让树不会往某个方向畸形生长。这和以前玩天平有点像两边的黑节点数必须持平谁多谁少都失衡。2.2 插入默认红色破坏规则也分三种情况TreeMap插入新节点时默认把它涂成红色。为什么因为红色节点不会破坏规则5也就是不会改变任何路径上的黑节点数唯一的风险是碰到红父节点造成“红红相连”违反规则4。这样就把问题限定在一个局部修起来快。新的红色节点插入后按父节点和叔叔节点的颜色分三种情况处理父节点为黑色直接插入什么事都不用做。父红、叔叔红把父和叔变黑把祖父变红然后从祖父继续往上调整因为祖父变红后可能会和它的父节点产生新的冲突。父红、叔叔黑需要旋转加变色。如果新节点在父亲的同侧LL或RR做一次旋转加变色如果在异侧LR或RL先旋转成同侧再处理。这个流程比较绕但只要记住“旋转就是调整父子关系不改变中序遍历结果”就够了。TreeMap里的fixAfterInsertion方法核心代码其实就是按这个逻辑写的。我简化记录一下while (x ! null x ! root colorOf(parentOf(x)) RED) { if (parentOf(x) leftOf(parentOf(parentOf(x)))) { EntryK,V y rightOf(parentOf(parentOf(x))); // 叔叔 if (colorOf(y) RED) { // 情况一变色上溯 setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x parentOf(parentOf(x)); } else { if (x rightOf(parentOf(x))) { // 情况二先左旋变成情况三 x parentOf(x); rotateLeft(x); } // 情况三右旋 变色 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } // 对称方向就不展开了 } setColor(root, BLACK);老实说源码比这个还要密一些但骨架就在这里。真正优化过的红黑树插入调整平均只需要常数次旋转最多两次剩下的都是变色。所以即使面对几百万条数据TreeMap的插入也不会有明显的卡顿。2.3 删除为什么比插入麻烦得多删除是红黑树实现里最头疼的部分。林纳斯说过删除一个节点比插入要难一个数量级红黑树删除尤其如此。如果一个节点是红色直接删除就好因为红色不会影响黑高。麻烦的是删除黑色节点——它会让某条路径上的黑节点数变少违反规则5。修复的思路是引入“双重黑色”的概念先当成那个位置欠了一个黑然后看兄弟节点的颜色来决定怎么还债。TreeMap的fixAfterDeletion主要按兄弟节点的情况分兄弟是红色旋转一次把兄弟变黑父变红重新定位。兄弟是黑色且兄弟的两个孩子都是黑色兄弟变红问题向上推一层。兄弟是黑色但至少有一个红孩子通过旋转加变色把黑色补回来并直接结束。这些情况我自己刚开始也背不下来后来发现关键是理解“借颜色”的思想删除黑色节点等于拿走了路径上一个黑修复就是想办法让其他路径匀出一个黑来或者把问题推到父节点去解决。因为单次删除的旋转次数最多三次所以即使最坏情况也只是O(logN)的变色加常数次旋转。2.4 TreeMap如何利用红黑树实现O(logN)复杂度红黑树保证树高不超过2log2(N1)所以从根开始找任何一个键最多走这么深。TreeMap的put要先找到合适叶子位置get要先沿路径比较delete要找到节点再修复复杂度全都由树高决定。这也是TreeMap和HashMap最大的性能分水岭HashMap平均O(1)TreeMap稳定O(logN)但反过来HashMap没有序TreeMap天然有序。这种取舍在工程上非常经典。3. TreeMap源码实现put、get与迭代器的真实执行路径3.1 Entry节点结构和比较器注入TreeMap内部定义了一个静态内部类Entry它是整棵红黑树的基本单元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; Entry(K key, V value, EntryK,V parent) { this.key key; this.value value; this.parent parent; } // getKey/getValue/setValue/equals/hashCode 略 }可以看出每个节点除了key/value还要额外维护left、right、parent三个引用和一个布尔颜色。这也是TreeMap内存占用比HashMap大的原因之一——每个节点多了好几个指针。下面这个结构特点在后面聊性能时会再次出现。TreeMap支持两种排序方式自然排序和自定义Comparator。private final Comparator? super K comparator; SuppressWarnings(unchecked) final int compare(Object k1, Object k2) { return comparator null ? ((Comparable? super K) k1).compareTo((K) k2) : comparator.compare((K) k1, (K) k2); }看到没有如果构造时没传ComparatorTreeMap会把key强转成Comparable然后调用compareTo。所以使用TreeMap的时候key要么实现Comparable要么必须在构造时给Comparator否则第一次插入就会抛ClassCastException。这个细节很基础但很多人第一次见TreeMap的空构造器时都会踩到。3.2 put全流程比较、下钻、挂载、修复TreeMap的put方法逻辑非常清晰可以拆成四步从根节点开始用compare方法比较当前key和节点key。小于0走左子树大于0走右子树直到找到插入位置。如果中途发现key已经存在直接用新value替换旧value返回旧value。如果走到null位置创建一个新Entry挂上去然后调用fixAfterInsertion做红黑修复。public V put(K key, V value) { EntryK,V t root; if (t null) { compare(key, key); // 检查key类型顺便触发空检查 root new Entry(key, value, null); size 1; modCount; return null; } Comparator? super K cpr comparator; 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); } while (t ! null); } // 其他分支类似最后创建新节点并调整 EntryK,V e new Entry(key, value, parent); if (cmp 0) parent.left e; else parent.right e; fixAfterInsertion(e); size; modCount; return null; }注意TreeMap的value是允许为null的但key默认不允许null。为什么因为compare方法在key为null时根本没法比较自然序调用null.compareTo会直接NPE。前面说了除非你传一个能处理null的比较器否则TreeMap的键必须非空。这个和HashMap能存null键值形成鲜明对比后面坑里再细说。3.3 迭代器如何做到“天然有序”TreeMap能按升序遍历靠的是迭代器使用中序遍历。所谓中序遍历就是“左子树 → 当前节点 → 右子树”的顺序由于BST左小右大的特性结果天然升序。TreeMap的EntryIterator在实现next时内部其实是调用了successor方法static K,V TreeMap.EntryK,V successor(EntryK,V t) { if (t null) return null; else if (t.right ! null) { EntryK,V p t.right; while (p.left ! null) p p.left; return p; } else { EntryK,V p t.parent; EntryK,V ch t; while (p ! null ch p.right) { ch p; p p.parent; } return p; } }逻辑不复杂如果当前节点有右子树后继就是右子树里最左的那个节点否则向上找第一个“自己是父节点左孩子”的祖先那个祖先就是后继。迭代器的失败保护也依赖modCount——如果遍历时TreeMap被结构性修改再调next就会抛ConcurrentModificationException。这点和ArrayList的行为一致。如果你需要反向遍历TreeMap还提供了descendingMap()返回的视图迭代顺序是降序的。它不是一个新副本而是同一个树上的反向视图这个设计在Java集合框架里很常见。3.4 删除后继替换与双黑修复在TreeMap里的落点TreeMap的removeEntry走的是标准的二叉搜索树删除路线被删节点有两个孩子时找后继右子树最小节点把后继的key/value复制到被删节点上然后实际去删后继节点。后继节点至多只有一个右孩子所以真正的物理删除很简单。如果删除的节点是黑色就调用fixAfterDeletion做红黑修复。最后size--modCount。整个过程我不会在文章里贴全源码因为那个fixAfterDeletion分支如果画出来会有四个case加镜像太长了。但只要记住实际删除的往往不是“最初想删的那个节点”而是它“中序遍历后面的继任者”。这个后继替换思路在很多有序数据结构里都能看到比如二叉搜索树的remove甚至跳表删除也是一样的思想。4. TreeSet一个披着Set外衣的TreeMap4.1 核心构造器与方法委托的背后TreeSet的实现原理用一句话概括就是委托TreeMap。JDK内部给了它一个NavigableMap类型的引用m默认构造器直接new一个TreeMappublic TreeSet() { this(new TreeMap()); } public TreeSet(Comparator? super E comparator) { this(new TreeMap(comparator)); } TreeSet(NavigableMapE,Object m) { this.m m; }第三个构造器是包级私有的专门服务于subSet、headSet等视图方法。TreeSet的add和remove前面已经看过如果给TreeSet构造传了一个已有的TreeMap那它们的view就是共用的同一棵树。TreeSet和HashSet的区别也在这里体现出来特性TreeSetHashSet底层结构TreeMap红黑树HashMap哈希表排序性按比较器或自然序升序无序去重依据compareTo/compare 0hashCode equals核心复杂度O(logN)O(1) 平均是否允许null默认不允许会NPE允许一个null这张表基本就是面试里高频对比题的完整答案。4.2 去重判定不是equals是compareTreeSet最容易被忽视的点是它的“相等”定义。HashSet去重依赖hashCode和equalsTreeSet去重却只看比较器的返回值compare(a, b) 0就算同一个元素。这意味着你甚至可以构造出两个equals返回false、但compare返回0的对象它们放进TreeSet会被当成重复元素第二个add会返回false。反过来如果compare永远不返回0即使两个对象equals为trueTreeSet也能同时存下两个——这会让集合行为彻底“跑偏”。JDK文档明确建议Comparator应该和equals保持一致性但因为它只是建议很多人就忽略了结果线上出现“去重去不掉”或“误去重”的诡异问题。实际开发里我的建议是如果对象同时需要放HashSet和TreeSet一定要让compareTo和equals的定义保持一致。做不到的话至少保证单一容器里只依赖一种判定逻辑不要交叉使用。4.3 子集合视图subSet/headSet/tailSet的实现逻辑TreeSet的范围视图方法返回的不是一份拷贝而是一个“视图”public NavigableSetE subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet(m.subMap(fromElement, fromInclusive, toElement, toInclusive)); }这里构造的TreeSet内部持有的m是原TreeMap的子映射视图。往子集合里add元素原集合也会多出这个元素原集合删了元素子集合也看不到它。这种视图机制的好处是零拷贝、操作直接映射到底层红黑树代价是如果你没意识到这一点很容易在修改子集合时“意外影响”全量数据。我见过有人拿subSet做临时过滤过滤完不清空结果原集合一直包含那些“不该存在”的数据排查半天才发现是视图的传染性。这不算TreeSet的bug而是设计上的约定用之前必须清楚。5. 实战用法与选型有序Map在真实需求里的打开方式5.1 区间查询subMap、headMap、tailMap的用法与边界TreeMap最有价值的地方不是简单的排序遍历而是范围查询。比如你有大量带时间戳的日志要查某一分钟内有哪些记录用HashMap就只能全遍历用TreeMap就是一条subMap调用TreeMapLong, String eventMap new TreeMap(); eventMap.put(1700000000000L, start); eventMap.put(1700000001000L, slow); eventMap.put(1700000002000L, end); NavigableMapLong, String window eventMap.subMap(1700000000000L, true, 1700000000200L, true);subMap返回的是位于[fromKey, toKey]之间的视图两个boolean参数控制是否包含边界。headMap(toKey)取小于toKey的部分tailMap(fromKey)取大于等于fromKey的部分。这些操作都是基于红黑树从根开始定位边界再向后遍历所以复杂度是O(logN m)m是返回的元素数量尤其在大量数据下优势非常明显。用的时候有个习惯要注意JDK很多范围习惯叫“左闭右开”但subMap的边界默认是包含头、不包含尾除非你显式指定inclusive。所以判断区间时一定要想清楚自己的业务是闭区间还是开区间否则多一条记录少一条记录是常事。5.2 最近邻匹配与有序弹出floorKey、ceilingKey、pollFirstEntry除了范围查询TreeMap还能做“查找最接近某个值”的操作这是HashMap完全做不到的ceilingKey(k)返回大于等于k的最小键找不到返回null。floorKey(k)返回小于等于k的最大键。lowerKey(k)返回严格小于k的最大键。higherKey(k)返回严格大于k的最小键。举个实际场景系统要给请求分配端口端口池里有一批空闲端口每次分配“最接近某个基准值的端口”用ceilingEntry就能直接命中再比如优惠券过期时间表里要找到一张“过期时间刚好大于当前时间”的券不用遍历全表直接ceilingKey(now)就行。还有一组方法叫pollFirstEntry / pollLastEntry返回并移除最小/最大的键值对。配合这两个方法和TreeMap的有序性我经常直接把它当“有序队列”用任务按优先级入队每次pollFirstEntry取最紧急的那个比PriorityQueue多出来的优势是还能直接按区间条件批量取出任务。这个用法很冷门但实战效率极高。5.3 与HashMap、LinkedHashMap的选择矩阵容器顺序平均复杂度典型场景HashMap无序O(1)快速等值查找、缓存LinkedHashMap插入序/访问序O(1)LRU缓存、保持写入顺序TreeMapkey自然序/自定义序O(logN)范围查询、排序遍历、最近邻LinkedHashMap虽然也是“有序”但它保持的是插入顺序或访问顺序不是key的逻辑顺序。如果需求是“按key大小排序再读取”例如榜单按分数高低、价格区间检索LinkedHashMap就完全无能为力只能TreeMap上场。这是选型时最容易搞混的一点。顺带说一句HashMap底层在极端哈希冲突时也会用红黑树。JDK 8以后当链表长度超过8且数组容量达到64链表会转成红黑树目的就是把最坏情况下冲突桶里的查找从O(N)压到O(logN)。这也说明红黑树在JDK里不只是TreeMap/TreeSet在用它已经是哈希冲突兜底方案的一部分了。至于布隆过滤器那种“只判断存在性、不关心有序”的场景和红黑树压根不是一类工具——它允许误判但省内存没法做范围查询所以两者没有可比性别混为一谈。6. 踩坑复盘真正让我翻车的三个场景6.1 可变键的灾难字段变更后整棵树直接“错乱”有次我用一个自定义对象做TreeMap的key比较器按对象的id字段排序。业务逻辑里有个操作会直接修改对象的id值然后我再用这个对象调用get返回null而原key明明还在map里。当时第一反应是怀疑比较器写错了打印出来才发现树里那个键的“位置”还是旧的id对应的位置可对象本身的id已经变了。原因就在红黑树的机制上树的平衡只在put和remove时根据当时的比较结果调整它不会感知对象字段的变化。你把一个键的排序字段改了树里的物理位置却没有跟着变后续所有查找、范围判断都会拿新值和旧位置比自然找不到。这个坑的根治办法很简单用作key的对象必须不可变或者至少保证参与比较的字段在整个生命周期里不动。如果业务确实要修改排序字段那就先remove再重新put不要试图原地改。类似的坑在HashSet/HashMap里也有——修改了参与hashCode计算的字段会导致元素“丢”在旧桶里。只是TreeMap的树结构让这个问题更隐蔽因为它表面看还像那么回事。6.2 比较器与equals不一致同一批对象在两套集合里“判若两样”另一个案例更典型。项目中有一批用户对象两个对象只要id相同就认为相同于是我写Comparator时只比较id但没有同步重写equalsequals仍然比较所有字段。结果就是同一份数据放进TreeSet能去重放进HashSet去重失败。更麻烦的是两个地方的数据汇总时出现了“一边说重复、一边说不重复”的矛盾最后只能写额外逻辑去对齐。这个坑的根子是Comparator和equals的契约不一致。TreeSet拿Comparator当唯一标准HashSet拿equals/hashCode当唯一标准你让它们各执一词行为必然打架。我现在的习惯是写任何比较器之前先问自己“这个东西放进TreeSet和HashSet时我希望它们对重复的定义一样吗”如果一样就强制保证compare返回0时equals也为true否则宁可抛异常也别静默容忍。6.3 null处理一个NPE引发的排查疲劳第一次在项目里用TreeMap存配置往里面put了一个null键结果直接炸了NullPointerException。我第一反应是TreeMap出bug了后来翻源码才发现自然排序的compare方法调用null的compareTo这个异常是必然的。TreeMap允许null值但默认不允许null键TreeSet则连null元素都装不进去因为add(null)会转成put(null, PRESENT)一样NPE。如果你想在TreeMap里用null键唯一的办法是自定义Comparator并且在比较器里显式处理null比如Comparator.nullsFirst或nullsLast。但这会引入更多边界两个null键在nullsFirst下会被视为相等直接互相覆盖。说实话在有序容器里塞null键业务设计本身就要打个问号我后来基本都是提前在入口做非空校验。还有个很容易误判的点TreeMap的value允许为null所以get(key)返回null时你分不清楚是“键不存在”还是“键存在但value为null”。如果需要判断键是否存在一定用containsKey别拿get的结果当存在性依据。这个规则其实也适用于HashMap但在TreeMap里会因为你下意识认为“它那么严格应该不会允许null”而更容易踩。6.4 性能边界红黑树不是万能银弹TreeMap的优秀是相对“手动维持有序”来说的它的常数并不小。每个Entry除了key/value还带着left、right、parent和color内存开销比HashMap桶里的Node高不少。我曾经压过百万级的随机数插入TreeMap的耗时大概是HashMap的两到三倍这在量级上不算离谱但如果你只是要一个能快速查到元素、无所谓顺序的缓存拿TreeMap来存就是平白给内存和CPU上税。更现实的问题是线程安全。TreeMap本身不是线程安全的并发写会出问题。如果你既需要有序又需要并发安全应该考虑ConcurrentSkipListMap底层用跳表无锁并发范围查询一样支持只是内部结构完全不同。跳表的原理和红黑树有相似之处都是通过多层索引加速查找但跳表对并发友好得多CAS改节点比红黑树的旋转变色好实现得多。所以选型时别只看接口长一样底层机制决定了它们的并发性能上限。最后一句话收束我自己的经验凡是需要“有序集合范围切片最近邻查找”这三个能力里的任何一个TreeMap/TreeSet都是第一默认选项但前提是你从一开始就把键设计成不可变对象把比较器写成和equals一致的规则。这个小习惯比任何源码细节都更能帮你少踩坑。另外还有一个我很常用的冷门技巧NavigableMap接口提供了pollFirstEntry和pollLastEntry配合subMap用一棵TreeMap就能实现一个支持按区间批量弹出任务的有序队列省掉自己维护PriorityQueue外加时间戳的麻烦。等你真正跑过几轮百万级数据体会过那棵红黑树在动态插入和删除之间保持平衡的稳定感你自然就会明白为什么JDK作者会把这个结构安放在两个最常用的有序集合类底部。