两个学生A的分数是90B的分数也是90。编号不同它们的equals结果也是false。但把他们依次放进一个“按分数排序”的TreeMap结果却是先放 A - Alice 再放 B - Bob size 1 get(A) Bob get(B) Bob排序不是应该让同分的人排在一起吗为什么反而少了一条关键在于TreeMap不只用比较结果安排顺序也用它判断键是否已经存在。比较器返回0不只是说“排名并列”还让它们成为同一个键位置上的两次写入。这篇先把这个现象跑出来再看查找分支、键的设计和范围视图。使用Amazon Corretto17.0.12运行时17.0.127-LTS源码核对来自安装目录的lib/src.zip不在这里展开全部红黑树旋转与删除。1. 比较结果为0不只是“同分”定义两个不可变的学生键record Student(String id, int score) {} Student a new Student(A, 90); Student b new Student(B, 90);record生成的equals会比较两个字段因此a与b不相等。但如果只按分数比较ComparatorStudent scoreOnly Comparator.comparingInt(Student::score); TreeMapStudent, String map new TreeMap(scoreOnly); map.put(a, Alice); String old map.put(b, Bob);本轮观察如下检查结果a.equals(b)falsescoreOnly.compare(a,b)0第二次put返回值oldAlicemap.size()1get(a)、get(b)都为BobfirstKey()是否仍为原a对象是本轮实现的对象身份检查不是TreeMap随机丢了学生B而是比较器把A与B划进了同一个键等价类。第二次put命中已有条目更新它的value本轮实现保留原节点中的key没有把原a对象换成b。图故意把key与value分成两格看第二次来的B让比较器返回0所以更新value却没有在本轮实现里把原key对象换成B。这里不画红黑树形状、颜色或旋转避免把比较器的问题误看成平衡过程的问题。这不只影响put。接着检查containsKey(b)结果是true再执行remove(b)返回Bob整个map变空了。虽然节点里保留的是ab仍然能查询和删除它因为这些操作都沿同一套比较规则定位条目。所以调试这类问题不能只问“equals是不是写错了”还要直接看compare(a, b)是否为0。2. 回到搜索树三条分支分别意味着什么旧稿用“小于往左、大于往右、等于更新”理解查找这是很好的入口。但这里的“等于”必须说明依据不是自动调用equals而是compareTo或比较器返回0。本轮源码的put(key,value)进入内部put方法比较器路径重复做下面的判断。以下是逻辑提要不是完整源码cmp comparator.compare(待插入键, 当前节点键) cmp 0进入左子树 cmp 0进入右子树 cmp 0找到已有条目更新value并返回旧值 走到空位置新增节点再进行平衡维护自然顺序路径用compareTo作判断带比较器的查询沿getEntryUsingComparator也使用同样的三分支。因此“put把两人当同一个键get却能靠equals分开”并不存在。从TreeMap中观察到的“左右”按比较器的大小关系定义不一定是数字大小。如果比较器是降序不能继续拿自然升序的直觉解释每个左右分支。这一步比先背旋转情况更值得明确平衡树保证查找路径不至于过长比较规则则决定查找的目标究竟是什么。3. 补上编号但别只为了不覆盖乱加条件如果这个业务的键就是“编号与分数这一对信息”可以先比分数再比编号ComparatorStudent distinct Comparator.comparingInt(Student::score) .thenComparing(Student::id);本轮a与b都会保留同分时编号A排在B之前。这里Student只有id与score两个字段本例id均非null在这个非null编号的定义域内比较结果为0与record的equals保持一致。不要把这个写成任何业务的通用学生主键如果编号才是稳定身份、分数是会变的属性更自然的设计往往是用编号作key把分数放进value按分数看榜单是另一个索引或排序问题。比较器的一致性、反对称与传递性要求见Comparator契约。故意让compare与equals不一致会偏离通常Map的等价约定不能把覆盖现象当成推荐技巧。还要避免用a - b比较整数。附录里Integer.MIN_VALUE - Integer.MAX_VALUE溢出后得到正数符号与大小关系相反Integer.compare则返回正确方向。较小的整数样例很可能发现不了这个错误。4. 为什么有序映射能回答“附近的键”前面的问题是“两个键是否会被当作同一个”。如果没有相等的键呢搜索树每次比较都能判断目标该往左还是往右找没有精确命中时还可以寻找符合方向的边界候选。所以同一套比较规则不仅决定是否覆盖也决定“不大于这个键的最后一个是谁”“一个区间从哪里到哪里”。下面不是另背一份API清单而是沿着已有顺序继续问这些问题。找到范围后再检查它是一份副本还是共享视图。再换成自然升序键10、20、30、40区别几种查询查询含义本轮结果floorKey(25)不大于25的最大键20ceilingKey(25)不小于25的最小键30lowerKey(20)严格小于20的最大键10higherKey(20)严格大于20的最小键30这个例子中的floorKey(5)和ceilingKey(50)都返回null没有符合方向的候选不是自动返回最近的端点。上表按自然升序写换比较器后“大于”“小于”也按该比较规则解释。范围还能写成subMap(20,true,40,false)得到包含20、不包含40的视图。本轮初始键为20、30。这里有两件不同的事比较规则决定哪些键属于这个范围视图则决定结果是否仍与原容器共享数据。“看到了一个子范围”不能自动理解成“得到了一份新数据”。视图不是复制在视图里改20的value原map也变化在原map里新增25视图立即能看到25从视图删除30原map的30也被删除。试图通过这个视图插入40会抛IllegalArgumentException因为40是被排除的上界。需要独立快照时应明确创建新容器而不是把“获取范围”当成“复制数据”。范围视图也不提供并发隔离保证。5. 从“少了一个学生”再往回看只按分数比较TreeMap并没有忘记一次插入而是把两个人判成了同一个键位置。因此查找和删除也会按这套规则命中它不能指望get再用equals把两个人分开。设计键时先问什么才是业务身份再决定比较规则。范围查询沿这个顺序找边界但范围视图是否共享数据又是另一个问题。把“比较相等”“属于范围”“得到副本”分开就不会把几个看似相近的结果混成同一件事。附录一验证不只看size更要看留了谁附录检查自然/逆序、比较为0的覆盖、旧值返回、两个键的查询、原键对象身份、加编号后两条都在、范围边界与双向联动还检查默认自然顺序拒绝null以及显式nullsFirst比较器允许这个样本中的null。原键保留用检查对象身份不只用equalskeySet复制为列表检查顺序视图写入后反查原map确认不是副本。检查使用显式AssertionError不依赖Java默认关闭的assert。测试是固定小样本不是红黑树完整正确性证明。它没有覆盖所有旋转、删除、可变键或并发但可以明确区分“排序正确”“唯一性符合业务”和“范围数据是否共享”三件事。附录二和其他Map相比顺序依据有什么不同按3、1、2依次插入整数键比较三个容器容器模式顺序依据本例应如何理解HashMap不承诺遍历顺序不能依赖插入先后LinkedHashMap默认模式插入先后3、1、2TreeMap默认模式键的自然顺序1、2、3TreeMap默认用键的自然顺序传入比较器后按比较器定义的顺序。例如Comparator.reverseOrder()在这个整数样本中得到3、2、1。get(1)不会让它像访问顺序LinkedHashMap那样把1移到最后。TreeMap是红黑树实现的有序映射不是HashMap外面套一个排序后的列表。红黑树维持平衡避免普通搜索树因不利插入顺序退化成很长的链但平衡解决的是路径长度问题不能替你修正错误的比较规则。官方对get、put、remove、containsKey给出对数时间保证下面的实验不测耗时也不从三条记录推算复杂度。Java17 TreeMap文档附录三完整可运行源码需要JDK17将下面程序命名为TreeOrderLab.java在新建目录运行javac -encoding UTF-8 TreeOrderLab.java java TreeOrderLab无需第三方库或网络。每项检查打印PASS出错时异常退出。本轮实际输出节选如下其余PASS行省略runtime17.0.127-LTS PASS natural order [1, 2, 3] PASS score-only size is one PASS score plus id retains both PASS half-open view [20, 30] PASS parent updates view [20, 25, 30] PASS view rejects excluded endpoint CHECKS_PASSED28我还单独删去修正比较器中的.thenComparing(Student::id)重新编译并运行。错误版本在score plus id retains both处触发AssertionError这确认测试会发现“以为保留了两人实际仍按分数合并”的错误而不是只检查程序能启动。import java.util.*; public class TreeOrderLab { record Student(String id, int score) {} private static int checks; private static void check(String label, boolean ok) { if (!ok) throw new AssertionError(label); checks; System.out.println(PASS label); } private static K void keys(String label, MapK, ? map, ListK expected) { ListK actual new ArrayList(map.keySet()); check(label actual, actual.equals(expected)); } public static void main(String[] args) { System.out.println(runtime System.getProperty(java.runtime.version)); TreeMapInteger, String natural new TreeMap(); natural.put(3, three); natural.put(1, one); natural.put(2, two); keys(natural order, natural, List.of(1, 2, 3)); natural.get(1); keys(get does not reorder, natural, List.of(1, 2, 3)); TreeMapInteger, String reverse new TreeMap(Comparator.reverseOrder()); reverse.putAll(natural); keys(reverse order, reverse, List.of(3, 2, 1)); Student a new Student(A, 90), b new Student(B, 90); check(distinct students are not equals, !a.equals(b)); ComparatorStudent scoreOnly Comparator.comparingInt(Student::score); check(score comparator returns zero, scoreOnly.compare(a, b) 0); TreeMapStudent, String collapsed new TreeMap(scoreOnly); collapsed.put(a, Alice); check(second put returns old value, Alice.equals(collapsed.put(b, Bob))); check(score-only size is one, collapsed.size() 1); check(both lookups find Bob, Bob.equals(collapsed.get(a)) Bob.equals(collapsed.get(b))); check(original key retained in this runtime, collapsed.firstKey() a); check(equivalent key is contained, collapsed.containsKey(b)); check(removing equivalent key removes mapping, Bob.equals(collapsed.remove(b)) collapsed.isEmpty()); ComparatorStudent distinct Comparator.comparingInt(Student::score) .thenComparing(Student::id); TreeMapStudent, String retained new TreeMap(distinct); retained.put(a, Alice); retained.put(b, Bob); check(score plus id retains both, retained.size() 2); keys(equal-score tie order, retained, List.of(a, b)); check(distinct values retained, Alice.equals(retained.get(a)) Bob.equals(retained.get(b))); TreeMapInteger, String range new TreeMap(); for (int key : List.of(10, 20, 30, 40)) range.put(key, v key); check(floor(25)20, Objects.equals(range.floorKey(25), 20)); check(ceiling(25)30, Objects.equals(range.ceilingKey(25), 30)); check(lower(20)10, Objects.equals(range.lowerKey(20), 10)); check(higher(20)30, Objects.equals(range.higherKey(20), 30)); check(no lower or higher candidate, range.floorKey(5) null range.ceilingKey(50) null); NavigableMapInteger, String view range.subMap(20, true, 40, false); keys(half-open view, view, List.of(20, 30)); view.put(20, changed); check(view updates parent, changed.equals(range.get(20))); range.put(25, new); keys(parent updates view, view, List.of(20, 25, 30)); view.remove(30); check(view removal updates parent, !range.containsKey(30)); boolean outside false; try { view.put(40, outside); } catch (IllegalArgumentException expected) { outside true; } check(view rejects excluded endpoint, outside); boolean nullRejected false; try { natural.put(null, null); } catch (NullPointerException expected) { nullRejected true; } check(natural order rejects null, nullRejected); TreeMapInteger, String nullable new TreeMap(Comparator.nullsFirst(Comparator.naturalOrder())); nullable.put(1, one); nullable.put(null, null); keys(explicit null order, nullable, Arrays.asList(null, 1)); int low Integer.MIN_VALUE, high Integer.MAX_VALUE; check(subtraction overflows to wrong sign, (low - high) 0); check(Integer.compare gives correct sign, Integer.compare(low, high) 0); System.out.println(CHECKS_PASSED checks); } }