安卓开发中树形数据结构的选择：TreeMap、TreeSet及性能对比
近期趋势：树形数据在安卓开发中的回归
随着安卓应用处理的数据规模持续增长，有序、可排序的数据结构需求再次受到关注。尤其是涉及实时排序、范围查询或日志类数据聚合的场景，树形结构的稳定性和可预测性优势逐渐凸显。TreeMap与TreeSet作为Java集合框架中的红黑树实现，在安卓平台上依然保持着稳定的使用比例。近期社区讨论集中在“避免不必要的排序开销”和“内存占用与GC压力的平衡”上。
行业背景：从列表到树的演进逻辑
安卓开发早期，ArrayList与HashMap几乎统治了所有存储需求。但面对以下三类场景时，线性结构或哈希结构的局限性暴露出来：
- 需要随时保持元素有序（例如排行榜、定时任务队列）
- 频繁进行范围查找或前驱/后继访问（如日历事件、区间合并）
- 要求顺序迭代且插入删除操作稳定（日志分析器、消息中间缓存）
此时，TreeMap（键值对有序映射）与TreeSet（元素不可重复有序集合）成为天然候选。它们基于红黑树实现，插入、删除、查找的时间复杂度稳定在O(log n)，且天然支持升序或定制排序。
用户关注点：TreeMap vs TreeSet 到底怎么选
开发者在实际项目中往往面对以下判断维度：
1. 存储结构需求不同
- TreeMap：适用于需要根据key快速查找对应value，且key需要排序的场景。例如用户ID与积分的映射，并按照积分降序获取前10名。
- TreeSet：更关注元素本身的有序唯一性，不关心value。例如用自定义时间戳对象去重并按时间排序。
2. 性能对比要点
| 操作 | TreeMap | TreeSet（内部实际使用TreeMap实现） | 说明 |
|---|---|---|---|
| 插入/删除 | O(log n) | O(log n) | 红黑树自平衡，大量元素后仍稳定 |
| 查找 | O(log n) | O(log n) | 两者内部均使用导航查找 |
| 遍历顺序 | 按key自然顺序或Comparator | 按元素自然顺序或Comparator | 中序遍历，相对稳定 |
| 内存开销 | 较高（Entry含key+value+左右子节点+颜色+父节点引用） | 较低（内部使用TreeMap的底层Entry，但只存储元素作为key，value为固定对象） | TreeMap大约比HashMap多出约40字节/元素（视JVM实现略有差异） |
值得注意：TreeSet在安卓中实际是包装了TreeMap，以元素作为key，value为常量PRESENT对象。因此性能特征与TreeMap高度相似，但遍历时只输出key，内存占用略小于同等数据规模的TreeMap。
3. 对比其他有序结构
- 与ArrayList+Collections.sort对比：如果元素变动不频繁，使用ArrayList再手动排序可能更快（O(n log n)但常数更小）。但插入频繁时，ArrayList的O(n)插入成为瓶颈，而树结构稳定O(log n)。
- 与LinkedHashMap对比：LinkedHashMap只保留插入顺序或访问顺序，不支持自然排序或自定义排序。若需按值排序，无法直接满足需求。
- 与ConcurrentSkipListMap对比：后者是跳表实现，适用于并发环境，但在单线程安卓场景下，TreeMap因常数更小通常更快。
可能影响：谨慎使用才能避免坑
引入树形数据结构会带来以下潜在影响：
- GC压力增大：每次插入删除产生新的Entry对象，在大量频繁操作时可能触发更多GC。建议批量操作时先收集到临时ArrayList，再一次性构建TreeMap。
- 排序时自定义Comparable/Comparator的效能：比较函数每次分裂节点时都会被调用，如果比较逻辑复杂（例如嵌套字段访问、字符串比较），会显著拖慢操作。推荐先对比较键预处理，或使用数值型键。
- 非线程安全：安卓主线程操作集合虽常见，但如果任务线程中共享TreeMap/TreeSet，需手动加锁或使用同步包装，否则ConcurrentModificationException风险较高。
一个典型反例：某外卖应用在订单列表中使用TreeSet按距离排序，每次收到新订单直接add，随着订单量增长出现停顿。优化后改为先累积批量再重建TreeSet，GC次数下降约30%。
后续观察：替代方案与演进方向
未来安卓开发中，树形数据结构的地位可能受到以下因素影响：
- Kotlin标准库的增强：Kotlin原生的排序集合（如sortedSetOf）依然基于Java TreeSet，但提供了更简洁的lambda排序，调参更灵活。
- Jetpack Compose对数据流的反应式需求：不可变数据流行，可能需要每次都创建新的TreeMap副本，这时of()静态工厂方法+builders的效能需要评估。
- 大数据量下的替代方案：当元素数超过十万级别，红黑树的缓存不友好性开始显现，可考虑外部排序或使用数据库内建索引。
- 直接使用Room数据库的有序查询：如果数据持久化，直接用ORDER BY比内存排序更可靠，TreeMap可降级为简单缓存。
总结而言，TreeMap与TreeSet在安卓开发中仍是“有序且高效”的可靠选择，但务必根据插入频率、排序开销与内存限制综合评估。对于简单排序列表，优先考虑ArrayList+Collections.sort；对于频繁动态维护的有序集合，才推荐引入红黑树结构。