JAVA集合：TreeMap
本篇内容包括：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 的特点：
- TreeMap 是有序的 key-value 集合，通过红黑树实现。根据键的自然顺序进行排序或根据提供的 Comparator 进行排序。
- TreeMap 继承了 AbstractMap，实现了 NavigableMap 接口，支持一系列的导航方法，给定具体搜索目标，可以返回最接近的匹配项。如
floorEntry()、ceilingEntry()分别返回小于等于、大于等于给定键关联的Map.Entry()对象，不存在则返回 null。lowerKey()、floorKey、ceilingKey、higherKey()只返回关联的key。
二、红黑树回顾
红⿊树和 AVL 树 类似，都是在进⾏插⼊和删除时通过旋转保持⾃身平衡，从⽽获得较⾼的查找性能。与 AVL 树 相⽐，红⿊树不追求所有递归⼦树的⾼度差不超过 1，保证从根节点到叶尾的最⻓路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。
红⿊树通过重新着⾊和左右旋转，更加⾼效地完成了插⼊和删除之后的⾃平衡调整。红⿊树在本质上还是⼆叉查找树，它额外引⼊了 5 个约束条件： ① 节点只能是红⾊或⿊⾊。 ② 根节点必须是⿊⾊。 ③ 所有 NIL 节点都是⿊⾊的。 ④ ⼀条路径上不能出现相邻的两个红⾊节点。 ⑤ 在任何递归⼦树中，根节点到叶⼦节点的所有路径上包含相同数⽬的⿊⾊节点。
这五个约束条件保证了红⿊树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果⼀个树的左⼦节点或右⼦节点不存在，则均认定为⿊⾊。红⿊树的任何旋转在 3 次之内均可完成。
三、TreeMap 的使用
1、构造方法
方法名 | 方法说明 | 方法名 | 方法说明 |
|---|---|---|---|
public TreeMap() | 创建一个空TreeMap，keys按照自然排序 | public TreeMap(Comparator comparator) | 创建一个空TreeMap，按照指定的comparator排序 |
public TreeMap(Map m) | 由给定的map创建一个TreeMap，keys按照自然排序 | public TreeMap(SortedMap m) | 由给定的有序map创建TreeMap，keys按照原顺序排序 |
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的第一个（最小的）映射的keyMap.Entry<K, V> lastEntry()：返回该TreeMap的最后一个（最大的）映射K lastKey()：返回该TreeMap的最后一个（最大的）映射的keyv get(K key)：返回指定key对应的valueSortedMap<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，若为自然排序则返回nullint size()：返回该TreepMap中包含的映射的数量