我们继续分析TreeMap的源码

1.TreeMap源码分析（续）

1. 存取方法

        TreeMap中的存取方法本质上就是对红黑树的插入和删除操作，从源码里体现的更为明显，其实就是对红黑树的插入和删除（可以参考：红黑树），下面简单看下源码：

[java]  view plain  copy

 

1. /*************************** put和remove **********************************/  
2. //将key-value对添加到TreeMap中，理解TreeMap的前提是理解红黑树  
3. //因为和红黑树中的添加基本一样  
4. public V put(K key, V value) {  
5.     Entry<K,V> t = root;  
6.     if (t == null) { //若红黑树为空，直接添加根节点  
7.         compare(key, key); // type (and possibly null) check  
8.   
9.         root = new Entry<>(key, value, null);  
10.         size = 1;  
11.         modCount++;  
12.         return null;  
13.     }  
14.     int cmp;  
15.     Entry<K,V> parent;  
16.     //在红黑树中找到插入的位置  
17.     Comparator<? super K> cpr = comparator;  
18.     if (cpr != null) {  
19.         do {  
20.             parent = t;  
21.             cmp = cpr.compare(key, t.key);  
22.             if (cmp < 0)  
23.                 t = t.left;  
24.             else if (cmp > 0)  
25.                 t = t.right;  
26.             else  
27.                 return t.setValue(value);  
28.         } while (t != null);  
29.     }  
30.     else {  
31.         if (key == null)  
32.             throw new NullPointerException();  
33.         Comparable<? super K> k = (Comparable<? super K>) key;  
34.         do {  
35.             parent = t;  
36.             cmp = k.compareTo(t.key);  
37.             if (cmp < 0)  
38.                 t = t.left;  
39.             else if (cmp > 0)  
40.                 t = t.right;  
41.             else  
42.                 return t.setValue(value);  
43.         } while (t != null);  
44.     }  
45.     //新建红黑树的节点e  
46.     Entry<K,V> e = new Entry<>(key, value, parent);  
47.     if (cmp < 0)  
48.         parent.left = e;  
49.     else  
50.         parent.right = e;  
51.     fixAfterInsertion(e);//插入新节点后，要重新修复红黑树的特性  
52.     size++;  
53.     modCount++;  
54.     return null;  
55. }  
56.   
57. //插入新节点后的修正操作，保证红黑树的平衡性  
58. //跟红黑树中的修正方式一样的  
59. private void fixAfterInsertion(Entry<K,V> x) {  
60.     x.color = RED;  
61.   
62.     while (x != null && x != root && x.parent.color == RED) {  
63.         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {  
64.             Entry<K,V> y = rightOf(parentOf(parentOf(x)));  
65.             if (colorOf(y) == RED) {  
66.                 setColor(parentOf(x), BLACK);  
67.                 setColor(y, BLACK);  
68.                 setColor(parentOf(parentOf(x)), RED);  
69.                 x = parentOf(parentOf(x));  
70.             } else {  
71.                 if (x == rightOf(parentOf(x))) {  
72.                     x = parentOf(x);  
73.                     rotateLeft(x);  
74.                 }  
75.                 setColor(parentOf(x), BLACK);  
76.                 setColor(parentOf(parentOf(x)), RED);  
77.                 rotateRight(parentOf(parentOf(x)));  
78.             }  
79.         } else {  
80.             Entry<K,V> y = leftOf(parentOf(parentOf(x)));  
81.             if (colorOf(y) == RED) {  
82.                 setColor(parentOf(x), BLACK);  
83.                 setColor(y, BLACK);  
84.                 setColor(parentOf(parentOf(x)), RED);  
85.                 x = parentOf(parentOf(x));  
86.             } else {  
87.                 if (x == leftOf(parentOf(x))) {  
88.                     x = parentOf(x);  
89.                     rotateRight(x);  
90.                 }  
91.                 setColor(parentOf(x), BLACK);  
92.                 setColor(parentOf(parentOf(x)), RED);  
93.                 rotateLeft(parentOf(parentOf(x)));  
94.             }  
95.         }  
96.     }  
97.     root.color = BLACK;  
98. }  
99.   
100. //左旋操作  
101. private void rotateLeft(Entry<K,V> p) {  
102.     if (p != null) {  
103.         Entry<K,V> r = p.right;  
104.         p.right = r.left;  
105.         if (r.left != null)  
106.             r.left.parent = p;  
107.         r.parent = p.parent;  
108.         if (p.parent == null)  
109.             root = r;  
110.         else if (p.parent.left == p)  
111.             p.parent.left = r;  
112.         else  
113.             p.parent.right = r;  
114.         r.left = p;  
115.         p.parent = r;  
116.     }  
117. }  
118.   
119. //右旋操作  
120. private void rotateRight(Entry<K,V> p) {  
121.     if (p != null) {  
122.         Entry<K,V> l = p.left;  
123.         p.left = l.right;  
124.         if (l.right != null) l.right.parent = p;  
125.         l.parent = p.parent;  
126.         if (p.parent == null)  
127.             root = l;  
128.         else if (p.parent.right == p)  
129.             p.parent.right = l;  
130.         else p.parent.left = l;  
131.         l.right = p;  
132.         p.parent = l;  
133.     }  
134. }  
135.   
136. //删除指定key的Entry  
137. public V remove(Object key) {  
138.     Entry<K,V> p = getEntry(key);  
139.     if (p == null)  
140.         return null;  
141.   
142.     V oldValue = p.value;  
143.     deleteEntry(p);  
144.     return oldValue;  
145. }  
146.   
147. private void deleteEntry(Entry<K,V> p) {  
148.     modCount++;  
149.     size--;  
150.   
151.     // If strictly internal, copy successor's element to p and then make p  
152.     // point to successor.  
153.     if (p.left != null && p.right != null) {  
154.         Entry<K,V> s = successor(p);  
155.         p.key = s.key;  
156.         p.value = s.value;  
157.         p = s;  
158.     } // p has 2 children  
159.   
160.     // Start fixup at replacement node, if it exists.  
161.     Entry<K,V> replacement = (p.left != null ? p.left : p.right);  
162.   
163.     if (replacement != null) {  
164.         // Link replacement to parent  
165.         replacement.parent = p.parent;  
166.         if (p.parent == null)  
167.             root = replacement;  
168.         else if (p == p.parent.left)  
169.             p.parent.left  = replacement;  
170.         else  
171.             p.parent.right = replacement;  
172.   
173.         // Null out links so they are OK to use by fixAfterDeletion.  
174.         p.left = p.right = p.parent = null;  
175.   
176.         // Fix replacement  
177.         if (p.color == BLACK)  
178.             fixAfterDeletion(replacement);  
179.     } else if (p.parent == null) { // return if we are the only node.  
180.         root = null;  
181.     } else { //  No children. Use self as phantom replacement and unlink.  
182.         if (p.color == BLACK)  
183.             fixAfterDeletion(p);  
184.   
185.         if (p.parent != null) {  
186.             if (p == p.parent.left)  
187.                 p.parent.left = null;  
188.             else if (p == p.parent.right)  
189.                 p.parent.right = null;  
190.             p.parent = null;  
191.         }  
192.     }  
193. }  
194.   
195. //删除后的修复，与红黑树一样  
196. private void fixAfterDeletion(Entry<K,V> x) {  
197.     while (x != root && colorOf(x) == BLACK) {  
198.         if (x == leftOf(parentOf(x))) {  
199.             Entry<K,V> sib = rightOf(parentOf(x));  
200.   
201.             if (colorOf(sib) == RED) {  
202.                 setColor(sib, BLACK);  
203.                 setColor(parentOf(x), RED);  
204.                 rotateLeft(parentOf(x));  
205.                 sib = rightOf(parentOf(x));  
206.             }  
207.   
208.             if (colorOf(leftOf(sib))  == BLACK &&  
209.                 colorOf(rightOf(sib)) == BLACK) {  
210.                 setColor(sib, RED);  
211.                 x = parentOf(x);  
212.             } else {  
213.                 if (colorOf(rightOf(sib)) == BLACK) {  
214.                     setColor(leftOf(sib), BLACK);  
215.                     setColor(sib, RED);  
216.                     rotateRight(sib);  
217.                     sib = rightOf(parentOf(x));  
218.                 }  
219.                 setColor(sib, colorOf(parentOf(x)));  
220.                 setColor(parentOf(x), BLACK);  
221.                 setColor(rightOf(sib), BLACK);  
222.                 rotateLeft(parentOf(x));  
223.                 x = root;  
224.             }  
225.         } else { // symmetric  
226.             Entry<K,V> sib = leftOf(parentOf(x));  
227.   
228.             if (colorOf(sib) == RED) {  
229.                 setColor(sib, BLACK);  
230.                 setColor(parentOf(x), RED);  
231.                 rotateRight(parentOf(x));  
232.                 sib = leftOf(parentOf(x));  
233.             }  
234.   
235.             if (colorOf(rightOf(sib)) == BLACK &&  
236.                 colorOf(leftOf(sib)) == BLACK) {  
237.                 setColor(sib, RED);  
238.                 x = parentOf(x);  
239.             } else {  
240.                 if (colorOf(leftOf(sib)) == BLACK) {  
241.                     setColor(rightOf(sib), BLACK);  
242.                     setColor(sib, RED);  
243.                     rotateLeft(sib);  
244.                     sib = leftOf(parentOf(x));  
245.                 }  
246.                 setColor(sib, colorOf(parentOf(x)));  
247.                 setColor(parentOf(x), BLACK);  
248.                 setColor(leftOf(sib), BLACK);  
249.                 rotateRight(parentOf(x));  
250.                 x = root;  
251.             }  
252.         }  
253.     }  
254.   
255.     setColor(x, BLACK);  
256. }  

1.2 其他方法

[java]  view plain  copy

 

1. public int size() {  
2.     return size;  
3. }  
4.   
5. //返回TreeMap中是否包含“键(key)”  
6. public boolean containsKey(Object key) {  
7.     return getEntry(key) != null;  
8. }  
9.   
10. //返回TreeMap中是否包含"值(value)"  
11. public boolean containsValue(Object value) {  
12.     //从最小的节点开始找  
13.     for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))  
14.         if (valEquals(value, e.value))  
15.             return true;  
16.     return false;  
17. }  
18.   
19. // 获取“键(key)”对应的“值(value)”  
20. public V get(Object key) {  
21.     Entry<K,V> p = getEntry(key);  
22.     return (p==null ? null : p.value);  
23. }  
24.   
25. public Comparator<? super K> comparator() {  
26.     return comparator;  
27. }  
28.   
29. // 获取第一个节点对应的key  
30. public K firstKey() {  
31.     return key(getFirstEntry());  
32. }  
33. // 获取最后一个节点对应的key  
34. public K lastKey() {  
35.     return key(getLastEntry());  
36. }  
37.   
38. // 返回不大于key的最大的键值对所对应的KEY，没有的话返回null  
39. public K floorKey(K key) {  
40.     return keyOrNull(getFloorEntry(key));  
41. }  
42. // 返回不小于key的最小的键值对所对应的KEY，没有的话返回null  
43. public K ceilingKey(K key) {  
44.     return keyOrNull(getCeilingEntry(key));  
45. }  
46. // 返回小于key的最大的键值对所对应的KEY，没有的话返回null  
47. public K lowerKey(K key) {  
48.     return keyOrNull(getLowerEntry(key));  
49. }  
50. // 返回大于key的最小的键值对所对应的KEY，没有的话返回null  
51. public K higherKey(K key) {  
52.     return keyOrNull(getHigherEntry(key));  
53. }  
54.   
55. //TreeMap的红黑树节点对应的集合  
56. private transient EntrySet entrySet = null;  
57. //navigableKeySet为KeySet导航类  
58. private transient KeySet<K> navigableKeySet = null;  
59. //descendingMap为键值对的倒序“映射”  
60. private transient NavigableMap<K,V> descendingMap = null;  
61.   
62. // 返回TreeMap的“键的集合”  
63. public Set<K> keySet() {  
64.     return navigableKeySet();  
65. }  
66.   
67. // 获取“可导航”的Key的集合  
68. // 实际上是返回KeySet类的对象。  
69. public NavigableSet<K> navigableKeySet() {  
70.     KeySet<K> nks = navigableKeySet;  
71.     return (nks != null) ? nks : (navigableKeySet = new KeySet(this));  
72. }  
73. // 获取TreeMap的降序的key的集合  
74. public NavigableSet<K> descendingKeySet() {  
75.     return descendingMap().navigableKeySet();  
76. }  
77. // 获取TreeMap的降序Map  
78. // 实际上是返回DescendingSubMap类的对象  
79. public NavigableMap<K, V> descendingMap() {  
80.     NavigableMap<K, V> km = descendingMap;  
81.     return (km != null) ? km :  
82.         (descendingMap = new DescendingSubMap(this,  
83.                                               true, null, true,  
84.                                               true, null, true));  
85. }  
86. // 返回“TreeMap的值对应的集合”  
87. public Collection<V> values() {  
88.     Collection<V> vs = values;  
89.     return (vs != null) ? vs : (values = new Values());  
90. }  
91. // ”TreeMap的值的集合“对应的类，它继承于AbstractCollection  
92. class Values extends AbstractCollection<V> {  
93.     public Iterator<V> iterator() {  
94.         return new ValueIterator(getFirstEntry());  
95.     }  
96.   
97.     public int size() {  
98.         return TreeMap.this.size();  
99.     }  
100.   
101.     public boolean contains(Object o) {  
102.         return TreeMap.this.containsValue(o);  
103.     }  
104.   
105.     public boolean remove(Object o) {  
106.         for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {  
107.             if (valEquals(e.getValue(), o)) {  
108.                 deleteEntry(e);  
109.                 return true;  
110.             }  
111.         }  
112.         return false;  
113.     }  
114.   
115.     public void clear() {  
116.         TreeMap.this.clear();  
117.     }  
118. }  
119.   
120. // 获取TreeMap的Entry的集合，实际上是返回EntrySet类的对象。  
121. public Set<Map.Entry<K,V>> entrySet() {  
122.     EntrySet es = entrySet;  
123.     return (es != null) ? es : (entrySet = new EntrySet());  
124. }  
125. // EntrySet是“TreeMap的所有键值对组成的集合”，  
126. // EntrySet集合的单位是单个“键值对”。  
127. class EntrySet extends AbstractSet<Map.Entry<K,V>> {  
128.     public Iterator<Map.Entry<K,V>> iterator() {  
129.         return new EntryIterator(getFirstEntry());  
130.     }  
131.   
132.     public boolean contains(Object o) {  
133.         if (!(o instanceof Map.Entry))  
134.             return false;  
135.         Map.Entry<K,V> entry = (Map.Entry<K,V>) o;  
136.         V value = entry.getValue();  
137.         Entry<K,V> p = getEntry(entry.getKey());  
138.         return p != null && valEquals(p.getValue(), value);  
139.     }  
140.   
141.     public boolean remove(Object o) {  
142.         if (!(o instanceof Map.Entry))  
143.             return false;  
144.         Map.Entry<K,V> entry = (Map.Entry<K,V>) o;  
145.         V value = entry.getValue();  
146.         Entry<K,V> p = getEntry(entry.getKey());  
147.         if (p != null && valEquals(p.getValue(), value)) {  
148.             deleteEntry(p);  
149.             return true;  
150.         }  
151.         return false;  
152.     }  
153.   
154.     public int size() {  
155.         return TreeMap.this.size();  
156.     }  
157.   
158.     public void clear() {  
159.         TreeMap.this.clear();  
160.     }  
161. }  
162.   
163. // 获取TreeMap的子Map  
164. // 范围是从fromKey 到 toKey；fromInclusive是是否包含fromKey的标记，toInclusive是是否包含toKey的标记  
165. public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,  
166.                                 K toKey,   boolean toInclusive) {  
167.     return new AscendingSubMap(this,  
168.                                false, fromKey, fromInclusive,  
169.                                false, toKey,   toInclusive);  
170. }  
171.   
172. // 获取“Map的头部”  
173. // 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记  
174. public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {  
175.     return new AscendingSubMap(this,  
176.                                true,  null,  true,  
177.                                false, toKey, inclusive);  
178. }  
179.   
180. // 获取“Map的尾部”。  
181. // 范围是从 fromKey 到 最后一个节点，inclusive是是否包含fromKey的标记  
182. public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {  
183.     return new AscendingSubMap(this,  
184.                                false, fromKey, inclusive,  
185.                                true,  null,    true);  
186. }  
187.   
188. // 获取“子Map”。  
189. // 范围是从fromKey(包括) 到 toKey(不包括)  
190. public SortedMap<K,V> subMap(K fromKey, K toKey) {  
191.     return subMap(fromKey, true, toKey, false);  
192. }  
193.   
194. // 获取“Map的头部”。  
195. // 范围从第一个节点 到 toKey(不包括)  
196. public SortedMap<K,V> headMap(K toKey) {  
197.     return headMap(toKey, false);  
198. }  
199.   
200. // 获取“Map的尾部”。  
201. // 范围是从 fromKey(包括) 到 最后一个节点  
202. public SortedMap<K,V> tailMap(K fromKey) {  
203.     return tailMap(fromKey, true);  
204. }  
205.   
206. //返回“TreeMap的KEY组成的迭代器(顺序)”  
207. Iterator<K> keyIterator() {  
208.     return new KeyIterator(getFirstEntry());  
209. }  
210.   
211. // 返回“TreeMap的KEY组成的迭代器(逆序)”  
212. Iterator<K> descendingKeyIterator() {  
213.     return new DescendingKeyIterator(getLastEntry());  
214. }  
215.   
216. // KeySet是“TreeMap中所有的KEY组成的集合”  
217. // KeySet继承于AbstractSet，而且实现了NavigableSet接口。  
218. static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {  
219.     private final NavigableMap<E, Object> m;  
220.     KeySet(NavigableMap<E,Object> map) { m = map; }  
221.   
222.     //升序迭代器  
223.     public Iterator<E> iterator() {  
224.         // 若是TreeMap对象，则调用TreeMap的迭代器keyIterator()  
225.         // 否则，调用TreeMap子类NavigableSubMap的迭代器keyIterator()  
226.         if (m instanceof TreeMap)  
227.             return ((TreeMap<E,Object>)m).keyIterator();  
228.         else  
229.             return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());  
230.     }  
231.       
232.     //降序迭代器  
233.     public Iterator<E> descendingIterator() {  
234.         // 若是TreeMap对象，则调用TreeMap的迭代器descendingKeyIterator()  
235.         // 否则，调用TreeMap子类NavigableSubMap的迭代器descendingKeyIterator()  
236.         if (m instanceof TreeMap)  
237.             return ((TreeMap<E,Object>)m).descendingKeyIterator();  
238.         else  
239.             return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());  
240.     }  
241.   
242.     public int size() { return m.size(); }  
243.     public boolean isEmpty() { return m.isEmpty(); }  
244.     public boolean contains(Object o) { return m.containsKey(o); }  
245.     public void clear() { m.clear(); }  
246.     public E lower(E e) { return m.lowerKey(e); }  
247.     public E floor(E e) { return m.floorKey(e); }  
248.     public E ceiling(E e) { return m.ceilingKey(e); }  
249.     public E higher(E e) { return m.higherKey(e); }  
250.     public E first() { return m.firstKey(); }  
251.     public E last() { return m.lastKey(); }  
252.     public Comparator<? super E> comparator() { return m.comparator(); }  
253.     public E pollFirst() {  
254.         Map.Entry<E,Object> e = m.pollFirstEntry();  
255.         return (e == null) ? null : e.getKey();  
256.     }  
257.     public E pollLast() {  
258.         Map.Entry<E,Object> e = m.pollLastEntry();  
259.         return (e == null) ? null : e.getKey();  
260.     }  
261.     public boolean remove(Object o) {  
262.         int oldSize = size();  
263.         m.remove(o);  
264.         return size() != oldSize;  
265.     }  
266.     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,  
267.                                   E toElement,   boolean toInclusive) {  
268.         return new KeySet<>(m.subMap(fromElement, fromInclusive,  
269.                                       toElement,   toInclusive));  
270.     }  
271.     public NavigableSet<E> headSet(E toElement, boolean inclusive) {  
272.         return new KeySet<>(m.headMap(toElement, inclusive));  
273.     }  
274.     public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {  
275.         return new KeySet<>(m.tailMap(fromElement, inclusive));  
276.     }  
277.     public SortedSet<E> subSet(E fromElement, E toElement) {  
278.         return subSet(fromElement, true, toElement, false);  
279.     }  
280.     public SortedSet<E> headSet(E toElement) {  
281.         return headSet(toElement, false);  
282.     }  
283.     public SortedSet<E> tailSet(E fromElement) {  
284.         return tailSet(fromElement, true);  
285.     }  
286.     public NavigableSet<E> descendingSet() {  
287.         return new KeySet(m.descendingMap());  
288.     }  
289. }  
290.   
291. /// 它是TreeMap中的一个抽象迭代器，实现了一些通用的接口。  
292. abstract class PrivateEntryIterator<T> implements Iterator<T> {  
293.     Entry<K,V> next;  
294.     Entry<K,V> lastReturned;  
295.     int expectedModCount;  
296.   
297.     PrivateEntryIterator(Entry<K,V> first) {  
298.         expectedModCount = modCount;  
299.         lastReturned = null;  
300.         next = first;  
301.     }  
302.   
303.     public final boolean hasNext() {  
304.         return next != null;  
305.     }  
306.   
307.     final Entry<K,V> nextEntry() {  
308.         Entry<K,V> e = next;  
309.         if (e == null)  
310.             throw new NoSuchElementException();  
311.         if (modCount != expectedModCount)  
312.             throw new ConcurrentModificationException();  
313.         next = successor(e);  
314.         lastReturned = e;  
315.         return e;  
316.     }  
317.   
318.     final Entry<K,V> prevEntry() {  
319.         Entry<K,V> e = next;  
320.         if (e == null)  
321.             throw new NoSuchElementException();  
322.         if (modCount != expectedModCount)  
323.             throw new ConcurrentModificationException();  
324.         next = predecessor(e);  
325.         lastReturned = e;  
326.         return e;  
327.     }  
328.   
329.     public void remove() {  
330.         if (lastReturned == null)  
331.             throw new IllegalStateException();  
332.         if (modCount != expectedModCount)  
333.             throw new ConcurrentModificationException();  
334.         // 这里重点强调一下“为什么当lastReturned的左右孩子都不为空时，要将其赋值给next”。  
335.         // 目的是为了“删除lastReturned节点之后，next节点指向的仍然是下一个节点”。  
336.         //     根据“红黑树”的特性可知：  
337.         //     当被删除节点有两个儿子时。那么，首先把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。  
338.         //     这意味着“当被删除节点有两个儿子时，删除当前节点之后，'新的当前节点'实际上是‘原有的后继节点(即下一个节点)’”。  
339.         //     而此时next仍然指向"新的当前节点"。也就是说next是仍然是指向下一个节点；能继续遍历红黑树。  
340.         if (lastReturned.left != null && lastReturned.right != null)  
341.             next = lastReturned;  
342.         deleteEntry(lastReturned);  
343.         expectedModCount = modCount;  
344.         lastReturned = null;  
345.     }  
346. }  
347.   
348. // TreeMap的Entry对应的迭代器  
349. final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {  
350.     EntryIterator(Entry<K,V> first) {  
351.         super(first);  
352.     }  
353.     public Map.Entry<K,V> next() {  
354.         return nextEntry();  
355.     }  
356. }  
357.   
358. // TreeMap的Value对应的迭代器  
359. final class ValueIterator extends PrivateEntryIterator<V> {  
360.     ValueIterator(Entry<K,V> first) {  
361.         super(first);  
362.     }  
363.     public V next() {  
364.         return nextEntry().value;  
365.     }  
366. }  
367.   
368. // reeMap的KEY组成的迭代器(顺序)  
369. final class KeyIterator extends PrivateEntryIterator<K> {  
370.     KeyIterator(Entry<K,V> first) {  
371.         super(first);  
372.     }  
373.     public K next() {  
374.         return nextEntry().key;  
375.     }  
376. }  
377.   
378. // TreeMap的KEY组成的迭代器(逆序)  
379. final class DescendingKeyIterator extends PrivateEntryIterator<K> {  
380.     DescendingKeyIterator(Entry<K,V> first) {  
381.         super(first);  
382.     }  
383.     public K next() {  
384.         return prevEntry().key;  
385.     }  
386. }  
387.   
388. // 比较两个对象的大小  
389. final int compare(Object k1, Object k2) {  
390.     return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)  
391.         : comparator.compare((K)k1, (K)k2);  
392. }  
393.   
394. // 判断两个对象是否相等  
395. static final boolean valEquals(Object o1, Object o2) {  
396.     return (o1==null ? o2==null : o1.equals(o2));  
397. }  
398.   
399. // 返回“Key-Value键值对”的一个简单拷贝(AbstractMap.SimpleImmutableEntry<K,V>对象)  
400. // 可用来读取“键值对”的值  
401. static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {  
402.     return (e == null) ? null :  
403.         new AbstractMap.SimpleImmutableEntry<>(e);  
404. }  
405.   
406. // 若“键值对”不为null，则返回KEY；否则，返回null  
407. static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {  
408.     return (e == null) ? null : e.key;  
409. }  
410.   
411. // 若“键值对”不为null，则返回KEY；否则，抛出异常  
412. static <K> K key(Entry<K,?> e) {  
413.     if (e==null)  
414.         throw new NoSuchElementException();  
415.     return e.key;  
416. }  
417.   
418. private static final Object UNBOUNDED = new Object();  
419.   
420. // TreeMap的SubMap，它一个抽象类，实现了公共操作。  
421. // 它包括了"(升序)AscendingSubMap"和"(降序)DescendingSubMap"两个子类。  
422. abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>  
423.     implements NavigableMap<K,V>, java.io.Serializable {  
424.     // TreeMap的拷贝  
425.     final TreeMap<K,V> m;  
426.   
427.     // lo是“子Map范围的最小值”，hi是“子Map范围的最大值”；  
428.     // loInclusive是“是否包含lo的标记”，hiInclusive是“是否包含hi的标记”  
429.     // fromStart是“表示是否从第一个节点开始计算”，  
430.     // toEnd是“表示是否计算到最后一个节点     
431.     final K lo, hi;  
432.     final boolean fromStart, toEnd;  
433.     final boolean loInclusive, hiInclusive;  
434.   
435.     NavigableSubMap(TreeMap<K,V> m,  
436.                     boolean fromStart, K lo, boolean loInclusive,  
437.                     boolean toEnd,     K hi, boolean hiInclusive) {  
438.         if (!fromStart && !toEnd) {  
439.             if (m.compare(lo, hi) > 0)  
440.                 throw new IllegalArgumentException("fromKey > toKey");  
441.         } else {  
442.             if (!fromStart) // type check  
443.                 m.compare(lo, lo);  
444.             if (!toEnd)  
445.                 m.compare(hi, hi);  
446.         }  
447.   
448.         this.m = m;  
449.         this.fromStart = fromStart;  
450.         this.lo = lo;  
451.         this.loInclusive = loInclusive;  
452.         this.toEnd = toEnd;  
453.         this.hi = hi;  
454.         this.hiInclusive = hiInclusive;  
455.     }  
456.   
457.     // 判断key是否太小  
458.     final boolean tooLow(Object key) {  
459.         // 若该SubMap不包括“起始节点”，  
460.         // 并且，“key小于最小键(lo)”或者“key等于最小键(lo)，但最小键却没包括在该SubMap内”  
461.         // 则判断key太小。其余情况都不是太小！  
462.         if (!fromStart) {  
463.             int c = m.compare(key, lo);  
464.             if (c < 0 || (c == 0 && !loInclusive))  
465.                 return true;  
466.         }  
467.         return false;  
468.     }  
469.       
470.     // 判断key是否太大  
471.     final boolean tooHigh(Object key) {  
472.         // 若该SubMap不包括“结束节点”，  
473.         // 并且，“key大于最大键(hi)”或者“key等于最大键(hi)，但最大键却没包括在该SubMap内”  
474.         // 则判断key太大。其余情况都不是太大！  
475.         if (!toEnd) {  
476.             int c = m.compare(key, hi);  
477.             if (c > 0 || (c == 0 && !hiInclusive))  
478.                 return true;  
479.         }  
480.         return false;  
481.     }  
482.       
483.     // 判断key是否在“lo和hi”开区间范围内  
484.     final boolean inRange(Object key) {  
485.         return !tooLow(key) && !tooHigh(key);  
486.     }  
487.       
488.     // 判断key是否在封闭区间内  
489.     final boolean inClosedRange(Object key) {  
490.         return (fromStart || m.compare(key, lo) >= 0)  
491.             && (toEnd || m.compare(hi, key) >= 0);  
492.     }  
493.       
494.     // 判断key是否在区间内, inclusive是区间开关标志  
495.     final boolean inRange(Object key, boolean inclusive) {  
496.         return inclusive ? inRange(key) : inClosedRange(key);  
497.     }  
498.   
499.     // 返回最低的Entry  
500.     final TreeMap.Entry<K,V> absLowest() {  
501.         // 若“包含起始节点”，则调用getFirstEntry()返回第一个节点  
502.         // 否则的话，若包括lo，则调用getCeilingEntry(lo)获取大于/等于lo的最小的Entry;  
503.         // 否则，调用getHigherEntry(lo)获取大于lo的最小Entry  
504.         TreeMap.Entry<K,V> e =  
505.             (fromStart ?  m.getFirstEntry() :  
506.              (loInclusive ? m.getCeilingEntry(lo) :  
507.                             m.getHigherEntry(lo)));  
508.         return (e == null || tooHigh(e.key)) ? null : e;  
509.     }  
510.   
511.     // 返回最高的Entry  
512.     final TreeMap.Entry<K,V> absHighest() {  
513.         // 若“包含结束节点”，则调用getLastEntry()返回最后一个节点  
514.         // 否则的话，若包括hi，则调用getFloorEntry(hi)获取小于/等于hi的最大的Entry;  
515.         //           否则，调用getLowerEntry(hi)获取大于hi的最大Entry  
516.         TreeMap.Entry<K,V> e =  
517.             (toEnd ?  m.getLastEntry() :  
518.              (hiInclusive ?  m.getFloorEntry(hi) :  
519.                              m.getLowerEntry(hi)));  
520.         return (e == null || tooLow(e.key)) ? null : e;  
521.     }  
522.     // 返回"大于/等于key的最小的Entry"  
523.     final TreeMap.Entry<K,V> absCeiling(K key) {  
524.         // 只有在“key太小”的情况下，absLowest()返回的Entry才是“大于/等于key的最小Entry”  
525.         // 其它情况下不行。例如，当包含“起始节点”时，absLowest()返回的是最小Entry了！  
526.         if (tooLow(key))  
527.             return absLowest();  
528.         // 获取“大于/等于key的最小Entry”  
529.         TreeMap.Entry<K,V> e = m.getCeilingEntry(key);  
530.         return (e == null || tooHigh(e.key)) ? null : e;  
531.     }  
532.       
533.     // 返回"大于key的最小的Entry"  
534.     final TreeMap.Entry<K,V> absHigher(K key) {  
535.         // 只有在“key太小”的情况下，absLowest()返回的Entry才是“大于key的最小Entry”  
536.         // 其它情况下不行。例如，当包含“起始节点”时，absLowest()返回的是最小Entry了,而不一定是“大于key的最小Entry”！  
537.         if (tooLow(key))  
538.             return absLowest();  
539.         // 获取“大于key的最小Entry”  
540.         TreeMap.Entry<K,V> e = m.getHigherEntry(key);  
541.         return (e == null || tooHigh(e.key)) ? null : e;  
542.     }  
543.   
544.     // 返回"小于/等于key的最大的Entry"  
545.     final TreeMap.Entry<K,V> absFloor(K key) {  
546.         // 只有在“key太大”的情况下，(absHighest)返回的Entry才是“小于/等于key的最大Entry”  
547.         // 其它情况下不行。例如，当包含“结束节点”时，absHighest()返回的是最大Entry了！  
548.         if (tooHigh(key))  
549.             return absHighest();  
550.         // 获取"小于/等于key的最大的Entry"  
551.         TreeMap.Entry<K,V> e = m.getFloorEntry(key);  
552.         return (e == null || tooLow(e.key)) ? null : e;  
553.     }  
554.       
555.     // 返回"小于key的最大的Entry"  
556.     final TreeMap.Entry<K,V> absLower(K key) {  
557.         // 只有在“key太大”的情况下，(absHighest)返回的Entry才是“小于key的最大Entry”  
558.         // 其它情况下不行。例如，当包含“结束节点”时，absHighest()返回的是最大Entry了,而不一定是“小于key的最大Entry”！  
559.         if (tooHigh(key))  
560.             return absHighest();  
561.         // 获取"小于key的最大的Entry"  
562.         TreeMap.Entry<K,V> e = m.getLowerEntry(key);  
563.         return (e == null || tooLow(e.key)) ? null : e;  
564.     }  
565.   
566.     // 返回“大于最大节点中的最小节点”，不存在的话，返回null  
567.     final TreeMap.Entry<K,V> absHighFence() {  
568.         return (toEnd ? null : (hiInclusive ?  
569.                                 m.getHigherEntry(hi) :  
570.                                 m.getCeilingEntry(hi)));  
571.     }  
572.   
573.     // 返回“小于最小节点中的最大节点”，不存在的话，返回null  
574.     final TreeMap.Entry<K,V> absLowFence() {  
575.         return (fromStart ? null : (loInclusive ?  
576.                                     m.getLowerEntry(lo) :  
577.                                     m.getFloorEntry(lo)));  
578.     }  
579.   
580.     // 下面几个abstract方法是需要NavigableSubMap的实现类实现的方法  
581.     abstract TreeMap.Entry<K,V> subLowest();  
582.     abstract TreeMap.Entry<K,V> subHighest();  
583.     abstract TreeMap.Entry<K,V> subCeiling(K key);  
584.     abstract TreeMap.Entry<K,V> subHigher(K key);  
585.     abstract TreeMap.Entry<K,V> subFloor(K key);  
586.     abstract TreeMap.Entry<K,V> subLower(K key);  
587.   
588.     // 返回“顺序”的键迭代器  
589.     abstract Iterator<K> keyIterator();  
590.   
591.     // 返回“逆序”的键迭代器  
592.     abstract Iterator<K> descendingKeyIterator();  
593.   
594.     // 返回SubMap是否为空。空的话，返回true，否则返回false  
595.     public boolean isEmpty() {  
596.         return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();  
597.     }  
598.     // 返回SubMap的大小  
599.     public int size() {  
600.         return (fromStart && toEnd) ? m.size() : entrySet().size();  
601.     }  
602.     // 返回SubMap是否包含键key  
603.     public final boolean containsKey(Object key) {  
604.         return inRange(key) && m.containsKey(key);  
605.     }  
606.     // 将key-value 插入SubMap中  
607.     public final V put(K key, V value) {  
608.         if (!inRange(key))  
609.             throw new IllegalArgumentException("key out of range");  
610.         return m.put(key, value);  
611.     }  
612.     // 获取key对应值  
613.     public final V get(Object key) {  
614.         return !inRange(key) ? null :  m.get(key);  
615.     }  
616.     // 删除key对应的键值对  
617.     public final V remove(Object key) {  
618.         return !inRange(key) ? null : m.remove(key);  
619.     }  
620.     // 获取“大于/等于key的最小键值对”  
621.     public final Map.Entry<K,V> ceilingEntry(K key) {  
622.         return exportEntry(subCeiling(key));  
623.     }  
624.     // 获取“大于/等于key的最小键”  
625.     public final K ceilingKey(K key) {  
626.         return keyOrNull(subCeiling(key));  
627.     }  
628.     // 获取“大于key的最小键值对”  
629.     public final Map.Entry<K,V> higherEntry(K key) {  
630.         return exportEntry(subHigher(key));  
631.     }  
632.     // 获取“大于key的最小键”  
633.     public final K higherKey(K key) {  
634.         return keyOrNull(subHigher(key));  
635.     }  
636.     // 获取“小于/等于key的最大键值对”  
637.     public final Map.Entry<K,V> floorEntry(K key) {  
638.         return exportEntry(subFloor(key));  
639.     }  
640.     // 获取“小于/等于key的最大键”  
641.     public final K floorKey(K key) {  
642.         return keyOrNull(subFloor(key));  
643.     }  
644.     // 获取“小于key的最大键值对”  
645.     public final Map.Entry<K,V> lowerEntry(K key) {  
646.         return exportEntry(subLower(key));  
647.     }  
648.     // 获取“小于key的最大键”  
649.     public final K lowerKey(K key) {  
650.         return keyOrNull(subLower(key));  
651.     }  
652.     // 获取"SubMap的第一个键"  
653.     public final K firstKey() {  
654.         return key(subLowest());  
655.     }  
656.     // 获取"SubMap的最后一个键"  
657.     public final K lastKey() {  
658.         return key(subHighest());  
659.     }  
660.     // 获取"SubMap的第一个键值对"  
661.     public final Map.Entry<K,V> firstEntry() {  
662.         return exportEntry(subLowest());  
663.     }  
664.     // 获取"SubMap的最后一个键值对"  
665.     public final Map.Entry<K,V> lastEntry() {  
666.         return exportEntry(subHighest());  
667.     }  
668.     // 返回"SubMap的第一个键值对"，并从SubMap中删除改键值对  
669.     public final Map.Entry<K,V> pollFirstEntry() {  
670.         TreeMap.Entry<K,V> e = subLowest();  
671.         Map.Entry<K,V> result = exportEntry(e);  
672.         if (e != null)  
673.             m.deleteEntry(e);  
674.         return result;  
675.     }  
676.     // 返回"SubMap的最后一个键值对"，并从SubMap中删除改键值对  
677.     public final Map.Entry<K,V> pollLastEntry() {  
678.         TreeMap.Entry<K,V> e = subHighest();  
679.         Map.Entry<K,V> result = exportEntry(e);  
680.         if (e != null)  
681.             m.deleteEntry(e);  
682.         return result;  
683.     }  
684.   
685.     // Views  
686.     transient NavigableMap<K,V> descendingMapView = null;  
687.     transient EntrySetView entrySetView = null;  
688.     transient KeySet<K> navigableKeySetView = null;  
689.     // 返回NavigableSet对象，实际上返回的是当前对象的"Key集合"。   
690.     public final NavigableSet<K> navigableKeySet() {  
691.         KeySet<K> nksv = navigableKeySetView;  
692.         return (nksv != null) ? nksv :  
693.             (navigableKeySetView = new TreeMap.KeySet(this));  
694.     }  
695.     // 返回"Key集合"对象  
696.     public final Set<K> keySet() {  
697.         return navigableKeySet();  
698.     }  
699.     // 返回“逆序”的Key集合  
700.     public NavigableSet<K> descendingKeySet() {  
701.         return descendingMap().navigableKeySet();  
702.     }  
703.     // 排列fromKey(包含) 到 toKey(不包含) 的子map  
704.     public final SortedMap<K,V> subMap(K fromKey, K toKey) {  
705.         return subMap(fromKey, true, toKey, false);  
706.     }  
707.     // 返回当前Map的头部(从第一个节点 到 toKey, 不包括toKey)  
708.     public final SortedMap<K,V> headMap(K toKey) {  
709.         return headMap(toKey, false);  
710.     }  
711.     // 返回当前Map的尾部[从 fromKey(包括fromKeyKey) 到 最后一个节点]  
712.     public final SortedMap<K,V> tailMap(K fromKey) {  
713.         return tailMap(fromKey, true);  
714.     }  
715.   
716.     // Map的Entry的集合  
717.     abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {  
718.         private transient int size = -1, sizeModCount;  
719.   
720.         public int size() {  
721.             if (fromStart && toEnd)  
722.                 return m.size();  
723.             if (size == -1 || sizeModCount != m.modCount) {  
724.                 sizeModCount = m.modCount;  
725.                 size = 0;  
726.                 Iterator i = iterator();  
727.                 while (i.hasNext()) {  
728.                     size++;  
729.                     i.next();  
730.                 }  
731.             }  
732.             return size;  
733.         }  
734.   
735.         public boolean isEmpty() {  
736.             TreeMap.Entry<K,V> n = absLowest();  
737.             return n == null || tooHigh(n.key);  
738.         }  
739.   
740.         public boolean contains(Object o) {  
741.             if (!(o instanceof Map.Entry))  
742.                 return false;  
743.             Map.Entry<K,V> entry = (Map.Entry<K,V>) o;  
744.             K key = entry.getKey();  
745.             if (!inRange(key))  
746.                 return false;  
747.             TreeMap.Entry node = m.getEntry(key);  
748.             return node != null &&  
749.                 valEquals(node.getValue(), entry.getValue());  
750.         }  
751.   
752.         public boolean remove(Object o) {  
753.             if (!(o instanceof Map.Entry))  
754.                 return false;  
755.             Map.Entry<K,V> entry = (Map.Entry<K,V>) o;  
756.             K key = entry.getKey();  
757.             if (!inRange(key))  
758.                 return false;  
759.             TreeMap.Entry<K,V> node = m.getEntry(key);  
760.             if (node!=null && valEquals(node.getValue(),  
761.                                         entry.getValue())) {  
762.                 m.deleteEntry(node);  
763.                 return true;  
764.             }  
765.             return false;  
766.         }  
767.     }  
768.   
769.     // SubMap的迭代器  
770.     abstract class SubMapIterator<T> implements Iterator<T> {  
771.         TreeMap.Entry<K,V> lastReturned;  
772.         TreeMap.Entry<K,V> next;  
773.         final Object fenceKey;  
774.         int expectedModCount;  
775.   
776.         SubMapIterator(TreeMap.Entry<K,V> first,  
777.                        TreeMap.Entry<K,V> fence) {  
778.             expectedModCount = m.modCount;  
779.             lastReturned = null;  
780.             next = first;  
781.             fenceKey = fence == null ? UNBOUNDED : fence.key;  
782.         }  
783.   
784.         public final boolean hasNext() {  
785.             return next != null && next.key != fenceKey;  
786.         }  
787.   
788.         final TreeMap.Entry<K,V> nextEntry() {  
789.             TreeMap.Entry<K,V> e = next;  
790.             if (e == null || e.key == fenceKey)  
791.                 throw new NoSuchElementException();  
792.             if (m.modCount != expectedModCount)  
793.                 throw new ConcurrentModificationException();  
794.             next = successor(e);  
795.             lastReturned = e;  
796.             return e;  
797.         }  
798.   
799.         final TreeMap.Entry<K,V> prevEntry() {  
800.             TreeMap.Entry<K,V> e = next;  
801.             if (e == null || e.key == fenceKey)  
802.                 throw new NoSuchElementException();  
803.             if (m.modCount != expectedModCount)  
804.                 throw new ConcurrentModificationException();  
805.             next = predecessor(e);  
806.             lastReturned = e;  
807.             return e;  
808.         }  
809.         // 删除当前节点(用于“升序的SubMap”)。  
810.         // 删除之后，可以继续升序遍历；红黑树特性没变。  
811.         final void removeAscending() {  
812.             if (lastReturned == null)  
813.                 throw new IllegalStateException();  
814.             if (m.modCount != expectedModCount)  
815.                 throw new ConcurrentModificationException();  
816.             // 这里重点强调一下“为什么当lastReturned的左右孩子都不为空时，要将其赋值给next”。  
817.             // 目的是为了“删除lastReturned节点之后，next节点指向的仍然是下一个节点”。  
818.             //     根据“红黑树”的特性可知：  
819.             //     当被删除节点有两个儿子时。那么，首先把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。  
820.             //     这意味着“当被删除节点有两个儿子时，删除当前节点之后，'新的当前节点'实际上是‘原有的后继节点(即下一个节点)’”。  
821.             //     而此时next仍然指向"新的当前节点"。也就是说next是仍然是指向下一个节点；能继续遍历红黑树。  
822.             if (lastReturned.left != null && lastReturned.right != null)  
823.                 next = lastReturned;  
824.             m.deleteEntry(lastReturned);  
825.             lastReturned = null;  
826.             expectedModCount = m.modCount;  
827.         }  
828.         // 删除当前节点(用于“降序的SubMap”)。  
829.         // 删除之后，可以继续降序遍历；红黑树特性没变。  
830.         final void removeDescending() {  
831.             if (lastReturned == null)  
832.                 throw new IllegalStateException();  
833.             if (m.modCount != expectedModCount)  
834.                 throw new ConcurrentModificationException();  
835.             m.deleteEntry(lastReturned);  
836.             lastReturned = null;  
837.             expectedModCount = m.modCount;  
838.         }  
839.   
840.     }  
841.     // SubMap的Entry迭代器，它只支持升序操作，继承于SubMapIterator  
842.     final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {  
843.         SubMapEntryIterator(TreeMap.Entry<K,V> first,  
844.                             TreeMap.Entry<K,V> fence) {  
845.             super(first, fence);  
846.         }  
847.         public Map.Entry<K,V> next() {  
848.             return nextEntry();  
849.         }  
850.         public void remove() {  
851.             removeAscending();  
852.         }  
853.     }  
854.     // SubMap的Key迭代器，它只支持升序操作，继承于SubMapIterator  
855.     final class SubMapKeyIterator extends SubMapIterator<K> {  
856.         SubMapKeyIterator(TreeMap.Entry<K,V> first,  
857.                           TreeMap.Entry<K,V> fence) {  
858.             super(first, fence);  
859.         }  
860.         // 获取下一个节点(升序)  
861.         public K next() {  
862.             return nextEntry().key;  
863.         }  
864.         // 删除当前节点(升序)  
865.         public void remove() {  
866.             removeAscending();  
867.         }  
868.     }  
869.     // 降序SubMap的Entry迭代器，它只支持降序操作，继承于SubMapIterator  
870.     final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {  
871.         DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,  
872.                                       TreeMap.Entry<K,V> fence) {  
873.             super(last, fence);  
874.         }  
875.         // 获取下一个节点(降序)  
876.         public Map.Entry<K,V> next() {  
877.             return prevEntry();  
878.         }  
879.         // 删除当前节点(降序)  
880.         public void remove() {  
881.             removeDescending();  
882.         }  
883.     }  
884.     // 降序SubMap的Key迭代器，它只支持降序操作，继承于SubMapIterator  
885.     final class DescendingSubMapKeyIterator extends SubMapIterator<K> {  
886.         DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,  
887.                                     TreeMap.Entry<K,V> fence) {  
888.             super(last, fence);  
889.         }  
890.         // 获取下一个节点(降序)  
891.         public K next() {  
892.             return prevEntry().key;  
893.         }  
894.         // 删除当前节点(降序)  
895.         public void remove() {  
896.             removeDescending();  
897.         }  
898.     }  
899. }  
900.   
901. // 升序的SubMap，继承于NavigableSubMap  
902. static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {  
903.     private static final long serialVersionUID = 912986545866124060L;  
904.   
905.     AscendingSubMap(TreeMap<K,V> m,  
906.                     boolean fromStart, K lo, boolean loInclusive,  
907.                     boolean toEnd,     K hi, boolean hiInclusive) {  
908.         super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);  
909.     }  
910.   
911.     public Comparator<? super K> comparator() {  
912.         return m.comparator();  
913.     }  
914.     // 获取“子Map”。  
915.     // 范围是从fromKey 到 toKey；fromInclusive是是否包含fromKey的标记，toInclusive是是否包含toKey的标记  
916.     public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,  
917.                                     K toKey,   boolean toInclusive) {  
918.         if (!inRange(fromKey, fromInclusive))  
919.             throw new IllegalArgumentException("fromKey out of range");  
920.         if (!inRange(toKey, toInclusive))  
921.             throw new IllegalArgumentException("toKey out of range");  
922.         return new AscendingSubMap(m,  
923.                                    false, fromKey, fromInclusive,  
924.                                    false, toKey,   toInclusive);  
925.     }  
926.       
927.     // 获取“Map的头部”。  
928.     // 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记  
929.     public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {  
930.         if (!inRange(toKey, inclusive))  
931.             throw new IllegalArgumentException("toKey out of range");  
932.         return new AscendingSubMap(m,  
933.                                    fromStart, lo,    loInclusive,  
934.                                    false,     toKey, inclusive);  
935.     }  
936.       
937.     // 获取“Map的尾部”。  
938.     // 范围是从 fromKey 到 最后一个节点，inclusive是是否包含fromKey的标记  
939.     public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {  
940.         if (!inRange(fromKey, inclusive))  
941.             throw new IllegalArgumentException("fromKey out of range");  
942.         return new AscendingSubMap(m,  
943.                                    false, fromKey, inclusive,  
944.                                    toEnd, hi,      hiInclusive);  
945.     }  
946.     // 获取对应的降序Map  
947.     public NavigableMap<K,V> descendingMap() {  
948.         NavigableMap<K,V> mv = descendingMapView;  
949.         return (mv != null) ? mv :  
950.             (descendingMapView =  
951.              new DescendingSubMap(m,  
952.                                   fromStart, lo, loInclusive,  
953.                                   toEnd,     hi, hiInclusive));  
954.     }  
955.     // 返回“升序Key迭代器”  
956.     Iterator<K> keyIterator() {  
957.         return new SubMapKeyIterator(absLowest(), absHighFence());  
958.     }  
959.     // 返回“降序Key迭代器”  
960.     Iterator<K> descendingKeyIterator() {  
961.         return new DescendingSubMapKeyIterator(absHighest(), absLowFence());  
962.     }  
963.     // “升序EntrySet集合”类  
964.     // 实现了iterator()  
965.     final class AscendingEntrySetView extends EntrySetView {  
966.         public Iterator<Map.Entry<K,V>> iterator() {  
967.             return new SubMapEntryIterator(absLowest(), absHighFence());  
968.         }  
969.     }  
970.     // 返回“升序EntrySet集合”  
971.     public Set<Map.Entry<K,V>> entrySet() {  
972.         EntrySetView es = entrySetView;  
973.         return (es != null) ? es : new AscendingEntrySetView();  
974.     }  
975.   
976.     TreeMap.Entry<K,V> subLowest()       { return absLowest(); }  
977.     TreeMap.Entry<K,V> subHighest()      { return absHighest(); }  
978.     TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }  
979.     TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }  
980.     TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }  
981.     TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }  
982. }  
983.   
984. // 降序的SubMap，继承于NavigableSubMap  
985. // 相比于升序SubMap，它的实现机制是将“SubMap的比较器反转”！  
986. static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {  
987.     private static final long serialVersionUID = 912986545866120460L;  
988.     DescendingSubMap(TreeMap<K,V> m,  
989.                     boolean fromStart, K lo, boolean loInclusive,  
990.                     boolean toEnd,     K hi, boolean hiInclusive) {  
991.         super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);  
992.     }  
993.     // 反转的比较器：是将原始比较器反转得到的。  
994.     private final Comparator<? super K> reverseComparator =  
995.         Collections.reverseOrder(m.comparator);  
996.     // 获取反转比较器  
997.     public Comparator<? super K> comparator() {  
998.         return reverseComparator;  
999.     }  
1000.     // 获取“子Map”。  
1001.     // 范围是从fromKey 到 toKey；fromInclusive是是否包含fromKey的标记，toInclusive是是否包含toKey的标记  
1002.     public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,  
1003.                                     K toKey,   boolean toInclusive) {  
1004.         if (!inRange(fromKey, fromInclusive))  
1005.             throw new IllegalArgumentException("fromKey out of range");  
1006.         if (!inRange(toKey, toInclusive))  
1007.             throw new IllegalArgumentException("toKey out of range");  
1008.         return new DescendingSubMap(m,  
1009.                                     false, toKey,   toInclusive,  
1010.                                     false, fromKey, fromInclusive);  
1011.     }  
1012.     // 获取“Map的头部”。  
1013.     // 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记  
1014.     public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {  
1015.         if (!inRange(toKey, inclusive))  
1016.             throw new IllegalArgumentException("toKey out of range");  
1017.         return new DescendingSubMap(m,  
1018.                                     false, toKey, inclusive,  
1019.                                     toEnd, hi,    hiInclusive);  
1020.     }  
1021.     // 获取“Map的尾部”。  
1022.     // 范围是从 fromKey 到 最后一个节点，inclusive是是否包含fromKey的标记  
1023.     public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {  
1024.         if (!inRange(fromKey, inclusive))  
1025.             throw new IllegalArgumentException("fromKey out of range");  
1026.         return new DescendingSubMap(m,  
1027.                                     fromStart, lo, loInclusive,  
1028.                                     false, fromKey, inclusive);  
1029.     }  
1030.     // 获取对应的降序Map  
1031.     public NavigableMap<K,V> descendingMap() {  
1032.         NavigableMap<K,V> mv = descendingMapView;  
1033.         return (mv != null) ? mv :  
1034.             (descendingMapView =  
1035.              new AscendingSubMap(m,  
1036.                                  fromStart, lo, loInclusive,  
1037.                                  toEnd,     hi, hiInclusive));  
1038.     }  
1039.     // 返回“升序Key迭代器”  
1040.     Iterator<K> keyIterator() {  
1041.         return new DescendingSubMapKeyIterator(absHighest(), absLowFence());  
1042.     }  
1043.     // 返回“降序Key迭代器”  
1044.     Iterator<K> descendingKeyIterator() {  
1045.         return new SubMapKeyIterator(absLowest(), absHighFence());  
1046.     }  
1047.     // “降序EntrySet集合”类  
1048.     // 实现了iterator()  
1049.     final class DescendingEntrySetView extends EntrySetView {  
1050.         public Iterator<Map.Entry<K,V>> iterator() {  
1051.             return new DescendingSubMapEntryIterator(absHighest(), absLowFence());  
1052.         }  
1053.     }  
1054.     // 返回“降序EntrySet集合”  
1055.     public Set<Map.Entry<K,V>> entrySet() {  
1056.         EntrySetView es = entrySetView;  
1057.         return (es != null) ? es : new DescendingEntrySetView();  
1058.     }  
1059.   
1060.     TreeMap.Entry<K,V> subLowest()       { return absHighest(); }  
1061.     TreeMap.Entry<K,V> subHighest()      { return absLowest(); }  
1062.     TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }  
1063.     TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }  
1064.     TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }  
1065.     TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }  
1066. }  
1067. // SubMap是旧版本的类，新的Java中没有用到。  
1068. private class SubMap extends AbstractMap<K,V>  
1069.     implements SortedMap<K,V>, java.io.Serializable {  
1070.     private static final long serialVersionUID = -6520786458950516097L;  
1071.     private boolean fromStart = false, toEnd = false;  
1072.     private K fromKey, toKey;  
1073.     private Object readResolve() {  
1074.         return new AscendingSubMap(TreeMap.this,  
1075.                                    fromStart, fromKey, true,  
1076.                                    toEnd, toKey, false);  
1077.     }  
1078.     public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }  
1079.     public K lastKey() { throw new InternalError(); }  
1080.     public K firstKey() { throw new InternalError(); }  
1081.     public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }  
1082.     public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }  
1083.     public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }  
1084.     public Comparator<? super K> comparator() { throw new InternalError(); }  
1085. }  
1086.   
1087. private static final boolean RED   = false;  
1088. private static final boolean BLACK = true;  
1089.   
1090. // 返回“节点t的后继节点”  
1091. static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {  
1092.     if (t == null)  
1093.         return null;  
1094.     else if (t.right != null) {  
1095.         Entry<K,V> p = t.right;  
1096.         while (p.left != null)  
1097.             p = p.left;  
1098.         return p;  
1099.     } else {  
1100.         Entry<K,V> p = t.parent;  
1101.         Entry<K,V> ch = t;  
1102.         while (p != null && ch == p.right) {  
1103.             ch = p;  
1104.             p = p.parent;  
1105.         }  
1106.         return p;  
1107.     }  
1108. }  
1109.   
1110. // 返回“节点t的前继节点”  
1111. static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {  
1112.     if (t == null)  
1113.         return null;  
1114.     else if (t.left != null) {  
1115.         Entry<K,V> p = t.left;  
1116.         while (p.right != null)  
1117.             p = p.right;  
1118.         return p;  
1119.     } else {  
1120.         Entry<K,V> p = t.parent;  
1121.         Entry<K,V> ch = t;  
1122.         while (p != null && ch == p.left) {  
1123.             ch = p;  
1124.             p = p.parent;  
1125.         }  
1126.         return p;  
1127.     }  
1128. }  
1129.   
1130. // 返回“节点p的颜色”  
1131. // 根据“红黑树的特性”可知：空节点颜色是黑色。  
1132. private static <K,V> boolean colorOf(Entry<K,V> p) {  
1133.     return (p == null ? BLACK : p.color);  
1134. }  
1135. // 返回“节点p的父节点”  
1136. private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {  
1137.     return (p == null ? null: p.parent);  
1138. }  
1139. // 设置“节点p的颜色为c”  
1140. private static <K,V> void setColor(Entry<K,V> p, boolean c) {  
1141.     if (p != null)  
1142.         p.color = c;  
1143. }  
1144. // 设置“节点p的左孩子”  
1145. private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {  
1146.     return (p == null) ? null: p.left;  
1147. }  
1148. // 设置“节点p的右孩子”  
1149. private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {  
1150.     return (p == null) ? null: p.right;  
1151. }  
1152.   
1153. private static final long serialVersionUID = 919286545866124006L;  
1154.   
1155. // java.io.Serializable的写入函数  
1156. // 将TreeMap的“容量，所有的Entry”都写入到输出流中    
1157. private void writeObject(java.io.ObjectOutputStream s)  
1158.     throws java.io.IOException {  
1159.     // Write out the Comparator and any hidden stuff  
1160.     s.defaultWriteObject();  
1161.   
1162.     // Write out size (number of Mappings)  
1163.     s.writeInt(size);  
1164.   
1165.     // Write out keys and values (alternating)  
1166.     for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {  
1167.         Map.Entry<K,V> e = i.next();  
1168.         s.writeObject(e.getKey());  
1169.         s.writeObject(e.getValue());  
1170.     }  
1171. }  
1172.   
1173. // java.io.Serializable的读取函数：根据写入方式读出  
1174. // 先将TreeMap的“容量、所有的Entry”依次读出  
1175. private void readObject(final java.io.ObjectInputStream s)  
1176.     throws java.io.IOException, ClassNotFoundException {  
1177.     // Read in the Comparator and any hidden stuff  
1178.     s.defaultReadObject();  
1179.   
1180.     // Read in size  
1181.     int size = s.readInt();  
1182.   
1183.     buildFromSorted(size, null, s, null);  
1184. }  
1185.   
1186. /** Intended to be called only from TreeSet.readObject */  
1187. void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)  
1188.     throws java.io.IOException, ClassNotFoundException {  
1189.     buildFromSorted(size, null, s, defaultVal);  
1190. }  
1191.   
1192. /** Intended to be called only from TreeSet.addAll */  
1193. void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {  
1194.     try {  
1195.         buildFromSorted(set.size(), set.iterator(), null, defaultVal);  
1196.     } catch (java.io.IOException cannotHappen) {  
1197.     } catch (ClassNotFoundException cannotHappen) {  
1198.     }  
1199. }  
1200. // 根据已经一个排好序的map创建一个TreeMap  
1201. private void buildFromSorted(int size, Iterator it,  
1202.                              java.io.ObjectInputStream str,  
1203.                              V defaultVal)  
1204.     throws  java.io.IOException, ClassNotFoundException {  
1205.     this.size = size;  
1206.     root = buildFromSorted(0, 0, size-1, computeRedLevel(size),  
1207.                            it, str, defaultVal);  
1208. }  
1209. // 根据已经一个排好序的map创建一个TreeMap  
1210. // 将map中的元素逐个添加到TreeMap中，并返回map的中间元素作为根节点。  
1211. private final Entry<K,V> buildFromSorted(int level, int lo, int hi,  
1212.                                          int redLevel,  
1213.                                          Iterator it,  
1214.                                          java.io.ObjectInputStream str,  
1215.                                          V defaultVal)  
1216.     throws  java.io.IOException, ClassNotFoundException {  
1217.      
1218.     if (hi < lo) return null;  
1219.     // 获取中间元素  
1220.     int mid = (lo + hi) >>> 1;  
1221.   
1222.     Entry<K,V> left  = null;  
1223.     // 若lo小于mid，则递归调用获取(middel的)左孩子。  
1224.     if (lo < mid)  
1225.         left = buildFromSorted(level+1, lo, mid - 1, redLevel,  
1226.                                it, str, defaultVal);  
1227.   
1228.     // 获取middle节点对应的key和value  
1229.     K key;  
1230.     V value;  
1231.     if (it != null) {  
1232.         if (defaultVal==null) {  
1233.             Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();  
1234.             key = entry.getKey();  
1235.             value = entry.getValue();  
1236.         } else {  
1237.             key = (K)it.next();  
1238.             value = defaultVal;  
1239.         }  
1240.     } else { // use stream  
1241.         key = (K) str.readObject();  
1242.         value = (defaultVal != null ? defaultVal : (V) str.readObject());  
1243.     }  
1244.     // 创建middle节点  
1245.     Entry<K,V> middle =  new Entry<>(key, value, null);  
1246.   
1247.     // 若当前节点的深度=红色节点的深度，则将节点着色为红色。  
1248.     if (level == redLevel)  
1249.         middle.color = RED;  
1250.     // 设置middle为left的父亲，left为middle的左孩子  
1251.     if (left != null) {  
1252.         middle.left = left;  
1253.         left.parent = middle;  
1254.     }  
1255.   
1256.     if (mid < hi) {  
1257.         // 递归调用获取(middel的)右孩子。  
1258.         Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,  
1259.                                            it, str, defaultVal);  
1260.         // 设置middle为left的父亲，left为middle的左孩子  
1261.         middle.right = right;  
1262.         right.parent = middle;  
1263.     }  
1264.   
1265.     return middle;  
1266. }  
1267. // 计算节点树为sz的最大深度，也是红色节点的深度值。  
1268. private static int computeRedLevel(int sz) {  
1269.     int level = 0;  
1270.     for (int m = sz - 1; m >= 0; m = m / 2 - 1)  
1271.         level++;  
1272.     return level;  
1273. }  

2. TreeMap的遍历方式

       TreeMap的遍历方式一般分为两步：

        1. 先通过entrySet()或keySet()或value()方法获得相应的集合；

        2. 通过Iterator迭代器遍历上面得到的集合。

2.1 遍历TreeMap的Entry

[java]  view plain  copy

 

1. // 假设map是TreeMap对象  
2. // map中的key是String类型，value是Integer类型  
3. Integer integ = null;  
4. Iterator iter = map.entrySet().iterator();  
5. while(iter.hasNext()) {  
6.     Map.Entry entry = (Map.Entry)iter.next();  
7.     // 获取key  
8.     key = (String)entry.getKey();  
9.     // 获取value  
10.     integ = (Integer)entry.getValue();  
11. }  

2.2 遍历TreeMap的key

[java]  view plain  copy

 

1. // 假设map是TreeMap对象  
2. // map中的key是String类型，value是Integer类型  
3. String key = null;  
4. Integer integ = null;  
5. Iterator iter = map.keySet().iterator();  
6. while (iter.hasNext()) {  
7.         // 获取key  
8.     key = (String)iter.next();  
9.         // 根据key，获取value  
10.     integ = (Integer)map.get(key);  
11. }  

2.3 遍历TreeMap的value

[java]  view plain  copy

 

1. // 假设map是TreeMap对象  
2. // map中的key是String类型，value是Integer类型  
3. Integer value = null;  
4. Collection c = map.values();  
5. Iterator iter= c.iterator();  
6. while (iter.hasNext()) {  
7.     value = (Integer)iter.next();  
8. }  

_____________________________________________________________________________________________________________________________________________________

-----乐于分享，共同进步！