JAVA集合：TreeMap

朴灿烈づ我的快乐病毒、 2023-09-24 07:38 141阅读 0赞

> 本篇内容包括：TreeMap 概述、红黑树回顾以及 HashMap 的使用。

## 一、TreeMap 概述 ##

> Map 在 Java 里面分为两种：HashMap 和 TreeMap，区别就是 TreeMap 有序，HashMap 无序。如果只需要存映射，那么 HashMap 就够了，但是如果需要存有顺序的 key 那么就用 TreeMap。
> 
> 写程序需要知道怎么构建 comparator 去自定义排序，还要知道 floorKey 和 floorEntry。

TreeMap 存储 K-V 键值对，通过红黑树（R-B tree）实现。TreeMap 继承了 NavigableMap 接口，NavigableMap 接口继承了 SortedMap 接口，可支持一系列的导航定位以及导航操作的方法，当然只是提供了接口，需要 TreeMap 自己去实现；TreeMap 实现了 Cloneable 接口，可被克隆，实现了 Serializable 接口，可序列化；TreeMap 因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过 Key 值的自然顺序进行排序。

TreeMap 是一个能比较元素大小的 Map 集合，会对传入的 key 进行了大小排序。可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序。

TreeMap 的特点：

1.  TreeMap 是有序的 key-value 集合，通过红黑树实现。根据键的自然顺序进行排序或根据提供的 Comparator 进行排序。
2.  TreeMap 继承了 AbstractMap，实现了 NavigableMap 接口，支持一系列的导航方法，给定具体搜索目标，可以返回最接近的匹配项。如 `floorEntry()`、`ceilingEntry()` 分别返回小于等于、大于等于给定键关联的 `Map.Entry()` 对象，不存在则返回 null。`lowerKey()`、`floorKey`、`ceilingKey`、`higherKey()`只返回关联的key。

--------------------

## 二、红黑树回顾 ##

红⿊树和 AVL 树 类似，都是在进⾏插⼊和删除时通过旋转保持⾃身平衡，从⽽获得较⾼的查找性能。与 AVL 树 相⽐，红⿊树不追求所有递归⼦树的⾼度差不超过 1，保证从根节点到叶尾的最⻓路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。

![JAVA_TreeMap-_1.png][]

红⿊树通过重新着⾊和左右旋转，更加⾼效地完成了插⼊和删除之后的⾃平衡调整。红⿊树在本质上还是⼆叉查找树，它额外引⼊了 5 个约束条件： ① 节点只能是红⾊或⿊⾊。 ② 根节点必须是⿊⾊。 ③ 所有 NIL 节点都是⿊⾊的。 ④ ⼀条路径上不能出现相邻的两个红⾊节点。 ⑤ 在任何递归⼦树中，根节点到叶⼦节点的所有路径上包含相同数⽬的⿊⾊节点。

这五个约束条件保证了红⿊树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果⼀个树的左⼦节点或右⼦节点不存在，则均认定为⿊⾊。红⿊树的任何旋转在 3 次之内均可完成。

--------------------

## 三、TreeMap 的使用 ##

#### 1、构造方法 ####

<table> 
 <thead> 
  <tr> 
   <th align="center">方法名</th> 
   <th align="center">方法说明</th> 
   <th align="center">方法名</th> 
   <th align="center">方法说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center"><code> public TreeMap()</code></td> 
   <td align="center">创建一个空TreeMap，keys按照自然排序</td> 
   <td align="center"><code>public TreeMap(Comparator comparator)</code></td> 
   <td align="center">创建一个空TreeMap，按照指定的comparator排序</td> 
  </tr> 
  <tr> 
   <td align="center"><code>public TreeMap(Map m)</code></td> 
   <td align="center">由给定的map创建一个TreeMap，keys按照自然排序</td> 
   <td align="center"><code>public TreeMap(SortedMap m)</code></td> 
   <td align="center">由给定的有序map创建TreeMap，keys按照原顺序排序</td> 
  </tr> 
 </tbody> 
</table>

#### 2、常用方法-增添元素 ####

*  `V put(K key, V value)`：将指定映射放入该TreeMap中
 *  `V putAll(Map map)`：将指定map放入该TreeMap中

#### 3、常用方法-删除元素 ####

*  `void clear()`：清空TreeMap中的所有元素
 *  `V remove(Object key)`：从TreeMap中移除指定key对应的映射

#### 4、常用方法-修改元素 ####

*  `V replace(K key, V value)`：替换指定key对应的value值
 *  `boolean replace(K key, V oldValue, V newValue)`：当指定key的对应的value为指定值时，替换该值为新值

#### 5、常用方法-查找元素 ####

*  `boolean containsKey(Object key)`：判断该TreeMap中是否包含指定key的映射
 *  `boolean containsValue(Object value)`：判断该TreeMap中是否包含有关指定value的映射
 *  `Map.Entry<K, V> firstEntry()`：返回该TreeMap的第一个（最小的）映射
 *  `K firstKey()`：返回该TreeMap的第一个（最小的）映射的key
 *  `Map.Entry<K, V> lastEntry()`：返回该TreeMap的最后一个（最大的）映射
 *  `K lastKey()`：返回该TreeMap的最后一个（最大的）映射的key
 *  `v get(K key)`：返回指定key对应的value
 *  `SortedMap<K, V> headMap(K toKey)`：返回该TreeMap中严格小于指定key的映射集合
 *  `SortedMap<K, V> subMap(K fromKey, K toKey)`：返回该TreeMap中指定范围的映射集合（大于等于fromKey，小于toKey）

#### 6、常用方法-遍历接口 ####

*  `Set<Map<K, V>> entrySet()`：返回由该TreeMap中的所有映射组成的Set对象
 *  `void forEach(BiConsumer<? super K,? super V> action)`：对该TreeMap中的每一个映射执行指定操作
 *  `Collection<V> values()`：返回由该TreeMap中所有的values构成的集合

#### 7、常用方法-其他方法 ####

*  `Object clone()`：返回TreeMap实例的浅拷贝
 *  `Comparator<? super K> comparator()`：返回给该TreeMap的keys排序的comparator，若为自然排序则返回null
 *  `int size()`：返回该TreepMap中包含的映射的数量

[JAVA_TreeMap-_1.png]: https://lizhengi.oss-cn-beijing.aliyuncs.com/BenjaminNode/JAVA集合：TreeMap-图1.png