Java中的Map【十一】TreeMap 类

╰+攻爆jí腚メ 2021-09-21 09:24 311阅读 0赞

**      所使用的jdk版本为1.8.0\_172版本**，先看一下 TreeMap<K,V> 在JDK中Map的UML类图中的主要继承实现关系：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMDc2MzQ1_size_16_color_FFFFFF_t_70][]

# 概述 #

TreeMap<K,V> 是基于红黑树的实现Navigable接口的Map。TreeMap 根据key的自然顺序（参见 java.lang.Comparable 接口）或者根据创建TreeMap时指定的比较器（java.util.Comparator）进行排序存放键值映射，具体取决于使用的构造方法。

TreeMap 中 containsKey、get、put、remove 的时间复杂度是 log(n) 的。需要注意的是，TreeMap 的实现是不同步的。

# 数据结构 #

public class TreeMap<K,V>
        extends AbstractMap<K,V>
        implements NavigableMap<K,V>, Cloneable, java.io.Serializable
    {
        /**
         * The comparator used to maintain order in this tree map, or
         * null if it uses the natural ordering of its keys.
         *
         * @serial
         */
        /**
         * 用于维护 TreeMap 中的顺序的比较器，如果使用其键的自然顺序，则 comparator 为null。
         */
        private final Comparator<? super K> comparator;
    
        /**
         * 红黑树的根节点
         */
        private transient Entry<K,V> root;
    
        /**
         * The number of entries in the tree
         */
        /**
         * 红黑树中映射的数量
         */
        private transient int size = 0;
    
        /**
         * The number of structural modifications to the tree.
         */
        /**
         * 树的结构修改次数
         */
        private transient int modCount = 0;

红黑树的节点类型 Entry<K,V> ：

private static final boolean RED   = false;
        private static final boolean BLACK = true;
    
        /**
         * Node in the Tree.  Doubles as a means to pass key-value pairs back to
         * user (see Map.Entry).
         */
    
        static final class Entry<K,V> implements Map.Entry<K,V> {
            K key;
            V value;
            Entry<K,V> left;
            Entry<K,V> right;
            Entry<K,V> parent;
            boolean color = BLACK;

#   构造方法 #

TreeMap 提供了四种构造方法：

/**
         * 使用键的自然顺序构造一个新的、空的TreeMap。
         * 注意比较器为 null
         */
        public TreeMap() {
            comparator = null;
        }
    
        /**
         * 构造一个新的、空的树映射，该映射根据给定比较器进行排序。
         */
        public TreeMap(Comparator<? super K> comparator) {
            this.comparator = comparator;
        }
    
        /**
         * 构造一个与给定映射具有相同映射关系的新的树映射，该映射根据其键的自然顺序 进行排序。
         */
        public TreeMap(Map<? extends K, ? extends V> m) {
            comparator = null;
            putAll(m);
        }
    
        /**
         * 构造一个与指定有序映射具有相同映射关系和相同排序顺序的新的树映射。
         */
        public TreeMap(SortedMap<K, ? extends V> m) {
            comparator = m.comparator();
            try {
                buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
        }

# 实现原理 #

## V put(K key, V value) ##

// 异常：
        // 抛出 NullPointerException ： 如果指定键为 null 并且此映射使用自然顺序，或者其比较器不允许使用 null 键
        // 抛出 ClassCastException ： 如果指定键不能与映射中的当前键进行比较
        public V put(K key, V value) {
            Entry<K,V> t = root;
            // 初始化红黑树根结点
            if (t == null) {
                // 输入 key（可能为空）检查
                compare(key, key); // type (and possibly null) check
    
                root = new Entry<>(key, value, null);
                size = 1;
                modCount++;
                return null;
            }
            int cmp;
            Entry<K,V> parent;
            // split comparator and comparable paths
            // 如果比较器 comparator 不为 null,则使用比较器比较新放入的key
            // 反之，比较器 comparator 为 null,使用自然排序Comparable接口
            /**插入处理【先插入，后调整】
             * 1、先不考虑红黑树的规则，查找到新的key在树中的位置插入；
             * 2、然后再调整树使其满足红黑树规则
             * */
            Comparator<? super K> cpr = comparator;
            if (cpr != null) {
                do {
                    parent = t;
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            else {
                if (key == null)
                    throw new NullPointerException();
                @SuppressWarnings("unchecked")
                    Comparable<? super K> k = (Comparable<? super K>) key;
                do {
                    parent = t;
                    cmp = k.compareTo(t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            Entry<K,V> e = new Entry<>(key, value, parent);
            if (cmp < 0)
                parent.left = e;
            else
                parent.right = e;
            //插入节点后，红黑树的自平衡调整：左旋、右旋、变色等
            fixAfterInsertion(e);
            size++;
            modCount++;
            return null;
        }

通过分析，需要清楚放在 TreeMap 中的 key，必须有自然排序（实现Comparable接口）或者在构造方法中指定比较器Comparator，否则会抛出异常。如果要在 TreeMap 中支持存储 key 为 null 的键值对，则需要我们自己实现比较器Comparator，Comparable 接口不能支持 key 为 null 的情况。示例如下：

public class TreeMapTest {
    
        public static void main(String[] args) {
            /** 默认构造方法，没有指定比较器Comparator，使用自然排序Comparable，会报NullPointerException*/
            /*Map<Student, Grade> map = new TreeMap<>();
            map.put(null, new Grade());
            map.put(new Student("snow_white"), new Grade(99, "English"));
            map.put(new Student("pear_snow"), new Grade(100, "English"));
    
            System.out.println(map);*/
    
            Map<Student, Grade> map1 = new TreeMap<>(new StudentComparator());
            map1.put(null, new Grade());
            map1.put(new Student("pear_snow"), new Grade(100, "English"));
            map1.put(new Student("snow_white"), new Grade(99, "English"));
            System.out.println(map1);
        }
    
        public static class Student implements Comparable<Student>{
            private String name;
    
            public Student(String name) {
                this.name = name;
            }
    
            public String getName() {
                return name;
            }
    
            @Override
            public int compareTo(Student s) {
                return name.compareTo(s.name);
            }
    
            @Override
            public String toString(){
                return "{student=" + name + "}";
            }
        }
    
        public static class Grade {
            private Integer point;
            private String subject;
    
            public Grade(){}
    
            public Grade(Integer point, String subject) {
                this.point = point;
                this.subject = subject;
            }
    
            @Override
            public String toString(){
                return "{point=" + point + "," + "subject=" + subject +"}";
            }
        }
    
        /**
         * 自定义比较器，处理 key = null 的情况
         */
        public static class StudentComparator implements Comparator<Student> {
    
            @Override
            public int compare(Student o1, Student o2) {
                if (o1 == null || o2 == null) {
                    return -1;
                }
                return o1.getName().compareTo(o2.getName());
            }
        }
    
    
    
    }

输出结果：

{
       {student=pear_snow}={point=100,subject=English}, {student=snow_white}={point=99,subject=English}, null={point=null,subject=null}}

插入节点后树的自平衡调节：**fixAfterInsertion** 方法，是 Cormen、Leiserson 和 Rivest 的 《*Introduction to Algorithms》（算法导论）* 中的算法的改编实现，感兴趣的可以看下。

## V get(Object key) ##

get 方法很简单，就是红黑树的查找过程：

/**
         * 注：返回null，可能是 treeMap 不包含该 key 的映射关系；也可能此映射将该 key 显式地映射为 null。
         */
        public V get(Object key) {
            Entry<K,V> p = getEntry(key);
            return (p==null ? null : p.value);
        }
    
     final Entry<K,V> getEntry(Object key) {
            // Offload comparator-based version for sake of performance
            if (comparator != null)
                return getEntryUsingComparator(key);
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = k.compareTo(p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
            return null;
        }

# 简单总结： #

TreeMap 就是借助红黑树实现的，因此在插入节点、删除节点等出现改变树的结构状况时，就要随之进行红黑树的平衡操作。本质上，查找和变更就是查找和变更一个红黑树。

TreeMap 实现了 NavigableMap<K,V> 接口，所以可以查找得到映射的部分子集，如 subMap、headMap、floorEntry等方法。

注意事项：

1、如果使用 TreeMap 默认的构造方法，则键 key 必须实现 Comparable 接口，且无法支持 key 为 null 的情况。

2、采用指定比较器 Comparator 的构造方法，键 key 不需要实现 Comparable 接口，且可以支持 key 为 null 的情况。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMDc2MzQ1_size_16_color_FFFFFF_t_70]: /images/20210920/408e0f63b8fc4ea7a27e934c92512678.png