一、TreeMap
类继承图
总体概述：
- TreeMap实现了NavigableMap（可以返回特定条件最近匹配的导航方法），而NavigableMap又继承了了SortedMap接口，这说明TreeMap是排序的
- 底层结构是红黑树，方法的时间复杂度都是log（n）
- 构造时，默认使用元素的自然顺序排序，也可以提供一个Comparator(自定义对象要重写hashCode（）和equals（）)
1.1 域
/**
* treeMap的排序规则，如果为null，则根据键的自然顺序进行排序
*
* @serial
*/
private final Comparator<? super K> comparator;
/**
* 红黑数的根节点
*/
private transient Entry<K,V> root;
/**
* 红黑树节点的个数
*/
private transient int size = 0;
/**
* treeMap的结构性修改次数。实现fast-fail机制的关键。
*/
private transient int modCount = 0;
1.2 构造方法
TreeMap()：使用key的自然排序来构造一个空的treeMap。
TreeMap(Comparator<? super K> comparator)：使用给定的比较器来构造一个空的treeMap。
TreeMap(Map<? extends K, ? extends V> m)：使用key的自然排序来将一个普通Map转换成treeMap，treeMap包含给定map中所有的键值对。
TreeMap(SortedMap<K, ? extends V> m)：使用指定的sortedMap来构造treeMap。treeMap中含有sortedMap中所有的键值对，键值对顺序和sortedMap中相同。
1.3 put（）
2019-02-27_113316.png
找到父节点的位置，新建节点，比较大小，插入
1.4 get（...）
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
2019-02-27_114706.png
2019-02-27_114905.png
1.5 remove(...)
/**
* 如果key在treeMap中存在，删除对应的节点，返回旧value，否则返回null
*
* @param key 参数key
* @return 如果节点被删除，返回节点的value，否则返回null。当然，可能key对应的value就是null
* @throws ClassCastException 如果指定参数key为null而且map使用自然排序，或者比较器不允许key为null
*/
public V remove(Object key) {
//获取key对应的节点
Entry<K,V> p = getEntry(key);
//如果节点为null，返回null
if (p == null)
return null;
//记录旧value
V oldValue = p.value;
//删除节点
deleteEntry(p);
//返回旧value
return oldValue;
}
二、总结
TreeMap底层是红黑树，能够实现排序。如果在构造函数中传入了Comparator对象，就可以根据compare（o1,o2）的规则进行排序，否则就是使用Comparable的compareTo（o1）（前提是这个类要实现了Comparable接口）
- 因为底层是红黑树，所以数据的操作时间复杂度都是O(logn)
- TreeMap非同步的，想要同步可以使用Collections来进行封装
- 想要自定义比较就要传入重写compare的Comparator的对象，否则就是自然排序（自定义类也要实现Comparable接口）
- key不能为null，但是HashMap的可以为null
image.png
参考：
网友评论