Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例
1 package ;
2
3 public class TreeMap<K,V>
4 extends AbstractMap<K,V>
5 implements NavigableMap<K,V>, Cloneable,
6 {
7
8 // 比较器。用来给TreeMap排序
9 private final Comparator<? super K> comparator;
10
11 // TreeMap是红黑树实现的，root是红黑书的根节点
12 private transient Entry<K,V> root = null;
13
14 // 红黑树的节点总数
15 private transient int size = 0;
16
17 // 记录红黑树的修改次数
18 private transient int modCount = 0;
19
20 // 默认构造函数
21 public TreeMap() {
22 comparator = null;
23 }
24
25 // 带比较器的构造函数
26 public TreeMap(Comparator<? super K> comparator) {
27 this.comparator = comparator;
28 }
29
30 // 带Map的构造函数，Map会成为TreeMap的子集
31 public TreeMap(Map<? extends K, ? extends V> m) {
32 comparator = null;
33 putAll(m);
34 }
35
36 // 带SortedMap的构造函数，SortedMap会成为TreeMap的子集
37 public TreeMap(SortedMap<K, ? extends V> m) {
38 comparator = ();
39 try {
40 buildFromSorted((), ().iterator(), null, null);
41 } catch ( cannotHappen) {
42 } catch (ClassNotFoundException cannotHappen) {
43 }
44 }
45
46 public int size() {
47 return size;
48 }
49
50 // 返回TreeMap中是否保护“键(key)”
51 public boolean containsKey(Object key) {
52 return getEntry(key) != null;
53 }
54
55 // 返回TreeMap中是否保护"值(value)"
56 public boolean containsValue(Object value) {
57 // getFirstEntry() 是返回红黑树的第一个节点
58 // successor(e) 是获取节点e的后继节点
59 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
60 if (valEquals(value, ))
61 return true;
62 return false;
63 }
64
65 // 获取“键(key)”对应的“值(value)”
66 public V get(Object key) {
67 // 获取“键”为key的节点(p)
68 Entry<K,V> p = getEntry(key);
69 // 若节点(p)为null，返回null；否则，返回节点对应的值
70 return (p==null ? null : );
71 }
72
73 public Comparator<? super K> comparator() {
74 return comparator;
75 }
76
77 // 获取第一个节点对应的key
78 public K firstKey() {
79 return key(getFirstEntry());
80 }
81
82 // 获取最后一个节点对应的key
83 public K lastKey() {
84 return key(getLastEntry());
85 }
86
87 // 将map中的全部节点添加到TreeMap中
88 public void putAll(Map<? extends K, ? extends V> map) {
89 // 获取map的大小
90 int mapSize = ();
91 // 如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value对”
92 if (size==0 && mapSize!=0 && map instanceof SortedMap) {
93 Comparator c = ((SortedMap)map).comparator();
94 // 如果TreeMap和map的比较器相等；
95 // 则将map的元素全部拷贝到TreeMap中，然后返回！
96 if (c == comparator || (c != null && (comparator))) {
97 ++modCount;
98 try {
99 buildFromSorted(mapSize, ().iterator(),
100 null, null);
101 } catch ( cannotHappen) {
102 } catch (ClassNotFoundException cannotHappen) {
103 }
104 return;
105 }
106 }
107 // 调用AbstractMap中的putAll();
108 // AbstractMap中的putAll()又会调用到TreeMap的put()
109 super.putAll(map);
110 }
111
112 // 获取TreeMap中“键”为key的节点
113 final Entry<K,V> getEntry(Object key) {
114 // 若“比较器”为null，则通过getEntryUsingComparator()获取“键”为key的节点
115 if (comparator != null)
116 return getEntryUsingComparator(key);
117 if (key == null)
118 throw new NullPointerException();
119 Comparable<? super K> k = (Comparable<? super K>) key;
120 // 将p设为根节点
121 Entry<K,V> p = root;
122 while (p != null) {
123 int cmp = ();
124 // 若“p的key” < key，则p=“p的左孩子”
125 if (cmp < 0)
126 p = ;
127 // 若“p的key” > key，则p=“p的左孩子”
128 else if (cmp > 0)
129 p = ;
130 // 若“p的key” = key，则返回节点p
131 else
132 return p;
133 }
134 return null;
135 }
136
137 // 获取TreeMap中“键”为key的节点(对应TreeMap的比较器不是null的情况)
138 final Entry<K,V> getEntryUsingComparator(Object key) {
139 K k = (K) key;
140 Comparator<? super K> cpr = comparator;
141 if (cpr != null) {
142 // 将p设为根节点
143 Entry<K,V> p = root;
144 while (p != null) {
145 int cmp = (k, );
146 // 若“p的key” < key，则p=“p的左孩子”
147 if (cmp < 0)
148 p = ;
149 // 若“p的key” > key，则p=“p的左孩子”
150 else if (cmp > 0)
151 p = ;
152 // 若“p的key” = key，则返回节点p
153 else
154 return p;
155 }
156 }
157 return null;
158 }
159
160 // 获取TreeMap中不小于key的最小的节点；
161 // 若不存在(即TreeMap中所有节点的键都比key大)，就返回null
162 final Entry<K,V> getCeilingEntry(K key) {
163 Entry<K,V> p = root;
164 while (p != null) {
165 int cmp = compare(key, );
166 // 情况一：若“p的key” > key。
167 // 若 p 存在左孩子，则设 p=“p的左孩子”；
168 // 否则，返回p
169 if (cmp < 0) {
170 if ( != null)
171 p = ;
172 else
173 return p;
174 // 情况二：若“p的key” < key。
175 } else if (cmp > 0) {
176 // 若 p 存在右孩子，则设 p=“p的右孩子”
177 if ( != null) {
178 p = ;
179 } else {
180 // 若 p 不存在右孩子，则找出 p 的后继节点，并返回
181 // 注意：这里返回的 “p的后继节点”有2种可能性：第一，null；第二，TreeMap中大于key的最小的节点。
182 // 理解这一点的核心是，getCeilingEntry是从root开始遍历的。
183 // 若getCeilingEntry能走到这一步，那么，它之前“已经遍历过的节点的key”都 > key。
184 // 能理解上面所说的，那么就很容易明白，为什么“p的后继节点”又2种可能性了。
185 Entry<K,V> parent = ;
186 Entry<K,V> ch = p;
187 while (parent != null && ch == ) {
188 ch = parent;
189 parent = ;
190 }
191 return parent;
192 }
193 // 情况三：若“p的key” = key。
194 } else
195 return p;
196 }
197 return null;
198 }
199
200 // 获取TreeMap中不大于key的最大的节点；
201 // 若不存在(即TreeMap中所有节点的键都比key小)，就返回null
202 // getFloorEntry的原理和getCeilingEntry类似，这里不再多说。
203 final Entry<K,V> getFloorEntry(K key) {
204 Entry<K,V> p = root;
205 while (p != null) {
206 int cmp = compare(key, );
207 if (cmp > 0) {
208 if ( != null)
209 p = ;
210 else
211 return p;
212 } else if (cmp < 0) {
213 if ( != null) {
214 p = ;
215 } else {
216 Entry<K,V> parent = ;
217 Entry<K,V> ch = p;
218 while (parent != null && ch == ) {
219 ch = parent;
220 parent = ;
221 }
222 return parent;
223 }
224 } else
225 return p;
226
227 }
228 return null;
229 }
230
231 // 获取TreeMap中大于key的最小的节点。
232 // 若不存在，就返回null。
233 // 请参照getCeilingEntry来对getHigherEntry进行理解。
234 final Entry<K,V> getHigherEntry(K key) {
235 Entry<K,V> p = root;
236 while (p != null) {
237 int cmp = compare(key, );
238 if (cmp < 0) {
239 if ( != null)
240 p = ;
241 else
242 return p;
243 } else {
244 if ( != null) {
245 p = ;
246 } else {
247 Entry<K,V> parent = ;
248 Entry<K,V> ch = p;
249 while (parent != null && ch == ) {
250 ch = parent;
251 parent = ;
252 }
253 return parent;
254 }
255 }
256 }
257 return null;
258 }
259
260 // 获取TreeMap中小于key的最大的节点。
261 // 若不存在，就返回null。
262 // 请参照getCeilingEntry来对getLowerEntry进行理解。
263 final Entry<K,V> getLowerEntry(K key) {
264 Entry<K,V> p = root;
265 while (p != null) {
266 int cmp = compare(key, );
267 if (cmp > 0) {
268 if ( != null)
269 p = ;
270 else
271 return p;
272 } else {
273 if ( != null) {
274 p = ;
275 } else {
276 Entry<K,V> parent = ;
277 Entry<K,V> ch = p;
278 while (parent != null && ch == ) {
279 ch = parent;
280 parent = ;
281 }
282 return parent;
283 }
284 }
285 }
286 return null;
287 }
288
289 // 将“key, value”添加到TreeMap中
290 // 理解TreeMap的前提是掌握“红黑树”。
291 // 若理解“红黑树中添加节点”的算法，则很容易理解put。
292 public V put(K key, V value) {
293 Entry<K,V> t = root;
294 // 若红黑树为空，则插入根节点
295 if (t == null) {
296 // TBD:
297 // 5045147: (coll) Adding null to an empty TreeSet should
298 // throw NullPointerException
299 //
300 // compare(key, key); // type check
301 root = new Entry<K,V>(key, value, null);
302 size = 1;
303 modCount++;
304 return null;
305 }
306 int cmp;
307 Entry<K,V> parent;
308 // split comparator and comparable paths
309 Comparator<? super K> cpr = comparator;
310 // 在二叉树(红黑树是特殊的二叉树)中，找到(key, value)的插入位置。
311 // 红黑树是以key来进行排序的，所以这里以key来进行查找。
312 if (cpr != null) {
313 do {
314 parent = t;
315 cmp = (key, );
316 if (cmp < 0)
317 t = ;
318 else if (cmp > 0)
319 t = ;
320 else
321 return (value);
322 } while (t != null);
323 }
324 else {
325 if (key == null)
326 throw new NullPointerException();
327 Comparable<? super K> k = (Comparable<? super K>) key;
328 do {
329 parent = t;
330 cmp = ();
331 if (cmp < 0)
332 t = ;
333 else if (cmp > 0)
334 t = ;
335 else
336 return (value);
337 } while (t != null);
338 }
339 // 新建红黑树的节点(e)
340 Entry<K,V> e = new Entry<K,V>(key, value, parent);
341 if (cmp < 0)
342 = e;
343 else
344 = e;
345 // 红黑树插入节点后，不再是一颗红黑树；
346 // 这里通过fixAfterInsertion的处理，来恢复红黑树的特性。
347 fixAfterInsertion(e);
348 size++;
349 modCount++;
350 return null;
351 }
352
353 // 删除TreeMap中的键为key的节点，并返回节点的值
354 public V remove(Object key) {
355 // 找到键为key的节点
356 Entry<K,V> p = getEntry(key);
357 if (p == null)
358 return null;
359
360 // 保存节点的值
361 V oldValue = ;
362 // 删除节点
363 deleteEntry(p);
364 return oldValue;
365 }
366
367 // 清空红黑树
368 public void clear() {
369 modCount++;
370 size = 0;
371 root = null;
372 }
373
374 // 克隆一个TreeMap，并返回Object对象
375 public Object clone() {
376 TreeMap<K,V> clone = null;
377 try {
378 clone = (TreeMap<K,V>) super.clone();
379 } catch (CloneNotSupportedException e) {
380 throw new InternalError();
381 }
382
383 // Put clone into "virgin" state (except for comparator)
384 = null;
385 = 0;
386 = 0;
387 = null;
388 = null;
389 = null;
390
391 // Initialize clone with our mappings
392 try {
393 (size, entrySet().iterator(), null, null);
394 } catch ( cannotHappen) {
395 } catch (ClassNotFoundException cannotHappen) {
396 }
397
398 return clone;
399 }
400
401 // 获取第一个节点(对外接口)。
402 public <K,V> firstEntry() {
403 return exportEntry(getFirstEntry());
404 }
405
406 // 获取最后一个节点(对外接口)。
407 public <K,V> lastEntry() {
408 return exportEntry(getLastEntry());
409 }
410
411 // 获取第一个节点，并将改节点从TreeMap中删除。
412 public <K,V> pollFirstEntry() {
413 // 获取第一个节点
414 Entry<K,V> p = getFirstEntry();
415 <K,V> result = exportEntry(p);
416 // 删除第一个节点
417 if (p != null)
418 deleteEntry(p);
419 return result;
420 }
421
422 // 获取最后一个节点，并将改节点从TreeMap中删除。
423 public <K,V> pollLastEntry() {
424 // 获取最后一个节点
425 Entry<K,V> p = getLastEntry();
426 <K,V> result = exportEntry(p);
427 // 删除最后一个节点
428 if (p != null)
429 deleteEntry(p);
430 return result;
431 }
432
433 // 返回小于key的最大的键值对，没有的话返回null
434 public <K,V> lowerEntry(K key) {
435 return exportEntry(getLowerEntry(key));
436 }
437
438 // 返回小于key的最大的键值对所对应的KEY，没有的话返回null
439 public K lowerKey(K key) {
440 return keyOrNull(getLowerEntry(key));
441 }
442
443 // 返回不大于key的最大的键值对，没有的话返回null
444 public <K,V> floorEntry(K key) {
445 return exportEntry(getFloorEntry(key));
446 }
447
448 // 返回不大于key的最大的键值对所对应的KEY，没有的话返回null
449 public K floorKey(K key) {
450 return keyOrNull(getFloorEntry(key));
451 }
452
453 // 返回不小于key的最小的键值对，没有的话返回null
454 public <K,V> ceilingEntry(K key) {
455 return exportEntry(getCeilingEntry(key));
456 }
457
458 // 返回不小于key的最小的键值对所对应的KEY，没有的话返回null
459 public K ceilingKey(K key) {
460 return keyOrNull(getCeilingEntry(key));
461 }
462
463 // 返回大于key的最小的键值对，没有的话返回null
464 public <K,V> higherEntry(K key) {
465 return exportEntry(getHigherEntry(key));
466 }
467
468 // 返回大于key的最小的键值对所对应的KEY，没有的话返回null
469 public K higherKey(K key) {
470 return keyOrNull(getHigherEntry(key));
471 }
472
473 // TreeMap的红黑树节点对应的集合
474 private transient EntrySet entrySet = null;
475 // KeySet为KeySet导航类
476 private transient KeySet<K> navigableKeySet = null;
477 // descendingMap为键值对的倒序“映射”
478 private transient NavigableMap<K,V> descendingMap = null;
479
480 // 返回TreeMap的“键的集合”
481 public Set<K> keySet() {
482 return navigableKeySet();
483 }
484
485 // 获取“可导航”的Key的集合
486 // 实际上是返回KeySet类的对象。
487 public NavigableSet<K> navigableKeySet() {
488 KeySet<K> nks = navigableKeySet;
489 return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
490 }
491
492 // 返回“TreeMap的值对应的集合”
493 public Collection<V> values() {
494 Collection<V> vs = values;
495 return (vs != null) ? vs : (values = new Values());
496 }
497
498 // 获取TreeMap的Entry的集合，实际上是返回EntrySet类的对象。
499 public Set<<K,V>> entrySet() {
500 EntrySet es = entrySet;
501 return (es != null) ? es : (entrySet = new EntrySet());
502 }
503
504 // 获取TreeMap的降序Map
505 // 实际上是返回DescendingSubMap类的对象
506 public NavigableMap<K, V> descendingMap() {
507 NavigableMap<K, V> km = descendingMap;
508 return (km != null) ? km :
509 (descendingMap = new DescendingSubMap(this,
510 true, null, true,
511 true, null, true));
512 }
513
514 // 获取TreeMap的子Map
515 // 范围是从fromKey 到 toKey；fromInclusive是是否包含fromKey的标记，toInclusive是是否包含toKey的标记
516 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
517 K toKey, boolean toInclusive) {
518 return new AscendingSubMap(this,
519 false, fromKey, fromInclusive,
520 false, toKey, toInclusive);
521 }
522
523 // 获取“Map的头部”
524 // 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记
525 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
526 return new AscendingSubMap(this,
527 true, null, true,
528 false, toKey, inclusive);
529 }
530
531 // 获取“Map的尾部”。
532 // 范围是从 fromKey 到 最后一个节点，inclusive是是否包含fromKey的标记
533 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
534 return new AscendingSubMap(this,
535 false, fromKey, inclusive,
536 true, null, true);
537 }
538
539 // 获取“子Map”。
540 // 范围是从fromKey(包括) 到 toKey(不包括)
541 public SortedMap<K,V> subMap(K fromKey, K toKey) {
542 return subMap(fromKey, true, toKey, false);
543 }
544
545 // 获取“Map的头部”。
546 // 范围从第一个节点 到 toKey(不包括)
547 public SortedMap<K,V> headMap(K toKey) {
548 return headMap(toKey, false);
549 }
550
551 // 获取“Map的尾部”。
552 // 范围是从 fromKey(包括) 到 最后一个节点
553 public SortedMap<K,V> tailMap(K fromKey) {
554 return tailMap(fromKey, true);
555 }
556
557 // ”TreeMap的值的集合“对应的类，它集成于AbstractCollection
558 class Values extends AbstractCollection<V> {
559 // 返回迭代器
560 public Iterator<V> iterator() {
561 return new ValueIterator(getFirstEntry());
562 }
563
564 // 返回个数
565 public int size() {
566 return TreeMap.this.size();
567 }
568
569 // "TreeMap的值的集合"中是否包含"对象o"
570 public boolean contains(Object o) {
571 return TreeMap.this.containsValue(o);
572 }
573
574 // 删除"TreeMap的值的集合"中的"对象o"
575 public boolean remove(Object o) {
576 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
577 if (valEquals((), o)) {
578 deleteEntry(e);
579 return true;
580 }
581 }
582 return false;
583 }
584
585 // 清空删除"TreeMap的值的集合"
586 public void clear() {
587 TreeMap.this.clear();
588 }
589 }
590
591 // EntrySet是“TreeMap的所有键值对组成的集合”，
592 // EntrySet集合的单位是单个“键值对”。
593 class EntrySet extends AbstractSet<<K,V>> {
594 public Iterator<<K,V>> iterator() {
595 return new EntryIterator(getFirstEntry());
596 }
597
598 // EntrySet中是否包含“键值对Object”
599 public boolean contains(Object o) {
600 if (!(o instanceof ))
601 return false;
602 <K,V> entry = (<K,V>) o;
603 V value = ();
604 Entry<K,V> p = getEntry(());
605 return p != null && valEquals((), value);
606 }
607
608 // 删除EntrySet中的“键值对Object”
609 public boolean remove(Object o) {
610 if (!(o instanceof ))
611 return false;
612 <K,V> entry = (<K,V>) o;
613 V value = ();
614 Entry<K,V> p = getEntry(());
615 if (p != null && valEquals((), value)) {
616 deleteEntry(p);
617 return true;
618 }
619 return false;
620 }
621
622 // 返回EntrySet中元素个数
623 public int size() {
624 return TreeMap.this.size();
625 }
626
627 // 清空EntrySet
628 public void clear() {
629 TreeMap.this.clear();
630 }
631 }
632
633 // 返回“TreeMap的KEY组成的迭代器(顺序)”
634 Iterator<K> keyIterator() {
635 return new KeyIterator(getFirstEntry());
636 }
637
638 // 返回“TreeMap的KEY组成的迭代器(逆序)”
639 Iterator<K> descendingKeyIterator() {
640 return new DescendingKeyIterator(getLastEntry());
641 }
642
643 // KeySet是“TreeMap中所有的KEY组成的集合”
644 // KeySet继承于AbstractSet，而且实现了NavigableSet接口。
645 static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
646 // NavigableMap成员，KeySet是通过NavigableMap实现的
647 private final NavigableMap<E, Object> m;
648 KeySet(NavigableMap<E,Object> map) { m = map; }
649
650 // 升序迭代器
651 public Iterator<E> iterator() {
652 // 若是TreeMap对象，则调用TreeMap的迭代器keyIterator()
653 // 否则，调用TreeMap子类NavigableSubMap的迭代器keyIterator()
654 if (m instanceof TreeMap)
655 return ((TreeMap<E,Object>)m).keyIterator();
656 else
657 return (Iterator<E>)((()m).keyIterator());
658 }
659
660 // 降序迭代器
661 public Iterator<E> descendingIterator() {
662 // 若是TreeMap对象，则调用TreeMap的迭代器descendingKeyIterator()
663 // 否则，调用TreeMap子类NavigableSubMap的迭代器descendingKeyIterator()
664 if (m instanceof TreeMap)
665 return ((TreeMap<E,Object>)m).descendingKeyIterator();
666 else
667 return (Iterator<E>)((()m).descendingKeyIterator());
668 }
669
670 public int size() { return (); }
671 public boolean isEmpty() { return (); }
672 public boolean contains(Object o) { return (o); }
673 public void clear() { (); }
674 public E lower(E e) { return (e); }
675 public E floor(E e) { return (e); }
676 public E ceiling(E e) { return (e); }
677 public E higher(E e) { return (e); }
678 public E first() { return (); }
679 public E last() { return (); }
680 public Comparator<? super E> comparator() { return (); }
681 public E pollFirst() {
682 <E,Object> e = ();
683 return e == null? null : ();
684 }
685 public E pollLast() {
686 <E,Object> e = ();
687 return e == null? null : ();
688 }
689 public boolean remove(Object o) {
690 int oldSize = size();
691 (o);
692 return size() != oldSize;
693 }
694 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
695 E toElement, boolean toInclusive) {
696 return new TreeSet<E>((fromElement, fromInclusive,
697 toElement, toInclusive));
698 }
699 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
700 return new TreeSet<E>((toElement, inclusive));
701 }
702 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
703 return new TreeSet<E>((fromElement, inclusive));
704 }
705 public SortedSet<E> subSet(E fromElement, E toElement) {
706 return subSet(fromElement, true, toElement, false);
707 }
708 public SortedSet<E> headSet(E toElement) {
709 return headSet(toElement, false);
710 }
711 public SortedSet<E> tailSet(E fromElement) {
712 return tailSet(fromElement, true);
713 }
714 public NavigableSet<E> descendingSet() {
715 return new TreeSet(());
716 }
717 }
718
719 // 它是TreeMap中的一个抽象迭代器，实现了一些通用的接口。
720 abstract class PrivateEntryIterator<T> implements Iterator<T> {
721 // 下一个元素
722 Entry<K,V> next;
723 // 上一次返回元素
724 Entry<K,V> lastReturned;
725 // 期望的修改次数，用于实现fast-fail机制
726 int expectedModCount;
727
728 PrivateEntryIterator(Entry<K,V> first) {
729 expectedModCount = modCount;
730 lastReturned = null;
731 next = first;
732 }
733
734 public final boolean hasNext() {
735 return next != null;
736 }
737
738 // 获取下一个节点
739 final Entry<K,V> nextEntry() {
740 Entry<K,V> e = next;
741 if (e == null)
742 throw new NoSuchElementException();
743 if (modCount != expectedModCount)
744 throw new ConcurrentModificationException();
745 next = successor(e);
746 lastReturned = e;
747 return e;
748 }
749
750 // 获取上一个节点
751 final Entry<K,V> prevEntry() {
752 Entry<K,V> e = next;
753 if (e == null)
754 throw new NoSuchElementException();
755 if (modCount != expectedModCount)
756 throw new ConcurrentModificationException();
757 next = predecessor(e);
758 lastReturned = e;
759 return e;
760 }
761
762 // 删除当前节点
763 public void remove() {
764 if (lastReturned == null)
765 throw new IllegalStateException();
766 if (modCount != expectedModCount)
767 throw new ConcurrentModificationException();
768 // 这里重点强调一下“为什么当lastReturned的左右孩子都不为空时，要将其赋值给next”。
769 // 目的是为了“删除lastReturned节点之后，next节点指向的仍然是下一个节点”。
770 // 根据“红黑树”的特性可知：
771 // 当被删除节点有两个儿子时。那么，首先把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
772 // 这意味着“当被删除节点有两个儿子时，删除当前节点之后，'新的当前节点'实际上是‘原有的后继节点(即下一个节点)’”。
773 // 而此时next仍然指向"新的当前节点"。也就是说next是仍然是指向下一个节点；能继续遍历红黑树。
774 if ( != null && != null)
775 next = lastReturned;
776 deleteEntry(lastReturned);
777 expectedModCount = modCount;
778 lastReturned = null;
779 }
780 }
781
782 // TreeMap的Entry对应的迭代器
783 final class EntryIterator extends PrivateEntryIterator<<K,V>> {
784 EntryIterator(Entry<K,V> first) {
785 super(first);
786 }
787 public <K,V> next() {
788 return nextEntry();
789 }
790 }
791
792 // TreeMap的Value对应的迭代器
793 final class ValueIterator extends PrivateEntryIterator<V> {
794 ValueIterator(Entry<K,V> first) {
795 super(first);
796 }
797 public V next() {
798 return nextEntry().value;
799 }
800 }
801
802 // reeMap的KEY组成的迭代器(顺序)
803 final class KeyIterator extends PrivateEntryIterator<K> {
804 KeyIterator(Entry<K,V> first) {
805 super(first);
806 }
807 public K next() {
808 return nextEntry().key;
809 }
810 }
811
812 // TreeMap的KEY组成的迭代器(逆序)
813 final class DescendingKeyIterator extends PrivateEntryIterator<K> {
814 DescendingKeyIterator(Entry<K,V> first) {
815 super(first);
816 }
817 public K next() {
818 return prevEntry().key;
819 }
820 }
821
822 // 比较两个对象的大小
823 final int compare(Object k1, Object k2) {
824 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
825 : ((K)k1, (K)k2);
826 }
827
828 // 判断两个对象是否相等
829 final static boolean valEquals(Object o1, Object o2) {
830 return (o1==null ? o2==null : (o2));
831 }
832
833 // 返回“Key-Value键值对”的一个简单拷贝(<K,V>对象)
834 // 可用来读取“键值对”的值
835 static <K,V> <K,V> exportEntry(<K,V> e) {
836 return e == null? null :
837 new <K,V>(e);
838 }
839
840 // 若“键值对”不为null，则返回KEY；否则，返回null
841 static <K,V> K keyOrNull(<K,V> e) {
842 return e == null? null : ;
843 }
844
845 // 若“键值对”不为null，则返回KEY；否则，抛出异常
846 static <K> K key(Entry<K,?> e) {
847 if (e==null)
848 throw new NoSuchElementException();
849 return ;
850 }
851
852 // TreeMap的SubMap，它一个抽象类，实现了公共操作。
853 // 它包括了"(升序)AscendingSubMap"和"(降序)DescendingSubMap"两个子类。
854 static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
855 implements NavigableMap<K,V>, {
856 // TreeMap的拷贝
857 final TreeMap<K,V> m;
858 // lo是“子Map范围的最小值”，hi是“子Map范围的最大值”；
859 // loInclusive是“是否包含lo的标记”，hiInclusive是“是否包含hi的标记”
860 // fromStart是“表示是否从第一个节点开始计算”，
861 // toEnd是“表示是否计算到最后一个节点 ”
862 final K lo, hi;
863 final boolean fromStart, toEnd;
864 final boolean loInclusive, hiInclusive;
865
866 // 构造函数
867 NavigableSubMap(TreeMap<K,V> m,
868 boolean fromStart, K lo, boolean loInclusive,
869 boolean toEnd, K hi, boolean hiInclusive) {
870 if (!fromStart && !toEnd) {
871 if ((lo, hi) > 0)
872 throw new IllegalArgumentException("fromKey > toKey");
873 } else {
874 if (!fromStart) // type check
875 (lo, lo);
876 if (!toEnd)
877 (hi, hi);
878 }
879
880 this.m = m;
881 this.fromStart = fromStart;
882 this.lo = lo;
883 this.loInclusive = loInclusive;
884 this.toEnd = toEnd;
885 this.hi = hi;
886 this.hiInclusive = hiInclusive;
887 }
888
889 // 判断key是否太小
890 final boolean tooLow(Object key) {
891 // 若该SubMap不包括“起始节点”，
892 // 并且，“key小于最小键(lo)”或者“key等于最小键(lo)，但最小键却没包括在该SubMap内”
893 // 则判断key太小。其余情况都不是太小！
894 if (!fromStart) {
895 int c = (key, lo);
896 if (c < 0 || (c == 0 && !loInclusive))
897 return true;
898 }
899 return false;
900 }
901
902 // 判断key是否太大
903 final boolean tooHigh(Object key) {
904 // 若该SubMap不包括“结束节点”，
905 // 并且，“key大于最大键(hi)”或者“key等于最大键(hi)，但最大键却没包括在该SubMap内”
906 // 则判断key太大。其余情况都不是太大！
907 if (!toEnd) {
908 int c = (key, hi);
909 if (c > 0 || (c == 0 && !hiInclusive))
910 return true;
911 }
912 return false;
913 }
914
915 // 判断key是否在“lo和hi”开区间范围内
916 final boolean inRange(Object key) {
917 return !tooLow(key) && !tooHigh(key);
918 }
919
920 // 判断key是否在封闭区间内
921 final boolean inClosedRange(Object key) {
922 return (fromStart || (key, lo) >= 0)
923 && (toEnd || (hi, key) >= 0);
924 }
925
926 // 判断key是否在区间内, inclusive是区间开关标志
927 final boolean inRange(Object key, boolean inclusive) {
928 return inclusive ? inRange(key) : inClosedRange(key);
929 }
930
931 // 返回最低的Entry
932 final <K,V> absLowest() {
933 // 若“包含起始节点”，则调用getFirstEntry()返回第一个节点
934 // 否则的话，若包括lo，则调用getCeilingEntry(lo)获取大于/等于lo的最小的Entry;
935 // 否则，调用getHigherEntry(lo)获取大于lo的最小Entry
936 <K,V> e =
937 (fromStart ? () :
938 (loInclusive ? (lo) :
939 (lo)));
940 return (e == null || tooHigh()) ? null : e;
941 }
942
943 // 返回最高的Entry
944 final <K,V> absHighest() {
945 // 若“包含结束节点”，则调用getLastEntry()返回最后一个节点
946 // 否则的话，若包括hi，则调用getFloorEntry(hi)获取小于/等于hi的最大的Entry;
947 // 否则，调用getLowerEntry(hi)获取大于hi的最大Entry
948 <K,V> e =
949 <K,V> e =
950 (toEnd ? () :
951 (hiInclusive ? (hi) :
952 (hi)));
953 return (e == null || tooLow()) ? null : e;
954 }
955
956 // 返回"大于/等于key的最小的Entry"
957 final <K,V> absCeiling(K key) {
958 // 只有在“key太小”的情况下，absLowest()返回的Entry才是“大于/等于key的最小Entry”
959 // 其它情况下不行。例如，当包含“起始节点”时，absLowest()返回的是最小Entry了！
960 if (tooLow(key))
961 return absLowest();
962 // 获取“大于/等于key的最小Entry”
963 <K,V> e = (key);
964 return (e == null || tooHigh()) ? null : e;
965 }
966
967 // 返回"大于key的最小的Entry"
968 final <K,V> absHigher(K key) {
969 // 只有在“key太小”的情况下，absLowest()返回的Entry才是“大于key的最小Entry”
970 // 其它情况下不行。例如，当包含“起始节点”时，absLowest()返回的是最小Entry了,而不一定是“大于key的最小Entry”！
971 if (tooLow(key))
972 return absLowest();
973 // 获取“大于key的最小Entry”
974 <K,V> e = (key);
975 return (e == null || tooHigh()) ? null : e;
976 }
977
978 // 返回"小于/等于key的最大的Entry"
979 final <K,V> absFloor(K key) {
980 // 只有在“key太大”的情况下，(absHighest)返回的Entry才是“小于/等于key的最大Entry”
981 // 其它情况下不行。例如，当包含“结束节点”时，absHighest()返回的是最大Entry了！
982 if (tooHigh(key))
983 return absHighest();
984 // 获取"小于/等于key的最大的Entry"
985 <K,V> e = (key);
986 return (e == null || tooLow()) ? null : e;
987 }
988
989 // 返回"小于key的最大的Entry"
990 final <K,V> absLower(K key) {
991 // 只有在“key太大”的情况下，(absHighest)返回的Entry才是“小于key的最大Entry”
992 // 其它情况下不行。例如，当包含“结束节点”时，absHighest()返回的是最大Entry了,而不一定是“小于key的最大Entry”！
993 if (tooHigh(key))
994 return absHighest();
995 // 获取"小于key的最大的Entry"
996 <K,V> e = (key);
997 return (e == null || tooLow()) ? null : e;
998 }
999
1000 // 返回“大于最大节点中的最小节点”，不存在的话，返回null
1001 final <K,V> absHighFence() {
1002 return (toEnd ? null : (hiInclusive ?
1003 (hi) :
1004 (hi)));
1005 }
1006
1007 // 返回“小于最小节点中的最大节点”，不存在的话，返回null
1008 final <K,V> absLowFence() {
1009 return (fromStart ? null : (loInclusive ?
1010 (lo) :
1011 (lo)));
1012 }
1013
1014 // 下面几个abstract方法是需要NavigableSubMap的实现类实现的方法
1015 abstract <K,V> subLowest();
1016 abstract <K,V> subHighest();
1017 abstract <K,V> subCeiling(K key);
1018 abstract <K,V> subHigher(K key);
1019 abstract <K,V> subFloor(K key);
1020 abstract <K,V> subLower(K key);
1021 // 返回“顺序”的键迭代器
1022 abstract Iterator<K> keyIterator();
1023 // 返回“逆序”的键迭代器
1024 abstract Iterator<K> descendingKeyIterator();
1025
1026 // 返回SubMap是否为空。空的话，返回true，否则返回false
1027 public boolean isEmpty() {
1028 return (fromStart && toEnd) ? () : entrySet().isEmpty();
1029 }
1030
1031 // 返回SubMap的大小
1032 public int size() {
1033 return (fromStart && toEnd) ? () : entrySet().size();
1034 }
1035
1036 // 返回SubMap是否包含键key
1037 public final boolean containsKey(Object key) {
1038 return inRange(key) && (key);
1039 }
1040
1041 // 将key-value 插入SubMap中
1042 public final V put(K key, V value) {
1043 if (!inRange(key))
1044 throw new IllegalArgumentException("key out of range");
1045 return (key, value);
1046 }
1047
1048 // 获取key对应值
1049 public final V get(Object key) {
1050 return !inRange(key)? null : (key);
1051 }
1052
1053 // 删除key对应的键值对
1054 public final V remove(Object key) {
1055 return !inRange(key)? null : (key);
1056 }
1057
1058 // 获取“大于/等于key的最小键值对”
1059 public final <K,V> ceilingEntry(K key) {
1060 return exportEntry(subCeiling(key));
1061 }
1062
1063 // 获取“大于/等于key的最小键”
1064 public final K ceilingKey(K key) {
1065 return keyOrNull(subCeiling(key));
1066 }
1067
1068 // 获取“大于key的最小键值对”
1069 public final <K,V> higherEntry(K key) {
1070 return exportEntry(subHigher(key));
1071 }
1072
1073 // 获取“大于key的最小键”
1074 public final K higherKey(K key) {
1075 return keyOrNull(subHigher(key));
1076 }
1077
1078 // 获取“小于/等于key的最大键值对”
1079 public final <K,V> floorEntry(K key) {
1080 return exportEntry(subFloor(key));
1081 }
1082
1083 // 获取“小于/等于key的最大键”
1084 public final K floorKey(K key) {
1085 return keyOrNull(subFloor(key));
1086 }
1087
1088 // 获取“小于key的最大键值对”
1089 public final <K,V> lowerEntry(K key) {
1090 return exportEntry(subLower(key));
1091 }
1092
1093 // 获取“小于key的最大键”
1094 public final K lowerKey(K key) {
1095 return keyOrNull(subLower(key));
1096 }
1097
1098 // 获取"SubMap的第一个键"
1099 public final K firstKey() {
1100 return key(subLowest());
1101 }
1102
1103 // 获取"SubMap的最后一个键"
1104 public final K lastKey() {
1105 return key(subHighest());
1106 }
1107
1108 // 获取"SubMap的第一个键值对"
1109 public final <K,V> firstEntry() {
1110 return exportEntry(subLowest());
1111 }
1112
1113 // 获取"SubMap的最后一个键值对"
1114 public final <K,V> lastEntry() {
1115 return exportEntry(subHighest());
1116 }
1117
1118 // 返回"SubMap的第一个键值对"，并从SubMap中删除改键值对
1119 public final <K,V> pollFirstEntry() {
1120 <K,V> e = subLowest();
1121 <K,V> result = exportEntry(e);
1122 if (e != null)
1123 (e);
1124 return result;
1125 }
1126
1127 // 返回"SubMap的最后一个键值对"，并从SubMap中删除改键值对
1128 public final <K,V> pollLastEntry() {
1129 <K,V> e = subHighest();
1130 <K,V> result = exportEntry(e);
1131 if (e != null)
1132 (e);
1133 return result;
1134 }
1135
1136 // Views
1137 transient NavigableMap<K,V> descendingMapView = null;
1138 transient EntrySetView entrySetView = null;
1139 transient KeySet<K> navigableKeySetView = null;
1140
1141 // 返回NavigableSet对象，实际上返回的是当前对象的"Key集合"。
1142 public final NavigableSet<K> navigableKeySet() {
1143 KeySet<K> nksv = navigableKeySetView;
1144 return (nksv != null) ? nksv :
1145 (navigableKeySetView = new (this));
1146 }
1147
1148 // 返回"Key集合"对象
1149 public final Set<K> keySet() {
1150 return navigableKeySet();
1151 }
1152
1153 // 返回“逆序”的Key集合
1154 public NavigableSet<K> descendingKeySet() {
1155 return descendingMap().navigableKeySet();
1156 }
1157
1158 // 排列fromKey(包含) 到 toKey(不包含) 的子map
1159 public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1160 return subMap(fromKey, true, toKey, false);
1161 }
1162
1163 // 返回当前Map的头部(从第一个节点 到 toKey, 不包括toKey)
1164 public final SortedMap<K,V> headMap(K toKey) {
1165 return headMap(toKey, false);
1166 }
1167
1168 // 返回当前Map的尾部[从 fromKey(包括fromKeyKey) 到 最后一个节点]
1169 public final SortedMap<K,V> tailMap(K fromKey) {
1170 return tailMap(fromKey, true);
1171 }
1172
1173 // Map的Entry的集合
1174 abstract class EntrySetView extends AbstractSet<<K,V>> {
1175 private transient int size = -1, sizeModCount;
1176
1177 // 获取EntrySet的大小
1178 public int size() {
1179 // 若SubMap是从“开始节点”到“结尾节点”，则SubMap大小就是原TreeMap的大小
1180 if (fromStart && toEnd)
1181 return ();
1182 // 若SubMap不是从“开始节点”到“结尾节点”，则调用iterator()遍历EntrySetView中的元素
1183 if (size == -1 || sizeModCount != ) {
1184 sizeModCount = ;
1185 size = 0;
1186 Iterator i = iterator();
1187 while (()) {
1188 size++;
1189 ();
1190 }
1191 }
1192 return size;
1193 }
1194
1195 // 判断EntrySetView是否为空
1196 public boolean isEmpty() {
1197 <K,V> n = absLowest();
1198 return n == null || tooHigh();
1199 }
1200
1201 // 判断EntrySetView是否包含Object
1202 public boolean contains(Object o) {
1203 if (!(o instanceof ))
1204 return false;
1205 <K,V> entry = (<K,V>) o;
1206 K key = ();
1207 if (!inRange(key))
1208 return false;
1209 node = (key);
1210 return node != null &&
1211 valEquals((), ());
1212 }
1213
1214 // 从EntrySetView中删除Object
1215 public boolean remove(Object o) {
1216 if (!(o instanceof ))
1217 return false;
1218 <K,V> entry = (<K,V>) o;
1219 K key = ();
1220 if (!inRange(key))
1221 return false;
1222 <K,V> node = (key);
1223 if (node!=null && valEquals((),())){
1224 (node);
1225 return true;
1226 }
1227 return false;
1228 }
1229 }
1230
1231 // SubMap的迭代器
1232 abstract class SubMapIterator<T> implements Iterator<T> {
1233 // 上一次被返回的Entry
1234 <K,V> lastReturned;
1235 // 指向下一个Entry
1236 <K,V> next;
1237 // “栅栏key”。根据SubMap是“升序”还是“降序”具有不同的意义
1238 final K fenceKey;
1239 int expectedModCount;
1240
1241 // 构造函数
1242 SubMapIterator(<K,V> first,
1243 <K,V> fence) {
1244 // 每创建一个SubMapIterator时，保存修改次数
1245 // 若后面发现expectedModCount和modCount不相等，则抛出ConcurrentModificationException异常。
1246 // 这就是所说的fast-fail机制的原理！
1247 expectedModCount = ;
1248 lastReturned = null;
1249 next = first;
1250 fenceKey = fence == null ? null : ;
1251 }
1252
1253 // 是否存在下一个Entry
1254 public final boolean hasNext() {
1255 return next != null && != fenceKey;
1256 }
1257
1258 // 返回下一个Entry
1259 final <K,V> nextEntry() {
1260 <K,V> e = next;
1261 if (e == null || == fenceKey)
1262 throw new NoSuchElementException();
1263 if ( != expectedModCount)
1264 throw new ConcurrentModificationException();
1265 // next指向e的后继节点
1266 next = successor(e);
1267 lastReturned = e;
1268 return e;
1269 }
1270
1271 // 返回上一个Entry
1272 final <K,V> prevEntry() {
1273 <K,V> e = next;
1274 if (e == null || == fenceKey)
1275 throw new NoSuchElementException();
1276 if ( != expectedModCount)
1277 throw new ConcurrentModificationException();
1278 // next指向e的前继节点
1279 next = predecessor(e);
1280 lastReturned = e;
1281 return e;
1282 }
1283
1284 // 删除当前节点(用于“升序的SubMap”)。
1285 // 删除之后，可以继续升序遍历；红黑树特性没变。
1286 final void removeAscending() {
1287 if (lastReturned == null)
1288 throw new IllegalStateException();
1289 if ( != expectedModCount)
1290 throw new ConcurrentModificationException();
1291 // 这里重点强调一下“为什么当lastReturned的左右孩子都不为空时，要将其赋值给next”。
1292 // 目的是为了“删除lastReturned节点之后，next节点指向的仍然是下一个节点”。
1293 // 根据“红黑树”的特性可知：
1294 // 当被删除节点有两个儿子时。那么，首先把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
1295 // 这意味着“当被删除节点有两个儿子时，删除当前节点之后，'新的当前节点'实际上是‘原有的后继节点(即下一个节点)’”。
1296 // 而此时next仍然指向"新的当前节点"。也就是说next是仍然是指向下一个节点；能继续遍历红黑树。
1297 if ( != null && != null)
1298 next = lastReturned;
1299 (lastReturned);
1300 lastReturned = null;
1301 expectedModCount = ;
1302 }
1303
1304 // 删除当前节点(用于“降序的SubMap”)。
1305 // 删除之后，可以继续降序遍历；红黑树特性没变。
1306 final void removeDescending() {
1307 if (lastReturned == null)
1308 throw new IllegalStateException();
1309 if ( != expectedModCount)
1310 throw new ConcurrentModificationException();
1311 (lastReturned);
1312 lastReturned = null;
1313 expectedModCount = ;
1314 }
1315
1316 }
1317
1318 // SubMap的Entry迭代器，它只支持升序操作，继承于SubMapIterator
1319 final class SubMapEntryIterator extends SubMapIterator<<K,V>> {
1320 SubMapEntryIterator(<K,V> first,
1321 <K,V> fence) {
1322 super(first, fence);
1323 }
1324 // 获取下一个节点(升序)
1325 public <K,V> next() {
1326 return nextEntry();
1327 }
1328 // 删除当前节点(升序)
1329 public void remove() {
1330 removeAscending();
1331 }
1332 }
1333
1334 // SubMap的Key迭代器，它只支持升序操作，继承于SubMapIterator
1335 final class SubMapKeyIterator extends SubMapIterator<K> {
1336 SubMapKeyIterator(<K,V> first,
1337 <K,V> fence) {
1338 super(first, fence);
1339 }
1340 // 获取下一个节点(升序)
1341 public K next() {
1342 return nextEntry().key;
1343 }
1344 // 删除当前节点(升序)
1345 public void remove() {
1346 removeAscending();
1347 }
1348 }
1349
1350 // 降序SubMap的Entry迭代器，它只支持降序操作，继承于SubMapIterator
1351 final class DescendingSubMapEntryIterator extends SubMapIterator<<K,V>> {
1352 DescendingSubMapEntryIterator(<K,V> last,
1353 <K,V> fence) {
1354 super(last, fence);
1355 }
1356
1357 // 获取下一个节点(降序)
1358 public <K,V> next() {
1359 return prevEntry();
1360 }
1361 // 删除当前节点(降序)
1362 public void remove() {
1363 removeDescending();
1364 }
1365 }
1366
1367 // 降序SubMap的Key迭代器，它只支持降序操作，继承于SubMapIterator
1368 final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
1369 DescendingSubMapKeyIterator(<K,V> last,
1370 <K,V> fence) {
1371 super(last, fence);
1372 }
1373 // 获取下一个节点(降序)
1374 public K next() {
1375 return prevEntry().key;
1376 }
1377 // 删除当前节点(降序)
1378 public void remove() {
1379 removeDescending();
1380 }
1381 }
1382 }
1383
1384
1385 // 升序的SubMap，继承于NavigableSubMap
1386 static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1387 private static final long serialVersionUID = 912986545866124060L;
1388
1389 // 构造函数
1390 AscendingSubMap(TreeMap<K,V> m,
1391 boolean fromStart, K lo, boolean loInclusive,
1392 boolean toEnd, K hi, boolean hiInclusive) {
1393 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1394 }
1395
1396 // 比较器
1397 public Comparator<? super K> comparator() {
1398 return ();
1399 }
1400
1401 // 获取“子Map”。
1402 // 范围是从fromKey 到 toKey；fromInclusive是是否包含fromKey的标记，toInclusive是是否包含toKey的标记
1403 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1404 K toKey, boolean toInclusive) {
1405 if (!inRange(fromKey, fromInclusive))
1406 throw new IllegalArgumentException("fromKey out of range");
1407 if (!inRange(toKey, toInclusive))
1408 throw new IllegalArgumentException("toKey out of range");
1409 return new AscendingSubMap(m,
1410 false, fromKey, fromInclusive,
1411 false, toKey, toInclusive);
1412 }
1413
1414 // 获取“Map的头部”。
1415 // 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记
1416 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1417 if (!inRange(toKey, inclusive))
1418 throw new IllegalArgumentException("toKey out of range");
1419 return new AscendingSubMap(m,
1420 fromStart, lo, loInclusive,
1421 false, toKey, inclusive);
1422 }
1423
1424 // 获取“Map的尾部”。
1425 // 范围是从 fromKey 到 最后一个节点，inclusive是是否包含fromKey的标记
1426 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1427 if (!inRange(fromKey, inclusive))
1428 throw new IllegalArgumentException("fromKey out of range");
1429 return new AscendingSubMap(m,
1430 false, fromKey, inclusive,
1431 toEnd, hi, hiInclusive);
1432 }
1433
1434 // 获取对应的降序Map
1435 public NavigableMap<K,V> descendingMap() {
1436 NavigableMap<K,V> mv = descendingMapView;
1437 return (mv != null) ? mv :
1438 (descendingMapView =
1439 new DescendingSubMap(m,
1440 fromStart, lo, loInclusive,
1441 toEnd, hi, hiInclusive));
1442 }
1443
1444 // 返回“升序Key迭代器”
1445 Iterator<K> keyIterator() {
1446 return new SubMapKeyIterator(absLowest(), absHighFence());
1447 }
1448
1449 // 返回“降序Key迭代器”
1450 Iterator<K> descendingKeyIterator() {
1451 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1452 }
1453
1454 // “升序EntrySet集合”类
1455 // 实现了iterator()
1456 final class AscendingEntrySetView extends EntrySetView {
1457 public Iterator<<K,V>> iterator() {
1458 return new SubMapEntryIterator(absLowest(), absHighFence());
1459 }
1460 }
1461
1462 // 返回“升序EntrySet集合”
1463 public Set<<K,V>> entrySet() {
1464 EntrySetView es = entrySetView;
1465 return (es != null) ? es : new AscendingEntrySetView();
1466 }
1467
1468 <K,V> subLowest() { return absLowest(); }
1469 <K,V> subHighest() { return absHighest(); }
1470 <K,V> subCeiling(K key) { return absCeiling(key); }
1471 <K,V> subHigher(K key) { return absHigher(key); }
1472 <K,V> subFloor(K key) { return absFloor(key); }
1473 <K,V> subLower(K key) { return absLower(key); }
1474 }
1475
1476 // 降序的SubMap，继承于NavigableSubMap
1477 // 相比于升序SubMap，它的实现机制是将“SubMap的比较器反转”！
1478 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1479 private static final long serialVersionUID = 912986545866120460L;
1480 DescendingSubMap(TreeMap<K,V> m,
1481 boolean fromStart, K lo, boolean loInclusive,
1482 boolean toEnd, K hi, boolean hiInclusive) {
1483 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1484 }
1485
1486 // 反转的比较器：是将原始比较器反转得到的。
1487 private final Comparator<? super K> reverseComparator =
1488 ();
1489
1490 // 获取反转比较器
1491 public Comparator<? super K> comparator() {
1492 return reverseComparator;
1493 }
1494
1495 // 获取“子Map”。
1496 // 范围是从fromKey 到 toKey；fromInclusive是是否包含fromKey的标记，toInclusive是是否包含toKey的标记
1497 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1498 K toKey, boolean toInclusive) {
1499 if (!inRange(fromKey, fromInclusive))
1500 throw new IllegalArgumentException("fromKey out of range");
1501 if (!inRange(toKey, toInclusive))
1502 throw new IllegalArgumentException("toKey out of range");
1503 return new DescendingSubMap(m,
1504 false, toKey, toInclusive,
1505 false, fromKey, fromInclusive);
1506 }
1507
1508 // 获取“Map的头部”。
1509 // 范围从第一个节点 到 toKey, inclusive是是否包含toKey的标记
1510 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1511 if (!inRange(toKey, inclusive))
1512 throw new IllegalArgumentException("toKey out of range");
1513 return new DescendingSubMap(m,
1514 false, toKey, inclusive,
1515 toEnd, hi, hiInclusive);
1516 }
1517
1518 // 获取“Map的尾部”。
1519 // 范围是从 fromKey 到 最后一个节点，inclusive是是否包含fromKey的标记
1520 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
1521 if (!inRange(fromKey, inclusive))
1522 throw new IllegalArgumentException("fromKey out of range");
1523 return new DescendingSubMap(m,
1524 fromStart, lo, loInclusive,
1525 false, fromKey, inclusive);
1526 }
1527
1528 // 获取对应的降序Map
1529 public NavigableMap<K,V> descendingMap() {
1530 NavigableMap<K,V> mv = descendingMapView;
1531 return (mv != null) ? mv :
1532 (descendingMapView =
1533 new AscendingSubMap(m,
1534 fromStart, lo, loInclusive,
1535 toEnd, hi, hiInclusive));
1536 }
1537
1538 // 返回“升序Key迭代器”
1539 Iterator<K> keyIterator() {
1540 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1541 }
1542
1543 // 返回“降序Key迭代器”
1544 Iterator<K> descendingKeyIterator() {
1545 return new SubMapKeyIterator(absLowest(), absHighFence());
1546 }
1547
1548 // “降序EntrySet集合”类
1549 // 实现了iterator()
1550 final class DescendingEntrySetView extends EntrySetView {
1551 public Iterator<<K,V>> iterator() {
1552 return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1553 }
1554 }
1555
1556 // 返回“降序EntrySet集合”
1557 public Set<<K,V>> entrySet() {
1558 EntrySetView es = entrySetView;
1559 return (es != null) ? es : new DescendingEntrySetView();
1560 }
1561
1562 <K,V> subLowest() { return absHighest(); }
1563 <K,V> subHighest() { return absLowest(); }
1564 <K,V> subCeiling(K key) { return absFloor(key); }
1565 <K,V> subHigher(K key) { return absLower(key); }
1566 <K,V> subFloor(K key) { return absCeiling(key); }
1567 <K,V> subLower(K key) { return absHigher(key); }
1568 }
1569
1570 // SubMap是旧版本的类，新的Java中没有用到。
1571 private class SubMap extends AbstractMap<K,V>
1572 implements SortedMap<K,V>, {
1573 private static final long serialVersionUID = -6520786458950516097L;
1574 private boolean fromStart = false, toEnd = false;
1575 private K fromKey, toKey;
1576 private Object readResolve() {
1577 return new AscendingSubMap(TreeMap.this,
1578 fromStart, fromKey, true,
1579 toEnd, toKey, false);
1580 }
1581 public Set<<K,V>> entrySet() { throw new InternalError(); }
1582 public K lastKey() { throw new InternalError(); }
1583 public K firstKey() { throw new InternalError(); }
1584 public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1585 public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1586 public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
1587 public Comparator<? super K> comparator() { throw new InternalError(); }
1588 }
1589
1590
1591 // 红黑树的节点颜色--红色
1592 private static final boolean RED = false;
1593 // 红黑树的节点颜色--黑色
1594 private static final boolean BLACK = true;
1595
1596 // “红黑树的节点”对应的类。
1597 // 包含了 key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)
1598 static final class Entry<K,V> implements <K,V> {
1599 // 键
1600 K key;
1601 // 值
1602 V value;
1603 // 左孩子
1604 Entry<K,V> left = null;
1605 // 右孩子
1606 Entry<K,V> right = null;
1607 // 父节点
1608 Entry<K,V> parent;
1609 // 当前节点颜色
1610 boolean color = BLACK;
1611
1612 // 构造函数
1613 Entry(K key, V value, Entry<K,V> parent) {
1614 this.key = key;
1615 this.value = value;
1616 this.parent = parent;
1617 }
1618
1619 // 返回“键”
1620 public K getKey() {
1621 return key;
1622 }
1623
1624 // 返回“值”
1625 public V getValue() {
1626 return value;
1627 }
1628
1629 // 更新“值”，返回旧的值
1630 public V setValue(V value) {
1631 V oldValue = this.value;
1632 this.value = value;
1633 return oldValue;
1634 }
1635
1636 // 判断两个节点是否相等的函数，覆盖equals()函数。
1637 // 若两个节点的“key相等”并且“value相等”，则两个节点相等
1638 public boolean equals(Object o) {
1639 if (!(o instanceof ))
1640 return false;
1641 <?,?> e = (<?,?>)o;
1642
1643 return valEquals(key,()) && valEquals(value,());
1644 }
1645
1646 // 覆盖hashCode函数。
1647 public int hashCode() {
1648 int keyHash = (key==null ? 0 : ());
1649 int valueHash = (value==null ? 0 : ());
1650 return keyHash ^ valueHash;
1651 }
1652
1653 // 覆盖toString()函数。
1654 public String toString() {
1655 return key + "=" + value;
1656 }
1657 }
1658
1659 // 返回“红黑树的第一个节点”
1660 final Entry<K,V> getFirstEntry() {
1661 Entry<K,V> p = root;
1662 if (p != null)
1663 while ( != null)
1664 p = ;
1665 return p;
1666 }
1667
1668 // 返回“红黑树的最后一个节点”
1669 final Entry<K,V> getLastEntry() {
1670 Entry<K,V> p = root;
1671 if (p != null)
1672 while ( != null)
1673 p = ;
1674 return p;
1675 }
1676
1677 // 返回“节点t的后继节点”
1678 static <K,V> <K,V> successor(Entry<K,V> t) {
1679 if (t == null)
1680 return null;
1681 else if ( != null) {
1682 Entry<K,V> p = ;
1683 while ( != null)
1684 p = ;
1685 return p;
1686 } else {
1687 Entry<K,V> p = ;
1688 Entry<K,V> ch = t;
1689 while (p != null && ch == ) {
1690 ch = p;
1691 p = ;
1692 }
1693 return p;
1694 }
1695 }
1696
1697 // 返回“节点t的前继节点”
1698 static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
1699 if (t == null)
1700 return null;
1701 else if ( != null) {
1702 Entry<K,V> p = ;
1703 while ( != null)
1704 p = ;
1705 return p;
1706 } else {
1707 Entry<K,V> p = ;
1708 Entry<K,V> ch = t;
1709 while (p != null && ch == ) {
1710 ch = p;
1711 p = ;
1712 }
1713 return p;
1714 }
1715 }
1716
1717 // 返回“节点p的颜色”
1718 // 根据“红黑树的特性”可知：空节点颜色是黑色。
1719 private static <K,V> boolean colorOf(Entry<K,V> p) {
1720 return (p == null ? BLACK : );
1721 }
1722
1723 // 返回“节点p的父节点”
1724 private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
1725 return (p == null ? null: );
1726 }
1727
1728 // 设置“节点p的颜色为c”
1729 private static <K,V> void setColor(Entry<K,V> p, boolean c) {
1730 if (p != null)
1731 = c;
1732 }
1733
1734 // 设置“节点p的左孩子”
1735 private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
1736 return (p == null) ? null: ;
1737 }
1738
1739 // 设置“节点p的右孩子”
1740 private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
1741 return (p == null) ? null: ;
1742 }
1743
1744 // 对节点p执行“左旋”操作
1745 private void rotateLeft(Entry<K,V> p) {
1746 if (p != null) {
1747 Entry<K,V> r = ;
1748 = ;
1749 if ( != null)
1750 = p;
1751 = ;
1752 if ( == null)
1753 root = r;
1754 else if ( == p)
1755 = r;
1756 else
1757 = r;
1758 = p;
1759 = r;
1760 }
1761 }
1762
1763 // 对节点p执行“右旋”操作
1764 private void rotateRight(Entry<K,V> p) {
1765 if (p != null) {
1766 Entry<K,V> l = ;
1767 = ;
1768 if ( != null) = p;
1769 = ;
1770 if ( == null)
1771 root = l;
1772 else if ( == p)
1773 = l;
1774 else = l;
1775 = p;
1776 = l;
1777 }
1778 }
1779
1780 // 插入之后的修正操作。
1781 // 目的是保证：红黑树插入节点之后，仍然是一颗红黑树
1782 private void fixAfterInsertion(Entry<K,V> x) {
1783 = RED;
1784
1785 while (x != null && x != root && == RED) {
1786 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
1787 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
1788 if (colorOf(y) == RED) {
1789 setColor(parentOf(x), BLACK);
1790 setColor(y, BLACK);
1791 setColor(parentOf(parentOf(x)), RED);
1792 x = parentOf(parentOf(x));
1793 } else {
1794 if (x == rightOf(parentOf(x))) {
1795 x = parentOf(x);
1796 rotateLeft(x);
1797 }
1798 setColor(parentOf(x), BLACK);
1799 setColor(parentOf(parentOf(x)), RED);
1800 rotateRight(parentOf(parentOf(x)));
1801 }
1802 } else {
1803 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
1804 if (colorOf(y) == RED) {
1805 setColor(parentOf(x), BLACK);
1806 setColor(y, BLACK);
1807 setColor(parentOf(parentOf(x)), RED);
1808 x = parentOf(parentOf(x));
1809 } else {
1810 if (x == leftOf(parentOf(x))) {
1811 x = parentOf(x);
1812 rotateRight(x);
1813 }
1814 setColor(parentOf(x), BLACK);
1815 setColor(parentOf(parentOf(x)), RED);
1816 rotateLeft(parentOf(parentOf(x)));
1817 }
1818 }
1819 }
1820 = BLACK;
1821 }
1822
1823 // 删除“红黑树的节点p”
1824 private void deleteEntry(Entry<K,V> p) {
1825 modCount++;
1826 size--;
1827
1828 // If strictly internal, copy successor's element to p and then make p
1829 // point to successor.
1830 if ( != null && != null) {
1831 Entry<K,V> s = successor (p);
1832 = ;
1833 = ;
1834 p = s;
1835 } // p has 2 children
1836
1837 // Start fixup at replacement node, if it exists.
1838 Entry<K,V> replacement = ( != null ? : );
1839
1840 if (replacement != null) {
1841 // Link replacement to parent
1842 = ;
1843 if ( == null)
1844 root = replacement;
1845 else if (p == )
1846 = replacement;
1847 else
1848 = replacement;
1849
1850 // Null out links so they are OK to use by fixAfterDeletion.
1851 = = = null;
1852
1853 // Fix replacement
1854 if ( == BLACK)
1855 fixAfterDeletion(replacement);
1856 } else if ( == null) { // return if we are the only node.
1857 root = null;
1858 } else { // No children. Use self as phantom replacement and unlink.
1859 if ( == BLACK)
1860 fixAfterDeletion(p);
1861
1862 if ( != null) {
1863 if (p == )
1864 = null;
1865 else if (p == )
1866 = null;
1867 = null;
1868 }
1869 }
1870 }
1871
1872 // 删除之后的修正操作。
1873 // 目的是保证：红黑树删除节点之后，仍然是一颗红黑树
1874 private void fixAfterDeletion(Entry<K,V> x) {
1875 while (x != root && colorOf(x) == BLACK) {
1876 if (x == leftOf(parentOf(x))) {
1877 Entry<K,V> sib = rightOf(parentOf(x));
1878
1879 if (colorOf(sib) == RED) {
1880 setColor(sib, BLACK);
1881 setColor(parentOf(x), RED);
1882 rotateLeft(parentOf(x));
1883 sib = rightOf(parentOf(x));
1884 }
1885
1886 if (colorOf(leftOf(sib)) == BLACK &&
1887 colorOf(rightOf(sib)) == BLACK) {
1888 setColor(sib, RED);
1889 x = parentOf(x);
1890 } else {
1891 if (colorOf(rightOf(sib)) == BLACK) {
1892 setColor(leftOf(sib), BLACK);
1893 setColor(sib, RED);
1894 rotateRight(sib);
1895 sib = rightOf(parentOf(x));
1896 }
1897 setColor(sib, colorOf(parentOf(x)));
1898 setColor(parentOf(x), BLACK);
1899 setColor(rightOf(sib), BLACK);
1900 rotateLeft(parentOf(x));
1901 x = root;
1902 }
1903 } else { // symmetric
1904 Entry<K,V> sib = leftOf(parentOf(x));
1905
1906 if (colorOf(sib) == RED) {
1907 setColor(sib, BLACK);
1908 setColor(parentOf(x), RED);
1909 rotateRight(parentOf(x));
1910 sib = leftOf(parentOf(x));
1911 }
1912
1913 if (colorOf(rightOf(sib)) == BLACK &&
1914 colorOf(leftOf(sib)) == BLACK) {
1915 setColor(sib, RED);
1916 x = parentOf(x);
1917 } else {
1918 if (colorOf(leftOf(sib)) == BLACK) {
1919 setColor(rightOf(sib), BLACK);
1920 setColor(sib, RED);
1921 rotateLeft(sib);
1922 sib = leftOf(parentOf(x));
1923 }
1924 setColor(sib, colorOf(parentOf(x)));
1925 setColor(parentOf(x), BLACK);
1926 setColor(leftOf(sib), BLACK);
1927 rotateRight(parentOf(x));
1928 x = root;
1929 }
1930 }
1931 }
1932
1933 setColor(x, BLACK);
1934 }
1935
1936 private static final long serialVersionUID = 919286545866124006L;
1937
1938 // 的写入函数
1939 // 将TreeMap的“容量，所有的Entry”都写入到输出流中
1940 private void writeObject( s)
1941 throws {
1942 // Write out the Comparator and any hidden stuff
1943 ();
1944
1945 // Write out size (number of Mappings)
1946 (size);
1947
1948 // Write out keys and values (alternating)
1949 for (Iterator<<K,V>> i = entrySet().iterator(); (); ) {
1950 <K,V> e = ();
1951 (());
1952 (());
1953 }
1954 }
1955
1956
1957 // 的读取函数：根据写入方式读出
1958 // 先将TreeMap的“容量、所有的Entry”依次读出
1959 private void readObject(final s)
1960 throws , ClassNotFoundException {
1961 // Read in the Comparator and any hidden stuff
1962 ();
1963
1964 // Read in size
1965 int size = ();
1966
1967 buildFromSorted(size, null, s, null);
1968 }
1969
1970 // 根据已经一个排好序的map创建一个TreeMap
1971 private void buildFromSorted(int size, Iterator it,
1972 str,
1973 V defaultVal)
1974 throws , ClassNotFoundException {
1975 this.size = size;
1976 root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
1977 it, str, defaultVal);
1978 }
1979
1980 // 根据已经一个排好序的map创建一个TreeMap
1981 // 将map中的元素逐个添加到TreeMap中，并返回map的中间元素作为根节点。
1982 private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
1983 int redLevel,
1984 Iterator it,
1985 str,
1986 V defaultVal)
1987 throws , ClassNotFoundException {
1988
1989 if (hi < lo) return null;
1990
1991
1992 // 获取中间元素
1993 int mid = (lo + hi) / 2;
1994
1995 Entry<K,V> left = null;
1996 // 若lo小于mid，则递归调用获取(middel的)左孩子。
1997 if (lo < mid)
1998 left = buildFromSorted(level+1, lo, mid - 1, redLevel,
1999 it, str, defaultVal);
2000
2001 // 获取middle节点对应的key和value
2002 K key;
2003 V value;
2004 if (it != null) {
2005 if (defaultVal==null) {
2006 <K,V> entry = (<K,V>)();
2007 key = ();
2008 value = ();
2009 } else {
2010 key = (K)();
2011 value = defaultVal;
2012 }
2013 } else { // use stream
2014 key = (K) ();
2015 value = (defaultVal != null ? defaultVal : (V) ());
2016 }
2017
2018 // 创建middle节点
2019 Entry<K,V> middle = new Entry<K,V>(key, value, null);
2020
2021 // 若当前节点的深度=红色节点的深度，则将节点着色为红色。
2022 if (level == redLevel)
2023 = RED;
2024
2025 // 设置middle为left的父亲，left为middle的左孩子
2026 if (left != null) {
2027 = left;
2028 = middle;
2029 }
2030
2031 if (mid < hi) {
2032 // 递归调用获取(middel的)右孩子。
2033 Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2034 it, str, defaultVal);
2035 // 设置middle为left的父亲，left为middle的左孩子
2036 = right;
2037 = middle;
2038 }
2039
2040 return middle;
2041 }
2042
2043 // 计算节点树为sz的最大深度，也是红色节点的深度值。
2044 private static int computeRedLevel(int sz) {
2045 int level = 0;
2046 for (int m = sz - 1; m >= 0; m = m / 2 - 1)
2047 level++;
2048 return level;
2049 }
2050 }