前言
本文使用用的是jdk1.8
TreeMap
- 基于红黑树的NavigableMap的实现。
- TreeMap实现了NavigableMap接口，而NavigableMap接口继承着SortedMap接口，致使我们的TreeMap符合SotredMap接口的定义。TreeMap根据key自然顺序进行排序，或者在构造实例构造的时候传递 Comparator 进行自定义规则排序。
- 由于是实现自SortedMap，所以存入TreeMap的所有元素的key都必须是实现了Comparable接口的，即保证其key相互调用
k1.compareTo(k2)的时候不会报ClassCastException，或者类型被TreeMap指定的Comparator所接受。 - containsKey、get、put 和 remove 函数的时间复杂度是
log(n) - 有序映射使用它的compareTo（或compare）方法对所有键进行比较，只要这两个方法认为相等，那么在有序映射中的两个键就是相等的。
- 非同步的
- 此类的所有方法及视图返回的所有Entry是其真实的映射关系的快照。它们不支持Entry.setValue方法来更改值。不过put函数中的Entry.setValue是被允许的
TreeMap类继承图
实现了NavigableMap接口，而NavigableMap接口继承着SortedMap接口，致使我们的TreeMap符合SotredMap接口的定义。元素有序
不同的是SortdeMap要求：插入SortedMap的所有元素的键都必须实现 Comparable 接口。或者类型在Comparator类(对应TreeMap维护的comparator变量)中所接受，这也就要求了此时的TreeMap你必须为其的成员变量comparator赋予了值。即对有序映射中的任意两个键 k1 和 k2 执行 k1.compareTo(k2)（或 comparator.compare(k1, k2)）必须是正确的。
TreeMap的域
/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
*
* @serial
*/
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
/**
* The number of entries in the tree
*/
private transient int size = 0;
/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;
-
comparator:TreeMap中维护了一个Comparator类型的变量。用来保证TreeMap的有序性。构造时传入该比较器 -
root：红黑树根节点 -
size: Entry数量 -
modCount：结构性修改的次数
TreeMap的构造函数
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
共四个，每个都对其实例维护的Comparator引用进行了赋值。
-
TreeMap()：无参构造函数规定，插入该有序Map的所有元素的键都必须实现Comparable接口，保证了其的可比较性。进而根据其键的自然排序来生成一个有序Map。 -
TreeMap(Comparator<? super K> comparator)：参数是Comparator引用的构造函数规定，插入该有序Map的所有元素的键都需要根据该Comparator来进行比较。 -
TreeMap(Map<? extends K, ? extends V> m)：参数是一个Map映射的构造函数会在其元素基础上构造一个TreeMap。同时该TreeMap规定元素需要满足TreeMap的默认规定，即和无惨构造函数所要求的一样，既然该构造函数没有指定TreeMap的域对象compartor比较器，那么该Map对象中的key就必须都满足TreeMap对所有Entry的key值的要求，即继承了Comparable接口且相互之间可以比较。 -
TreeMap(SortedMap<K, ? extends V> m)：参数是SortedMap的构造函数会拷贝一份和其相同元素和顺序的TreeMap。线性时间
TreeMap常见Api解析
put(K key, V value)
public V put(K key, V value) {
Entry<K,V> t = root;
// 如果红黑树为空
if (t == null) {
// key非空检查
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {// 根据自定义比较器进行比较
// 根据key找到元素在树中应该落点的位置
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {// 根据元素的键实现的Comparable接口进行比较
if (key == null)// key不允许为null
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {// 根据key找好元素在树的中落点
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 循环跳出，parent即元素所在点的父节点。
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 调整红黑树
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
- put函数规定：如果Entry已经存在那么oldValue替换成newValue。如果Entry第一次插入，返回null。
函数整体逻辑：判断当前红黑树是否为空，key是否为空检查，实例变量的维护。通过Comparable或者Comparator来找元素的落点，然后赋值。最后调整红黑树
Comparable接口的排序了解一下
重要：接口的compareTo函数，不支持null元素作为比较的参数传入。因为null 不是任何类的实例，如果传入会报NullPointerException。注释有说：
* @throws NullPointerException if the specified object is null
*/
public int compareTo(T o);
该接口强行对实现它的每个类的对象进行整体排序(隐式的)。这种排序被称为类的自然排序，类的 compareTo 方法被称为它的自然比较方法。一般情况下我们应该尽可能的使它的自然比较方法和它的equals方法的比较结果保持一致。即一个类实现了Comparable接口，那么他必然要重写compareTo函数，假设这个实现类是Student那么他的比较规则可能是
if(this.id > o.id){
return 0
}
……
此时equals函数的比较规则肯定是两个id不相等肯定不是同一个元素。但是compareTo的比较结果却是两个对象相等。这样的话就很不妥。但是一般情况下，我们的compareTo和equals的比较结果应该还是一致的，在指定比较规则的时候我们应该想到这些，并考虑周全一些。
实现了这个接口的对象的列表或数组可以通过其Collections.sort或Arrays.sort进行自动排序。
同时实现该接口的对象可以用作有序映射中的键或有序集合中的元素，无需再指定比较器。
一般的继承该接口的类型比较的时候，我们应该尽量保证其compareTo函数的比较结果与equals函数的比较结果一致。
Comparator接口的排序了解一下
重要：接口的compare函数也不支持比较参数出传入null值。因为null不是任何类的实例，如果传入会报NullPointerException。注释有说：
* @throws NullPointerException if an argument is null and this
* comparator does not permit null arguments
*/
int compare(T o1, T o2);
强行对某个对象 collection 进行整体排序 的接口。可以将 Comparator 传递给 sort 方法（如 Collections.sort 或 Arrays.sort），从而允许在排序顺序上实现精确控制。还可以使用 Comparator 来控制某些数据结构（如有序 set或有序映射）的顺序，或者为那些没有自然顺序的对象 collection 提供排序。
Comparable与Comparator接口比较总结
相比于Comparable接口的比较，Comparator的比较规则则是一种自定义规则的比较。也就意味着，对于实现了Comparable接口的类来说如果要想排序必须实现其compareTo函数，并且只有这一种方式。相比于我们自定义比较器可以有多个实现类的多个比较器的比较方式而言比较单一。并且没有比较器那么自由，可以随意安插。
Comparator体现了一种策略模式，就是不改变对象自身，而用一个策略对象来改变它的行为。
总的来说
Comparable是自已完成比较，Comparator是外部程序实现比较。
两种方法各有优劣,用Comparable简单,只要实现Comparable 接口的对象直接就成为一个可以比较的对象,但是需要修改源代码,用Comparator的好处是不需要修改源代码, 而是另外实现一个比较器,当某个自定义的对象需要作比较的时候,把比较器和对象一起传递过去就可以比大小了, 并且在Comparator里面用户可以自己实现复杂的可以通用的逻辑,使其可以匹配一些比较简单的对象,那样就可以节省很多重复劳动了。
get(Object key)
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
// 自定义比较器存在，那么就调用getEntryUsingComparator函数来从红黑树中来找对应的Entry
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
// 否则通过Comparable接口的compareTo函数来找
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
// 函数很简单，从红黑树中找到key对应的Entry并返回
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
从getEntry函数可以看出，Entry的获取途径有两种，即先通过comparator获取，如果comparator未指定的话再通过比较各元素的compareTo函数来定位。
remove(Object key)
函数的作用：删除该Entry，并返回Entry.value
public V remove(Object key) {
// 从红黑树中找到对应的Entry
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
上面我们分析过了getEntry的函数逻辑。而deleteEntry函数的主要作用则是删除红黑树中该节点并且调整红黑树。设计红黑树的比较复杂这里就不细说了
遍历
/**
* Base class for TreeMap Iterators
*/
abstract class PrivateEntryIterator<T> implements Iterator<T> {
// 下一个要迭代到的元素
Entry<K,V> next;
// 迭代最后一次所返回的元素
Entry<K,V> lastReturned;
int expectedModCount;
PrivateEntryIterator(Entry<K,V> first) {
expectedModCount = modCount;
lastReturned = null;
next = first;
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
lastReturned = e;
return e;
}
final Entry<K,V> prevEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = predecessor(e);
lastReturned = e;
return e;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
deleteEntry(lastReturned);
expectedModCount = modCount;
lastReturned = null;
}
}
// 返回下一个要迭代的元素
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
// 如果元素有右子树开始迭代右子树(因为既然遍历到了该元素，左子树肯定遍历完了)
else if (t.right != null) {
Entry<K,V> p = t.right;
// 找右子树中最小的
while (p.left != null)
p = p.left;
return p;
} else {
// 该返回其父节点了
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
// 下一个该返回的节点下左右子树全部清空，往上追溯，确认该节点的位置
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
对于successor函数我们需要时刻清晰，其迭代顺序是前序遍历的。先左后中后右
总结
- TreeMap底层是红黑树，能够实现该Map集合有序，很多函数的时间复杂度甚至可以到O(logn)
- key不能为null
- 想要自定义比较，在构造方法中传入Comparator对象，否则使用key的自然排序来进行比较
- 非同步，除非外部手动同步或者Collections封装。
该数据结构的精髓：
如果在构造方法中传递了Comparator对象，那么就会以Comparator对象的方法进行比较，来排序。否则，则使用Comparable的compareTo(T o)方法来比较排序。
需要注意的是
- 如果TreeMap使用Comparable接口来保证有序，那么使用其compareTo(T o)函数来比较时，key不能为null，并且该key必须实现了Comparable接口。
- 相对的如果是使用的是Comparator接口，使用compare函数来比较，key也不能为null，并且必须是Comparator接口支持的泛型类型。
