一、TreeMap剖析
国际惯例，先看一下顶部注释
/**
* A Red-Black tree based {@link NavigableMap} implementation.
* The map is sorted according to the {@linkplain Comparable natural
* ordering} of its keys, or by a {@link Comparator} provided at map
* creation time, depending on which constructor is used.
*
* <p>This implementation provides guaranteed log(n) time cost for the
* {@code containsKey}, {@code get}, {@code put} and {@code remove}
* operations. Algorithms are adaptations of those in Cormen, Leiserson, and
* Rivest's <em>Introduction to Algorithms</em>.
*
* <p>Note that the ordering maintained by a tree map, like any sorted map, and
* whether or not an explicit comparator is provided, must be <em>consistent
* with {@code equals}</em> if this sorted map is to correctly implement the
* {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
* precise definition of <em>consistent with equals</em>.) This is so because
* the {@code Map} interface is defined in terms of the {@code equals}
* operation, but a sorted map performs all key comparisons using its {@code
* compareTo} (or {@code compare}) method, so two keys that are deemed equal by
* this method are, from the standpoint of the sorted map, equal. The behavior
* of a sorted map <em>is</em> well-defined even if its ordering is
* inconsistent with {@code equals}; it just fails to obey the general contract
* of the {@code Map} interface.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access a map concurrently, and at least one of the
* threads modifies the map structurally, it <em>must</em> be synchronized
* externally. (A structural modification is any operation that adds or
* deletes one or more mappings; merely changing the value associated
* with an existing key is not a structural modification.) This is
* typically accomplished by synchronizing on some object that naturally
* encapsulates the map.
* If no such object exists, the map should be "wrapped" using the
* {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the map: <pre>
* SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
*
* <p>The iterators returned by the {@code iterator} method of the collections
* returned by all of this class's "collection view methods" are
* <em>fail-fast</em>: if the map is structurally modified at any time after
* the iterator is created, in any way except through the iterator's own
* {@code remove} method, the iterator will throw a {@link
* ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the future.
*
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <em>the fail-fast behavior of iterators
* should be used only to detect bugs.</em>
*
* <p>All {@code Map.Entry} pairs returned by methods in this class
* and its views represent snapshots of mappings at the time they were
* produced. They do <strong>not</strong> support the {@code Entry.setValue}
* method. (Note however that it is possible to change mappings in the
* associated map using {@code put}.)
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*
* @author Josh Bloch and Doug Lea
* @see Map
* @see HashMap
* @see Hashtable
* @see Comparable
* @see Comparator
* @see Collection
* @since 1.2
*/
底层是红黑树，实现NavigableMap这个接口，可以根据key自然排序，也可以在构造方法上传递Comparator实现Map的排序。
有序的map一般是使用compareTo或者compare方法来比较key，只要该两个方法认为相等，在map的角度就认为这两个元素相等
非同步的，时间复杂度都不会太高：logn
1.2 TreeMap构造方法
TreeMap的构造方法有4个
可以发现，TreeMap的构造方法大多数与comparator有关
也就是顶部注释说的：TreeMap有序是通过Comparator来进行比较的，如果comparator为null，那么就使用自然顺序~
打个比方
如果value是整数，自然顺序指的是我们平时的顺序（1，2，3，4，5）~
1 import java.util.*;
2 import java.util.Map.Entry;
3 public class Solution {
4 public static void main(String[] args) {
5 TreeMap<Integer, Integer> map = new TreeMap<>();
6 map.put(1, 5);
7 map.put(2, 4);
8 map.put(3, 3);
9 map.put(4, 2);
10 map.put(5, 1);
11
12 for (Entry<Integer, Integer> entry : map.entrySet()) {
13 String s = entry.getKey()+"--"+entry.getValue();
14 System.out.println(s);
15 }
16 }
17 }
1.3 put方法
我们来看看TreeMap的核心put方法，阅读它就可以获取了不少关于TreeMap特性的东西了
1 public V put(K key, V value) {
2 Entry<K,V> t = root;
3 if (t == null) {
4 compare(key, key); // type (and possibly null) check
5
6 root = new Entry<>(key, value, null);
7 size = 1;
8 modCount++;
9 return null;
10 }
11 int cmp;
12 Entry<K,V> parent;
13 // split comparator and comparable paths
14 Comparator<? super K> cpr = comparator;
15 if (cpr != null) {
16 do {
17 parent = t;
18 cmp = cpr.compare(key, t.key);
19 if (cmp < 0)
20 t = t.left;
21 else if (cmp > 0)
22 t = t.right;
23 else
24 return t.setValue(value);
25 } while (t != null);
26 }
27 else {
28 if (key == null)
29 throw new NullPointerException();
30 @SuppressWarnings("unchecked")
31 Comparable<? super K> k = (Comparable<? super K>) key;
32 do {
33 parent = t;
34 cmp = k.compareTo(t.key);
35 if (cmp < 0)
36 t = t.left;
37 else if (cmp > 0)
38 t = t.right;
39 else
40 return t.setValue(value);
41 } while (t != null);
42 }
43 Entry<K,V> e = new Entry<>(key, value, parent);
44 if (cmp < 0)
45 parent.left = e;
46 else
47 parent.right = e;
48 fixAfterInsertion(e);
49 size++;
50 modCount++;
51 return null;
52 }
如果红黑树为null，则新建红黑树，要判断key是否为空类型
comparator比较找到合适的位置插入到红黑树中
如果Comparator为null，则利用key作为比较器进行比较，并且key必须实现Comparable接口
key不能为null，找到合适的位置插入到红黑树中
下面是compare(Object k1, Object k2)方法
1 /**
2 * Compares two keys using the correct comparison method for this TreeMap.
3 */
4 @SuppressWarnings("unchecked")
5 final int compare(Object k1, Object k2) {
6 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
7 : comparator.compare((K)k1, (K)k2);
8 }
1.4 get方法
接下来我们看看get方法的实现
找到返回value，找不到返回null
1 public V get(Object key) {
2 Entry<K,V> p = getEntry(key);
3 return (p==null ? null : p.value);
4 }
点进去看看getEntry看看实现
1 final Entry<K,V> getEntry(Object key) {
2 // Offload comparator-based version for sake of performance
3 if (comparator != null)
4 return getEntryUsingComparator(key);
5 if (key == null)
6 throw new NullPointerException();
7 @SuppressWarnings("unchecked")
8 Comparable<? super K> k = (Comparable<? super K>) key;
9 Entry<K,V> p = root;
10 while (p != null) {
11 int cmp = k.compareTo(p.key);
12 if (cmp < 0)
13 p = p.left;
14 else if (cmp > 0)
15 p = p.right;
16 else
17 return p;
18 }
19 return null;
20 }
如果comparator不为null，调的是
getEntryUsingComparator(key)
不然就是使用compareTo()方法，从红黑树中找到对应的值，返回出去。
如果Comparator不为null，接下来我们进去看看getEntryUsingComparator(Object key)，是怎么实现的
1 final Entry<K,V> getEntryUsingComparator(Object key) {
2 @SuppressWarnings("unchecked")
3 K k = (K) key;
4 Comparator<? super K> cpr = comparator;
5 if (cpr != null) {
6 Entry<K,V> p = root;
7 while (p != null) {
8 int cmp = cpr.compare(k, p.key);
9 if (cmp < 0)
10 p = p.left;
11 else if (cmp > 0)
12 p = p.right;
13 else
14 return p;
15 }
16 }
17 return null;
18 }
只不过是调用Comparator自己实现的方法来获取相应的位置，总体逻辑和外面的没啥区别
1.5 remove方法
1 public V remove(Object key) {
2 Entry<K,V> p = getEntry(key);
3 if (p == null)
4 return null;
5
6 V oldValue = p.value;
7 deleteEntry(p);
8 return oldValue;
9 }
先找到这个节点的位置，记录这个想要删除的值（返回），删除这个节点
删除节点的时候调用的是deleteEntry(Entry<K,V> p)方法，这个方法主要是删除节点并且平衡红黑树。
平衡红黑树的代码是比较复杂的。emm，以后有空再整理
1.6遍历方法
TreeMap遍历是使用EntryIterator这个内部类的
可以发现，EntryIterator大多的实现都是在父类中：
1 final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
2 EntryIterator(Entry<K,V> first) {
3 super(first);
4 }
5 public Map.Entry<K,V> next() {
6 return nextEntry();
7 }
8 }
那接下来我们去看看PrivateEntryIterator比较重要的方法：
1 abstract class PrivateEntryIterator<T> implements Iterator<T> {
2 Entry<K,V> next;
3 Entry<K,V> lastReturned;
4 int expectedModCount;
5
6 PrivateEntryIterator(Entry<K,V> first) {
7 expectedModCount = modCount;
8 lastReturned = null;
9 next = first;
10 }
11
12 public final boolean hasNext() {
13 return next != null;
14 }
15
16 final Entry<K,V> nextEntry() {
17 Entry<K,V> e = next;
18 if (e == null)
19 throw new NoSuchElementException();
20 if (modCount != expectedModCount)
21 throw new ConcurrentModificationException();
22 next = successor(e);
23 lastReturned = e;
24 return e;
25 }
lastReturned是返回的节点
successor是获取下一个节点
我们进去方法
successor
看看实现
successor其实就是一个节点的下一个节点，所谓的下一个，是按次序排序后的下一个节点，从代码中可以看出，如果右子树不为空，就返回右子树中最小结点。如果右子树为空，就要向上回溯了。在这种情况下，t是以其为根的树的最后一个节点。如果它是其父节点的左孩子，那么父节点就是它的下一个节点，否则，t就是以其父节点为根的树的最后一个节点，需要再次向上回溯，一直到ch是p的右孩子为止。
1 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2 if (t == null)
3 return null;
4 else if (t.right != null) {
5 Entry<K,V> p = t.right;
6 while (p.left != null)
7 p = p.left;
8 return p;
9 } else {
10 Entry<K,V> p = t.parent;
11 Entry<K,V> ch = t;
12 while (p != null && ch == p.right) {
13 ch = p;
14 p = p.parent;
15 }
16 return p;
17 }
18 }
二、总结
TreeMap底层是红黑树，能够实现该Map集合有序
如果在构造方法传递了Comparator对象，那么就会以Comparator对象的方法进行比较。否则则使用Comparable的compareTo(T o)方法来比较。
值得说明的是：如果使用的是compareTo(T o)方法来进行比较，key一定不能是null，并且实现了Comparable接口的。
即使是传入了Comparator对象，不用compareTo方法进行比较，key也不能为null的
我们从源码中的很多地方中发现：Comparator和Comparable出现的频率是很高的，因为TreeMap实现有序要么就是外界传递进来Comparator对象，要么就使用默认key的Comparable接口(实现自然排序)
最后我就来总结一下TreeMap要点吧：
由于底层是红黑树，那么时间复杂度可以保证为log(n)
key不能为null，为null为抛出NullPointException的
想要自定义比较，在构造方法中传入Comparator对象，否则使用key的自然排序来进行比较
TreeMap非同步的，想要同步可以使用Collections来进行封装
