java集合框架10——TreeMap和源码分析（一）

2021-12-27 23:04:22

版权声明：尊重博主原创文章，转载请注明出处哦~http://blog.csdn.net/eson_15/article/details/51217741

目录(?)[+]

前面讨论完了HashMap和HashTable的源码，这一节我们来讨论一下TreeMap。先从整体上把握TreeMap，然后分析其源码，深入剖析TreeMap的实现。

1. TreeMap简介

        TreeMap是一个有序的key-value集合，它内部是通过红-黑树实现的，如果对红-黑树不太了解，请先参考下这篇博文：红-黑树。下面我们先来看看TreeMap的继承关系：

[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. java.lang.Object  
  2.    ↳     java.util.AbstractMap<K, V>  
  3.          ↳     java.util.TreeMap<K, V>  
  4.   
  5. public class TreeMap<K,V>  
  6.     extends AbstractMap<K,V>  
  7.     implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}  
        从继承关系可以看出，TreeMap继承与AbstractMap，实现了NavigableMap接口，意味着它支持一系列的导航方法，比如返回有序的key集合。它还实现了Cloneable接口，意味着它能被克隆。另外也实现了Serializable接口，表示它支持序列化。

        TreeMap是基于红-黑树实现的，该映射根据其key的自然顺序进行排序，或者根据用户创建映射时提供的Comarator进行排序，另外，TreeMap是非同步的。

        我们先总览一下TreeMap都有哪些API：

[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. Entry<K, V>                ceilingEntry(K key)  
  2. K                          ceilingKey(K key)  
  3. void                       clear()  
  4. Object                     clone()  
  5. Comparator<? super K>      comparator()  
  6. boolean                    containsKey(Object key)  
  7. NavigableSet<K>            descendingKeySet()  
  8. NavigableMap<K, V>         descendingMap()  
  9. Set<Entry<K, V>>           entrySet()  
  10. Entry<K, V>                firstEntry()  
  11. K                          firstKey()  
  12. Entry<K, V>                floorEntry(K key)  
  13. K                          floorKey(K key)  
  14. V                          get(Object key)  
  15. NavigableMap<K, V>         headMap(K to, boolean inclusive)  
  16. SortedMap<K, V>            headMap(K toExclusive)  
  17. Entry<K, V>                higherEntry(K key)  
  18. K                          higherKey(K key)  
  19. boolean                    isEmpty()  
  20. Set<K>                     keySet()  
  21. Entry<K, V>                lastEntry()  
  22. K                          lastKey()  
  23. Entry<K, V>                lowerEntry(K key)  
  24. K                          lowerKey(K key)  
  25. NavigableSet<K>            navigableKeySet()  
  26. Entry<K, V>                pollFirstEntry()  
  27. Entry<K, V>                pollLastEntry()  
  28. V                          put(K key, V value)  
  29. V                          remove(Object key)  
  30. int                        size()  
  31. SortedMap<K, V>            subMap(K fromInclusive, K toExclusive)  
  32. NavigableMap<K, V>         subMap(K from, boolean fromInclusive, K to, boolean toInclusive)  
  33. NavigableMap<K, V>         tailMap(K from, boolean inclusive)  
  34. SortedMap<K, V>            tailMap(K fromInclusive)  
        从这些API中可以看出，总共可分为这几大类：跟Entry相关的，跟key相关的以及跟Map相关的，另外还有keySet和entrySet等方法，下文详细讨论这些API。

2. TreeMap的源码分析（基于JDK1.7)

2.1 存储结构

        由于TreeMap是基于红黑树实现的，所以其内部维护了一个红-黑树的数据结构，每个key-value对也存储在一个Entry里，只不过这个Entry和前面HashMap或者HashTable中的Entry不同，TreeMap的Entry其实是红-黑树的一个节点。我们来看一下TreeMap中的Entry定义：

[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. private transient Entry<K,V> root = null;  
        然后我们看看Entry实体类的实现：

2.2 Entry实体类和相关方法

        先看一下Entry实体类：

[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. private static final boolean RED   = false;  
  2. private static final boolean BLACK = true;  
  3. //就是一个红黑树的节点  
  4. static final class Entry<K,V> implements Map.Entry<K,V> {  
  5.     K key;  
  6.     V value;  
  7.     Entry<K,V> left = null; //左子节点  
  8.     Entry<K,V> right = null; //右子节点  
  9.     Entry<K,V> parent; //父节点  
  10.     boolean color = BLACK; //树的颜色，默认为黑色  
  11.   
  12.     Entry(K key, V value, Entry<K,V> parent) { //构造方法  
  13.         this.key = key;  
  14.         this.value = value;  
  15.         this.parent = parent;  
  16.     }  
  17.   
  18.     public K getKey() { //获得key  
  19.         return key;  
  20.     }  
  21.   
  22.     public V getValue() { //获得value  
  23.         return value;  
  24.     }  
  25.   
  26.     public V setValue(V value) { //设置value  
  27.         V oldValue = this.value;  
  28.         this.value = value;  
  29.         return oldValue;  
  30.     }  
  31.   
  32.     public boolean equals(Object o) { //key和value均相等才返回true  
  33.         if (!(o instanceof Map.Entry))  
  34.             return false;  
  35.         Map.Entry<?,?> e = (Map.Entry<?,?>)o;  
  36.   
  37.         return valEquals(key,e.getKey()) && valEquals(value,e.getValue());  
  38.     }  
  39.   
  40.     public int hashCode() { //计算hashCode  
  41.         int keyHash = (key==null ? 0 : key.hashCode());  
  42.         int valueHash = (value==null ? 0 : value.hashCode());  
  43.         return keyHash ^ valueHash;  
  44.     }  
  45.   
  46.     public String toString() { //重写toString方法  
  47.         return key + "=" + value;  
  48.     }  
  49. }  
        从Entry实体类中可以看出，TreeMap中的Entry就是一个红黑树的节点。跟这个Entry相关的方法都有firstEntry()、lastEntry()、lowerEntry()、higherEntry()、floorEntry()、ceilingEntry()。它们的原理都是类似的，我们只分析firstEntry()，其他的放到源码里分析：
[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. public Map.Entry<K,V> firstEntry() {  
  2.     return exportEntry(getFirstEntry());  
  3. }  
  4.   
  5. //获得TreeMap里第一个节点(即根据key排序最小的节点)，如果TreeMap为空，返回null  
  6. final Entry<K,V> getFirstEntry() {  
  7.     Entry<K,V> p = root;  
  8.     if (p != null)  
  9.         while (p.left != null)  
  10.             p = p.left;  
  11.     return p;  
  12. }  
        代码很简单，一直往下走，直到找到那个节点，然后返回即可。这里为什么不直接调用getFirtstEntry()，而是对外提供firstEntry()供外界调用呢？这就说到了exportEntry()方法的作用了，因为如果直接调用getFirstEntry()方法的话，返回的Entry是可以被修改的，但是经过exportEntry()方法包装过之后就不能修改了，所以这么做事防止用于修改返回的Entry。我们来看看exportEntry()方法是如何对Entry对象进行包装的：
[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {  
  2.     return (e == null) ? null :  
  3.         new AbstractMap.SimpleImmutableEntry<>(e);  
  4. }  
        我们可以看出，它是通过新new一个AbstractMap类中的一个静态类SimpleImmutableEntry实现的，那么SimpleImmutableEntry类中是如何实现的呢，为了方便，我们也把该类拿过来（当然也可以看这篇博文Map架构与源码分析，里面有讲到AbstractMap抽象类的源码），下面看看这个SimpleImmutableEntry静态类是如何实现的：
[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. public static class SimpleImmutableEntry<K,V>  
  2.     implements Entry<K,V>, java.io.Serializable  
  3. {  
  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) { //通过key和value初始化对象  
  10.         this.key   = key;  
  11.         this.value = value;  
  12.     }  
  13.   
  14.     public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) { //通过传进来一个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) { //!!!关键地方在这里，不能setValue，否则会抛出UnsupportedOperationException异常  
  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.     //重写了toString方法，返回key=value形式  
  44.     public String toString() {  
  45.         return key + "=" + value;  
  46.     }  
  47. }  
        从上面代码中可以看出，被这个类包装过的Entry是不允许被修改内容的，这也就是为什么TreeMap类不直接把getFirstEntry()方法暴露出去，而是提供了firstEntry()供外界调用的原因。关于Entry的其他类似的方法我就不一一赘述了，我放到源代码里分析，都不难理解。如下：
[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. /*********************** 与Entry相关的方法 ******************************/      
  2.   
  3.  //获取TreeMap中键为key对应的节点  
  4.  final Entry<K,V> getEntry(Object key) {  
  5.     // 若比较器不为null，则通过getEntryUsingComparator来获得  
  6.     if (comparator != null)  
  7.         return getEntryUsingComparator(key);  
  8.     if (key == null)  
  9.         throw new NullPointerException();  
  10.     Comparable<? super K> k = (Comparable<? super K>) key;  
  11.     Entry<K,V> p = root; //若没有比较器，则正常往下走  
  12.     while (p != null) {  
  13.         int cmp = k.compareTo(p.key);  
  14.         if (cmp < 0)  
  15.             p = p.left;  
  16.         else if (cmp > 0)  
  17.             p = p.right;  
  18.         else  
  19.             return p; //找到了就返回  
  20.     }  
  21.     return null;  
  22. }  
  23. //使用比较器获得与key对应的Entry  
  24. final Entry<K,V> getEntryUsingComparator(Object key) {  
  25.     K k = (K) key;  
  26.     Comparator<? super K> cpr = comparator;  
  27.     if (cpr != null) {  
  28.         Entry<K,V> p = root;  
  29.         while (p != null) {  
  30.             int cmp = cpr.compare(k, p.key);  
  31.             if (cmp < 0)  
  32.                 p = p.left;  
  33.             else if (cmp > 0)  
  34.                 p = p.right;  
  35.             else  
  36.                 return p;  
  37.         }  
  38.     }  
  39.     return null;  
  40. }  
  41. /*--------------------------------------------------------*/  
  42. public Map.Entry<K,V> firstEntry() {  
  43.     return exportEntry(getFirstEntry());  
  44. }  
  45. //获得TreeMap里第一个节点(即根据key排序最小的节点)，如果TreeMap为空，返回null  
  46. final Entry<K,V> getFirstEntry() {  
  47.     Entry<K,V> p = root;  
  48.     if (p != null)  
  49.         while (p.left != null)  
  50.             p = p.left;  
  51.     return p;  
  52. }  
  53. /*-----------------------------------------------*/  
  54. public Map.Entry<K,V> lastEntry() {  
  55.     return exportEntry(getLastEntry());  
  56. }  
  57. //获得TreeMap里最后一个节点(根据key排序最大的节点)，如果TreeMap为空，返回null  
  58. final Entry<K,V> getLastEntry() {  
  59.     Entry<K,V> p = root;  
  60.     if (p != null)  
  61.         while (p.right != null)  
  62.             p = p.right;  
  63.     return p;  
  64. }  
  65. /*------------------------------------------------*/  
  66. //弹出第一个节点，即删除  
  67. public Map.Entry<K,V> pollFirstEntry() {  
  68.     Entry<K,V> p = getFirstEntry();   
  69.     Map.Entry<K,V> result = exportEntry(p);  
  70.     if (p != null)  
  71.         deleteEntry(p);  
  72.     return result;  
  73. }  
  74. //弹出最后一个节点，即删除  
  75. public Map.Entry<K,V> pollLastEntry() {  
  76.     Entry<K,V> p = getLastEntry();  
  77.     Map.Entry<K,V> result = exportEntry(p);  
  78.     if (p != null)  
  79.         deleteEntry(p);  
  80.     return result;  
  81. }  
  82. /*-------------------------------------------------*/  
  83. public Map.Entry<K,V> floorEntry(K key) {  
  84.     return exportEntry(getFloorEntry(key));  
  85. }  
  86. public Map.Entry<K,V> ceilingEntry(K key) {  
  87.     return exportEntry(getCeilingEntry(key));  
  88. }  
  89.   
  90. //获取TreeMap中不小于key的最小的节点；  
  91. //若不存在(即TreeMap中所有节点的键都比key大)，就返回null  
  92. final Entry<K,V> getCeilingEntry(K key) {  
  93.     Entry<K,V> p = root;  
  94.     while (p != null) {  
  95.         int cmp = compare(key, p.key);  
  96.         if (cmp < 0) { //情况1. 若p.key > key  
  97.             if (p.left != null) //若p有左子节点  
  98.                 p = p.left; //往左下走  
  99.             else  
  100.                 return p; //否则返回p  
  101.         } else if (cmp > 0) { //情况2：p.key < key  
  102.             if (p.right != null) {  
  103.                 p = p.right;  
  104.             } else {  
  105.                 // 若 p 不存在右孩子，则找出 p 的后继节点，并返回  
  106.                 // 注意：这里返回的 “p的后继节点”有2种可能性：第一，null；第二，TreeMap中大于key的最小的节点。  
  107.                 // 理解这一点的核心是，getCeilingEntry是从root开始遍历的。  
  108.                 // 若getCeilingEntry能走到这一步，那么，它之前“已经遍历过的节点的key”都 > key。  
  109.                 // 能理解上面所说的，那么就很容易明白，为什么“p的后继节点”又2种可能性了。  
  110.                 Entry<K,V> parent = p.parent;  
  111.                 Entry<K,V> ch = p;  
  112.                 while (parent != null && ch == parent.right) {  
  113.                     ch = parent;  
  114.                     parent = parent.parent;  
  115.                 }  
  116.                 return parent;  
  117.             }  
  118.         } else //情况3：p.key = key  
  119.             return p;  
  120.     }  
  121.     return null;  
  122. }  
  123. // 获取TreeMap中不大于key的最大的节点；  
  124. // 若不存在(即TreeMap中所有节点的键都比key小)，就返回null  
  125. // getFloorEntry的原理和getCeilingEntry类似，这里不再多说。  
  126. final Entry<K,V> getFloorEntry(K key) {  
  127.     Entry<K,V> p = root;  
  128.     while (p != null) {  
  129.         int cmp = compare(key, p.key);  
  130.         if (cmp > 0) {  
  131.             if (p.right != null)  
  132.                 p = p.right;  
  133.             else  
  134.                 return p;  
  135.         } else if (cmp < 0) {  
  136.             if (p.left != null) {  
  137.                 p = p.left;  
  138.             } else {  
  139.                 Entry<K,V> parent = p.parent;  
  140.                 Entry<K,V> ch = p;  
  141.                 while (parent != null && ch == parent.left) {  
  142.                     ch = parent;  
  143.                     parent = parent.parent;  
  144.                 }  
  145.                 return parent;  
  146.             }  
  147.         } else  
  148.             return p;  
  149.   
  150.     }  
  151.     return null;  
  152. }  
  153. /*--------------------------------------------------*/  
  154. public Map.Entry<K,V> lowerEntry(K key) {  
  155.     return exportEntry(getLowerEntry(key));  
  156. }  
  157. public Map.Entry<K,V> higherEntry(K key) {  
  158.     return exportEntry(getHigherEntry(key));  
  159. }   
  160.   
  161. // 获取TreeMap中大于key的最小的节点。  
  162. // 若不存在，就返回null。  
  163. // 请参照getCeilingEntry来对getHigherEntry进行理解。  
  164. final Entry<K,V> getLowerEntry(K key) {  
  165.     Entry<K,V> p = root;  
  166.     while (p != null) {  
  167.         int cmp = compare(key, p.key);  
  168.         if (cmp > 0) {  
  169.             if (p.right != null)  
  170.                 p = p.right;  
  171.             else  
  172.                 return p;  
  173.         } else {  
  174.             if (p.left != null) {  
  175.                 p = p.left;  
  176.             } else {  
  177.                 Entry<K,V> parent = p.parent;  
  178.                 Entry<K,V> ch = p;  
  179.                 while (parent != null && ch == parent.left) {  
  180.                     ch = parent;  
  181.                     parent = parent.parent;  
  182.                 }  
  183.                 return parent;  
  184.             }  
  185.         }  
  186.     }  
  187.     return null;  
  188. }  
  189. // 获取TreeMap中小于key的最大的节点。  
  190. // 若不存在，就返回null。  
  191. // 请参照getCeilingEntry来对getLowerEntry进行理解。  
  192. final Entry<K,V> getHigherEntry(K key) {  
  193.     Entry<K,V> p = root;  
  194.     while (p != null) {  
  195.         int cmp = compare(key, p.key);  
  196.         if (cmp < 0) {  
  197.             if (p.left != null)  
  198.                 p = p.left;  
  199.             else  
  200.                 return p;  
  201.         } else {  
  202.             if (p.right != null) {  
  203.                 p = p.right;  
  204.             } else {  
  205.                 Entry<K,V> parent = p.parent;  
  206.                 Entry<K,V> ch = p;  
  207.                 while (parent != null && ch == parent.right) {  
  208.                     ch = parent;  
  209.                     parent = parent.parent;  
  210.                 }  
  211.                 return parent;  
  212.             }  
  213.         }  
  214.     }  
  215.     return null;  
  216. }  
  217. /*---------------------------------------------------*/  

2.3 成员属性的构造方法

        分析完了Entry实体相关的源码后，我们来看看TreeMap里的成员属性。

[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. /********************* 成员属性 ****************************/  
  2. private final Comparator<? super K> comparator; //比较器  
  3. private transient Entry<K,V> root = null; //实体对象  
  4. private transient int size = 0; //红黑树节点个数，即Entry数  
  5. private transient int modCount = 0; //修改次数  
  6.   
  7. /*********************** 构造方法 **************************/  
  8. public TreeMap() {  //默认构造方法  
  9.     comparator = null;  
  10. }  
  11. public TreeMap(Comparator<? super K> comparator) { //带比较器的构造方法  
  12.     this.comparator = comparator;  
  13. }  
  14. public TreeMap(Map<? extends K, ? extends V> m) { //带Map的构造方法，Map会为TreeMap的子类  
  15.     comparator = null;  
  16.     putAll(m);  
  17. }  
  18. ////带sortedMap的构造方法，sortedMap会为TreeMap的子类  
  19. public TreeMap(SortedMap<K, ? extends V> m) {  
  20.     comparator = m.comparator();  
  21.     try {  
  22.         buildFromSorted(m.size(), m.entrySet().iterator(), null, null);  
  23.     } catch (java.io.IOException cannotHappen) {  
  24.     } catch (ClassNotFoundException cannotHappen) {  
  25.     }  
  26. }  
        我们可以看出，TreeMap有四个构造函数，这里分析一下第三个构造函数，内部调用了putAll方法，我们看一下putAll方法：

[java] view plain copy  java集合框架10——TreeMap和源码分析（一）java集合框架10——TreeMap和源码分析（一）
  1. public void putAll(Map<? extends K, ? extends V> map) {  
  2.     int mapSize = map.size();//获取map的大小  
  3.     //如果TreeMap大小是0，且map的大小不为0，且map是已排序的key-value对，才执行下面的程序  
  4.     if (size==0 && mapSize!=0 && map instanceof SortedMap) {  
  5.         Comparator c = ((SortedMap)map).comparator();  
  6.         if (c == comparator || (c != null && c.equals(comparator))) {  
  7.             ++modCount;  
  8.             try {  
  9.                 buildFromSorted(mapSize, map.entrySet().iterator(),  
  10.                                 null, null);  
  11.             } catch (java.io.IOException cannotHappen) {  
  12.             } catch (ClassNotFoundException cannotHappen) {  
  13.             }  
  14.             return;  
  15.         }  
  16.     }  
  17.     //否则调用AbstractMap中的putAll()  
  18.     //AbstractMap中的putAll()又会调用TreeMap的put()方法  
  19.     super.putAll(map);  
  20. }  

        在putAll方法内部，会先进行判断，如果TreeMap是空的，且传进来的map符合条件，则执行if内的语句，然后调用buildFromSorted方法（后面放到源码中分析）来put进去，否则调用父类的putAll方法，父类的putAll方法则直接调用TreeMap的put方法。

        由于TreeMap的源码比较多，这里先写到这，后面的源码分析放到下一篇博客中写：java集合框架11——TreeMap和源码分析（二）。

        如有错误之处，欢迎留言指正~

_____________________________________________________________________________________________________________________________________________________

-----乐于分享，共同进步！

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

上一篇：hadoop压缩框架


下一篇：Android -- SDcard文件读取和保存