JDK容器学习之TreeMap (二) : 使用说明

TreeMap 使用说明

TreeMap 的底层数据结构为红黑树，主要是根据key进行排序，相比较于HashMap的数组+链表+红黑树的数据结构而言，两者的应用场景是有明显的区别的

1. TreeMap 的优点

1. 红黑树，先天支持排序

TreeMap 根绝key进行比较排序

• 支持自定义实现的比较器
• key实现 Comparable 接口

HashMap 无排序功能

2. 存储空间少

Treemap 红黑树中一个节点对应一个kv对，没有冗余无效的Node节点

HashMap 的数组中，可能存在较多的空位

2. TreeMap 的缺点

1. 查询的时间复杂度

正常来讲，TreeMap 的查询时间复杂度为 O(logN), 而HashMap为 O(1)

所以Map的元素越多，TreeMap根据key查询的效率会更低；

另一方面，HashMap 在糟糕的情况下，可能退化为链表

2. 修改导致重排

TreeMap 每次新增or删除一个kv对，都可能导致红黑树的重排

HashMap 当新增一个kv对，使得Map中的个数大于阀值时，需要对数组进行重新扩容

3. 使用场景

通过上面的优缺点对比，可以看出TreeMap和HashMap两者的使用场景差别算是比较大的

对Map中的kv对有排序需求时，选择 TreeMap, 这种场景下，尽量保证以下几点

• Map 元素基本保持不变（即很少添加和删除）
• 主要用于遍历迭代获取数据
• 不存在碰撞的情况（即两个不同的key，根据比较器获取值不能为0）

相关博文

• JDK容器学习之HashMap (一) ： 底层存储结构分析
• JDK容器学习之HashMap (二) ： 读写逻辑详解
• JDK容器学习之HashMap (三) : 迭代器实现
• JDK容器学习之TreeMap (一) : 底层数据结构

关注更多

关注 小灰灰blog