企业官网建设流程全解析

1. 从一个真实的数据统计需求说起

去年帮一个做电商的朋友处理订单数据时，遇到一个挺典型的问题：他们需要统计每个商品在一天内的被下单次数，并且要按商品ID排序输出。第一反应是用TreeMap<Long, Integer>，key 是商品ID，value 是次数。但很快就发现不对劲——同一个商品ID在一天内可能被下单多次，每次都要先get再put，代码写起来啰嗦不说，还容易在并发场景下出问题。

后来想，要是有一个既能自动排序、又能存重复元素的集合就好了。TreeSet能排序但不允许重复，ArrayList能重复但不排序，PriorityQueue能排序也能重复但遍历时不保证有序。翻了一圈 JDK 源码，发现确实没有现成的TreeMultiSet。但 Google 的 Guava 库里有一个TreeMultiset，用起来相当顺手。不过 Guava 是个大依赖，如果项目里只是偶尔需要这个功能，引入整个 Guava 有点杀鸡用牛刀的意思。

于是就有了自己动手实现一个TreeMultiSet的想法。这篇文章就把整个实现过程、踩过的坑、以及实际使用中的经验完整地分享出来。如果你也遇到过"需要排序又要允许重复"的场景，或者对红黑树、TreeMap 的底层实现感兴趣，这篇内容应该能给你一些参考。我会从设计思路讲起，然后给出完整实现，最后聊聊性能表现和几个容易踩的坑。

2. 为什么JDK没有现成的TreeMultiSet

2.1 TreeSet的去重逻辑到底卡在哪

要理解为什么需要自己实现TreeMultiSet，得先搞清楚TreeSet为什么不允许重复元素。TreeSet底层是基于TreeMap实现的，每次添加元素时，实际上是把元素作为TreeMap的 key，value 统一放一个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手动计数的三个痛点

那直接用TreeMap<E, 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 类结构与字段设计

先看整体结构。TreeMultiSet<E>实现Iterable<E>接口，内部持有一个TreeMap<E, Integer>作为计数器，以及一个int类型的size字段记录总元素个数（包括重复）。

public class TreeMultiSet<E> implements Iterable<E> { private final TreeMap<E, 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方法直接返回计数，不存在返回 0：

public 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 Iterator<E> iterator() { return new Iterator<E>() { private final Iterator<Map.Entry<E, Integer>> entryIter = countMap.entrySet().iterator(); private Map.Entry<E, 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 TreeMultiSet<E> subSet(E fromElement, E toElement) { TreeMultiSet<E> result = new TreeMultiSet<>(comparator); for (Map.Entry<E, 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和TreeMap<E, Integer>插入 100 万个随机整数（范围 0 到 10 万，所以有大量重复），记录耗时。

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); // 抛异常 } }

正确做法是用迭代器遍历，或者先收集要删除的元素再统一删除：

// 正确用法：先收集再删除 List<Integer> 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包装所有修改方法，或者用ConcurrentHashMap+AtomicInteger替代TreeMap。但后者会失去排序特性，需要额外维护一个有序结构。如果确实需要并发场景下的有序多集，建议直接用 Guava 的ConcurrentHashMultiset加排序，或者用ConcurrentSkipListMap替代TreeMap。

5.4 自定义Comparator时的等价性陷阱

最后一个坑比较隐蔽：当使用自定义Comparator时，TreeMap判断 key 是否相等用的是Comparator.compare() == 0，而不是equals()。这意味着如果Comparator认为两个元素相等但equals()返回false，TreeMultiSet会把它们当成同一个元素计数。

// 按字符串长度排序的Comparator Comparator<String> byLength = Comparator.comparingInt(String::length); TreeMultiSet<String> 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 排行榜中的同分并列处理

做排行榜时经常遇到同分的情况。比如游戏得分排行榜，多个玩家可能分数相同。用TreeMultiSet<Integer>存储分数，count(score)就能快速知道有多少人得了这个分数，subSet(minScore, maxScore)可以快速筛选分数段。比用List排序再遍历要高效得多。

6.2 词频统计与TopK查询

文本处理中的词频统计是TreeMultiSet的经典场景。把每个词add进去，count(word)就是词频。如果要找 TopK 高频词，可以遍历countMap的 entrySet，用优先队列维护前 K 个。因为TreeMultiSet本身是有序的，遍历时按字典序输出，结果很稳定。

6.3 时间窗口内的重复事件检测

监控系统中，经常需要检测"某个事件在 5 分钟内出现了多少次"。可以把事件时间戳作为 key 存入TreeMultiSet<Long>，用subSet(now - 300000, now)快速获取时间窗口内的所有事件，size()就是事件总数。因为TreeMultiSet支持重复元素，同一个时间戳的多个事件也能正确计数。

6.4 与TreeSet组合使用的混合策略

有时候既需要去重又需要计数。比如统计 UV（独立访客）和 PV（页面浏览量）。可以用TreeSet<String>存 UV，用TreeMultiSet<String>存 PV。两者共享同一份数据源，但提供不同的视图。这种组合策略在实际项目中很常见，比用两个HashMap更省内存，而且天然有序。

7. 写在最后的一些个人体会

实现这个TreeMultiSet的过程中，最大的收获不是代码本身，而是对 JDK 集合框架设计思路的理解。TreeSet和TreeMap的关系、Comparator与equals的语义差异、fail-fast 迭代器的设计取舍，这些细节在平时用集合时很少关注，但自己动手实现一遍就全明白了。

另外一点体会是：不要过度设计。我一开始想支持视图、支持并发、支持序列化，结果代码越写越复杂，bug 也越来越多。后来砍掉了这些高级功能，只保留最核心的 add/remove/count/iterator，代码量控制在 200 行以内，反而更稳定、更好维护。如果确实需要高级功能，直接用 Guava 的TreeMultiset就好，没必要重复造轮子。

最后分享一个小技巧：如果你只需要计数不需要排序，用HashMap<E, Integer>就够了，性能比TreeMap好很多（O(1) vs O(log n)）。只有在确实需要按 key 排序的场景下，才值得用TreeMultiSet。这个选择标准在实际项目中帮我省了不少性能优化的功夫。