TreeMap源码分析——深入分析（基于JDK1.6）

 1 // 从类的定义可以看出，Values是一个集合类
 2 class Values extends AbstractCollection<V> {
 3     // 提供集合类Values的迭代器
 4     public Iterator<V> iterator() {
 5         return new ValueIterator(getFirstEntry());
 6     }
 7     // 返回TreeMap中保存的节点数
 8     public int size() {
 9         return TreeMap.this.size();
10     }
11     // 判断TreeMap中是否存在Value为o的节点
12     public boolean contains(Object o) {
13         return TreeMap.this.containsValue(o);
14     }
15     // 删除一个对象
16     public boolean remove(Object o) {
17         // 遍历TreeMap
18         for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
19             // 寻找值相等的节点
20             if (valEquals(e.getValue(), o)) {
21                 // 删除找到的节点
22                 deleteEntry(e);
23                 return true;
24             }
25         }
26         return false;
27     }
28     // 清空TreeMap
29     public void clear() {
30         TreeMap.this.clear();
31     }
32 }

 1 abstract class PrivateEntryIterator<T> implements Iterator<T> {
 2     // 指向next的引用
 3 Entry<K,V> next;
 4 // 保留对上一次返回节点的引用
 5     Entry<K,V> lastReturned;
 6     int expectedModCount;
 7     // 构造方法，lastReturned置空，next指向传入的节点
 8     PrivateEntryIterator(Entry<K,V> first) {
 9         expectedModCount = modCount;
10         lastReturned = null;
11         next = first;
12     }
13     // 判断是否还有下一个节点
14     public final boolean hasNext() {
15         return next != null;
16     }
17     // 返回下一个节点
18     final Entry<K,V> nextEntry() {
19         Entry<K,V> e = next;
20         if (e == null)
21             throw new NoSuchElementException();
22         if (modCount != expectedModCount)
23             throw new ConcurrentModificationException();
24         // next移动到它的继承者
25         next = successor(e);
26         // 记录被返回的节点
27         lastReturned = e;
28         // 返回原先记录的next节点
29         return e;
30     }
31     // 前一个节点
32     final Entry<K,V> prevEntry() {
33         Entry<K,V> e = next;
34         if (e == null)
35             throw new NoSuchElementException();
36         if (modCount != expectedModCount)
37             throw new ConcurrentModificationException();
38         // 获取指定节点的“前任”（按遍历次序的前一个节点）
39         next = predecessor(e);
40         // 记录被返回的节点
41         lastReturned = e;
42         return e;
43     }
44     // 移除最近一次被返回的节点
45     public void remove() {
46         if (lastReturned == null)
47             throw new IllegalStateException();
48         if (modCount != expectedModCount)
49             throw new ConcurrentModificationException();
50         // deleted entries are replaced by their successors
51         if (lastReturned.left != null && lastReturned.right != null)
52             /* 如果被删除节点有两个孩子，删除节点e的时候e的引用会被修改为指向原节点的继承者，所以这里先保留next对lastReturned的引用，这样在删除节点后就能获取到继承者的引用，继而继续遍历树 */
53             next = lastReturned;
54         // 删除节点
55         deleteEntry(lastReturned);
56         expectedModCount = modCount;
57         lastReturned = null;
58     }
59 }

 1 static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
 2     if (t == null)
 3         return null;
 4 else if (t.left != null) {
 5     // 获得左孩子
 6         Entry<K,V> p = t.left;
 7         // 对左孩子进行遍历，获取左孩子最右的子孙
 8         while (p.right != null)
 9             p = p.right;
10         return p;
11 } else {
12     // 获取t的父节点
13         Entry<K,V> p = t.parent;
14         Entry<K,V> ch = t; 
15 // 沿着右孩子向上查找继承者，直到根节点或找到节点ch是其父节点的右孩子的节点
16         while (p != null && ch == p.left) {
17             ch = p;
18             p = p.parent;
19         }
20         return p;
21     }
22 }

 1 // EntryIterator就是树节点的迭代器，和PrivateEntryIterator完全一样，因为提供的方法都直接的调用而来父类的方法。
 2 final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
 3     EntryIterator(Entry<K,V> first) {
 4         super(first);
 5     }
 6     public Map.Entry<K,V> next() {
 7         return nextEntry();
 8     }
 9 }
10 /** Value的迭代器 */
11 final class ValueIterator extends PrivateEntryIterator<V> {
12     ValueIterator(Entry<K,V> first) {
13         super(first);
14 }
15 // next()方法返回的是节点的value值
16     public V next() {
17         return nextEntry().value;
18     }
19 }
20 /** Key迭代器 */
21 final class KeyIterator extends PrivateEntryIterator<K> {
22     KeyIterator(Entry<K,V> first) {
23         super(first);
24 }
25 // next()方法返回的是节点的key
26     public K next() {
27         return nextEntry().key;
28     }
29 }
30 /** 逆序的Key迭代器 */
31 final class DescendingKeyIterator extends PrivateEntryIterator<K> {
32     DescendingKeyIterator(Entry<K,V> first) {
33         super(first);
34 }
35 // next()方法返回的是节点的“前任”（按照遍历次序的前一个节点）的key
36     public K next() {
37         return prevEntry().key;
38     }
39 }

 1 // 继承自AbstractSet说明是一个Set
 2 class EntrySet extends AbstractSet<Map.Entry<K,V>> {
 3     // iterator()方法返回的是上面介绍过的EntryIterator对象
 4     public Iterator<Map.Entry<K,V>> iterator() {
 5         return new EntryIterator(getFirstEntry());
 6     }
 7     // 判断是否包含某个节点的方法
 8     public boolean contains(Object o) {
 9         if (!(o instanceof Map.Entry))
10             return false;
11         Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
12         V value = entry.getValue();
13         Entry<K,V> p = getEntry(entry.getKey());
14         // 判断是否包含某个对象的标准是存在节点的key的与传入对象的key值，且该节点的value也与存入对象的value值相等
15         return p != null && valEquals(p.getValue(), value);
16     }
17     // 删除一个对象
18     public boolean remove(Object o) {
19         if (!(o instanceof Map.Entry))
20             return false;
21         Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
22         V value = entry.getValue();
23         Entry<K,V> p = getEntry(entry.getKey());
24         // 如果存在该对象，则进行删除操作并返回true
25         if (p != null && valEquals(p.getValue(), value)) {
26             deleteEntry(p);
27             return true;
28         }
29         // 不存在直接返回false
30         return false;
31     }
32     // size()返回的是TreeMap中包含的节点的数量
33     public int size() {
34         return TreeMap.this.size();
35     }
36     // clear()方法实际调用了TreeMap的clear()方法，和size()方法都是代理方法
37     public void clear() {
38         TreeMap.this.clear();
39     }
40 }

 1 // KeySet同样继承自AbstractSet。KeySet实现了NavigableSet接口，意味着是“可导航”的Set，包含更多的获取指定节点的方法
 2 static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
 3 private final NavigableMap<E, Object> m;
 4 // 构造方法
 5     KeySet(NavigableMap<E,Object> map) { m = map; }
 6     // 
 7     public Iterator<E> iterator() {
 8         if (m instanceof TreeMap)
 9             return ((TreeMap<E,Object>)m).keyIterator();
10         else
11             // 这里涉及到的NavigableSubMap将在后面介绍
12             return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
13     }
14 
15     public Iterator<E> descendingIterator() {
16         if (m instanceof TreeMap)
17             return ((TreeMap<E,Object>)m).descendingKeyIterator();
18         else
19             return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
20     }
21     // size()方法返回的是通过构造方法传入的map的大小
22 public int size() { return m.size(); }
23 // isEmpty()判断是否为空也是判断的传入的map是否为空
24 public boolean isEmpty() { return m.isEmpty(); }
25 // contains(Object o)方法判断传入map中是否包含这个key
26     public boolean contains(Object o) { return m.containsKey(o); }
27 public void clear() { m.clear(); }
28 // 因为传入的map是NavigableMap，所以下面这几个方法都是代理方法，调用map中相应的方法
29     public E lower(E e) { return m.lowerKey(e); }
30     public E floor(E e) { return m.floorKey(e); }
31     public E ceiling(E e) { return m.ceilingKey(e); }
32     public E higher(E e) { return m.higherKey(e); }
33     public E first() { return m.firstKey(); }
34 public E last() { return m.lastKey(); }
35 // 获取传入map的比较器
36 public Comparator<? super E> comparator() { return m.comparator(); }
37 // 获取map中第一个节点的key
38     public E pollFirst() {
39         Map.Entry<E,Object> e = m.pollFirstEntry();
40         return e == null? null : e.getKey();
41 }
42 // 获取map中最后一个节点的key
43     public E pollLast() {
44         Map.Entry<E,Object> e = m.pollLastEntry();
45         return e == null? null : e.getKey();
46 }
47 // 删除一个对象，实际上是删除map中以这个对象为key的一个节点
48     public boolean remove(Object o) {
49         int oldSize = size();
50         m.remove(o);
51         return size() != oldSize;
52 }
53 // 下面的方法都是通过NavigableMap和TreeSet实现的，NavigableMap将在下文介绍，TreeSet将另开博文介绍
54     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
55                                       E toElement,   boolean toInclusive) {
56         return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
57                                            toElement,   toInclusive));
58     }
59     public NavigableSet<E> headSet(E toElement, boolean inclusive) {
60         return new TreeSet<E>(m.headMap(toElement, inclusive));
61     }
62     public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
63         return new TreeSet<E>(m.tailMap(fromElement, inclusive));
64     }
65     public SortedSet<E> subSet(E fromElement, E toElement) {
66         return subSet(fromElement, true, toElement, false);
67     }
68     public SortedSet<E> headSet(E toElement) {
69         return headSet(toElement, false);
70     }
71     public SortedSet<E> tailSet(E fromElement) {
72         return tailSet(fromElement, true);
73     }
74     public NavigableSet<E> descendingSet() {
75         return new TreeSet(m.descendingMap());
76     }
77 }

 1 // AscendingSubMap继承自NavigableSubMap
 2 static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
 3     private static final long serialVersionUID = 912986545866124060L;
 4     // 构造方法，直接调用父类构造方法
 5     AscendingSubMap(TreeMap<K,V> m,
 6                         boolean fromStart, K lo, boolean loInclusive,
 7                         boolean toEnd,     K hi, boolean hiInclusive) {
 8         super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
 9     }
10     // 获得比较器
11     public Comparator<? super K> comparator() {
12         return m.comparator();
13     }
14     // “截取”子Map
15     public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
16                                         K toKey,   boolean toInclusive) {
17         // 截取之前判断是否超出范围
18         if (!inRange(fromKey, fromInclusive))
19             throw new IllegalArgumentException("fromKey out of range");
20         if (!inRange(toKey, toInclusive))
21             throw new IllegalArgumentException("toKey out of range");
22         return new AscendingSubMap(m,
23                                        false, fromKey, fromInclusive,
24                                        false, toKey,   toInclusive);
25     }
26     // “截取”子Map，headMap通过构造方法便可以实现
27     public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
28         if (!inRange(toKey, inclusive))
29             throw new IllegalArgumentException("toKey out of range");
30         return new AscendingSubMap(m,
31                                        fromStart, lo,    loInclusive,
32                                        false,     toKey, inclusive);
33     }
34     // 和headMap类似
35     public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
36         if (!inRange(fromKey, inclusive))
37             throw new IllegalArgumentException("fromKey out of range");
38         return new AscendingSubMap(m,
39                                        false, fromKey, inclusive,
40                                        toEnd, hi,      hiInclusive);
41     }
42     // 这个方法涉及到DescendingSubMap类的构造方法，在下面会介绍到
43     public NavigableMap<K,V> descendingMap() {
44         NavigableMap<K,V> mv = descendingMapView;
45         return (mv != null) ? mv :
46                 (descendingMapView =
47                  new DescendingSubMap(m,
48                                       fromStart, lo, loInclusive,
49                                       toEnd,     hi, hiInclusive));
50     }
51     // 下面两个方法都是对上面提到过的构造方法的调用
52     Iterator<K> keyIterator() {
53         return new SubMapKeyIterator(absLowest(), absHighFence());
54     }
55     Iterator<K> descendingKeyIterator() {
56         return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
57 }
58     // AscendingEntrySetView是一个视图类，重写了父类的iterator()方法，调用SubMapEntryIterator构造迭代器
59     final class AscendingEntrySetView extends EntrySetView {
60         public Iterator<Map.Entry<K,V>> iterator() {
61             return new SubMapEntryIterator(absLowest(), absHighFence());
62         }
63     }
64     // 获取节点集合的方法
65     public Set<Map.Entry<K,V>> entrySet() {
66         EntrySetView es = entrySetView;
67         return (es != null) ? es : new AscendingEntrySetView();
68     }
69     // 父类中抽象方法的实现，都很简单
70     TreeMap.Entry<K,V> subLowest()       { return absLowest(); }
71     TreeMap.Entry<K,V> subHighest()      { return absHighest(); }
72     TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
73     TreeMap.Entry<K,V> subHigher(K key)  { return absHigher(key); }
74     TreeMap.Entry<K,V> subFloor(K key)   { return absFloor(key); }
75     TreeMap.Entry<K,V> subLower(K key)   { return absLower(key); }
76 }

 1 // DescendingSubMap也继承自NavigableSubMap，和上面的AscendingSubMap对应
 2 static final class DescendingSubMap<K,V>  extends NavigableSubMap<K,V> {
 3     private static final long serialVersionUID = 912986545866120460L;
 4     DescendingSubMap(TreeMap<K,V> m,
 5                         boolean fromStart, K lo, boolean loInclusive,
 6                         boolean toEnd,     K hi, boolean hiInclusive) {
 7         super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
 8     }
 9     // 构造一个“相反”的比较器
10     private final Comparator<? super K> reverseComparator =
11         Collections.reverseOrder(m.comparator);
12     // 获取的比较器是“相反”的比较器，比较结果会对调
13     public Comparator<? super K> comparator() {
14         return reverseComparator;
15     }
16     // subMap方法和AscendingSubMap类中类似
17     public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
18                                         K toKey,   boolean toInclusive) {
19         if (!inRange(fromKey, fromInclusive))
20             throw new IllegalArgumentException("fromKey out of range");
21         if (!inRange(toKey, toInclusive))
22             throw new IllegalArgumentException("toKey out of range");
23         return new DescendingSubMap(m,
24                                         false, toKey,   toInclusive,
25                                         false, fromKey, fromInclusive);
26     }
27     // 与AscendingSubMap中其实是相反的
28     public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
29         if (!inRange(toKey, inclusive))
30             throw new IllegalArgumentException("toKey out of range");
31         // 因为DescendingSubMap表示的是逆序的map，所以其实是通过获取原序的尾部
32         return new DescendingSubMap(m,
33                                         false, toKey, inclusive,
34                                         toEnd, hi,    hiInclusive);
35     }
36     // 与headMap对应，tailMap其实获取的是原序中的头部
37     public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){
38         if (!inRange(fromKey, inclusive))
39             throw new IllegalArgumentException("fromKey out of range");
40         return new DescendingSubMap(m,
41                                         fromStart, lo, loInclusive,
42                                         false, fromKey, inclusive);
43     }
44     // 逆序的逆序其实是正序
45     public NavigableMap<K,V> descendingMap() {
46         NavigableMap<K,V> mv = descendingMapView;
47         return (mv != null) ? mv :
48                 (descendingMapView =
49                  new AscendingSubMap(m,
50                                      fromStart, lo, loInclusive,
51                                      toEnd,     hi, hiInclusive));
52     }
53     // 剩余内容和AscendingSubMap很类似，就不说了
54     Iterator<K> keyIterator() {
55         return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
56     }
57     Iterator<K> descendingKeyIterator() {
58         return new SubMapKeyIterator(absLowest(), absHighFence());
59     }
60     final class DescendingEntrySetView extends EntrySetView {
61         public Iterator<Map.Entry<K,V>> iterator() {
62             return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
63         }
64     }
65     public Set<Map.Entry<K,V>> entrySet() {
66         EntrySetView es = entrySetView;
67         return (es != null) ? es : new DescendingEntrySetView();
68     }
69     TreeMap.Entry<K,V> subLowest()       { return absHighest(); }
70     TreeMap.Entry<K,V> subHighest()      { return absLowest(); }
71     TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
72     TreeMap.Entry<K,V> subHigher(K key)  { return absLower(key); }
73     TreeMap.Entry<K,V> subFloor(K key)   { return absCeiling(key); }
74     TreeMap.Entry<K,V> subLower(K key)   { return absHigher(key); }
75 }

 1 // SubMap 继承自AbstractMap；这个类存在仅仅为了序列化兼容之前的版本不支持NavigableMap TreeMap。它被翻译成一个旧版本AscendingSubMap子映射到一个新版本。这个类是从来没有以其他方式使用。
 2 private class SubMap extends AbstractMap<K,V>
 3     implements SortedMap<K,V>, java.io.Serializable {
 4     private static final long serialVersionUID = -6520786458950516097L;
 5     // 标识是否从map的开始到结尾都属于子map
 6     private boolean fromStart = false, toEnd = false;
 7     // 开始位置和结束位置的key
 8     private K fromKey, toKey;
 9     private Object readResolve() {
10         return new AscendingSubMap(TreeMap.this,
11                                        fromStart, fromKey, true,
12                                        toEnd, toKey, false);
13     }
14     // 结合类定义和类的说明就明白为什么提供了这么多方法但是都不能用了
15     public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
16     public K lastKey() { throw new InternalError(); }
17     public K firstKey() { throw new InternalError(); }
18     public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
19     public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
20     public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
21     public Comparator<? super K> comparator() { throw new InternalError(); }
22 }