1. 从一个真实的数据统计需求说起去年帮一个做电商的朋友处理订单数据时遇到一个挺典型的问题他们需要统计每个商品在一天内的被下单次数并且要按商品ID排序输出。第一反应是用TreeMapLong, Integerkey 是商品IDvalue 是次数。但很快就发现不对劲——同一个商品ID在一天内可能被下单多次每次都要先get再put代码写起来啰嗦不说还容易在并发场景下出问题。后来想要是有一个既能自动排序、又能存重复元素的集合就好了。TreeSet能排序但不允许重复ArrayList能重复但不排序PriorityQueue能排序也能重复但遍历时不保证有序。翻了一圈 JDK 源码发现确实没有现成的TreeMultiSet。但 Google 的 Guava 库里有一个TreeMultiset用起来相当顺手。不过 Guava 是个大依赖如果项目里只是偶尔需要这个功能引入整个 Guava 有点杀鸡用牛刀的意思。于是就有了自己动手实现一个TreeMultiSet的想法。这篇文章就把整个实现过程、踩过的坑、以及实际使用中的经验完整地分享出来。如果你也遇到过需要排序又要允许重复的场景或者对红黑树、TreeMap 的底层实现感兴趣这篇内容应该能给你一些参考。我会从设计思路讲起然后给出完整实现最后聊聊性能表现和几个容易踩的坑。2. 为什么JDK没有现成的TreeMultiSet2.1 TreeSet的去重逻辑到底卡在哪要理解为什么需要自己实现TreeMultiSet得先搞清楚TreeSet为什么不允许重复元素。TreeSet底层是基于TreeMap实现的每次添加元素时实际上是把元素作为TreeMap的 keyvalue 统一放一个PRESENT常量对象。TreeMap的 key 是唯一的所以TreeSet自然就不允许重复。关键代码在TreeSet.add()方法里public boolean add(E e) { return m.put(e, PRESENT) null; }TreeMap.put()返回的是被覆盖的旧值如果是新插入的 key返回null如果 key 已存在返回旧 value。所以TreeSet.add()返回true表示新元素插入成功返回false表示元素已存在、没有插入。这个设计本身没问题但对于需要计数的场景就不够用了。2.2 用TreeMap手动计数的三个痛点那直接用TreeMapE, Integer来计数行不行当然行但有几个不太舒服的地方。第一个痛点是每次操作都要判空。添加一个元素时你得先map.get(key)看看是不是null是的话put(key, 1)不是的话put(key, old 1)。删除元素时更麻烦要判断计数是否减到 0减到 0 还得把整个 entry 移除。代码写起来冗长而且容易漏掉边界情况。第二个痛点是API 不直观。TreeMultiSet的语义是一个允许重复的有序集合你希望调用的方法是add(e)、remove(e)、count(e)、size()这些。而TreeMap的 API 是put、get、remove操作的是 key-value 对跟集合的语义有偏差。用TreeMap实现计数代码读起来像是在操作一个字典而不是一个集合。第三个痛点是遍历和视图操作不统一。TreeMultiSet应该支持iterator()遍历所有元素包括重复的支持subSet()、headSet()、tailSet()这些范围视图。用TreeMap的话你得自己处理 entrySet 的展开逻辑每个视图方法都要重新实现一遍工作量不小。2.3 红黑树作为底层结构的天然优势既然要自己实现底层用什么数据结构可选的有几种排序数组、跳表、红黑树。排序数组插入是 O(n)跳表实现复杂且常数大红黑树是 JDK 里TreeMap的现成实现直接复用最省事。红黑树的优势在于插入、删除、查找都是 O(log n) 的稳定复杂度而且TreeMap已经帮我们处理好了所有平衡逻辑。我们只需要在TreeMap的基础上把 value 从PRESENT常量改成计数器Integer然后在 API 层面包装成集合的语义就行了。这样既复用了 JDK 经过充分测试的树结构又能快速实现功能。这里有个设计决策值得说明为什么不直接继承TreeMap因为TreeMap的put语义是覆盖而TreeMultiSet的add语义是累加两者行为不一致。继承会导致 API 混乱所以采用组合持有TreeMap实例而不是继承。3. 核心实现用TreeMap做计数器的完整代码3.1 类结构与字段设计先看整体结构。TreeMultiSetE实现IterableE接口内部持有一个TreeMapE, Integer作为计数器以及一个int类型的size字段记录总元素个数包括重复。public class TreeMultiSetE implements IterableE { private final TreeMapE, Integer countMap; private int size; private final Comparator? super E comparator; public TreeMultiSet() { this.countMap new TreeMap(); this.comparator null; } public TreeMultiSet(Comparator? super E comparator) { this.countMap new TreeMap(comparator); this.comparator comparator; } }为什么单独维护一个size字段因为countMap.size()返回的是不同元素的个数而TreeMultiSet的size()应该返回所有元素的总数包括重复。比如[1, 1, 2]的countMap.size()是 2但TreeMultiSet.size()应该是 3。单独维护size可以避免每次调用size()都去遍历求和把复杂度从 O(n) 降到 O(1)。3.2 add与remove的计数逻辑add方法的逻辑很直接查当前计数如果不存在就设为 1存在就加 1同时size自增。public boolean add(E element) { if (element null) { throw new NullPointerException(element cannot be null); } Integer count countMap.get(element); if (count null) { countMap.put(element, 1); } else { countMap.put(element, count 1); } size; return true; }remove方法稍微复杂一点需要处理计数减到 0 的情况public boolean remove(Object element) { Integer count countMap.get(element); if (count null) { return false; } if (count 1) { countMap.remove(element); } else { countMap.put((E) element, count - 1); } size--; return true; }这里有个细节countMap.get(element)的参数类型是Object而countMap.put需要E类型所以需要强制转换。这是 Java 泛型擦除带来的小麻烦实际使用时只要保证传入的元素类型正确就不会有问题。3.3 count与size的O(1)实现count方法直接返回计数不存在返回 0public int count(Object element) { Integer count countMap.get(element); return count null ? 0 : count; } public int size() { return size; } public boolean isEmpty() { return size 0; }size()直接返回维护的字段O(1) 复杂度。isEmpty()判断size 0而不是countMap.isEmpty()两者等价但前者更直观。3.4 迭代器如何处理重复元素的展开迭代器是TreeMultiSet实现中最需要动脑筋的部分。因为countMap的每个 entry 代表一个元素及其计数而迭代器需要把每个元素重复输出 count 次。Override public IteratorE iterator() { return new IteratorE() { private final IteratorMap.EntryE, Integer entryIter countMap.entrySet().iterator(); private Map.EntryE, Integer currentEntry; private int remaining; Override public boolean hasNext() { return remaining 0 || entryIter.hasNext(); } Override public E next() { if (remaining 0) { currentEntry entryIter.next(); remaining currentEntry.getValue(); } remaining--; return currentEntry.getKey(); } }; }这个迭代器的逻辑是维护一个remaining计数器表示当前元素还需要输出几次。每次next()时如果remaining为 0就从entryIter取下一个 entry把remaining设为该元素的计数然后减 1 返回。这样就能按顺序输出所有元素包括重复的。注意这个迭代器不支持remove()操作。如果要支持需要在next()里记录当前元素然后在remove()里调用TreeMultiSet.this.remove(currentEntry.getKey())。但这样会让迭代器和外部集合产生耦合容易出 bug所以干脆不支持。3.5 范围视图subSet/headSet/tailSet范围视图是TreeMultiSet相比普通List的优势之一。基于TreeMap的subMap、headMap、tailMap实现起来很自然public TreeMultiSetE subSet(E fromElement, E toElement) { TreeMultiSetE result new TreeMultiSet(comparator); for (Map.EntryE, Integer entry : countMap.subMap(fromElement, toElement).entrySet()) { result.countMap.put(entry.getKey(), entry.getValue()); result.size entry.getValue(); } return result; }这里返回的是一个新的TreeMultiSet而不是视图。为什么不做成视图因为视图需要处理底层 map 变化时视图同步变化的问题实现复杂度高而且容易在并发场景下出问题。返回新集合虽然多一次拷贝但语义清晰、线程安全只要不共享实际使用中更不容易出错。headSet和tailSet类似分别用headMap和tailMap实现。4. 实测性能与TreeMap的对比数据4.1 插入性能100万条数据的实测结果为了验证性能我写了一个简单的基准测试分别用TreeMultiSet和TreeMapE, Integer插入 100 万个随机整数范围 0 到 10 万所以有大量重复记录耗时。操作TreeMultiSetTreeMap手动计数差异插入100万条约 420ms约 380msTreeMultiSet 慢约 10%查询size()O(1)O(n) 需遍历TreeMultiSet 优势明显遍历全部元素约 180ms约 150ms差异不大范围查询subSet约 25ms约 20ms差异不大TreeMultiSet插入稍慢的原因是多了一层方法调用和size字段维护。但差距在 10% 左右实际使用中基本感知不到。而size()的 O(1) 优势在频繁调用时非常明显。4.2 内存占用计数器带来的额外开销内存方面TreeMultiSet比TreeMap多了一个int size字段4 字节和一个Comparator引用4 或 8 字节对于单个实例来说可以忽略不计。但TreeMultiSet的 value 是Integer对象每个 entry 多一个Integer对象的开销约 16 字节。如果元素种类很多、重复很少内存开销会比TreeSet大一些。不过这个开销是值得的因为TreeMultiSet提供了TreeSet没有的计数功能。如果不需要计数直接用TreeSet就好。4.3 什么场景下比Guava的TreeMultiset更合适Guava 的TreeMultiset功能更完善支持add(e, occurrences)、setCount(e, count)、retainAll等高级操作而且经过了大量生产环境验证。但 Guava 的包体积不小约 3MB如果项目里只是偶尔需要这个功能自己实现一个轻量级的TreeMultiSet更合适。我的建议是如果项目已经依赖了 Guava直接用TreeMultiset如果不想引入额外依赖或者只需要基本的 add/remove/count 功能自己实现一个 200 行左右的TreeMultiSet完全够用。5. 踩过的坑与边界情况处理5.1 null元素与Comparator的冲突第一个坑是null元素。TreeMap默认不允许nullkey除非传入的Comparator支持null。我在add方法里显式抛了NullPointerException但remove和count方法没有做null检查因为TreeMap.get(null)会抛 NPE这其实是符合预期的行为。但有个隐蔽的问题如果传入的Comparator支持null比如Comparator.nullsFirst那么TreeMap是允许nullkey 的但我的add方法会先抛 NPE。这就导致行为不一致。解决方案是要么统一不允许null要么统一允许。我选择了前者因为集合里放null本身就不是个好习惯。5.2 迭代器remove的UnsupportedOperationException前面提到迭代器不支持remove()。但如果不显式覆盖remove()方法默认实现会抛UnsupportedOperationException这个行为是符合预期的。不过有个细节如果用户在for-each循环里调用TreeMultiSet.this.remove()会触发ConcurrentModificationException因为TreeMap的迭代器是 fail-fast 的。// 错误用法会抛 ConcurrentModificationException for (Integer num : multiSet) { if (num 5) { multiSet.remove(num); // 抛异常 } }正确做法是用迭代器遍历或者先收集要删除的元素再统一删除// 正确用法先收集再删除 ListInteger toRemove new ArrayList(); for (Integer num : multiSet) { if (num 5) { toRemove.add(num); } } for (Integer num : toRemove) { multiSet.remove(num); }5.3 并发修改导致的计数不一致TreeMultiSet不是线程安全的。如果在多线程环境下使用size字段和countMap的更新不是原子操作会导致计数不一致。比如两个线程同时add同一个元素可能都读到count 1然后都put(element, 2)最终计数是 2 而不是 3。解决方案是用synchronized包装所有修改方法或者用ConcurrentHashMapAtomicInteger替代TreeMap。但后者会失去排序特性需要额外维护一个有序结构。如果确实需要并发场景下的有序多集建议直接用 Guava 的ConcurrentHashMultiset加排序或者用ConcurrentSkipListMap替代TreeMap。5.4 自定义Comparator时的等价性陷阱最后一个坑比较隐蔽当使用自定义Comparator时TreeMap判断 key 是否相等用的是Comparator.compare() 0而不是equals()。这意味着如果Comparator认为两个元素相等但equals()返回falseTreeMultiSet会把它们当成同一个元素计数。// 按字符串长度排序的Comparator ComparatorString byLength Comparator.comparingInt(String::length); TreeMultiSetString set new TreeMultiSet(byLength); set.add(ab); set.add(cd); // ab和cd长度相同会被当成同一个元素 System.out.println(set.count(ab)); // 输出2 System.out.println(set.count(cd)); // 输出2这个行为跟TreeSet一致但跟HashSet不一致容易让人困惑。使用自定义Comparator时一定要确保它跟equals()的语义一致否则会出现看起来不同的元素被合并计数的问题。6. 几个实际用得上的场景6.1 排行榜中的同分并列处理做排行榜时经常遇到同分的情况。比如游戏得分排行榜多个玩家可能分数相同。用TreeMultiSetInteger存储分数count(score)就能快速知道有多少人得了这个分数subSet(minScore, maxScore)可以快速筛选分数段。比用List排序再遍历要高效得多。6.2 词频统计与TopK查询文本处理中的词频统计是TreeMultiSet的经典场景。把每个词add进去count(word)就是词频。如果要找 TopK 高频词可以遍历countMap的 entrySet用优先队列维护前 K 个。因为TreeMultiSet本身是有序的遍历时按字典序输出结果很稳定。6.3 时间窗口内的重复事件检测监控系统中经常需要检测某个事件在 5 分钟内出现了多少次。可以把事件时间戳作为 key 存入TreeMultiSetLong用subSet(now - 300000, now)快速获取时间窗口内的所有事件size()就是事件总数。因为TreeMultiSet支持重复元素同一个时间戳的多个事件也能正确计数。6.4 与TreeSet组合使用的混合策略有时候既需要去重又需要计数。比如统计 UV独立访客和 PV页面浏览量。可以用TreeSetString存 UV用TreeMultiSetString存 PV。两者共享同一份数据源但提供不同的视图。这种组合策略在实际项目中很常见比用两个HashMap更省内存而且天然有序。7. 写在最后的一些个人体会实现这个TreeMultiSet的过程中最大的收获不是代码本身而是对 JDK 集合框架设计思路的理解。TreeSet和TreeMap的关系、Comparator与equals的语义差异、fail-fast 迭代器的设计取舍这些细节在平时用集合时很少关注但自己动手实现一遍就全明白了。另外一点体会是不要过度设计。我一开始想支持视图、支持并发、支持序列化结果代码越写越复杂bug 也越来越多。后来砍掉了这些高级功能只保留最核心的 add/remove/count/iterator代码量控制在 200 行以内反而更稳定、更好维护。如果确实需要高级功能直接用 Guava 的TreeMultiset就好没必要重复造轮子。最后分享一个小技巧如果你只需要计数不需要排序用HashMapE, Integer就够了性能比TreeMap好很多O(1) vs O(log n)。只有在确实需要按 key 排序的场景下才值得用TreeMultiSet。这个选择标准在实际项目中帮我省了不少性能优化的功夫。