java集合框架11——TreeMap和源码分析(二)

目录(?)[+]

我们继续分析TreeMap的源码

1.TreeMap源码分析(续)

1. 存取方法

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

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

1.2 其他方法

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

2. TreeMap的遍历方式

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

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

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

2.1 遍历TreeMap的Entry

[java] view plain copy  java集合框架11——TreeMap和源码分析(二)java集合框架11——TreeMap和源码分析(二)
  1. // 假设map是TreeMap对象  
  2. // map中的key是String类型,value是Integer类型  
  3. Integer integ = null;  
  4. Iterator iter = map.entrySet().iterator();  
  5. while(iter.hasNext()) {  
  6.     Map.Entry entry = (Map.Entry)iter.next();  
  7.     // 获取key  
  8.     key = (String)entry.getKey();  
  9.     // 获取value  
  10.     integ = (Integer)entry.getValue();  
  11. }  

2.2 遍历TreeMap的key

[java] view plain copy  java集合框架11——TreeMap和源码分析(二)java集合框架11——TreeMap和源码分析(二)
  1. // 假设map是TreeMap对象  
  2. // map中的key是String类型,value是Integer类型  
  3. String key = null;  
  4. Integer integ = null;  
  5. Iterator iter = map.keySet().iterator();  
  6. while (iter.hasNext()) {  
  7.         // 获取key  
  8.     key = (String)iter.next();  
  9.         // 根据key,获取value  
  10.     integ = (Integer)map.get(key);  
  11. }  

2.3 遍历TreeMap的value

[java] view plain copy  java集合框架11——TreeMap和源码分析(二)java集合框架11——TreeMap和源码分析(二)
  1. // 假设map是TreeMap对象  
  2. // map中的key是String类型,value是Integer类型  
  3. Integer value = null;  
  4. Collection c = map.values();  
  5. Iterator iter= c.iterator();  
  6. while (iter.hasNext()) {  
  7.     value = (Integer)iter.next();  
  8. }  
TreeMap就介绍这么多吧,如有错误之处,欢迎留言指正~

_____________________________________________________________________________________________________________________________________________________

-----乐于分享,共同进步!

-----更多文章请看:http://blog.csdn.net/eson_15

上一篇:C#:设置CefSharp的一些参数,比如忽略安全证书


下一篇:iOS 归档