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)