Java集合--TreeMap
生活随笔
收集整理的這篇文章主要介紹了
Java集合--TreeMap
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
轉(zhuǎn)載請注明出處：http://www.cnblogs.com/skywang12345/admin/EditPosts.aspx?postid=3310928
?
第1部分 TreeMap介紹
TreeMap 簡介
TreeMap 是一個(gè)有序的key-value集合，它是通過紅黑樹實(shí)現(xiàn)的。
TreeMap?繼承于AbstractMap，所以它是一個(gè)Map，即一個(gè)key-value集合。
TreeMap 實(shí)現(xiàn)了NavigableMap接口，意味著它支持一系列的導(dǎo)航方法。比如返回有序的key集合。
TreeMap 實(shí)現(xiàn)了Cloneable接口，意味著它能被克隆。
TreeMap 實(shí)現(xiàn)了java.io.Serializable接口，意味著它支持序列化。
TreeMap基于紅黑樹（Red-Black tree）實(shí)現(xiàn)。該映射根據(jù)其鍵的自然順序進(jìn)行排序，或者根據(jù)創(chuàng)建映射時(shí)提供的 Comparator 進(jìn)行排序，具體取決于使用的構(gòu)造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的時(shí)間復(fù)雜度是 log(n) 。
另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。
?
TreeMap的構(gòu)造函數(shù)
// 默認(rèn)構(gòu)造函數(shù)。使用該構(gòu)造函數(shù)，TreeMap中的元素按照自然排序進(jìn)行排列。 TreeMap()// 創(chuàng)建的TreeMap包含Map TreeMap(Map<? extends K, ? extends V> copyFrom)// 指定Tree的比較器 TreeMap(Comparator<? super K> comparator)// 創(chuàng)建的TreeSet包含copyFrom TreeMap(SortedMap<K, ? extends V> copyFrom)?
TreeMap的API
Entry<K, V> ceilingEntry(K key) K ceilingKey(K key) void clear() Object clone() Comparator<? super K> comparator() boolean containsKey(Object key) NavigableSet<K> descendingKeySet() NavigableMap<K, V> descendingMap() Set<Entry<K, V>> entrySet() Entry<K, V> firstEntry() K firstKey() Entry<K, V> floorEntry(K key) K floorKey(K key) V get(Object key) NavigableMap<K, V> headMap(K to, boolean inclusive) SortedMap<K, V> headMap(K toExclusive) Entry<K, V> higherEntry(K key) K higherKey(K key) boolean isEmpty() Set<K> keySet() Entry<K, V> lastEntry() K lastKey() Entry<K, V> lowerEntry(K key) K lowerKey(K key) NavigableSet<K> navigableKeySet() Entry<K, V> pollFirstEntry() Entry<K, V> pollLastEntry() V put(K key, V value) V remove(Object key) int size() SortedMap<K, V> subMap(K fromInclusive, K toExclusive) NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) NavigableMap<K, V> tailMap(K from, boolean inclusive) SortedMap<K, V> tailMap(K fromInclusive)?
第2部分 TreeMap數(shù)據(jù)結(jié)構(gòu)
TreeMap的繼承關(guān)系
java.lang.Object? java.util.AbstractMap<K, V>? java.util.TreeMap<K, V>public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}?
TreeMap與Map關(guān)系如下圖：
從圖中可以看出：
(01) TreeMap實(shí)現(xiàn)繼承于AbstractMap，并且實(shí)現(xiàn)了NavigableMap接口。
(02) TreeMap的本質(zhì)是R-B Tree(紅黑樹)，它包含幾個(gè)重要的成員變量：?root,?size,?comparator。
root?是紅黑數(shù)的根節(jié)點(diǎn)。它是Entry類型，Entry是紅黑數(shù)的節(jié)點(diǎn)，它包含了紅黑數(shù)的6個(gè)基本組成成分：key(鍵)、value(值)、left(左孩子)、right(右孩子)、parent(父節(jié)點(diǎn))、color(顏色)。Entry節(jié)點(diǎn)根據(jù)key進(jìn)行排序，Entry節(jié)點(diǎn)包含的內(nèi)容為value。?
紅黑數(shù)排序時(shí)，根據(jù)Entry中的key進(jìn)行排序；Entry中的key比較大小是根據(jù)比較器comparator來進(jìn)行判斷的。
size是紅黑數(shù)中節(jié)點(diǎn)的個(gè)數(shù)。
關(guān)于紅黑數(shù)的具體算法，請參考"紅黑樹(一) 原理和算法詳細(xì)介紹"。
?
第3部分 TreeMap源碼解析(基于JDK1.6.0_45)
為了更了解TreeMap的原理，下面對TreeMap源碼代碼作出分析。我們先給出源碼內(nèi)容，后面再對源碼進(jìn)行詳細(xì)說明，當(dāng)然，源碼內(nèi)容中也包含了詳細(xì)的代碼注釋。讀者閱讀的時(shí)候，建議先看后面的說明，先建立一個(gè)整體印象；之后再閱讀源碼。
1 package java.util;2 3 public class TreeMap<K,V>4 extends AbstractMap<K,V>5 implements NavigableMap<K,V>, Cloneable, java.io.Serializable6 {7 8 // 比較器。用來給TreeMap排序9 private final Comparator<? super K> comparator;10 11 // TreeMap是紅黑樹實(shí)現(xiàn)的，root是紅黑書的根節(jié)點(diǎn)12 private transient Entry<K,V> root = null;13 14 // 紅黑樹的節(jié)點(diǎn)總數(shù)15 private transient int size = 0;16 17 // 記錄紅黑樹的修改次數(shù)18 private transient int modCount = 0;19 20 // 默認(rèn)構(gòu)造函數(shù)21 public TreeMap() {22 comparator = null;23 }24 25 // 帶比較器的構(gòu)造函數(shù)26 public TreeMap(Comparator<? super K> comparator) {27 this.comparator = comparator;28 }29 30 // 帶Map的構(gòu)造函數(shù)，Map會(huì)成為TreeMap的子集31 public TreeMap(Map<? extends K, ? extends V> m) {32 comparator = null;33 putAll(m);34 }35 36 // 帶SortedMap的構(gòu)造函數(shù)，SortedMap會(huì)成為TreeMap的子集37 public TreeMap(SortedMap<K, ? extends V> m) {38 comparator = m.comparator();39 try {40 buildFromSorted(m.size(), m.entrySet().iterator(), null, null);41 } catch (java.io.IOException cannotHappen) {42 } catch (ClassNotFoundException cannotHappen) {43 }44 }45 46 public int size() {47 return size;48 }49 50 // 返回TreeMap中是否保護(hù)“鍵(key)”51 public boolean containsKey(Object key) {52 return getEntry(key) != null;53 }54 55 // 返回TreeMap中是否保護(hù)"值(value)"56 public boolean containsValue(Object value) {57 // getFirstEntry() 是返回紅黑樹的第一個(gè)節(jié)點(diǎn)58 // successor(e) 是獲取節(jié)點(diǎn)e的后繼節(jié)點(diǎn)59 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))60 if (valEquals(value, e.value))61 return true;62 return false;63 }64 65 // 獲取“鍵(key)”對應(yīng)的“值(value)”66 public V get(Object key) {67 // 獲取“鍵”為key的節(jié)點(diǎn)(p)68 Entry<K,V> p = getEntry(key);69 // 若節(jié)點(diǎn)(p)為null，返回null；否則，返回節(jié)點(diǎn)對應(yīng)的值70 return (p==null ? null : p.value);71 }72 73 public Comparator<? super K> comparator() {74 return comparator;75 }76 77 // 獲取第一個(gè)節(jié)點(diǎn)對應(yīng)的key78 public K firstKey() {79 return key(getFirstEntry());80 }81 82 // 獲取最后一個(gè)節(jié)點(diǎn)對應(yīng)的key83 public K lastKey() {84 return key(getLastEntry());85 }86 87 // 將map中的全部節(jié)點(diǎn)添加到TreeMap中88 public void putAll(Map<? extends K, ? extends V> map) {89 // 獲取map的大小90 int mapSize = map.size();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 && c.equals(comparator))) {97 ++modCount;98 try {99 buildFromSorted(mapSize, map.entrySet().iterator(),100 null, null);101 } catch (java.io.IOException cannotHappen) {102 } catch (ClassNotFoundException cannotHappen) {103 }104 return;105 }106 }107 // 調(diào)用AbstractMap中的putAll();108 // AbstractMap中的putAll()又會(huì)調(diào)用到TreeMap的put()109 super.putAll(map);110 }111 112 // 獲取TreeMap中“鍵”為key的節(jié)點(diǎn)113 final Entry<K,V> getEntry(Object key) {114 // 若“比較器”為null，則通過getEntryUsingComparator()獲取“鍵”為key的節(jié)點(diǎn)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設(shè)為根節(jié)點(diǎn)121 Entry<K,V> p = root;122 while (p != null) {123 int cmp = k.compareTo(p.key);124 // 若“p的key” < key，則p=“p的左孩子”125 if (cmp < 0)126 p = p.left;127 // 若“p的key” > key，則p=“p的左孩子”128 else if (cmp > 0)129 p = p.right;130 // 若“p的key” = key，則返回節(jié)點(diǎn)p131 else132 return p;133 }134 return null;135 }136 137 // 獲取TreeMap中“鍵”為key的節(jié)點(diǎn)(對應(yīng)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設(shè)為根節(jié)點(diǎn)143 Entry<K,V> p = root;144 while (p != null) {145 int cmp = cpr.compare(k, p.key);146 // 若“p的key” < key，則p=“p的左孩子”147 if (cmp < 0)148 p = p.left;149 // 若“p的key” > key，則p=“p的左孩子”150 else if (cmp > 0)151 p = p.right;152 // 若“p的key” = key，則返回節(jié)點(diǎn)p153 else154 return p;155 }156 }157 return null;158 }159 160 // 獲取TreeMap中不小于key的最小的節(jié)點(diǎn)；161 // 若不存在(即TreeMap中所有節(jié)點(diǎn)的鍵都比key大)，就返回null162 final Entry<K,V> getCeilingEntry(K key) {163 Entry<K,V> p = root;164 while (p != null) {165 int cmp = compare(key, p.key);166 // 情況一：若“p的key” > key。167 // 若 p 存在左孩子，則設(shè) p=“p的左孩子”；168 // 否則，返回p169 if (cmp < 0) {170 if (p.left != null)171 p = p.left;172 else173 return p;174 // 情況二：若“p的key” < key。175 } else if (cmp > 0) {176 // 若 p 存在右孩子，則設(shè) p=“p的右孩子”177 if (p.right != null) {178 p = p.right;179 } else {180 // 若 p 不存在右孩子，則找出 p 的后繼節(jié)點(diǎn)，并返回181 // 注意：這里返回的 “p的后繼節(jié)點(diǎn)”有2種可能性：第一，null；第二，TreeMap中大于key的最小的節(jié)點(diǎn)。182 // 理解這一點(diǎn)的核心是，getCeilingEntry是從root開始遍歷的。183 // 若getCeilingEntry能走到這一步，那么，它之前“已經(jīng)遍歷過的節(jié)點(diǎn)的key”都 > key。184 // 能理解上面所說的，那么就很容易明白，為什么“p的后繼節(jié)點(diǎn)”又2種可能性了。185 Entry<K,V> parent = p.parent;186 Entry<K,V> ch = p;187 while (parent != null && ch == parent.right) {188 ch = parent;189 parent = parent.parent;190 }191 return parent;192 }193 // 情況三：若“p的key” = key。194 } else195 return p;196 }197 return null;198 }199 200 // 獲取TreeMap中不大于key的最大的節(jié)點(diǎn)；201 // 若不存在(即TreeMap中所有節(jié)點(diǎn)的鍵都比key小)，就返回null202 // 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, p.key);207 if (cmp > 0) {208 if (p.right != null)209 p = p.right;210 else211 return p;212 } else if (cmp < 0) {213 if (p.left != null) {214 p = p.left;215 } else {216 Entry<K,V> parent = p.parent;217 Entry<K,V> ch = p;218 while (parent != null && ch == parent.left) {219 ch = parent;220 parent = parent.parent;221 }222 return parent;223 }224 } else225 return p;226 227 }228 return null;229 }230 231 // 獲取TreeMap中大于key的最小的節(jié)點(diǎn)。232 // 若不存在，就返回null。233 // 請參照getCeilingEntry來對getHigherEntry進(jìn)行理解。234 final Entry<K,V> getHigherEntry(K key) {235 Entry<K,V> p = root;236 while (p != null) {237 int cmp = compare(key, p.key);238 if (cmp < 0) {239 if (p.left != null)240 p = p.left;241 else242 return p;243 } else {244 if (p.right != null) {245 p = p.right;246 } else {247 Entry<K,V> parent = p.parent;248 Entry<K,V> ch = p;249 while (parent != null && ch == parent.right) {250 ch = parent;251 parent = parent.parent;252 }253 return parent;254 }255 }256 }257 return null;258 }259 260 // 獲取TreeMap中小于key的最大的節(jié)點(diǎn)。261 // 若不存在，就返回null。262 // 請參照getCeilingEntry來對getLowerEntry進(jìn)行理解。263 final Entry<K,V> getLowerEntry(K key) {264 Entry<K,V> p = root;265 while (p != null) {266 int cmp = compare(key, p.key);267 if (cmp > 0) {268 if (p.right != null)269 p = p.right;270 else271 return p;272 } else {273 if (p.left != null) {274 p = p.left;275 } else {276 Entry<K,V> parent = p.parent;277 Entry<K,V> ch = p;278 while (parent != null && ch == parent.left) {279 ch = parent;280 parent = parent.parent;281 }282 return parent;283 }284 }285 }286 return null;287 }288 289 // 將“key, value”添加到TreeMap中290 // 理解TreeMap的前提是掌握“紅黑樹”。291 // 若理解“紅黑樹中添加節(jié)點(diǎn)”的算法，則很容易理解put。292 public V put(K key, V value) {293 Entry<K,V> t = root;294 // 若紅黑樹為空，則插入根節(jié)點(diǎn)295 if (t == null) {296 // TBD:297 // 5045147: (coll) Adding null to an empty TreeSet should298 // throw NullPointerException299 //300 // compare(key, key); // type check301 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 paths309 Comparator<? super K> cpr = comparator;310 // 在二叉樹(紅黑樹是特殊的二叉樹)中，找到(key, value)的插入位置。311 // 紅黑樹是以key來進(jìn)行排序的，所以這里以key來進(jìn)行查找。312 if (cpr != null) {313 do {314 parent = t;315 cmp = cpr.compare(key, t.key);316 if (cmp < 0)317 t = t.left;318 else if (cmp > 0)319 t = t.right;320 else321 return t.setValue(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 = k.compareTo(t.key);331 if (cmp < 0)332 t = t.left;333 else if (cmp > 0)334 t = t.right;335 else336 return t.setValue(value);337 } while (t != null);338 }339 // 新建紅黑樹的節(jié)點(diǎn)(e)340 Entry<K,V> e = new Entry<K,V>(key, value, parent);341 if (cmp < 0)342 parent.left = e;343 else344 parent.right = e;345 // 紅黑樹插入節(jié)點(diǎn)后，不再是一顆紅黑樹；346 // 這里通過fixAfterInsertion的處理，來恢復(fù)紅黑樹的特性。347 fixAfterInsertion(e);348 size++;349 modCount++;350 return null;351 }352 353 // 刪除TreeMap中的鍵為key的節(jié)點(diǎn)，并返回節(jié)點(diǎn)的值354 public V remove(Object key) {355 // 找到鍵為key的節(jié)點(diǎn)356 Entry<K,V> p = getEntry(key);357 if (p == null)358 return null;359 360 // 保存節(jié)點(diǎn)的值361 V oldValue = p.value;362 // 刪除節(jié)點(diǎn)363 deleteEntry(p);364 return oldValue;365 }366 367 // 清空紅黑樹368 public void clear() {369 modCount++;370 size = 0;371 root = null;372 }373 374 // 克隆一個(gè)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 clone.root = null;385 clone.size = 0;386 clone.modCount = 0;387 clone.entrySet = null;388 clone.navigableKeySet = null;389 clone.descendingMap = null;390 391 // Initialize clone with our mappings392 try {393 clone.buildFromSorted(size, entrySet().iterator(), null, null);394 } catch (java.io.IOException cannotHappen) {395 } catch (ClassNotFoundException cannotHappen) {396 }397 398 return clone;399 }400 401 // 獲取第一個(gè)節(jié)點(diǎn)(對外接口)。402 public Map.Entry<K,V> firstEntry() {403 return exportEntry(getFirstEntry());404 }405 406 // 獲取最后一個(gè)節(jié)點(diǎn)(對外接口)。407 public Map.Entry<K,V> lastEntry() {408 return exportEntry(getLastEntry());409 }410 411 // 獲取第一個(gè)節(jié)點(diǎn)，并將改節(jié)點(diǎn)從TreeMap中刪除。412 public Map.Entry<K,V> pollFirstEntry() {413 // 獲取第一個(gè)節(jié)點(diǎn)414 Entry<K,V> p = getFirstEntry();415 Map.Entry<K,V> result = exportEntry(p);416 // 刪除第一個(gè)節(jié)點(diǎn)417 if (p != null)418 deleteEntry(p);419 return result;420 }421 422 // 獲取最后一個(gè)節(jié)點(diǎn)，并將改節(jié)點(diǎn)從TreeMap中刪除。423 public Map.Entry<K,V> pollLastEntry() {424 // 獲取最后一個(gè)節(jié)點(diǎn)425 Entry<K,V> p = getLastEntry();426 Map.Entry<K,V> result = exportEntry(p);427 // 刪除最后一個(gè)節(jié)點(diǎn)428 if (p != null)429 deleteEntry(p);430 return result;431 }432 433 // 返回小于key的最大的鍵值對，沒有的話返回null434 public Map.Entry<K,V> lowerEntry(K key) {435 return exportEntry(getLowerEntry(key));436 }437 438 // 返回小于key的最大的鍵值對所對應(yīng)的KEY，沒有的話返回null439 public K lowerKey(K key) {440 return keyOrNull(getLowerEntry(key));441 }442 443 // 返回不大于key的最大的鍵值對，沒有的話返回null444 public Map.Entry<K,V> floorEntry(K key) {445 return exportEntry(getFloorEntry(key));446 }447 448 // 返回不大于key的最大的鍵值對所對應(yīng)的KEY，沒有的話返回null449 public K floorKey(K key) {450 return keyOrNull(getFloorEntry(key));451 }452 453 // 返回不小于key的最小的鍵值對，沒有的話返回null454 public Map.Entry<K,V> ceilingEntry(K key) {455 return exportEntry(getCeilingEntry(key));456 }457 458 // 返回不小于key的最小的鍵值對所對應(yīng)的KEY，沒有的話返回null459 public K ceilingKey(K key) {460 return keyOrNull(getCeilingEntry(key));461 }462 463 // 返回大于key的最小的鍵值對，沒有的話返回null464 public Map.Entry<K,V> higherEntry(K key) {465 return exportEntry(getHigherEntry(key));466 }467 468 // 返回大于key的最小的鍵值對所對應(yīng)的KEY，沒有的話返回null469 public K higherKey(K key) {470 return keyOrNull(getHigherEntry(key));471 }472 473 // TreeMap的紅黑樹節(jié)點(diǎn)對應(yīng)的集合474 private transient EntrySet entrySet = null;475 // KeySet為KeySet導(dǎo)航類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 // 獲取“可導(dǎo)航”的Key的集合486 // 實(shí)際上是返回KeySet類的對象。487 public NavigableSet<K> navigableKeySet() {488 KeySet<K> nks = navigableKeySet;489 return (nks != null) ? nks : (navigableKeySet = new KeySet(this));490 }491 492 // 返回“TreeMap的值對應(yīng)的集合”493 public Collection<V> values() {494 Collection<V> vs = values;495 return (vs != null) ? vs : (values = new Values());496 }497 498 // 獲取TreeMap的Entry的集合，實(shí)際上是返回EntrySet類的對象。499 public Set<Map.Entry<K,V>> entrySet() {500 EntrySet es = entrySet;501 return (es != null) ? es : (entrySet = new EntrySet());502 }503 504 // 獲取TreeMap的降序Map505 // 實(shí)際上是返回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的子Map515 // 范圍是從fromKey 到 toKey；fromInclusive是是否包含fromKey的標(biāo)記，toInclusive是是否包含toKey的標(biāo)記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 // 范圍從第一個(gè)節(jié)點(diǎn) 到 toKey, inclusive是是否包含toKey的標(biāo)記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 到 最后一個(gè)節(jié)點(diǎn)，inclusive是是否包含fromKey的標(biāo)記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 // 范圍從第一個(gè)節(jié)點(diǎn) 到 toKey(不包括)547 public SortedMap<K,V> headMap(K toKey) {548 return headMap(toKey, false);549 }550 551 // 獲取“Map的尾部”。552 // 范圍是從 fromKey(包括) 到 最后一個(gè)節(jié)點(diǎn)553 public SortedMap<K,V> tailMap(K fromKey) {554 return tailMap(fromKey, true);555 }556 557 // ”TreeMap的值的集合“對應(yīng)的類，它集成于AbstractCollection558 class Values extends AbstractCollection<V> {559 // 返回迭代器560 public Iterator<V> iterator() {561 return new ValueIterator(getFirstEntry());562 }563 564 // 返回個(gè)數(shù)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(e.getValue(), 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集合的單位是單個(gè)“鍵值對”。593 class EntrySet extends AbstractSet<Map.Entry<K,V>> {594 public Iterator<Map.Entry<K,V>> iterator() {595 return new EntryIterator(getFirstEntry());596 }597 598 // EntrySet中是否包含“鍵值對Object”599 public boolean contains(Object o) {600 if (!(o instanceof Map.Entry))601 return false;602 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;603 V value = entry.getValue();604 Entry<K,V> p = getEntry(entry.getKey());605 return p != null && valEquals(p.getValue(), value);606 }607 608 // 刪除EntrySet中的“鍵值對Object”609 public boolean remove(Object o) {610 if (!(o instanceof Map.Entry))611 return false;612 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;613 V value = entry.getValue();614 Entry<K,V> p = getEntry(entry.getKey());615 if (p != null && valEquals(p.getValue(), value)) {616 deleteEntry(p);617 return true;618 }619 return false;620 }621 622 // 返回EntrySet中元素個(gè)數(shù)623 public int size() {624 return TreeMap.this.size();625 }626 627 // 清空EntrySet628 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，而且實(shí)現(xiàn)了NavigableSet接口。645 static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {646 // NavigableMap成員，KeySet是通過NavigableMap實(shí)現(xiàn)的647 private final NavigableMap<E, Object> m;648 KeySet(NavigableMap<E,Object> map) { m = map; }649 650 // 升序迭代器651 public Iterator<E> iterator() {652 // 若是TreeMap對象，則調(diào)用TreeMap的迭代器keyIterator()653 // 否則，調(diào)用TreeMap子類NavigableSubMap的迭代器keyIterator()654 if (m instanceof TreeMap)655 return ((TreeMap<E,Object>)m).keyIterator();656 else657 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());658 }659 660 // 降序迭代器661 public Iterator<E> descendingIterator() {662 // 若是TreeMap對象，則調(diào)用TreeMap的迭代器descendingKeyIterator()663 // 否則，調(diào)用TreeMap子類NavigableSubMap的迭代器descendingKeyIterator()664 if (m instanceof TreeMap)665 return ((TreeMap<E,Object>)m).descendingKeyIterator();666 else667 return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());668 }669 670 public int size() { return m.size(); }671 public boolean isEmpty() { return m.isEmpty(); }672 public boolean contains(Object o) { return m.containsKey(o); }673 public void clear() { m.clear(); }674 public E lower(E e) { return m.lowerKey(e); }675 public E floor(E e) { return m.floorKey(e); }676 public E ceiling(E e) { return m.ceilingKey(e); }677 public E higher(E e) { return m.higherKey(e); }678 public E first() { return m.firstKey(); }679 public E last() { return m.lastKey(); }680 public Comparator<? super E> comparator() { return m.comparator(); }681 public E pollFirst() {682 Map.Entry<E,Object> e = m.pollFirstEntry();683 return e == null? null : e.getKey();684 }685 public E pollLast() {686 Map.Entry<E,Object> e = m.pollLastEntry();687 return e == null? null : e.getKey();688 }689 public boolean remove(Object o) {690 int oldSize = size();691 m.remove(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>(m.subMap(fromElement, fromInclusive,697 toElement, toInclusive));698 }699 public NavigableSet<E> headSet(E toElement, boolean inclusive) {700 return new TreeSet<E>(m.headMap(toElement, inclusive));701 }702 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {703 return new TreeSet<E>(m.tailMap(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(m.descendingMap());716 }717 }718 719 // 它是TreeMap中的一個(gè)抽象迭代器，實(shí)現(xiàn)了一些通用的接口。720 abstract class PrivateEntryIterator<T> implements Iterator<T> {721 // 下一個(gè)元素722 Entry<K,V> next;723 // 上一次返回元素724 Entry<K,V> lastReturned;725 // 期望的修改次數(shù)，用于實(shí)現(xiàn)fast-fail機(jī)制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 // 獲取下一個(gè)節(jié)點(diǎn)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 // 獲取上一個(gè)節(jié)點(diǎn)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 // 刪除當(dāng)前節(jié)點(diǎn)763 public void remove() {764 if (lastReturned == null)765 throw new IllegalStateException();766 if (modCount != expectedModCount)767 throw new ConcurrentModificationException();768 // 這里重點(diǎn)強(qiáng)調(diào)一下“為什么當(dāng)lastReturned的左右孩子都不為空時(shí)，要將其賦值給next”。769 // 目的是為了“刪除lastReturned節(jié)點(diǎn)之后，next節(jié)點(diǎn)指向的仍然是下一個(gè)節(jié)點(diǎn)”。770 // 根據(jù)“紅黑樹”的特性可知：771 // 當(dāng)被刪除節(jié)點(diǎn)有兩個(gè)兒子時(shí)。那么，首先把“它的后繼節(jié)點(diǎn)的內(nèi)容”復(fù)制給“該節(jié)點(diǎn)的內(nèi)容”；之后，刪除“它的后繼節(jié)點(diǎn)”。772 // 這意味著“當(dāng)被刪除節(jié)點(diǎn)有兩個(gè)兒子時(shí)，刪除當(dāng)前節(jié)點(diǎn)之后，'新的當(dāng)前節(jié)點(diǎn)'實(shí)際上是‘原有的后繼節(jié)點(diǎn)(即下一個(gè)節(jié)點(diǎn))’”。773 // 而此時(shí)next仍然指向"新的當(dāng)前節(jié)點(diǎn)"。也就是說next是仍然是指向下一個(gè)節(jié)點(diǎn)；能繼續(xù)遍歷紅黑樹。774 if (lastReturned.left != null && lastReturned.right != null)775 next = lastReturned;776 deleteEntry(lastReturned);777 expectedModCount = modCount;778 lastReturned = null;779 }780 }781 782 // TreeMap的Entry對應(yīng)的迭代器783 final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {784 EntryIterator(Entry<K,V> first) {785 super(first);786 }787 public Map.Entry<K,V> next() {788 return nextEntry();789 }790 }791 792 // TreeMap的Value對應(yīng)的迭代器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 // 比較兩個(gè)對象的大小823 final int compare(Object k1, Object k2) {824 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)825 : comparator.compare((K)k1, (K)k2);826 }827 828 // 判斷兩個(gè)對象是否相等829 final static boolean valEquals(Object o1, Object o2) {830 return (o1==null ? o2==null : o1.equals(o2));831 }832 833 // 返回“Key-Value鍵值對”的一個(gè)簡單拷貝(AbstractMap.SimpleImmutableEntry<K,V>對象)834 // 可用來讀取“鍵值對”的值835 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {836 return e == null? null :837 new AbstractMap.SimpleImmutableEntry<K,V>(e);838 }839 840 // 若“鍵值對”不為null，則返回KEY；否則，返回null841 static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {842 return e == null? null : e.key;843 }844 845 // 若“鍵值對”不為null，則返回KEY；否則，拋出異常846 static <K> K key(Entry<K,?> e) {847 if (e==null)848 throw new NoSuchElementException();849 return e.key;850 }851 852 // TreeMap的SubMap，它一個(gè)抽象類，實(shí)現(xiàn)了公共操作。853 // 它包括了"(升序)AscendingSubMap"和"(降序)DescendingSubMap"兩個(gè)子類。854 static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>855 implements NavigableMap<K,V>, java.io.Serializable {856 // TreeMap的拷貝857 final TreeMap<K,V> m;858 // lo是“子Map范圍的最小值”，hi是“子Map范圍的最大值”；859 // loInclusive是“是否包含lo的標(biāo)記”，hiInclusive是“是否包含hi的標(biāo)記”860 // fromStart是“表示是否從第一個(gè)節(jié)點(diǎn)開始計(jì)算”，861 // toEnd是“表示是否計(jì)算到最后一個(gè)節(jié)點(diǎn) ”862 final K lo, hi; 863 final boolean fromStart, toEnd;864 final boolean loInclusive, hiInclusive;865 866 // 構(gòu)造函數(shù)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 (m.compare(lo, hi) > 0)872 throw new IllegalArgumentException("fromKey > toKey");873 } else {874 if (!fromStart) // type check875 m.compare(lo, lo);876 if (!toEnd)877 m.compare(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不包括“起始節(jié)點(diǎn)”，892 // 并且，“key小于最小鍵(lo)”或者“key等于最小鍵(lo)，但最小鍵卻沒包括在該SubMap內(nèi)”893 // 則判斷key太小。其余情況都不是太小！894 if (!fromStart) {895 int c = m.compare(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不包括“結(jié)束節(jié)點(diǎn)”，905 // 并且，“key大于最大鍵(hi)”或者“key等于最大鍵(hi)，但最大鍵卻沒包括在該SubMap內(nèi)”906 // 則判斷key太大。其余情況都不是太大！907 if (!toEnd) {908 int c = m.compare(key, hi);909 if (c > 0 || (c == 0 && !hiInclusive))910 return true;911 }912 return false;913 }914 915 // 判斷key是否在“l(fā)o和hi”開區(qū)間范圍內(nèi)916 final boolean inRange(Object key) {917 return !tooLow(key) && !tooHigh(key);918 }919 920 // 判斷key是否在封閉區(qū)間內(nèi)921 final boolean inClosedRange(Object key) {922 return (fromStart || m.compare(key, lo) >= 0)923 && (toEnd || m.compare(hi, key) >= 0);924 }925 926 // 判斷key是否在區(qū)間內(nèi), inclusive是區(qū)間開關(guān)標(biāo)志927 final boolean inRange(Object key, boolean inclusive) {928 return inclusive ? inRange(key) : inClosedRange(key);929 }930 931 // 返回最低的Entry932 final TreeMap.Entry<K,V> absLowest() {933 // 若“包含起始節(jié)點(diǎn)”，則調(diào)用getFirstEntry()返回第一個(gè)節(jié)點(diǎn)934 // 否則的話，若包括lo，則調(diào)用getCeilingEntry(lo)獲取大于/等于lo的最小的Entry;935 // 否則，調(diào)用getHigherEntry(lo)獲取大于lo的最小Entry936 TreeMap.Entry<K,V> e =937 (fromStart ? m.getFirstEntry() :938 (loInclusive ? m.getCeilingEntry(lo) :939 m.getHigherEntry(lo)));940 return (e == null || tooHigh(e.key)) ? null : e;941 }942 943 // 返回最高的Entry944 final TreeMap.Entry<K,V> absHighest() {945 // 若“包含結(jié)束節(jié)點(diǎn)”，則調(diào)用getLastEntry()返回最后一個(gè)節(jié)點(diǎn)946 // 否則的話，若包括hi，則調(diào)用getFloorEntry(hi)獲取小于/等于hi的最大的Entry;947 // 否則，調(diào)用getLowerEntry(hi)獲取大于hi的最大Entry948 TreeMap.Entry<K,V> e =949 TreeMap.Entry<K,V> e =950 (toEnd ? m.getLastEntry() :951 (hiInclusive ? m.getFloorEntry(hi) :952 m.getLowerEntry(hi)));953 return (e == null || tooLow(e.key)) ? null : e;954 }955 956 // 返回"大于/等于key的最小的Entry"957 final TreeMap.Entry<K,V> absCeiling(K key) {958 // 只有在“key太小”的情況下，absLowest()返回的Entry才是“大于/等于key的最小Entry”959 // 其它情況下不行。例如，當(dāng)包含“起始節(jié)點(diǎn)”時(shí)，absLowest()返回的是最小Entry了！960 if (tooLow(key))961 return absLowest();962 // 獲取“大于/等于key的最小Entry”963 TreeMap.Entry<K,V> e = m.getCeilingEntry(key);964 return (e == null || tooHigh(e.key)) ? null : e;965 }966 967 // 返回"大于key的最小的Entry"968 final TreeMap.Entry<K,V> absHigher(K key) {969 // 只有在“key太小”的情況下，absLowest()返回的Entry才是“大于key的最小Entry”970 // 其它情況下不行。例如，當(dāng)包含“起始節(jié)點(diǎn)”時(shí)，absLowest()返回的是最小Entry了,而不一定是“大于key的最小Entry”！971 if (tooLow(key))972 return absLowest();973 // 獲取“大于key的最小Entry”974 TreeMap.Entry<K,V> e = m.getHigherEntry(key);975 return (e == null || tooHigh(e.key)) ? null : e;976 }977 978 // 返回"小于/等于key的最大的Entry"979 final TreeMap.Entry<K,V> absFloor(K key) {980 // 只有在“key太大”的情況下，(absHighest)返回的Entry才是“小于/等于key的最大Entry”981 // 其它情況下不行。例如，當(dāng)包含“結(jié)束節(jié)點(diǎn)”時(shí)，absHighest()返回的是最大Entry了！982 if (tooHigh(key))983 return absHighest();984 // 獲取"小于/等于key的最大的Entry"985 TreeMap.Entry<K,V> e = m.getFloorEntry(key);986 return (e == null || tooLow(e.key)) ? null : e;987 }988 989 // 返回"小于key的最大的Entry"990 final TreeMap.Entry<K,V> absLower(K key) {991 // 只有在“key太大”的情況下，(absHighest)返回的Entry才是“小于key的最大Entry”992 // 其它情況下不行。例如，當(dāng)包含“結(jié)束節(jié)點(diǎn)”時(shí)，absHighest()返回的是最大Entry了,而不一定是“小于key的最大Entry”！993 if (tooHigh(key))994 return absHighest();995 // 獲取"小于key的最大的Entry"996 TreeMap.Entry<K,V> e = m.getLowerEntry(key);997 return (e == null || tooLow(e.key)) ? null : e;998 }999 1000 // 返回“大于最大節(jié)點(diǎn)中的最小節(jié)點(diǎn)”，不存在的話，返回null 1001 final TreeMap.Entry<K,V> absHighFence() { 1002 return (toEnd ? null : (hiInclusive ? 1003 m.getHigherEntry(hi) : 1004 m.getCeilingEntry(hi))); 1005 } 1006 1007 // 返回“小于最小節(jié)點(diǎn)中的最大節(jié)點(diǎn)”，不存在的話，返回null 1008 final TreeMap.Entry<K,V> absLowFence() { 1009 return (fromStart ? null : (loInclusive ? 1010 m.getLowerEntry(lo) : 1011 m.getFloorEntry(lo))); 1012 } 1013 1014 // 下面幾個(gè)abstract方法是需要NavigableSubMap的實(shí)現(xiàn)類實(shí)現(xiàn)的方法 1015 abstract TreeMap.Entry<K,V> subLowest(); 1016 abstract TreeMap.Entry<K,V> subHighest(); 1017 abstract TreeMap.Entry<K,V> subCeiling(K key); 1018 abstract TreeMap.Entry<K,V> subHigher(K key); 1019 abstract TreeMap.Entry<K,V> subFloor(K key); 1020 abstract TreeMap.Entry<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) ? m.isEmpty() : entrySet().isEmpty(); 1029 } 1030 1031 // 返回SubMap的大小 1032 public int size() { 1033 return (fromStart && toEnd) ? m.size() : entrySet().size(); 1034 } 1035 1036 // 返回SubMap是否包含鍵key 1037 public final boolean containsKey(Object key) { 1038 return inRange(key) && m.containsKey(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 m.put(key, value); 1046 } 1047 1048 // 獲取key對應(yīng)值 1049 public final V get(Object key) { 1050 return !inRange(key)? null : m.get(key); 1051 } 1052 1053 // 刪除key對應(yīng)的鍵值對 1054 public final V remove(Object key) { 1055 return !inRange(key)? null : m.remove(key); 1056 } 1057 1058 // 獲取“大于/等于key的最小鍵值對” 1059 public final Map.Entry<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 Map.Entry<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 Map.Entry<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 Map.Entry<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的第一個(gè)鍵" 1099 public final K firstKey() { 1100 return key(subLowest()); 1101 } 1102 1103 // 獲取"SubMap的最后一個(gè)鍵" 1104 public final K lastKey() { 1105 return key(subHighest()); 1106 } 1107 1108 // 獲取"SubMap的第一個(gè)鍵值對" 1109 public final Map.Entry<K,V> firstEntry() { 1110 return exportEntry(subLowest()); 1111 } 1112 1113 // 獲取"SubMap的最后一個(gè)鍵值對" 1114 public final Map.Entry<K,V> lastEntry() { 1115 return exportEntry(subHighest()); 1116 } 1117 1118 // 返回"SubMap的第一個(gè)鍵值對"，并從SubMap中刪除改鍵值對 1119 public final Map.Entry<K,V> pollFirstEntry() { 1120 TreeMap.Entry<K,V> e = subLowest(); 1121 Map.Entry<K,V> result = exportEntry(e); 1122 if (e != null) 1123 m.deleteEntry(e); 1124 return result; 1125 } 1126 1127 // 返回"SubMap的最后一個(gè)鍵值對"，并從SubMap中刪除改鍵值對 1128 public final Map.Entry<K,V> pollLastEntry() { 1129 TreeMap.Entry<K,V> e = subHighest(); 1130 Map.Entry<K,V> result = exportEntry(e); 1131 if (e != null) 1132 m.deleteEntry(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對象，實(shí)際上返回的是當(dāng)前對象的"Key集合"。 1142 public final NavigableSet<K> navigableKeySet() { 1143 KeySet<K> nksv = navigableKeySetView; 1144 return (nksv != null) ? nksv : 1145 (navigableKeySetView = new TreeMap.KeySet(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 // 返回當(dāng)前Map的頭部(從第一個(gè)節(jié)點(diǎn) 到 toKey, 不包括toKey) 1164 public final SortedMap<K,V> headMap(K toKey) { 1165 return headMap(toKey, false); 1166 } 1167 1168 // 返回當(dāng)前Map的尾部[從 fromKey(包括fromKeyKey) 到 最后一個(gè)節(jié)點(diǎn)] 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<Map.Entry<K,V>> { 1175 private transient int size = -1, sizeModCount; 1176 1177 // 獲取EntrySet的大小 1178 public int size() { 1179 // 若SubMap是從“開始節(jié)點(diǎn)”到“結(jié)尾節(jié)點(diǎn)”，則SubMap大小就是原TreeMap的大小 1180 if (fromStart && toEnd) 1181 return m.size(); 1182 // 若SubMap不是從“開始節(jié)點(diǎn)”到“結(jié)尾節(jié)點(diǎn)”，則調(diào)用iterator()遍歷EntrySetView中的元素 1183 if (size == -1 || sizeModCount != m.modCount) { 1184 sizeModCount = m.modCount; 1185 size = 0; 1186 Iterator i = iterator(); 1187 while (i.hasNext()) { 1188 size++; 1189 i.next(); 1190 } 1191 } 1192 return size; 1193 } 1194 1195 // 判斷EntrySetView是否為空 1196 public boolean isEmpty() { 1197 TreeMap.Entry<K,V> n = absLowest(); 1198 return n == null || tooHigh(n.key); 1199 } 1200 1201 // 判斷EntrySetView是否包含Object 1202 public boolean contains(Object o) { 1203 if (!(o instanceof Map.Entry)) 1204 return false; 1205 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 1206 K key = entry.getKey(); 1207 if (!inRange(key)) 1208 return false; 1209 TreeMap.Entry node = m.getEntry(key); 1210 return node != null && 1211 valEquals(node.getValue(), entry.getValue()); 1212 } 1213 1214 // 從EntrySetView中刪除Object 1215 public boolean remove(Object o) { 1216 if (!(o instanceof Map.Entry)) 1217 return false; 1218 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 1219 K key = entry.getKey(); 1220 if (!inRange(key)) 1221 return false; 1222 TreeMap.Entry<K,V> node = m.getEntry(key); 1223 if (node!=null && valEquals(node.getValue(),entry.getValue())){ 1224 m.deleteEntry(node); 1225 return true; 1226 } 1227 return false; 1228 } 1229 } 1230 1231 // SubMap的迭代器 1232 abstract class SubMapIterator<T> implements Iterator<T> { 1233 // 上一次被返回的Entry 1234 TreeMap.Entry<K,V> lastReturned; 1235 // 指向下一個(gè)Entry 1236 TreeMap.Entry<K,V> next; 1237 // “柵欄key”。根據(jù)SubMap是“升序”還是“降序”具有不同的意義 1238 final K fenceKey; 1239 int expectedModCount; 1240 1241 // 構(gòu)造函數(shù) 1242 SubMapIterator(TreeMap.Entry<K,V> first, 1243 TreeMap.Entry<K,V> fence) { 1244 // 每創(chuàng)建一個(gè)SubMapIterator時(shí)，保存修改次數(shù) 1245 // 若后面發(fā)現(xiàn)expectedModCount和modCount不相等，則拋出ConcurrentModificationException異常。 1246 // 這就是所說的fast-fail機(jī)制的原理！ 1247 expectedModCount = m.modCount; 1248 lastReturned = null; 1249 next = first; 1250 fenceKey = fence == null ? null : fence.key; 1251 } 1252 1253 // 是否存在下一個(gè)Entry 1254 public final boolean hasNext() { 1255 return next != null && next.key != fenceKey; 1256 } 1257 1258 // 返回下一個(gè)Entry 1259 final TreeMap.Entry<K,V> nextEntry() { 1260 TreeMap.Entry<K,V> e = next; 1261 if (e == null || e.key == fenceKey) 1262 throw new NoSuchElementException(); 1263 if (m.modCount != expectedModCount) 1264 throw new ConcurrentModificationException(); 1265 // next指向e的后繼節(jié)點(diǎn) 1266 next = successor(e); 1267 lastReturned = e; 1268 return e; 1269 } 1270 1271 // 返回上一個(gè)Entry 1272 final TreeMap.Entry<K,V> prevEntry() { 1273 TreeMap.Entry<K,V> e = next; 1274 if (e == null || e.key == fenceKey) 1275 throw new NoSuchElementException(); 1276 if (m.modCount != expectedModCount) 1277 throw new ConcurrentModificationException(); 1278 // next指向e的前繼節(jié)點(diǎn) 1279 next = predecessor(e); 1280 lastReturned = e; 1281 return e; 1282 } 1283 1284 // 刪除當(dāng)前節(jié)點(diǎn)(用于“升序的SubMap”)。 1285 // 刪除之后，可以繼續(xù)升序遍歷；紅黑樹特性沒變。 1286 final void removeAscending() { 1287 if (lastReturned == null) 1288 throw new IllegalStateException(); 1289 if (m.modCount != expectedModCount) 1290 throw new ConcurrentModificationException(); 1291 // 這里重點(diǎn)強(qiáng)調(diào)一下“為什么當(dāng)lastReturned的左右孩子都不為空時(shí)，要將其賦值給next”。 1292 // 目的是為了“刪除lastReturned節(jié)點(diǎn)之后，next節(jié)點(diǎn)指向的仍然是下一個(gè)節(jié)點(diǎn)”。 1293 // 根據(jù)“紅黑樹”的特性可知： 1294 // 當(dāng)被刪除節(jié)點(diǎn)有兩個(gè)兒子時(shí)。那么，首先把“它的后繼節(jié)點(diǎn)的內(nèi)容”復(fù)制給“該節(jié)點(diǎn)的內(nèi)容”；之后，刪除“它的后繼節(jié)點(diǎn)”。 1295 // 這意味著“當(dāng)被刪除節(jié)點(diǎn)有兩個(gè)兒子時(shí)，刪除當(dāng)前節(jié)點(diǎn)之后，'新的當(dāng)前節(jié)點(diǎn)'實(shí)際上是‘原有的后繼節(jié)點(diǎn)(即下一個(gè)節(jié)點(diǎn))’”。 1296 // 而此時(shí)next仍然指向"新的當(dāng)前節(jié)點(diǎn)"。也就是說next是仍然是指向下一個(gè)節(jié)點(diǎn)；能繼續(xù)遍歷紅黑樹。 1297 if (lastReturned.left != null && lastReturned.right != null) 1298 next = lastReturned; 1299 m.deleteEntry(lastReturned); 1300 lastReturned = null; 1301 expectedModCount = m.modCount; 1302 } 1303 1304 // 刪除當(dāng)前節(jié)點(diǎn)(用于“降序的SubMap”)。 1305 // 刪除之后，可以繼續(xù)降序遍歷；紅黑樹特性沒變。 1306 final void removeDescending() { 1307 if (lastReturned == null) 1308 throw new IllegalStateException(); 1309 if (m.modCount != expectedModCount) 1310 throw new ConcurrentModificationException(); 1311 m.deleteEntry(lastReturned); 1312 lastReturned = null; 1313 expectedModCount = m.modCount; 1314 } 1315 1316 } 1317 1318 // SubMap的Entry迭代器，它只支持升序操作，繼承于SubMapIterator 1319 final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { 1320 SubMapEntryIterator(TreeMap.Entry<K,V> first, 1321 TreeMap.Entry<K,V> fence) { 1322 super(first, fence); 1323 } 1324 // 獲取下一個(gè)節(jié)點(diǎn)(升序) 1325 public Map.Entry<K,V> next() { 1326 return nextEntry(); 1327 } 1328 // 刪除當(dāng)前節(jié)點(diǎn)(升序) 1329 public void remove() { 1330 removeAscending(); 1331 } 1332 } 1333 1334 // SubMap的Key迭代器，它只支持升序操作，繼承于SubMapIterator 1335 final class SubMapKeyIterator extends SubMapIterator<K> { 1336 SubMapKeyIterator(TreeMap.Entry<K,V> first, 1337 TreeMap.Entry<K,V> fence) { 1338 super(first, fence); 1339 } 1340 // 獲取下一個(gè)節(jié)點(diǎn)(升序) 1341 public K next() { 1342 return nextEntry().key; 1343 } 1344 // 刪除當(dāng)前節(jié)點(diǎn)(升序) 1345 public void remove() { 1346 removeAscending(); 1347 } 1348 } 1349 1350 // 降序SubMap的Entry迭代器，它只支持降序操作，繼承于SubMapIterator 1351 final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> { 1352 DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last, 1353 TreeMap.Entry<K,V> fence) { 1354 super(last, fence); 1355 } 1356 1357 // 獲取下一個(gè)節(jié)點(diǎn)(降序) 1358 public Map.Entry<K,V> next() { 1359 return prevEntry(); 1360 } 1361 // 刪除當(dāng)前節(jié)點(diǎn)(降序) 1362 public void remove() { 1363 removeDescending(); 1364 } 1365 } 1366 1367 // 降序SubMap的Key迭代器，它只支持降序操作，繼承于SubMapIterator 1368 final class DescendingSubMapKeyIterator extends SubMapIterator<K> { 1369 DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last, 1370 TreeMap.Entry<K,V> fence) { 1371 super(last, fence); 1372 } 1373 // 獲取下一個(gè)節(jié)點(diǎn)(降序) 1374 public K next() { 1375 return prevEntry().key; 1376 } 1377 // 刪除當(dāng)前節(jié)點(diǎn)(降序) 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 // 構(gòu)造函數(shù) 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 m.comparator(); 1399 } 1400 1401 // 獲取“子Map”。 1402 // 范圍是從fromKey 到 toKey；fromInclusive是是否包含fromKey的標(biāo)記，toInclusive是是否包含toKey的標(biāo)記 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 // 范圍從第一個(gè)節(jié)點(diǎn) 到 toKey, inclusive是是否包含toKey的標(biāo)記 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 到 最后一個(gè)節(jié)點(diǎn)，inclusive是是否包含fromKey的標(biāo)記 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 // 獲取對應(yīng)的降序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 // 實(shí)現(xiàn)了iterator() 1456 final class AscendingEntrySetView extends EntrySetView { 1457 public Iterator<Map.Entry<K,V>> iterator() { 1458 return new SubMapEntryIterator(absLowest(), absHighFence()); 1459 } 1460 } 1461 1462 // 返回“升序EntrySet集合” 1463 public Set<Map.Entry<K,V>> entrySet() { 1464 EntrySetView es = entrySetView; 1465 return (es != null) ? es : new AscendingEntrySetView(); 1466 } 1467 1468 TreeMap.Entry<K,V> subLowest() { return absLowest(); } 1469 TreeMap.Entry<K,V> subHighest() { return absHighest(); } 1470 TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); } 1471 TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); } 1472 TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); } 1473 TreeMap.Entry<K,V> subLower(K key) { return absLower(key); } 1474 } 1475 1476 // 降序的SubMap，繼承于NavigableSubMap 1477 // 相比于升序SubMap，它的實(shí)現(xiàn)機(jī)制是將“SubMap的比較器反轉(zhuǎn)”！ 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 // 反轉(zhuǎn)的比較器：是將原始比較器反轉(zhuǎn)得到的。 1487 private final Comparator<? super K> reverseComparator = 1488 Collections.reverseOrder(m.comparator); 1489 1490 // 獲取反轉(zhuǎn)比較器 1491 public Comparator<? super K> comparator() { 1492 return reverseComparator; 1493 } 1494 1495 // 獲取“子Map”。 1496 // 范圍是從fromKey 到 toKey；fromInclusive是是否包含fromKey的標(biāo)記，toInclusive是是否包含toKey的標(biāo)記 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 // 范圍從第一個(gè)節(jié)點(diǎn) 到 toKey, inclusive是是否包含toKey的標(biāo)記 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 到 最后一個(gè)節(jié)點(diǎn)，inclusive是是否包含fromKey的標(biāo)記 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 // 獲取對應(yīng)的降序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 // 實(shí)現(xiàn)了iterator() 1550 final class DescendingEntrySetView extends EntrySetView { 1551 public Iterator<Map.Entry<K,V>> iterator() { 1552 return new DescendingSubMapEntryIterator(absHighest(), absLowFence()); 1553 } 1554 } 1555 1556 // 返回“降序EntrySet集合” 1557 public Set<Map.Entry<K,V>> entrySet() { 1558 EntrySetView es = entrySetView; 1559 return (es != null) ? es : new DescendingEntrySetView(); 1560 } 1561 1562 TreeMap.Entry<K,V> subLowest() { return absHighest(); } 1563 TreeMap.Entry<K,V> subHighest() { return absLowest(); } 1564 TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); } 1565 TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); } 1566 TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); } 1567 TreeMap.Entry<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>, java.io.Serializable { 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<Map.Entry<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 // 紅黑樹的節(jié)點(diǎn)顏色--紅色 1592 private static final boolean RED = false; 1593 // 紅黑樹的節(jié)點(diǎn)顏色--黑色 1594 private static final boolean BLACK = true; 1595 1596 // “紅黑樹的節(jié)點(diǎn)”對應(yīng)的類。 1597 // 包含了 key(鍵)、value(值)、left(左孩子)、right(右孩子)、parent(父節(jié)點(diǎn))、color(顏色) 1598 static final class Entry<K,V> implements Map.Entry<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 // 父節(jié)點(diǎn) 1608 Entry<K,V> parent; 1609 // 當(dāng)前節(jié)點(diǎn)顏色 1610 boolean color = BLACK; 1611 1612 // 構(gòu)造函數(shù) 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 // 判斷兩個(gè)節(jié)點(diǎn)是否相等的函數(shù)，覆蓋equals()函數(shù)。 1637 // 若兩個(gè)節(jié)點(diǎn)的“key相等”并且“value相等”，則兩個(gè)節(jié)點(diǎn)相等 1638 public boolean equals(Object o) { 1639 if (!(o instanceof Map.Entry)) 1640 return false; 1641 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 1642 1643 return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); 1644 } 1645 1646 // 覆蓋hashCode函數(shù)。 1647 public int hashCode() { 1648 int keyHash = (key==null ? 0 : key.hashCode()); 1649 int valueHash = (value==null ? 0 : value.hashCode()); 1650 return keyHash ^ valueHash; 1651 } 1652 1653 // 覆蓋toString()函數(shù)。 1654 public String toString() { 1655 return key + "=" + value; 1656 } 1657 } 1658 1659 // 返回“紅黑樹的第一個(gè)節(jié)點(diǎn)” 1660 final Entry<K,V> getFirstEntry() { 1661 Entry<K,V> p = root; 1662 if (p != null) 1663 while (p.left != null) 1664 p = p.left; 1665 return p; 1666 } 1667 1668 // 返回“紅黑樹的最后一個(gè)節(jié)點(diǎn)” 1669 final Entry<K,V> getLastEntry() { 1670 Entry<K,V> p = root; 1671 if (p != null) 1672 while (p.right != null) 1673 p = p.right; 1674 return p; 1675 } 1676 1677 // 返回“節(jié)點(diǎn)t的后繼節(jié)點(diǎn)” 1678 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { 1679 if (t == null) 1680 return null; 1681 else if (t.right != null) { 1682 Entry<K,V> p = t.right; 1683 while (p.left != null) 1684 p = p.left; 1685 return p; 1686 } else { 1687 Entry<K,V> p = t.parent; 1688 Entry<K,V> ch = t; 1689 while (p != null && ch == p.right) { 1690 ch = p; 1691 p = p.parent; 1692 } 1693 return p; 1694 } 1695 } 1696 1697 // 返回“節(jié)點(diǎn)t的前繼節(jié)點(diǎn)” 1698 static <K,V> Entry<K,V> predecessor(Entry<K,V> t) { 1699 if (t == null) 1700 return null; 1701 else if (t.left != null) { 1702 Entry<K,V> p = t.left; 1703 while (p.right != null) 1704 p = p.right; 1705 return p; 1706 } else { 1707 Entry<K,V> p = t.parent; 1708 Entry<K,V> ch = t; 1709 while (p != null && ch == p.left) { 1710 ch = p; 1711 p = p.parent; 1712 } 1713 return p; 1714 } 1715 } 1716 1717 // 返回“節(jié)點(diǎn)p的顏色” 1718 // 根據(jù)“紅黑樹的特性”可知：空節(jié)點(diǎn)顏色是黑色。 1719 private static <K,V> boolean colorOf(Entry<K,V> p) { 1720 return (p == null ? BLACK : p.color); 1721 } 1722 1723 // 返回“節(jié)點(diǎn)p的父節(jié)點(diǎn)” 1724 private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) { 1725 return (p == null ? null: p.parent); 1726 } 1727 1728 // 設(shè)置“節(jié)點(diǎn)p的顏色為c” 1729 private static <K,V> void setColor(Entry<K,V> p, boolean c) { 1730 if (p != null) 1731 p.color = c; 1732 } 1733 1734 // 設(shè)置“節(jié)點(diǎn)p的左孩子” 1735 private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) { 1736 return (p == null) ? null: p.left; 1737 } 1738 1739 // 設(shè)置“節(jié)點(diǎn)p的右孩子” 1740 private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) { 1741 return (p == null) ? null: p.right; 1742 } 1743 1744 // 對節(jié)點(diǎn)p執(zhí)行“左旋”操作 1745 private void rotateLeft(Entry<K,V> p) { 1746 if (p != null) { 1747 Entry<K,V> r = p.right; 1748 p.right = r.left; 1749 if (r.left != null) 1750 r.left.parent = p; 1751 r.parent = p.parent; 1752 if (p.parent == null) 1753 root = r; 1754 else if (p.parent.left == p) 1755 p.parent.left = r; 1756 else 1757 p.parent.right = r; 1758 r.left = p; 1759 p.parent = r; 1760 } 1761 } 1762 1763 // 對節(jié)點(diǎn)p執(zhí)行“右旋”操作 1764 private void rotateRight(Entry<K,V> p) { 1765 if (p != null) { 1766 Entry<K,V> l = p.left; 1767 p.left = l.right; 1768 if (l.right != null) l.right.parent = p; 1769 l.parent = p.parent; 1770 if (p.parent == null) 1771 root = l; 1772 else if (p.parent.right == p) 1773 p.parent.right = l; 1774 else p.parent.left = l; 1775 l.right = p; 1776 p.parent = l; 1777 } 1778 } 1779 1780 // 插入之后的修正操作。 1781 // 目的是保證：紅黑樹插入節(jié)點(diǎn)之后，仍然是一顆紅黑樹 1782 private void fixAfterInsertion(Entry<K,V> x) { 1783 x.color = RED; 1784 1785 while (x != null && x != root && x.parent.color == 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 root.color = BLACK; 1821 } 1822 1823 // 刪除“紅黑樹的節(jié)點(diǎn)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 (p.left != null && p.right != null) { 1831 Entry<K,V> s = successor (p); 1832 p.key = s.key; 1833 p.value = s.value; 1834 p = s; 1835 } // p has 2 children 1836 1837 // Start fixup at replacement node, if it exists. 1838 Entry<K,V> replacement = (p.left != null ? p.left : p.right); 1839 1840 if (replacement != null) { 1841 // Link replacement to parent 1842 replacement.parent = p.parent; 1843 if (p.parent == null) 1844 root = replacement; 1845 else if (p == p.parent.left) 1846 p.parent.left = replacement; 1847 else 1848 p.parent.right = replacement; 1849 1850 // Null out links so they are OK to use by fixAfterDeletion. 1851 p.left = p.right = p.parent = null; 1852 1853 // Fix replacement 1854 if (p.color == BLACK) 1855 fixAfterDeletion(replacement); 1856 } else if (p.parent == null) { // return if we are the only node. 1857 root = null; 1858 } else { // No children. Use self as phantom replacement and unlink. 1859 if (p.color == BLACK) 1860 fixAfterDeletion(p); 1861 1862 if (p.parent != null) { 1863 if (p == p.parent.left) 1864 p.parent.left = null; 1865 else if (p == p.parent.right) 1866 p.parent.right = null; 1867 p.parent = null; 1868 } 1869 } 1870 } 1871 1872 // 刪除之后的修正操作。 1873 // 目的是保證：紅黑樹刪除節(jié)點(diǎn)之后，仍然是一顆紅黑樹 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 // java.io.Serializable的寫入函數(shù) 1939 // 將TreeMap的“容量，所有的Entry”都寫入到輸出流中 1940 private void writeObject(java.io.ObjectOutputStream s) 1941 throws java.io.IOException { 1942 // Write out the Comparator and any hidden stuff 1943 s.defaultWriteObject(); 1944 1945 // Write out size (number of Mappings) 1946 s.writeInt(size); 1947 1948 // Write out keys and values (alternating) 1949 for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) { 1950 Map.Entry<K,V> e = i.next(); 1951 s.writeObject(e.getKey()); 1952 s.writeObject(e.getValue()); 1953 } 1954 } 1955 1956 1957 // java.io.Serializable的讀取函數(shù)：根據(jù)寫入方式讀出 1958 // 先將TreeMap的“容量、所有的Entry”依次讀出 1959 private void readObject(final java.io.ObjectInputStream s) 1960 throws java.io.IOException, ClassNotFoundException { 1961 // Read in the Comparator and any hidden stuff 1962 s.defaultReadObject(); 1963 1964 // Read in size 1965 int size = s.readInt(); 1966 1967 buildFromSorted(size, null, s, null); 1968 } 1969 1970 // 根據(jù)已經(jīng)一個(gè)排好序的map創(chuàng)建一個(gè)TreeMap 1971 private void buildFromSorted(int size, Iterator it, 1972 java.io.ObjectInputStream str, 1973 V defaultVal) 1974 throws java.io.IOException, ClassNotFoundException { 1975 this.size = size; 1976 root = buildFromSorted(0, 0, size-1, computeRedLevel(size), 1977 it, str, defaultVal); 1978 } 1979 1980 // 根據(jù)已經(jīng)一個(gè)排好序的map創(chuàng)建一個(gè)TreeMap 1981 // 將map中的元素逐個(gè)添加到TreeMap中，并返回map的中間元素作為根節(jié)點(diǎn)。 1982 private final Entry<K,V> buildFromSorted(int level, int lo, int hi, 1983 int redLevel, 1984 Iterator it, 1985 java.io.ObjectInputStream str, 1986 V defaultVal) 1987 throws java.io.IOException, 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，則遞歸調(diào)用獲取(middel的)左孩子。 1997 if (lo < mid) 1998 left = buildFromSorted(level+1, lo, mid - 1, redLevel, 1999 it, str, defaultVal); 2000 2001 // 獲取middle節(jié)點(diǎn)對應(yīng)的key和value 2002 K key; 2003 V value; 2004 if (it != null) { 2005 if (defaultVal==null) { 2006 Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next(); 2007 key = entry.getKey(); 2008 value = entry.getValue(); 2009 } else { 2010 key = (K)it.next(); 2011 value = defaultVal; 2012 } 2013 } else { // use stream 2014 key = (K) str.readObject(); 2015 value = (defaultVal != null ? defaultVal : (V) str.readObject()); 2016 } 2017 2018 // 創(chuàng)建middle節(jié)點(diǎn) 2019 Entry<K,V> middle = new Entry<K,V>(key, value, null); 2020 2021 // 若當(dāng)前節(jié)點(diǎn)的深度=紅色節(jié)點(diǎn)的深度，則將節(jié)點(diǎn)著色為紅色。 2022 if (level == redLevel) 2023 middle.color = RED; 2024 2025 // 設(shè)置middle為left的父親，left為middle的左孩子 2026 if (left != null) { 2027 middle.left = left; 2028 left.parent = middle; 2029 } 2030 2031 if (mid < hi) { 2032 // 遞歸調(diào)用獲取(middel的)右孩子。 2033 Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel, 2034 it, str, defaultVal); 2035 // 設(shè)置middle為left的父親，left為middle的左孩子 2036 middle.right = right; 2037 right.parent = middle; 2038 } 2039 2040 return middle; 2041 } 2042 2043 // 計(jì)算節(jié)點(diǎn)樹為sz的最大深度，也是紅色節(jié)點(diǎn)的深度值。 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 }說明:
在詳細(xì)介紹TreeMap的代碼之前，我們先建立一個(gè)整體概念。
TreeMap是通過紅黑樹實(shí)現(xiàn)的，TreeMap存儲(chǔ)的是key-value鍵值對，TreeMap的排序是基于對key的排序。
TreeMap提供了操作“key”、“key-value”、“value”等方法，也提供了對TreeMap這顆樹進(jìn)行整體操作的方法，如獲取子樹、反向樹。
后面的解說內(nèi)容分為幾部分,
首先，介紹TreeMap的核心，即紅黑樹相關(guān)部分；
然后，介紹TreeMap的主要函數(shù)；
再次，介紹TreeMap實(shí)現(xiàn)的幾個(gè)接口；
最后，補(bǔ)充介紹TreeMap的其它內(nèi)容。
TreeMap本質(zhì)上是一顆紅黑樹。要徹底理解TreeMap，建議讀者先理解紅黑樹。關(guān)于紅黑樹的原理，可以參考：紅黑樹(一) 原理和算法詳細(xì)介紹
?
第3.1部分 TreeMap的紅黑樹相關(guān)內(nèi)容
TreeMap中于紅黑樹相關(guān)的主要函數(shù)有:
1 數(shù)據(jù)結(jié)構(gòu)
1.1 紅黑樹的節(jié)點(diǎn)顏色--紅色
1.2 紅黑樹的節(jié)點(diǎn)顏色--黑色
private static final boolean BLACK = true;1.3 “紅黑樹的節(jié)點(diǎn)”對應(yīng)的類。
static final class Entry<K,V> implements Map.Entry<K,V> { ... }Entry包含了6個(gè)部分內(nèi)容：key(鍵)、value(值)、left(左孩子)、right(右孩子)、parent(父節(jié)點(diǎn))、color(顏色)
Entry節(jié)點(diǎn)根據(jù)key進(jìn)行排序，Entry節(jié)點(diǎn)包含的內(nèi)容為value。
?
2 相關(guān)操作
2.1 左旋
private void rotateLeft(Entry<K,V> p) { ... }2.2 右旋
private void rotateRight(Entry<K,V> p) { ... }2.3 插入操作
public V put(K key, V value) { ... }2.4 插入修正操作
紅黑樹執(zhí)行插入操作之后，要執(zhí)行“插入修正操作”。
目的是：保紅黑樹在進(jìn)行插入節(jié)點(diǎn)之后，仍然是一顆紅黑樹
2.5 刪除操作
private void deleteEntry(Entry<K,V> p) { ... }2.6 刪除修正操作
紅黑樹執(zhí)行刪除之后，要執(zhí)行“刪除修正操作”。
目的是保證：紅黑樹刪除節(jié)點(diǎn)之后，仍然是一顆紅黑樹
關(guān)于紅黑樹部分，這里主要是指出了TreeMap中那些是紅黑樹的主要相關(guān)內(nèi)容。具體的紅黑樹相關(guān)操作API，這里沒有詳細(xì)說明，因?yàn)樗鼈儍H僅只是將算法翻譯成代碼。讀者可以參考“紅黑樹(一) 原理和算法詳細(xì)介紹”進(jìn)行了解。
第3.2部分 TreeMap的構(gòu)造函數(shù)
1 默認(rèn)構(gòu)造函數(shù)
使用默認(rèn)構(gòu)造函數(shù)構(gòu)造TreeMap時(shí)，使用java的默認(rèn)的比較器比較Key的大小，從而對TreeMap進(jìn)行排序。
public TreeMap() {comparator = null; }2 帶比較器的構(gòu)造函數(shù)
public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator; }3 帶Map的構(gòu)造函數(shù)，Map會(huì)成為TreeMap的子集
public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m); }該構(gòu)造函數(shù)會(huì)調(diào)用putAll()將m中的所有元素添加到TreeMap中。putAll()源碼如下：
public void putAll(Map<? extends K, ? extends V> m) {for (Map.Entry<? extends K, ? extends V> e : m.entrySet())put(e.getKey(), e.getValue()); }從中，我們可以看出putAll()就是將m中的key-value逐個(gè)的添加到TreeMap中。
4 帶SortedMap的構(gòu)造函數(shù)，SortedMap會(huì)成為TreeMap的子集
public TreeMap(SortedMap<K, ? extends V> m) {comparator = m.comparator();try {buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException cannotHappen) {} catch (ClassNotFoundException cannotHappen) {} }該構(gòu)造函數(shù)不同于上一個(gè)構(gòu)造函數(shù)，在上一個(gè)構(gòu)造函數(shù)中傳入的參數(shù)是Map，Map不是有序的，所以要逐個(gè)添加。
而該構(gòu)造函數(shù)的參數(shù)是SortedMap是一個(gè)有序的Map，我們通過buildFromSorted()來創(chuàng)建對應(yīng)的Map。
buildFromSorted涉及到的代碼如下：
要理解buildFromSorted，重點(diǎn)說明以下幾點(diǎn)：
第一，buildFromSorted是通過遞歸將SortedMap中的元素逐個(gè)關(guān)聯(lián)。
第二，buildFromSorted返回middle節(jié)點(diǎn)(中間節(jié)點(diǎn))作為root。
第三，buildFromSorted添加到紅黑樹中時(shí)，只將level == redLevel的節(jié)點(diǎn)設(shè)為紅色。第level級(jí)節(jié)點(diǎn)，實(shí)際上是buildFromSorted轉(zhuǎn)換成紅黑樹后的最底端(假設(shè)根節(jié)點(diǎn)在最上方)的節(jié)點(diǎn)；只將紅黑樹最底端的階段著色為紅色，其余都是黑色。
?
第3.3部分 TreeMap的Entry相關(guān)函數(shù)
TreeMap的?firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry()?原理都是類似的；下面以firstEntry()來進(jìn)行詳細(xì)說明
我們先看看firstEntry()和getFirstEntry()的代碼：
public Map.Entry<K,V> firstEntry() {return exportEntry(getFirstEntry()); }final Entry<K,V> getFirstEntry() {Entry<K,V> p = root;if (p != null)while (p.left != null)p = p.left;return p; }從中，我們可以看出 firstEntry() 和 getFirstEntry() 都是用于獲取第一個(gè)節(jié)點(diǎn)。
但是，firstEntry() 是對外接口； getFirstEntry() 是內(nèi)部接口。而且，firstEntry() 是通過 getFirstEntry() 來實(shí)現(xiàn)的。那為什么外界不能直接調(diào)用 getFirstEntry()，而需要多此一舉的調(diào)用 firstEntry() 呢?
先告訴大家原因，再進(jìn)行詳細(xì)說明。這么做的目的是：防止用戶修改返回的Entry。getFirstEntry()返回的Entry是可以被修改的，但是經(jīng)過firstEntry()返回的Entry不能被修改，只可以讀取Entry的key值和value值。下面我們看看到底是如何實(shí)現(xiàn)的。
(01) getFirstEntry()返回的是Entry節(jié)點(diǎn)，而Entry是紅黑樹的節(jié)點(diǎn)，它的源碼如下：
從中，我們可以調(diào)用Entry的getKey()、getValue()來獲取key和value值，以及調(diào)用setValue()來修改value的值。
(02) firstEntry()返回的是exportEntry(getFirstEntry())。下面我們看看exportEntry()干了些什么？
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {return e == null? null :new AbstractMap.SimpleImmutableEntry<K,V>(e); }實(shí)際上，exportEntry() 是新建一個(gè)AbstractMap.SimpleImmutableEntry類型的對象，并返回。
SimpleImmutableEntry的實(shí)現(xiàn)在AbstractMap.java中，下面我們看看AbstractMap.SimpleImmutableEntry是如何實(shí)現(xiàn)的，代碼如下：
1 public static class SimpleImmutableEntry<K,V>2 implements Entry<K,V>, java.io.Serializable3 {4 private static final long serialVersionUID = 7138329143949025153L;5 6 private final K key;7 private final V value;8 9 public SimpleImmutableEntry(K key, V value) { 10 this.key = key; 11 this.value = value; 12 } 13 14 public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) { 15 this.key = entry.getKey(); 16 this.value = entry.getValue(); 17 } 18 19 public K getKey() { 20 return key; 21 } 22 23 public V getValue() { 24 return value; 25 } 26 27 public V setValue(V value) { 28 throw new UnsupportedOperationException(); 29 } 30 31 public boolean equals(Object o) { 32 if (!(o instanceof Map.Entry)) 33 return false; 34 Map.Entry e = (Map.Entry)o; 35 return eq(key, e.getKey()) && eq(value, e.getValue()); 36 } 37 38 public int hashCode() { 39 return (key == null ? 0 : key.hashCode()) ^ 40 (value == null ? 0 : value.hashCode()); 41 } 42 43 public String toString() { 44 return key + "=" + value; 45 } 46 }從中，我們可以看出SimpleImmutableEntry實(shí)際上是簡化的key-value節(jié)點(diǎn)。
它只提供了getKey()、getValue()方法類獲取節(jié)點(diǎn)的值；但不能修改value的值，因?yàn)檎{(diào)用 setValue() 會(huì)拋出異常UnsupportedOperationException();
再回到我們之前的問題：那為什么外界不能直接調(diào)用 getFirstEntry()，而需要多此一舉的調(diào)用 firstEntry() 呢?
現(xiàn)在我們清晰的了解到：
(01) firstEntry()是對外接口，而getFirstEntry()是內(nèi)部接口。
(02) 對firstEntry()返回的Entry對象只能進(jìn)行g(shù)etKey()、getValue()等讀取操作；而對getFirstEntry()返回的對象除了可以進(jìn)行讀取操作之后，還可以通過setValue()修改值。
?
第3.4部分 TreeMap的key相關(guān)函數(shù)
TreeMap的firstKey()、lastKey()、lowerKey()、higherKey()、floorKey()、ceilingKey()原理都是類似的；下面以ceilingKey()來進(jìn)行詳細(xì)說明
ceilingKey(K key)的作用是“返回大于/等于key的最小的鍵值對所對應(yīng)的KEY，沒有的話返回null”，它的代碼如下：
public K ceilingKey(K key) {return keyOrNull(getCeilingEntry(key)); }ceilingKey()是通過getCeilingEntry()實(shí)現(xiàn)的。keyOrNull()的代碼很簡單，它是獲取節(jié)點(diǎn)的key，沒有的話，返回null。
static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {return e == null? null : e.key; }getCeilingEntry(K key)的作用是“獲取TreeMap中大于/等于key的最小的節(jié)點(diǎn)，若不存在(即TreeMap中所有節(jié)點(diǎn)的鍵都比key大)，就返回null”。它的實(shí)現(xiàn)代碼如下：
1 final Entry<K,V> getCeilingEntry(K key) {2 Entry<K,V> p = root;3 while (p != null) {4 int cmp = compare(key, p.key);5 // 情況一：若“p的key” > key。6 // 若 p 存在左孩子，則設(shè) p=“p的左孩子”；7 // 否則，返回p8 if (cmp < 0) {9 if (p.left != null) 10 p = p.left; 11 else 12 return p; 13 // 情況二：若“p的key” < key。 14 } else if (cmp > 0) { 15 // 若 p 存在右孩子，則設(shè) p=“p的右孩子” 16 if (p.right != null) { 17 p = p.right; 18 } else { 19 // 若 p 不存在右孩子，則找出 p 的后繼節(jié)點(diǎn)，并返回 20 // 注意：這里返回的 “p的后繼節(jié)點(diǎn)”有2種可能性：第一，null；第二，TreeMap中大于key的最小的節(jié)點(diǎn)。 21 // 理解這一點(diǎn)的核心是，getCeilingEntry是從root開始遍歷的。 22 // 若getCeilingEntry能走到這一步，那么，它之前“已經(jīng)遍歷過的節(jié)點(diǎn)的key”都 > key。 23 // 能理解上面所說的，那么就很容易明白，為什么“p的后繼節(jié)點(diǎn)”有2種可能性了。 24 Entry<K,V> parent = p.parent; 25 Entry<K,V> ch = p; 26 while (parent != null && ch == parent.right) { 27 ch = parent; 28 parent = parent.parent; 29 } 30 return parent; 31 } 32 // 情況三：若“p的key” = key。 33 } else 34 return p; 35 } 36 return null; 37 }?
第3.5部分 TreeMap的values()函數(shù)
values() 返回“TreeMap中值的集合”
values()的實(shí)現(xiàn)代碼如下：
public Collection<V> values() {Collection<V> vs = values;return (vs != null) ? vs : (values = new Values()); }說明：從中，我們可以發(fā)現(xiàn)values()是通過 new Values() 來實(shí)現(xiàn) “返回TreeMap中值的集合”。
那么Values()是如何實(shí)現(xiàn)的呢？ 沒錯(cuò)！由于返回的是值的集合，那么Values()肯定返回一個(gè)集合；而Values()正好是集合類Value的構(gòu)造函數(shù)。Values繼承于AbstractCollection，它的代碼如下：
1 // ”TreeMap的值的集合“對應(yīng)的類，它集成于AbstractCollection2 class Values extends AbstractCollection<V> {3 // 返回迭代器4 public Iterator<V> iterator() {5 return new ValueIterator(getFirstEntry());6 }7 8 // 返回個(gè)數(shù)9 public int size() { 10 return TreeMap.this.size(); 11 } 12 13 // "TreeMap的值的集合"中是否包含"對象o" 14 public boolean contains(Object o) { 15 return TreeMap.this.containsValue(o); 16 } 17 18 // 刪除"TreeMap的值的集合"中的"對象o" 19 public boolean remove(Object o) { 20 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) { 21 if (valEquals(e.getValue(), o)) { 22 deleteEntry(e); 23 return true; 24 } 25 } 26 return false; 27 } 28 29 // 清空刪除"TreeMap的值的集合" 30 public void clear() { 31 TreeMap.this.clear(); 32 } 33 }說明：從中，我們可以知道Values類就是一個(gè)集合。而 AbstractCollection 實(shí)現(xiàn)了除 size() 和 iterator() 之外的其它函數(shù)，因此只需要在Values類中實(shí)現(xiàn)這兩個(gè)函數(shù)即可。
size() 的實(shí)現(xiàn)非常簡單，Values集合中元素的個(gè)數(shù)=該TreeMap的元素個(gè)數(shù)。(TreeMap每一個(gè)元素都有一個(gè)值嘛！)
iterator() 則返回一個(gè)迭代器，用于遍歷Values。下面，我們一起可以看看iterator()的實(shí)現(xiàn)：
說明： iterator() 是通過ValueIterator() 返回迭代器的，ValueIterator是一個(gè)類。代碼如下：
final class ValueIterator extends PrivateEntryIterator<V> {ValueIterator(Entry<K,V> first) {super(first);}public V next() {return nextEntry().value;} }說明：ValueIterator的代碼很簡單，它的主要實(shí)現(xiàn)應(yīng)該在它的父類PrivateEntryIterator中。下面我們一起看看PrivateEntryIterator的代碼：
?View Code說明：PrivateEntryIterator是一個(gè)抽象類，它的實(shí)現(xiàn)很簡單，只只實(shí)現(xiàn)了Iterator的remove()和hasNext()接口，沒有實(shí)現(xiàn)next()接口。
而我們在ValueIterator中已經(jīng)實(shí)現(xiàn)的next()接口。
至此，我們就了解了iterator()的完整實(shí)現(xiàn)了。
?
第3.6部分 TreeMap的entrySet()函數(shù)
entrySet() 返回“鍵值對集合”。顧名思義，它返回的是一個(gè)集合，集合的元素是“鍵值對”。
下面，我們看看它是如何實(shí)現(xiàn)的？entrySet() 的實(shí)現(xiàn)代碼如下：
public Set<Map.Entry<K,V>> entrySet() {EntrySet es = entrySet;return (es != null) ? es : (entrySet = new EntrySet()); }說明：entrySet()返回的是一個(gè)EntrySet對象。
下面我們看看EntrySet的代碼：
1 // EntrySet是“TreeMap的所有鍵值對組成的集合”，2 // EntrySet集合的單位是單個(gè)“鍵值對”。3 class EntrySet extends AbstractSet<Map.Entry<K,V>> {4 public Iterator<Map.Entry<K,V>> iterator() {5 return new EntryIterator(getFirstEntry());6 }7 8 // EntrySet中是否包含“鍵值對Object”9 public boolean contains(Object o) { 10 if (!(o instanceof Map.Entry)) 11 return false; 12 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 13 V value = entry.getValue(); 14 Entry<K,V> p = getEntry(entry.getKey()); 15 return p != null && valEquals(p.getValue(), value); 16 } 17 18 // 刪除EntrySet中的“鍵值對Object” 19 public boolean remove(Object o) { 20 if (!(o instanceof Map.Entry)) 21 return false; 22 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 23 V value = entry.getValue(); 24 Entry<K,V> p = getEntry(entry.getKey()); 25 if (p != null && valEquals(p.getValue(), value)) { 26 deleteEntry(p); 27 return true; 28 } 29 return false; 30 } 31 32 // 返回EntrySet中元素個(gè)數(shù) 33 public int size() { 34 return TreeMap.this.size(); 35 } 36 37 // 清空EntrySet 38 public void clear() { 39 TreeMap.this.clear(); 40 } 41 }說明：
EntrySet是“TreeMap的所有鍵值對組成的集合”，而且它單位是單個(gè)“鍵值對”。
EntrySet是一個(gè)集合，它繼承于AbstractSet。而AbstractSet實(shí)現(xiàn)了除size() 和 iterator() 之外的其它函數(shù)，因此，我們重點(diǎn)了解一下EntrySet的size() 和 iterator() 函數(shù)
size() 的實(shí)現(xiàn)非常簡單，AbstractSet集合中元素的個(gè)數(shù)=該TreeMap的元素個(gè)數(shù)。
iterator() 則返回一個(gè)迭代器，用于遍歷AbstractSet。從上面的源碼中，我們可以發(fā)現(xiàn)iterator() 是通過EntryIterator實(shí)現(xiàn)的；下面我們看看EntryIterator的源碼：
說明：和Values類一樣，EntryIterator也繼承于PrivateEntryIterator類。
?
第3.7部分 TreeMap實(shí)現(xiàn)的Cloneable接口
TreeMap實(shí)現(xiàn)了Cloneable接口，即實(shí)現(xiàn)了clone()方法。
clone()方法的作用很簡單，就是克隆一個(gè)TreeMap對象并返回。
?
第3.8部分 TreeMap實(shí)現(xiàn)的Serializable接口
TreeMap實(shí)現(xiàn)java.io.Serializable，分別實(shí)現(xiàn)了串行讀取、寫入功能。
串行寫入函數(shù)是writeObject()，它的作用是將TreeMap的“容量，所有的Entry”都寫入到輸出流中。
而串行讀取函數(shù)是readObject()，它的作用是將TreeMap的“容量、所有的Entry”依次讀出。
readObject() 和 writeObject() 正好是一對，通過它們，我能實(shí)現(xiàn)TreeMap的串行傳輸。
說到這里，就順便說一下“關(guān)鍵字transient”的作用
transient是Java語言的關(guān)鍵字，它被用來表示一個(gè)域不是該對象串行化的一部分。
Java的serialization提供了一種持久化對象實(shí)例的機(jī)制。當(dāng)持久化對象時(shí)，可能有一個(gè)特殊的對象數(shù)據(jù)成員，我們不想用serialization機(jī)制來保存它。為了在一個(gè)特定對象的一個(gè)域上關(guān)閉serialization，可以在這個(gè)域前加上關(guān)鍵字transient。?
當(dāng)一個(gè)對象被串行化的時(shí)候，transient型變量的值不包括在串行化的表示中，然而非transient型的變量是被包括進(jìn)去的。
?
第3.9部分 TreeMap實(shí)現(xiàn)的NavigableMap接口
firstKey()、lastKey()、lowerKey()、higherKey()、ceilingKey()、floorKey();
firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry();
上面已經(jīng)講解過這些API了，下面對其它的API進(jìn)行說明。
1 反向TreeMap
descendingMap() 的作用是返回當(dāng)前TreeMap的反向的TreeMap。所謂反向，就是排序順序和原始的順序相反。
我們已經(jīng)知道TreeMap是一顆紅黑樹，而紅黑樹是有序的。
TreeMap的排序方式是通過比較器，在創(chuàng)建TreeMap的時(shí)候，若指定了比較器，則使用該比較器；否則，就使用Java的默認(rèn)比較器。
而獲取TreeMap的反向TreeMap的原理就是將比較器反向即可！
理解了descendingMap()的反向原理之后，再講解一下descendingMap()的代碼。
// 獲取TreeMap的降序Map public NavigableMap<K, V> descendingMap() {NavigableMap<K, V> km = descendingMap;return (km != null) ? km :(descendingMap = new DescendingSubMap(this,true, null, true,true, null, true)); }從中，我們看出descendingMap()實(shí)際上是返回DescendingSubMap類的對象。下面，看看DescendingSubMap的源碼：
1 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {2 private static final long serialVersionUID = 912986545866120460L;3 DescendingSubMap(TreeMap<K,V> m,4 boolean fromStart, K lo, boolean loInclusive,5 boolean toEnd, K hi, boolean hiInclusive) {6 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);7 }8 9 // 反轉(zhuǎn)的比較器：是將原始比較器反轉(zhuǎn)得到的。 10 private final Comparator<? super K> reverseComparator = 11 Collections.reverseOrder(m.comparator); 12 13 // 獲取反轉(zhuǎn)比較器 14 public Comparator<? super K> comparator() { 15 return reverseComparator; 16 } 17 18 // 獲取“子Map”。 19 // 范圍是從fromKey 到 toKey；fromInclusive是是否包含fromKey的標(biāo)記，toInclusive是是否包含toKey的標(biāo)記 20 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, 21 K toKey, boolean toInclusive) { 22 if (!inRange(fromKey, fromInclusive)) 23 throw new IllegalArgumentException("fromKey out of range"); 24 if (!inRange(toKey, toInclusive)) 25 throw new IllegalArgumentException("toKey out of range"); 26 return new DescendingSubMap(m, 27 false, toKey, toInclusive, 28 false, fromKey, fromInclusive); 29 } 30 31 // 獲取“Map的頭部”。 32 // 范圍從第一個(gè)節(jié)點(diǎn) 到 toKey, inclusive是是否包含toKey的標(biāo)記 33 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { 34 if (!inRange(toKey, inclusive)) 35 throw new IllegalArgumentException("toKey out of range"); 36 return new DescendingSubMap(m, 37 false, toKey, inclusive, 38 toEnd, hi, hiInclusive); 39 } 40 41 // 獲取“Map的尾部”。 42 // 范圍是從 fromKey 到 最后一個(gè)節(jié)點(diǎn)，inclusive是是否包含fromKey的標(biāo)記 43 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive){ 44 if (!inRange(fromKey, inclusive)) 45 throw new IllegalArgumentException("fromKey out of range"); 46 return new DescendingSubMap(m, 47 fromStart, lo, loInclusive, 48 false, fromKey, inclusive); 49 } 50 51 // 獲取對應(yīng)的降序Map 52 public NavigableMap<K,V> descendingMap() { 53 NavigableMap<K,V> mv = descendingMapView; 54 return (mv != null) ? mv : 55 (descendingMapView = 56 new AscendingSubMap(m, 57 fromStart, lo, loInclusive, 58 toEnd, hi, hiInclusive)); 59 } 60 61 // 返回“升序Key迭代器” 62 Iterator<K> keyIterator() { 63 return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); 64 } 65 66 // 返回“降序Key迭代器” 67 Iterator<K> descendingKeyIterator() { 68 return new SubMapKeyIterator(absLowest(), absHighFence()); 69 } 70 71 // “降序EntrySet集合”類 72 // 實(shí)現(xiàn)了iterator() 73 final class DescendingEntrySetView extends EntrySetView { 74 public Iterator<Map.Entry<K,V>> iterator() { 75 return new DescendingSubMapEntryIterator(absHighest(), absLowFence()); 76 } 77 } 78 79 // 返回“降序EntrySet集合” 80 public Set<Map.Entry<K,V>> entrySet() { 81 EntrySetView es = entrySetView; 82 return (es != null) ? es : new DescendingEntrySetView(); 83 } 84 85 TreeMap.Entry<K,V> subLowest() { return absHighest(); } 86 TreeMap.Entry<K,V> subHighest() { return absLowest(); } 87 TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); } 88 TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); } 89 TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); } 90 TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); } 91 }從中，我們看出DescendingSubMap是降序的SubMap，它的實(shí)現(xiàn)機(jī)制是將“SubMap的比較器反轉(zhuǎn)”。
它繼承于NavigableSubMap。而NavigableSubMap是一個(gè)繼承于AbstractMap的抽象類；它包括2個(gè)子類——"(升序)AscendingSubMap"和"(降序)DescendingSubMap"。NavigableSubMap為它的兩個(gè)子類實(shí)現(xiàn)了許多公共API。
下面看看NavigableSubMap的源碼。
NavigableSubMap源碼很多，但不難理解；讀者可以通過源碼和注釋進(jìn)行理解。
其實(shí)，讀完NavigableSubMap的源碼后，我們可以得出它的核心思想是：它是一個(gè)抽象集合類，為2個(gè)子類——"(升序)AscendingSubMap"和"(降序)DescendingSubMap"而服務(wù)；因?yàn)镹avigableSubMap實(shí)現(xiàn)了許多公共API。它的最終目的是實(shí)現(xiàn)下面的一系列函數(shù)：
headMap(K toKey, boolean inclusive) headMap(K toKey) subMap(K fromKey, K toKey) subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) tailMap(K fromKey) tailMap(K fromKey, boolean inclusive) navigableKeySet() descendingKeySet()?
第3.10部分 TreeMap其它函數(shù)
1 順序遍歷和逆序遍歷
TreeMap的順序遍歷和逆序遍歷原理非常簡單。
由于TreeMap中的元素是從小到大的順序排列的。因此，順序遍歷，就是從第一個(gè)元素開始，逐個(gè)向后遍歷；而倒序遍歷則恰恰相反，它是從最后一個(gè)元素開始，逐個(gè)往前遍歷。
我們可以通過 keyIterator() 和 descendingKeyIterator()來說明！
keyIterator()的作用是返回順序的KEY的集合，
descendingKeyIterator()的作用是返回逆序的KEY的集合。
keyIterator() 的代碼如下：
Iterator<K> keyIterator() {return new KeyIterator(getFirstEntry()); }說明：從中我們可以看出keyIterator() 是返回以“第一個(gè)節(jié)點(diǎn)(getFirstEntry)” 為其實(shí)元素的迭代器。
KeyIterator的代碼如下：
說明：KeyIterator繼承于PrivateEntryIterator。當(dāng)我們通過next()不斷獲取下一個(gè)元素的時(shí)候，就是執(zhí)行的順序遍歷了。
descendingKeyIterator()的代碼如下：
說明：從中我們可以看出descendingKeyIterator() 是返回以“最后一個(gè)節(jié)點(diǎn)(getLastEntry)” 為其實(shí)元素的迭代器。
再看看DescendingKeyIterator的代碼：
說明：DescendingKeyIterator繼承于PrivateEntryIterator。當(dāng)我們通過next()不斷獲取下一個(gè)元素的時(shí)候，實(shí)際上調(diào)用的是prevEntry()獲取的上一個(gè)節(jié)點(diǎn)，這樣它實(shí)際上執(zhí)行的是逆序遍歷了。
至此，TreeMap的相關(guān)內(nèi)容就全部介紹完畢了。若有錯(cuò)誤或紕漏的地方，歡迎指正！
?
第4部分 TreeMap遍歷方式
4.1 遍歷TreeMap的鍵值對
第一步：根據(jù)entrySet()獲取TreeMap的“鍵值對”的Set集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。
?
4.2 遍歷TreeMap的鍵
第一步：根據(jù)keySet()獲取TreeMap的“鍵”的Set集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。
?
4.3 遍歷TreeMap的值
第一步：根據(jù)value()獲取TreeMap的“值”的集合。
第二步：通過Iterator迭代器遍歷“第一步”得到的集合。
TreeMap遍歷測試程序如下：
1 import java.util.Map;2 import java.util.Random;3 import java.util.Iterator;4 import java.util.TreeMap;5 import java.util.HashSet;6 import java.util.Map.Entry;7 import java.util.Collection;8 9 /*10 * @desc 遍歷TreeMap的測試程序。11 * (01) 通過entrySet()去遍歷key、value，參考實(shí)現(xiàn)函數(shù)：12 * iteratorTreeMapByEntryset()13 * (02) 通過keySet()去遍歷key、value，參考實(shí)現(xiàn)函數(shù)：14 * iteratorTreeMapByKeyset()15 * (03) 通過values()去遍歷value，參考實(shí)現(xiàn)函數(shù)：16 * iteratorTreeMapJustValues()17 *18 * @author skywang19 */20 public class TreeMapIteratorTest {21 22 public static void main(String[] args) {23 int val = 0;24 String key = null;25 Integer value = null;26 Random r = new Random();27 TreeMap map = new TreeMap();28 29 for (int i=0; i<12; i++) {30 // 隨機(jī)獲取一個(gè)[0,100)之間的數(shù)字31 val = r.nextInt(100);32 33 key = String.valueOf(val);34 value = r.nextInt(5);35 // 添加到TreeMap中36 map.put(key, value);37 System.out.println(" key:"+key+" value:"+value);38 }39 // 通過entrySet()遍歷TreeMap的key-value40 iteratorTreeMapByEntryset(map) ;41 42 // 通過keySet()遍歷TreeMap的key-value43 iteratorTreeMapByKeyset(map) ;44 45 // 單單遍歷TreeMap的value46 iteratorTreeMapJustValues(map); 47 }48 49 /*50 * 通過entry set遍歷TreeMap51 * 效率高!52 */53 private static void iteratorTreeMapByEntryset(TreeMap map) {54 if (map == null)55 return ;56 57 System.out.println("\niterator TreeMap By entryset");58 String key = null;59 Integer integ = null;60 Iterator iter = map.entrySet().iterator();61 while(iter.hasNext()) {62 Map.Entry entry = (Map.Entry)iter.next();63 64 key = (String)entry.getKey();65 integ = (Integer)entry.getValue();66 System.out.println(key+" -- "+integ.intValue());67 }68 }69 70 /*71 * 通過keyset來遍歷TreeMap72 * 效率低!73 */74 private static void iteratorTreeMapByKeyset(TreeMap map) {75 if (map == null)76 return ;77 78 System.out.println("\niterator TreeMap By keyset");79 String key = null;80 Integer integ = null;81 Iterator iter = map.keySet().iterator();82 while (iter.hasNext()) {83 key = (String)iter.next();84 integ = (Integer)map.get(key);85 System.out.println(key+" -- "+integ.intValue());86 }87 }88 89 90 /*91 * 遍歷TreeMap的values92 */93 private static void iteratorTreeMapJustValues(TreeMap map) {94 if (map == null)95 return ;96 97 Collection c = map.values();98 Iterator iter= c.iterator();99 while (iter.hasNext()) { 100 System.out.println(iter.next()); 101 } 102 } 103 }???
第5部分 TreeMap示例
下面通過實(shí)例來學(xué)習(xí)如何使用TreeMap
1 import java.util.*;2 3 /**4 * @desc TreeMap測試程序 5 *6 * @author skywang7 */8 public class TreeMapTest {9 10 public static void main(String[] args) {11 // 測試常用的API12 testTreeMapOridinaryAPIs();13 14 // 測試TreeMap的導(dǎo)航函數(shù)15 //testNavigableMapAPIs();16 17 // 測試TreeMap的子Map函數(shù)18 //testSubMapAPIs();19 }20 21 /**22 * 測試常用的API23 */24 private static void testTreeMapOridinaryAPIs() {25 // 初始化隨機(jī)種子26 Random r = new Random();27 // 新建TreeMap28 TreeMap tmap = new TreeMap();29 // 添加操作30 tmap.put("one", r.nextInt(10));31 tmap.put("two", r.nextInt(10));32 tmap.put("three", r.nextInt(10));33 34 System.out.printf("\n ---- testTreeMapOridinaryAPIs ----\n");35 // 打印出TreeMap36 System.out.printf("%s\n",tmap );37 38 // 通過Iterator遍歷key-value39 Iterator iter = tmap.entrySet().iterator();40 while(iter.hasNext()) {41 Map.Entry entry = (Map.Entry)iter.next();42 System.out.printf("next : %s - %s\n", entry.getKey(), entry.getValue());43 }44 45 // TreeMap的鍵值對個(gè)數(shù) 46 System.out.printf("size: %s\n", tmap.size());47 48 // containsKey(Object key) :是否包含鍵key49 System.out.printf("contains key two : %s\n",tmap.containsKey("two"));50 System.out.printf("contains key five : %s\n",tmap.containsKey("five"));51 52 // containsValue(Object value) :是否包含值value53 System.out.printf("contains value 0 : %s\n",tmap.containsValue(new Integer(0)));54 55 // remove(Object key) ： 刪除鍵key對應(yīng)的鍵值對56 tmap.remove("three");57 58 System.out.printf("tmap:%s\n",tmap );59 60 // clear() ： 清空TreeMap61 tmap.clear();62 63 // isEmpty() : TreeMap是否為空64 System.out.printf("%s\n", (tmap.isEmpty()?"tmap is empty":"tmap is not empty") );65 }66 67 68 /**69 * 測試TreeMap的子Map函數(shù)70 */71 public static void testSubMapAPIs() {72 // 新建TreeMap73 TreeMap tmap = new TreeMap();74 // 添加“鍵值對”75 tmap.put("a", 101);76 tmap.put("b", 102);77 tmap.put("c", 103);78 tmap.put("d", 104);79 tmap.put("e", 105);80 81 System.out.printf("\n ---- testSubMapAPIs ----\n");82 // 打印出TreeMap83 System.out.printf("tmap:\n\t%s\n", tmap);84 85 // 測試 headMap(K toKey)86 System.out.printf("tmap.headMap(\"c\"):\n\t%s\n", tmap.headMap("c"));87 // 測試 headMap(K toKey, boolean inclusive) 88 System.out.printf("tmap.headMap(\"c\", true):\n\t%s\n", tmap.headMap("c", true));89 System.out.printf("tmap.headMap(\"c\", false):\n\t%s\n", tmap.headMap("c", false));90 91 // 測試 tailMap(K fromKey)92 System.out.printf("tmap.tailMap(\"c\"):\n\t%s\n", tmap.tailMap("c"));93 // 測試 tailMap(K fromKey, boolean inclusive)94 System.out.printf("tmap.tailMap(\"c\", true):\n\t%s\n", tmap.tailMap("c", true));95 System.out.printf("tmap.tailMap(\"c\", false):\n\t%s\n", tmap.tailMap("c", false));96 97 // 測試 subMap(K fromKey, K toKey)98 System.out.printf("tmap.subMap(\"a\", \"c\"):\n\t%s\n", tmap.subMap("a", "c"));99 // 測試 100 System.out.printf("tmap.subMap(\"a\", true, \"c\", true):\n\t%s\n", 101 tmap.subMap("a", true, "c", true)); 102 System.out.printf("tmap.subMap(\"a\", true, \"c\", false):\n\t%s\n", 103 tmap.subMap("a", true, "c", false)); 104 System.out.printf("tmap.subMap(\"a\", false, \"c\", true):\n\t%s\n", 105 tmap.subMap("a", false, "c", true)); 106 System.out.printf("tmap.subMap(\"a\", false, \"c\", false):\n\t%s\n", 107 tmap.subMap("a", false, "c", false)); 108 109 // 測試 navigableKeySet() 110 System.out.printf("tmap.navigableKeySet():\n\t%s\n", tmap.navigableKeySet()); 111 // 測試 descendingKeySet() 112 System.out.printf("tmap.descendingKeySet():\n\t%s\n", tmap.descendingKeySet()); 113 } 114 115 /** 116 * 測試TreeMap的導(dǎo)航函數(shù) 117 */ 118 public static void testNavigableMapAPIs() { 119 // 新建TreeMap 120 NavigableMap nav = new TreeMap(); 121 // 添加“鍵值對” 122 nav.put("aaa", 111); 123 nav.put("bbb", 222); 124 nav.put("eee", 333); 125 nav.put("ccc", 555); 126 nav.put("ddd", 444); 127 128 System.out.printf("\n ---- testNavigableMapAPIs ----\n"); 129 // 打印出TreeMap 130 System.out.printf("Whole list:%s%n", nav); 131 132 // 獲取第一個(gè)key、第一個(gè)Entry 133 System.out.printf("First key: %s\tFirst entry: %s%n",nav.firstKey(), nav.firstEntry()); 134 135 // 獲取最后一個(gè)key、最后一個(gè)Entry 136 System.out.printf("Last key: %s\tLast entry: %s%n",nav.lastKey(), nav.lastEntry()); 137 138 // 獲取“小于/等于bbb”的最大鍵值對 139 System.out.printf("Key floor before bbb: %s%n",nav.floorKey("bbb")); 140 141 // 獲取“小于bbb”的最大鍵值對 142 System.out.printf("Key lower before bbb: %s%n", nav.lowerKey("bbb")); 143 144 // 獲取“大于/等于bbb”的最小鍵值對 145 System.out.printf("Key ceiling after ccc: %s%n",nav.ceilingKey("ccc")); 146 147 // 獲取“大于bbb”的最小鍵值對 148 System.out.printf("Key higher after ccc: %s%n\n",nav.higherKey("ccc")); 149 } 150 151 }運(yùn)行結(jié)果：
{one=8, three=4, two=2} next : one - 8 next : three - 4 next : two - 2 size: 3 contains key two : true contains key five : false contains value 0 : false tmap:{one=8, two=2} tmap is empty?
注意:TreeMap是基于紅黑樹實(shí)現(xiàn)的, 無容量限制;
? ? ? ?TreeMap是非線程安全的.
?
轉(zhuǎn)載于:https://www.cnblogs.com/kexianting/p/8545788.html
總結(jié)
以上是生活随笔為你收集整理的Java集合--TreeMap的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 2、内核的配置和移植
- 下一篇： SBC应用