JDK1.8源码(十一)——java.util.TreeMap类

分手后的思念是犯贱 2022-01-31 08:53 170阅读 0赞

# [JDK1.8源码(十一)——java.util.TreeMap类][JDK1.8_java.util.TreeMap] #

在前面几篇博客分别介绍了这样几种集合，基于数组实现的[ArrayList 类][ArrayList]，基于链表实现的[LinkedList 类][LinkedList]，基于散列表实现的[HashMap 类][HashMap]，本篇博客我们来介绍另一种数据类型，基于树实现的**TreeSet**类。

### 1、TreeMap 定义 ###

听名字就知道，TreeMap 是由Tree 和 Map 集合有关的，没错，TreeMap 是由红黑树实现的有序的 key-value 集合。

PS:想要学懂TreeMap的实现原理，[红黑树][Link 1]的了解是必不可少的！！！

public class TreeMap<K,V>
        extends AbstractMap<K,V>
        implements NavigableMap<K,V>, Cloneable, java.io.Serializable

![1120165-20190121213836953-1363088203.png][]

TreeMap 首先继承了 AbstractMap 抽象类，表示它具有散列表的性质，也就是由 key-value 组成。

其次 TreeMap 实现了 NavigableMap 接口，该接口支持一系列获取指定集合的导航方法，比如获取小于指定key的集合。

最后分别实现 Serializable 接口以及 Cloneable 接口，分别表示支持对象序列化以及[对象克隆][Link 2]。

### 2、字段定义 ###

①、Comparator

/**
         * The comparator used to maintain order in this tree map, or
         * null if it uses the natural ordering of its keys.
         *
         * @serial
         */
        private final Comparator<? super K> comparator;

可以看上面的英文注释，Comparator 是用来维护treemap集合中的顺序，如果为null，则按照key的自然顺序。

Comparator 是一个接口，**排序时需要实现其 compare 方法，该方法返回正数，零，负数分别代表大于，等于，小于**。那么怎么使用呢？这里举个例子：

这里有一个Person类，里面有两个属性pname，page，我们将该person对象放入ArrayList集合时，需要对其按照年龄进行排序。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 package com.ys.test;
     2 
     3 /**
     4  * Create by YSOcean
     5  */
     6 public class Person {
     7     private String pname;
     8     private Integer page;
     9 
    10     public Person() {
    11     }
    12 
    13     public Person(String pname, Integer page) {
    14         this.pname = pname;
    15         this.page = page;
    16     }
    17 
    18     public String getPname() {
    19         return pname;
    20     }
    21 
    22     public void setPname(String pname) {
    23         this.pname = pname;
    24     }
    25 
    26     public Integer getPage() {
    27         return page;
    28     }
    29 
    30     public void setPage(Integer page) {
    31         this.page = page;
    32     }
    33 
    34     @Override
    35     public String toString() {
    36         return "Person{" +
    37                 "pname='" + pname + '\'' +
    38                 ", page=" + page +
    39                 '}';
    40     }
    41 }

排序代码：

1 List<Person> personList = new ArrayList<>();
     2 personList.add(new Person("李四",20));
     3 personList.add(new Person("张三",10));
     4 personList.add(new Person("王五",30));
     5 System.out.println("原始顺序为："+personList.toString());
     6 Collections.sort(personList, new Comparator<Person>() {
     7     @Override
     8     public int compare(Person o1, Person o2) {
     9         //升序
    10         //return o1.getPage()-o2.getPage();
    11         //降序
    12         return o2.getPage()-o1.getPage();
    13         //不变
    14         //return 0
    15     }
    16 });
    17 System.out.println("排序后顺序为："+personList.toString());

打印结果为：

![1120165-20190220214637269-349676356.png][]

②、Entry

private transient Entry<K,V> root;

对于Entry详细源码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1     static final class Entry<K,V> implements Map.Entry<K,V> {
     2         K key;
     3         V value;
     4         Entry<K,V> left;
     5         Entry<K,V> right;
     6         Entry<K,V> parent;
     7         boolean color = BLACK;
     8 
     9         /**
    10          * Make a new cell with given key, value, and parent, and with
    11          * {
            @code null} child links, and BLACK color.
    12          */
    13         Entry(K key, V value, Entry<K,V> parent) {
    14             this.key = key;
    15             this.value = value;
    16             this.parent = parent;
    17         }
    18 
    19         /**
    20          * Returns the key.
    21          *
    22          * @return the key
    23          */
    24         public K getKey() {
    25             return key;
    26         }
    27 
    28         /**
    29          * Returns the value associated with the key.
    30          *
    31          * @return the value associated with the key
    32          */
    33         public V getValue() {
    34             return value;
    35         }
    36 
    37         /**
    38          * Replaces the value currently associated with the key with the given
    39          * value.
    40          *
    41          * @return the value associated with the key before this method was
    42          *         called
    43          */
    44         public V setValue(V value) {
    45             V oldValue = this.value;
    46             this.value = value;
    47             return oldValue;
    48         }
    49 
    50         public boolean equals(Object o) {
    51             if (!(o instanceof Map.Entry))
    52                 return false;
    53             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    54 
    55             return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    56         }
    57 
    58         public int hashCode() {
    59             int keyHash = (key==null ? 0 : key.hashCode());
    60             int valueHash = (value==null ? 0 : value.hashCode());
    61             return keyHash ^ valueHash;
    62         }
    63 
    64         public String toString() {
    65             return key + "=" + value;
    66         }
    67     }

这里主要看 Entry 类的几个字段：

K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;

相信对[红黑树][Link 1]这种数据结构了解的人，一看这几个字段就明白了，这也印证了前面所说的TreeMap底层有红黑树这种数据结构。

③、size

/**
         * The number of entries in the tree
         */
        private transient int size = 0;

用来表示entry的个数，也就是key-value的个数。

④、modCount

/**
         * The number of structural modifications to the tree.
         */
        private transient int modCount = 0;

基本上前面讲的在ArrayList,LinkedList,HashMap等线程不安全的集合都有此字段，用来实现Fail-Fast 机制，如果在迭代这些集合的过程中，有其他线程修改了这些集合，就会抛出ConcurrentModificationException异常。

⑤、红黑树常量

private static final boolean RED   = false;
        private static final boolean BLACK = true;

### 3、构造函数 ###

①、无参构造函数

1     public TreeMap() {
    2         comparator = null;
    3     }

将比较器 comparator 置为 null，表示按照key的自然顺序进行排序。

②、带比较器的构造函数

1     public TreeMap(Comparator<? super K> comparator) {
    2         this.comparator = comparator;
    3     }

需要自己实现Comparator。

③、构造包含指定map集合的元素

1     public TreeMap(Map<? extends K, ? extends V> m) {
    2         comparator = null;
    3         putAll(m);
    4     }

使用该构造器创建的TreeMap,会默认插入m表示的集合元素，并且comparator表示按照自然顺序进行插入。

④、带 SortedMap的构造函数

1     public TreeMap(SortedMap<K, ? extends V> m) {
    2         comparator = m.comparator();
    3         try {
    4             buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    5         } catch (java.io.IOException cannotHappen) {
    6         } catch (ClassNotFoundException cannotHappen) {
    7         }
    8     }

和上面带Map的构造函数不一样，map是无序的，而SortedMap 是有序的，使用 buildFromSorted() 方法将SortedMap集合中的元素插入到TreeMap 中。

### 4、添加元素 ###

1     //添加元素
     2     public V put(K key, V value) {
     3         TreeMap.Entry<K,V> t = root;
     4         //如果根节点为空，即TreeMap中一个元素都没有，那么设置新添加的元素为根节点
     5         //并且设置集合大小size=1,以及modCount+1，这是用于快速失败
     6         if (t == null) {
     7             compare(key, key); // type (and possibly null) check
     8 
     9             root = new TreeMap.Entry<>(key, value, null);
    10             size = 1;
    11             modCount++;
    12             return null;
    13         }
    14         int cmp;
    15         TreeMap.Entry<K,V> parent;
    16         // split comparator and comparable paths
    17         Comparator<? super K> cpr = comparator;
    18         //如果比较器不为空，即初始化TreeMap构造函数时，有传递comparator类
    19         //那么插入新的元素时，按照comparator实现的类进行排序
    20         if (cpr != null) {
    21             //通过do-while循环不断遍历树，调用比较器对key值进行比较
    22             do {
    23                 parent = t;
    24                 cmp = cpr.compare(key, t.key);
    25                 if (cmp < 0)
    26                     t = t.left;
    27                 else if (cmp > 0)
    28                     t = t.right;
    29                 else
    30                     //遇到key相等，直接将新值覆盖到原值上
    31                     return t.setValue(value);
    32             } while (t != null);
    33         }
    34         //如果比较器为空，即初始化TreeMap构造函数时，没有传递comparator类
    35         //那么插入新的元素时，按照key的自然顺序
    36         else {
    37             //如果key==null，直接抛出异常
    38             //注意，上面构造TreeMap传入了Comparator，是可以允许key==null
    39             if (key == null)
    40                 throw new NullPointerException();
    41             @SuppressWarnings("unchecked")
    42             Comparable<? super K> k = (Comparable<? super K>) key;
    43             do {
    44                 parent = t;
    45                 cmp = k.compareTo(t.key);
    46                 if (cmp < 0)
    47                     t = t.left;
    48                 else if (cmp > 0)
    49                     t = t.right;
    50                 else
    51                     return t.setValue(value);
    52             } while (t != null);
    53         }
    54         //找到父亲节点，根据父亲节点创建一个新节点
    55         TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);
    56         if (cmp < 0)
    57             parent.left = e;
    58         else
    59             parent.right = e;
    60         //修正红黑树（包括节点的左旋和右旋，具体可以看我Java数据结构和算法中对红黑树的介绍）
    61         fixAfterInsertion(e);
    62         size++;
    63         modCount++;
    64         return null;
    65     }

添加元素，如果初始化TreeMap构造函数时，没有传递comparator类，是不允许插入key==null的键值对的，相反，如果实现了Comparator，则可以传递key=null的键值对。

另外，当插入一个新的元素后（除了根节点），会对TreeMap数据结构进行修正，也就是对红黑树进行修正，使其满足红黑树的几个特点，具体修正方法包括改变节点颜色，左旋，右旋等操作，这里我不做详细介绍了，具体可以参考我的这篇博客：[https://www.cnblogs.com/ysocean/p/8004211.html][Link 1]

### 5、删除元素 ###

①、根据key删除

1     public V remove(Object key) {
     2         //根据key找到该节点
     3         TreeMap.Entry<K,V> p = getEntry(key);
     4         if (p == null)
     5             return null;
     6         //获取该节点的value，并返回
     7         V oldValue = p.value;
     8         //调用deleteEntry()方法删除节点
     9         deleteEntry(p);
    10         return oldValue;
    11     }
    12 
    13     private void deleteEntry(TreeMap.Entry<K,V> p) {
    14         modCount++;
    15         size--;
    16 
    17         //如果删除节点的左右节点都不为空，即有两个孩子
    18         if (p.left != null && p.right != null) {
    19             //得到该节点的中序后继节点
    20             TreeMap.Entry<K,V> s = successor(p);
    21             p.key = s.key;
    22             p.value = s.value;
    23             p = s;
    24         } // p has 2 children
    25 
    26         // Start fixup at replacement node, if it exists.
    27         TreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    28         //待删除节点只有一个子节点，直接删除该节点，并用该节点的唯一子节点顶替该节点
    29         if (replacement != null) {
    30             // Link replacement to parent
    31             replacement.parent = p.parent;
    32             if (p.parent == null)
    33                 root = replacement;
    34             else if (p == p.parent.left)
    35                 p.parent.left  = replacement;
    36             else
    37                 p.parent.right = replacement;
    38 
    39             // Null out links so they are OK to use by fixAfterDeletion.
    40             p.left = p.right = p.parent = null;
    41 
    42             // Fix replacement
    43             if (p.color == BLACK)
    44                 fixAfterDeletion(replacement);
    45 
    46             //TreeMap中只有待删除节点P，也就是只有一个节点，直接返回nul即可
    47         } else if (p.parent == null) { // return if we are the only node.
    48             root = null;
    49         } else { //  No children. Use self as phantom replacement and unlink.
    50             //待删除节点没有子节点，即为叶子节点，直接删除即可
    51             if (p.color == BLACK)
    52                 fixAfterDeletion(p);
    53 
    54             if (p.parent != null) {
    55                 if (p == p.parent.left)
    56                     p.parent.left = null;
    57                 else if (p == p.parent.right)
    58                     p.parent.right = null;
    59                 p.parent = null;
    60             }
    61         }
    62     }

删除节点分为四种情况：

1、根据key没有找到该节点：也就是集合中不存在这一个节点，直接返回null即可。

2、根据key找到节点，又分为三种情况：

①、待删除节点没有子节点，即为叶子节点：直接删除该节点即可。

②、待删除节点只有一个子节点：那么首先找到待删除节点的子节点，然后删除该节点，用其唯一子节点顶替该节点。

③、待删除节点有两个子节点：首先找到该节点的中序后继节点，然后把这个后继节点的内容复制给待删除节点，然后删除该中序后继节点，删除过程又转换成前面①、②两种情况了，这里主要是找到中序后继节点，相当于待删除节点的一个替身。

### 6、查找元素 ###

①、根据key查找

1     public V get(Object key) {
     2         TreeMap.Entry<K,V> p = getEntry(key);
     3         return (p==null ? null : p.value);
     4     }
     5 
     6     final TreeMap.Entry<K,V> getEntry(Object key) {
     7         // Offload comparator-based version for sake of performance
     8         if (comparator != null)
     9             return getEntryUsingComparator(key);
    10         if (key == null)
    11             throw new NullPointerException();
    12         @SuppressWarnings("unchecked")
    13         Comparable<? super K> k = (Comparable<? super K>) key;
    14         TreeMap.Entry<K,V> p = root;
    15         while (p != null) {
    16             int cmp = k.compareTo(p.key);
    17             if (cmp < 0)
    18                 p = p.left;
    19             else if (cmp > 0)
    20                 p = p.right;
    21             else
    22                 return p;
    23         }
    24         return null;
    25     }

### 7、遍历元素 ###

通常有下面两种方法，第二种方法效率要快很多。

1 TreeMap<String,Integer> map = new TreeMap<>();
     2 map.put("A",1);
     3 map.put("B",2);
     4 map.put("C",3);
     5 
     6 //第一种方法
     7 //首先利用keySet()方法得到key的集合，然后利用map.get()方法根据key得到value
     8 Iterator<String> iterator = map.keySet().iterator();
     9 while(iterator.hasNext()){
    10     String key = iterator.next();
    11     System.out.println(key+":"+map.get(key));
    12 }
    13 
    14 //第二种方法
    15 Iterator<Map.Entry<String,Integer>> iterator1 = map.entrySet().iterator();
    16 while(iterator1.hasNext()){
    17     Map.Entry<String,Integer> entry = iterator1.next();
    18     System.out.println(entry.getKey()+":"+entry.getValue());
    19 }

posted @ 2019-05-14 22:42 [YSOcean][] 阅读( ...) 评论( ...) [编辑][Link 3] 收藏

[JDK1.8_java.util.TreeMap]: https://www.cnblogs.com/ysocean/p/10300976.html
[ArrayList]: https://www.cnblogs.com/ysocean/p/8622264.html
[LinkedList]: https://www.cnblogs.com/ysocean/p/8657850.html
[HashMap]: https://www.cnblogs.com/ysocean/p/8711071.html
[Link 1]: https://www.cnblogs.com/ysocean/p/8004211.html
[1120165-20190121213836953-1363088203.png]: /images/20220131/3bb4b2d9b452453fbd07855d3cf38b3c.png
[Link 2]: https://www.cnblogs.com/ysocean/p/8482979.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220131/89a2c94a1d20446ebb4b2314fec80723.png
[1120165-20190220214637269-349676356.png]: /images/20220131/9d8e5c8c1a164e65b046f09deaa93007.png
[YSOcean]: https://www.cnblogs.com/ysocean/
[Link 3]: https://i.cnblogs.com/EditPosts.aspx?postid=10300976