TreeMap
类图:
TreeMap的构造器可以接受一个Comparator参数用以决定key的顺序，如果没有指定，那么尝试将key强转为Comparable，如果转换失败那就抛出异常了。
put
1public 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 root = new Entry<>(key, value, null);
6 size = 1;
7 modCount++;
8 return null;
9 }
10 int cmp;
11 Entry<K,V> parent;
12 // split comparator and comparable paths
13 Comparator<? super K> cpr = comparator;
14 //按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 //强转为Comparable
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 //修复红黑树
49 fixAfterInsertion(e);
50 size++;
51 modCount++;
52 return null;
53}
红黑树首先是一棵二叉查找树，put方法首先便是在树中进行搜索寻找合适的插入位置，然后修复红黑树。
get
即put的反过程，参考put即可。
entrySet
默认按照key的升序进行迭代:
1public Set<Map.Entry<K,V>> entrySet() {
2 EntrySet es = entrySet;
3 return (es != null) ? es : (entrySet = new EntrySet());
4}
我们重点关注EntrySet是如何获得下一个节点的:
1static <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}
很明显。