? ? ?TreeMap有Values、EntrySet、KeySet、PrivateEntryIterator、EntryIterator、ValueIterator、KeyIterator、DescendingKeyIterator、NavigableSubMap、AscendingSubMap、DescendingSubMap、SubMap、Entry共十三個內部類。Entry是在TreeMap中用于表示樹的節點的內部類，已經在《TreeMap源碼分析——基礎分析》中分析過。下面逐一介紹上面的內部類以及TreeMap中提供的和內部類相關的方法。

? ? ?先看Values。

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 }

? ? ?Values類實際上是一個代理，多數方法都是調用TreeMap的方法。在Values的iterator()方法中返回了一個ValuesIterator對象，下面來看和迭代器相關的內部類。PrivateEntryIterator是TreeMap中和迭代器相關的類的基礎，以下是PrivateEntryIterator的內容。

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 }

? ? ?PrivateEntryIterator類的prevEntry()方法用到了predecessor(Entry<K,V> t)方法，下面對這個方法進行介紹。

? ? ?predecessor(Entry<K,V> t)方法返回傳入節點的“前一個”節點，至于前一個節點是哪個節點，這和樹的遍歷次序相關。根據successor(Entry<K,V> t)和predecessor(Entry<K,V> t)方法可以推出TreeMap中樹的遍歷次序是中根遍歷（左孩子-根-右孩子）。

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 }

? ? ?下面是TreeMap中其它和迭代器相關的內部類。

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 }

? ? ?除了迭代器相關的內部類，TreeMap還有兩個和Set相關的內部類，分別是EntrySet和KeySet。兩個類分別表示節點的集合和鍵的集合。下面具體看這兩個類的實現。

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 }

? ? ?介紹完了兩個和Set相關的內部類，現在還剩下四個和SubMap相關的內部類：NavigableSubMap、AscendingSubMap、DescendingSubMap、SubMap。

? ? ?首先看NavigableSubMap，它足足有400多行代碼，相當的多，需要耐心啊。

很長很暈，慎入 1 // NavigableSubMap是一個抽象類，繼承了AbstractMap，實現了NavigableMap接口 2 static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V> 3 implements NavigableMap<K,V>, java.io.Serializable { 4 // 存儲內容的Map 5 final TreeMap<K,V> m; 6 // lowKey、highKey 7 final K lo, hi; 8 // 標識map的邊界是否是map的第一個節點和最后一個節點 9 final boolean fromStart, toEnd; 10 // 是否包含最低lo、最高位置hi 11 final boolean loInclusive, hiInclusive; 12 // 通過上面的三組變量可以組成兩個三元組表示一個集合的兩個端點 13 // 構造方法 14 NavigableSubMap(TreeMap<K,V> m, 15 boolean fromStart, K lo, boolean loInclusive, 16 boolean toEnd, K hi, boolean hiInclusive) { 17 if (!fromStart && !toEnd) { 18 // lo>hi拋出異常 19 if (m.compare(lo, hi) > 0) 20 throw new IllegalArgumentException("fromKey > toKey"); 21 } else { 22 if (!fromStart) // type check 23 m.compare(lo, lo); 24 if (!toEnd) 25 m.compare(hi, hi); 26 } 27 28 this.m = m; 29 this.fromStart = fromStart; 30 this.lo = lo; 31 this.loInclusive = loInclusive; 32 this.toEnd = toEnd; 33 this.hi = hi; 34 this.hiInclusive = hiInclusive; 35 } 36 37 // tooLow 判斷傳入的key是否太小 38 final boolean tooLow(Object key) { 39 // 如果fromStart為false，需要判斷最低邊界 40 if (!fromStart) { 41 int c = m.compare(key, lo); 42 // 如果key<lo或者相等但是map的邊界不包含lo，那么key越界了，即小于最小值 43 if (c < 0 || (c == 0 && !loInclusive)) 44 return true; 45 } 46 // 默認返回false 47 return false; 48 } 49 // 與上面的tooLow類似 50 final boolean tooHigh(Object key) { 51 if (!toEnd) { 52 int c = m.compare(key, hi); 53 if (c > 0 || (c == 0 && !hiInclusive)) 54 return true; 55 } 56 return false; 57 } 58 // 判斷是否在范圍內，即滿足最低最高限制，結合tooLow和tooHigh即可 59 final boolean inRange(Object key) { 60 return !tooLow(key) && !tooHigh(key); 61 } 62 // 是否在封閉的區間內 63 final boolean inClosedRange(Object key) { 64 return (fromStart || m.compare(key, lo) >= 0) 65 && (toEnd || m.compare(hi, key) >= 0); 66 } 67 // 判斷是否是在一個區間內 68 final boolean inRange(Object key, boolean inclusive) { 69 return inclusive ? inRange(key) : inClosedRange(key); 70 } 71 // 獲取絕對的最低的節點 72 final TreeMap.Entry<K,V> absLowest() { 73 /* 如果fromStart為true，獲取第一個節點，否則根據loInclusive是否為true，即是否包含lo來決定獲取Ceiling節點或Higher節點；getCeilingEntry意為獲取指定key的節點或者比指定key大的最小節點，如果不存在則返回null；getHigherEntry意為獲取比指定key大的最小節點，如果不存在，返回null */ 74 TreeMap.Entry<K,V> e = 75 (fromStart ? m.getFirstEntry() : 76 (loInclusive ? m.getCeilingEntry(lo) : 77 m.getHigherEntry(lo))); 78 // 判斷得到的節點是否為空或者key過大 79 return (e == null || tooHigh(e.key)) ? null : e; 80 } 81 // 與absLowest類似 82 final TreeMap.Entry<K,V> absHighest() { 83 TreeMap.Entry<K,V> e = 84 (toEnd ? m.getLastEntry() : 85 (hiInclusive ? m.getFloorEntry(hi) : 86 m.getLowerEntry(hi))); 87 return (e == null || tooLow(e.key)) ? null : e; 88 } 89 // 尋找大于等于key的最小的節點 90 final TreeMap.Entry<K,V> absCeiling(K key) { 91 // 如果key太小，返回絕對的最小的節點 92 if (tooLow(key)) 93 return absLowest(); 94 // 獲取允許的key的極限節點（滿足要求的最小的節點） 95 TreeMap.Entry<K,V> e = m.getCeilingEntry(key); 96 return (e == null || tooHigh(e.key)) ? null : e; 97 } 98 // 和absCeiling類似，只是獲取的不包含相等的情況，而是尋找大于key的最小節點 99 final TreeMap.Entry<K,V> absHigher(K key) { 100 if (tooLow(key)) 101 return absLowest(); 102 TreeMap.Entry<K,V> e = m.getHigherEntry(key); 103 return (e == null || tooHigh(e.key)) ? null : e; 104 } 105 // 獲取絕對的小于等于key的節點 106 final TreeMap.Entry<K,V> absFloor(K key) { 107 // 指定的key超出了hi，直接返回絕對的允許的最大的節點 108 if (tooHigh(key)) 109 return absHighest(); 110 /* getFloorEntry 獲取的是指定key的節點，如果不存在這樣的節點，就去獲取比指定key小的最大的節點，如果這樣的節點也不存在，返回null*/ 111 TreeMap.Entry<K,V> e = m.getFloorEntry(key); 112 return (e == null || tooLow(e.key)) ? null : e; 113 } 114 // 與上面的absFloor類似，只是不包含等于的情況 115 final TreeMap.Entry<K,V> absLower(K key) { 116 if (tooHigh(key)) 117 return absHighest(); 118 TreeMap.Entry<K,V> e = m.getLowerEntry(key); 119 return (e == null || tooLow(e.key)) ? null : e; 120 } 121 122 // 返回比最大的節點“還要大”的節點（Fence是柵欄、圍欄的意思） 123 final TreeMap.Entry<K,V> absHighFence() { 124 /* 如果toEnd是true，那么“圍在”它外面的是null，如果是false，根據hi是否被包含返回getHigherEntry或getCeilingEntry，這兩個方法意思在上面的方法中說明過了 */ 125 return (toEnd ? null : (hiInclusive ? 126 m.getHigherEntry(hi) : 127 m.getCeilingEntry(hi))); 128 } 129 130 // 與absHighFence類似 131 final TreeMap.Entry<K,V> absLowFence() { 132 return (fromStart ? null : (loInclusive ? 133 m.getLowerEntry(lo) : 134 m.getFloorEntry(lo))); 135 } 136 137 abstract TreeMap.Entry<K,V> subLowest(); 138 abstract TreeMap.Entry<K,V> subHighest(); 139 abstract TreeMap.Entry<K,V> subCeiling(K key); 140 abstract TreeMap.Entry<K,V> subHigher(K key); 141 abstract TreeMap.Entry<K,V> subFloor(K key); 142 abstract TreeMap.Entry<K,V> subLower(K key); 143 abstract Iterator<K> keyIterator(); 144 abstract Iterator<K> descendingKeyIterator(); 145 146 // 如果fromStart、toEnd都是true，那么判斷空、獲取大小都是直接通過m，不然就必須使用entrySet()先獲取節點集 147 public boolean isEmpty() { 148 return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty(); 149 } 150 151 public int size() { 152 return (fromStart && toEnd) ? m.size() : entrySet().size(); 153 } 154 // 判斷是否存在key先判斷范圍，在通過TreeMap的containKey方法來判斷 155 public final boolean containsKey(Object key) { 156 return inRange(key) && m.containsKey(key); 157 } 158 // 添加節點 159 public final V put(K key, V value) { 160 // 判斷要添加的key是否在范圍內 161 if (!inRange(key)) 162 throw new IllegalArgumentException("key out of range"); 163 return m.put(key, value); 164 } 165 public final V get(Object key) { 166 return !inRange(key)? null : m.get(key); 167 } 168 public final V remove(Object key) { 169 return !inRange(key)? null : m.remove(key); 170 } 171 public final Map.Entry<K,V> ceilingEntry(K key) { 172 /* exportEntry(TreeMap.Entry<K,V> e)方法返回的是Map.Entry<K,V>對象，它的Key 和Value和傳入的節點的Key 和Value相同 */ 173 return exportEntry(subCeiling(key)); 174 } 175 public final K ceilingKey(K key) { 176 // keyOrNull根據傳入的節點是否為null返回null或節點的key（相當于提供了一個null安全的獲取key的方法） 177 return keyOrNull(subCeiling(key)); 178 } 179 public final Map.Entry<K,V> higherEntry(K key) { 180 return exportEntry(subHigher(key)); 181 } 182 public final K higherKey(K key) { 183 return keyOrNull(subHigher(key)); 184 } 185 public final Map.Entry<K,V> floorEntry(K key) { 186 return exportEntry(subFloor(key)); 187 } 188 public final K floorKey(K key) { 189 return keyOrNull(subFloor(key)); 190 } 191 public final Map.Entry<K,V> lowerEntry(K key) { 192 return exportEntry(subLower(key)); 193 } 194 public final K lowerKey(K key) { 195 return keyOrNull(subLower(key)); 196 } 197 public final K firstKey() { 198 return key(subLowest()); 199 } 200 public final K lastKey() { 201 return key(subHighest()); 202 } 203 public final Map.Entry<K,V> firstEntry() { 204 return exportEntry(subLowest()); 205 } 206 public final Map.Entry<K,V> lastEntry() { 207 return exportEntry(subHighest()); 208 } 209 // 返回并刪除第一個節點 210 public final Map.Entry<K,V> pollFirstEntry() { 211 TreeMap.Entry<K,V> e = subLowest(); 212 Map.Entry<K,V> result = exportEntry(e); 213 if (e != null) 214 m.deleteEntry(e); 215 return result; 216 } 217 // 返回并刪除最后一個節點 218 public final Map.Entry<K,V> pollLastEntry() { 219 TreeMap.Entry<K,V> e = subHighest(); 220 Map.Entry<K,V> result = exportEntry(e); 221 if (e != null) 222 m.deleteEntry(e); 223 return result; 224 } 225 226 // 這些都是視圖 227 transient NavigableMap<K,V> descendingMapView = null; 228 transient EntrySetView entrySetView = null; 229 transient KeySet<K> navigableKeySetView = null; 230 // 返回TreeMap的KeySet 231 public final NavigableSet<K> navigableKeySet() { 232 KeySet<K> nksv = navigableKeySetView; 233 return (nksv != null) ? nksv : 234 (navigableKeySetView = new TreeMap.KeySet(this)); 235 } 236 public final Set<K> keySet() { 237 return navigableKeySet(); 238 } 239 // 逆序的KeySet 240 public NavigableSet<K> descendingKeySet() { 241 return descendingMap().navigableKeySet(); 242 } 243 // 返回一個子Map 244 public final SortedMap<K,V> subMap(K fromKey, K toKey) { 245 return subMap(fromKey, true, toKey, false); 246 } 247 // 下面這幾個方法會在后面給出分析 248 public final SortedMap<K,V> headMap(K toKey) { 249 return headMap(toKey, false); 250 } 251 public final SortedMap<K,V> tailMap(K fromKey) { 252 return tailMap(fromKey, true); 253 } 254 255 // 視圖類 256 abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> { 257 private transient int size = -1, sizeModCount; 258 // 返回子Map的大小 259 public int size() { 260 // 如果fromStart和toEnd都是true，返回的是m的size 261 if (fromStart && toEnd) 262 return m.size(); 263 // size=-1或標記size不同，重新計算一次size 264 if (size == -1 || sizeModCount != m.modCount) { 265 sizeModCount = m.modCount; 266 size = 0; 267 Iterator i = iterator(); 268 while (i.hasNext()) { 269 size++; 270 i.next(); 271 } 272 } 273 return size; 274 } 275 // 判斷EntrySet是否為空 276 public boolean isEmpty() { 277 TreeMap.Entry<K,V> n = absLowest(); 278 return n == null || tooHigh(n.key); 279 } 280 // 判斷是否包含某個對象 281 public boolean contains(Object o) { 282 if (!(o instanceof Map.Entry)) 283 return false; 284 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 285 K key = entry.getKey(); 286 // key不在范圍內，返回false 287 if (!inRange(key)) 288 return false; 289 // 判斷是否有鍵和值如傳入節點的鍵和值相等的節點 290 TreeMap.Entry node = m.getEntry(key); 291 return node != null && 292 valEquals(node.getValue(), entry.getValue()); 293 } 294 // 移除一個節點 295 public boolean remove(Object o) { 296 if (!(o instanceof Map.Entry)) 297 return false; 298 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 299 K key = entry.getKey(); 300 if (!inRange(key)) 301 return false; 302 TreeMap.Entry<K,V> node = m.getEntry(key); 303 // 找到節點并移除，返回true 304 if (node!=null && valEquals(node.getValue(),entry.getValue())){ 305 m.deleteEntry(node); 306 return true; 307 } 308 return false; 309 } 310 } 311 312 //子類迭代器 313 abstract class SubMapIterator<T> implements Iterator<T> { 314 // 上一次被返回的節點 315 TreeMap.Entry<K,V> lastReturned; 316 // 下一個節點 317 TreeMap.Entry<K,V> next; 318 // “柵欄”key（如果是向大的方向遍歷，不能訪問key大于等于fenceKey的節點；如果是向小的方向遍歷，不能訪問key小于等于fenceKey的節點） 319 final K fenceKey; 320 int expectedModCount; 321 // 構造方法 322 SubMapIterator(TreeMap.Entry<K,V> first, 323 TreeMap.Entry<K,V> fence) { 324 expectedModCount = m.modCount; 325 lastReturned = null; 326 next = first; 327 fenceKey = fence == null ? null : fence.key; 328 } 329 // 判斷是否還有下一個節點 330 public final boolean hasNext() { 331 // 與普通的hasNext的判斷不同的是這里必須判斷next的key是否超出了fenceKey 332 return next != null && next.key != fenceKey; 333 } 334 // 獲得下一個節點的方法，比較容易理解 335 final TreeMap.Entry<K,V> nextEntry() { 336 TreeMap.Entry<K,V> e = next; 337 if (e == null || e.key == fenceKey) 338 throw new NoSuchElementException(); 339 if (m.modCount != expectedModCount) 340 throw new ConcurrentModificationException(); 341 next = successor(e); 342 lastReturned = e; 343 return e; 344 } 345 // 另一種遍歷方法，向前遍歷 346 final TreeMap.Entry<K,V> prevEntry() { 347 TreeMap.Entry<K,V> e = next; 348 if (e == null || e.key == fenceKey) 349 throw new NoSuchElementException(); 350 if (m.modCount != expectedModCount) 351 throw new ConcurrentModificationException(); 352 next = predecessor(e); 353 lastReturned = e; 354 return e; 355 } 356 // 刪除節點后可以繼續遍歷剩余的節點，因為刪除前用next保留了lastReturned節點，而這個節點在刪除操作的過程中被替換成了它的繼承者 357 final void removeAscending() { 358 if (lastReturned == null) 359 throw new IllegalStateException(); 360 if (m.modCount != expectedModCount) 361 throw new ConcurrentModificationException(); 362 if (lastReturned.left != null && lastReturned.right != null) 363 // next指向lastReturned所指向的節點，這個節點的內容在刪除lastReturned的時候被改變了 364 next = lastReturned; 365 m.deleteEntry(lastReturned); 366 lastReturned = null; 367 expectedModCount = m.modCount; 368 } 369 // 刪除之后next指向的節點其實被刪除了，不能繼續迭代訪問 370 final void removeDescending() { 371 if (lastReturned == null) 372 throw new IllegalStateException(); 373 if (m.modCount != expectedModCount) 374 throw new ConcurrentModificationException(); 375 m.deleteEntry(lastReturned); 376 lastReturned = null; 377 expectedModCount = m.modCount; 378 } 379 380 } 381 //下面的幾個內部類很簡單，都是對SubMapIterator的調用或間接調用，不再解釋 382 final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { 383 SubMapEntryIterator(TreeMap.Entry<K,V> first, 384 TreeMap.Entry<K,V> fence) { 385 super(first, fence); 386 } 387 public Map.Entry<K,V> next() { 388 return nextEntry(); 389 } 390 public void remove() { 391 removeAscending(); 392 } 393 } 394 395 final class SubMapKeyIterator extends SubMapIterator<K> { 396 SubMapKeyIterator(TreeMap.Entry<K,V> first, 397 TreeMap.Entry<K,V> fence) { 398 super(first, fence); 399 } 400 public K next() { 401 return nextEntry().key; 402 } 403 public void remove() { 404 removeAscending(); 405 } 406 } 407 408 final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { 409 DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last, 410 TreeMap.Entry<K,V> fence) { 411 super(last, fence); 412 } 413 414 public Map.Entry<K,V> next() { 415 return prevEntry(); 416 } 417 public void remove() { 418 removeDescending(); 419 } 420 } 421 422 final class DescendingSubMapKeyIterator extends SubMapIterator<K> { 423 DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last, 424 TreeMap.Entry<K,V> fence) { 425 super(last, fence); 426 } 427 public K next() { 428 return prevEntry().key; 429 } 430 public void remove() { 431 removeDescending(); 432 } 433 } 434 }

? ? ?NavigableSubMap類算是看了一遍，很復雜，自身是個內部類，它里面還包含了好幾個類。理解它的代碼需要部分TreeMap中的其他代碼的深入理解，如涉及到的deleteEntry等方法（見《TreeMap源碼分析——基礎分析》）。

? ? ?下面看TreeMap的其他內部類，它們是NavigableSubMap的子類。

? ? ?AscendingSubMap

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 }

? ? ?DescendingSubMap

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 }

? ? ?最后一個內部類是SubMap，它比較特別。這個類存在僅僅為了序列化兼容之前的版本不支持NavigableMap TreeMap。它被翻譯成一個舊版本AscendingSubMap子映射到一個新版本。這個類是從來沒有以其他方式使用。

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 }

? ? ?結合上面的內部類分析和《TreeMap源碼分析——基礎分析》，對TreeMap的實現應該有個大致輪廓。不過TreeMap的代碼很長很復雜，不自己看一遍分析一邊，很難想明白，很難理解進去。

? ? ?自己也理解的不是很好，如果有牛人有對TreeMap的看法，望多指點。

?

?

?

?

?

轉載于:https://www.cnblogs.com/hzmark/archive/2013/01/05/TreeMap-Deep.html

總結

以上是生活随笔為你收集整理的TreeMap源码分析——深入分析（基于JDK1.6）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。