【Java入门提高篇】Day30 Java容器类详解(十二)TreeMap详解

  今天来看看Map家族的另一名大将——TreeMap。前面已经介绍过Map家族的两名大将,分别是HashMap,LinkedHashMap。HashMap可以高效查找和存储元素,LinkedHashMap可以在高效查找的基础上对元素进行有序遍历,那么TreeMap又有什么特点呢?别急别急,看完这篇你就知道了。

  本篇主要从以下几个方面对TreeMap进行介绍:

  1、TreeMap的特性以及使用栗子

  2、TreeMap继承结构简介

  3、TreeMap源码分析

  本篇预计食用10分钟,请各位食客合理分配时间。

一、TreeMap的特性以及使用栗子

1. 键值不允许重复 2. 默认会对键进行排序,所以键必须实现Comparable接口或者使用外部比较器 3. 查找、移除、添加操作的时间复杂度为log(n) 4. 底层使用的数据结构是红黑树

  没错,又是让你欲仙欲死的红黑树,不过不要慌,跟之前介绍HashMap时的红黑树是一毛一样的,所以这一篇里,不打算再做介绍啦,如果对红黑树的内容有些遗忘了,可以动动小手,往前面翻一翻。

  先来看一个TreeMap的使用小栗子。

public class TreeMapTest {

    public static void main(String[] args){
        TreeMap<String, Integer> grades = new TreeMap<>();
        grades.put("Frank", 100);
        grades.put("Alice", 95);
        grades.put("Mary", 90);
        grades.put("Bob", 85);
        grades.put("Jack", 90);
        System.out.println(grades);
        System.out.println(grades.subMap("Bob", "Jack"));
        System.out.println(grades.subMap("Bob", true, "Jack", true));
        System.out.println(grades.ceilingEntry("Bob"));
        System.out.println(grades.ceilingKey("Bob"));
        System.out.println(grades.higherEntry("Bob"));
        System.out.println(grades.higherKey("Bob"));
        System.out.println(grades.headMap("Bob"));
        System.out.println(grades.headMap("Bob", true));
        System.out.println(grades.tailMap("Bob"));
        System.out.println(grades.tailMap("Bob", true));
        System.out.println(grades.containsKey("Bob"));
        System.out.println(grades.containsValue(90));
        System.out.println(grades.descendingMap());
        System.out.println(grades.descendingKeySet());
    }
}

  输出如下:

{Alice=95, Bob=85, Frank=100, Jack=90, Mary=90}
{Bob=85, Frank=100}
{Bob=85, Frank=100, Jack=90}
Bob=85
Bob
Frank=100
Frank
{Alice=95}
{Alice=95, Bob=85}
{Bob=85, Frank=100, Jack=90, Mary=90}
{Bob=85, Frank=100, Jack=90, Mary=90}
true
true
{Mary=90, Jack=90, Frank=100, Bob=85, Alice=95}
[Mary, Jack, Frank, Bob, Alice]

  可以看到,放入TreeMap中的元素默认按键值升序排列,这里的键值类型为String,使用String的CompareTo方法进行比较和排序。subMap返回当前Map的子Map,headMap和tailMap也是如此,

二、TreeMap继承结构简介    

   TreeMap继承自AbstractMap,实现了NavigableMap接口,继承关系图如下:

  对于AbstractMap相信大家已经不陌生了,HashMap也是继承自AbstractMap,里面有对Map接口的一些默认实现。这里我们可以看到两个新的接口——SortedMap和NavigableMap。SortedMap接口继承自Map接口,从名字就能看出。SortedMap相比Map接口,憎加了排序的功能,内部的方法也不多,简单了解一下就好了

  NavigableMap接口继承自SortedMap接口,主要提供一下导航方法:

  说了这么多没啥营养的,接下来还是讲讲真正的干货吧。

三、TreeMap源码分析

  JDK 1.8中的TreeMap源码有两千多行,还是比较多的。所以本文并不打算逐句分析所有的源码,而是挑选几个常用的内部类和方法进行分析。这些方法实现的功能分别是查找、遍历、插入、删除等,其他的方法小伙伴们有兴趣可以自己分析。TreeMap实现的核心部分是关于红黑树的实现,其绝大部分的方法基本都是对底层红黑树增、删、查操作的一个封装。就像前面所说,只要弄懂了红黑树原理,TreeMap 就没什么秘密了。关于红黑树的原理,可以参考前面关于HashMap红黑树的文章,本篇文章不会对此展开讨论。

  TreeMap的主要数据结构是红黑树,而这红黑树结构的承载者便是内部类Entry,先来看看这个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;

        /**
         * 构造函数*/
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;

            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
        }

        public int hashCode() {
            int keyHash = (key==null ? 0 : key.hashCode());
            int valueHash = (value==null ? 0 : value.hashCode());
            return keyHash ^ valueHash;
        }

        public String toString() {
            return key + "=" + value;
        }
    }

  其实内部的结构也很简单,主要有key,value和三个分别指向左孩子,右孩子,父节点的引用,以及用来标识颜色的color成员变量。再来看看TreeMap中的几个重要的成员变量:

    /**
     * 外部比较器
     */
    private final Comparator<? super K> comparator;

    private transient Entry<K,V> root;

    /**
     * 键值对数量
     */
    private transient int size = 0;

    private transient int modCount = 0;

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

    /**
     * 键值对集合
     */
    private transient EntrySet entrySet;
    /**
     * 键的集合
     */
    private transient KeySet<K> navigableKeySet;
    /**
     * 倒序Map
     */
    private transient NavigableMap<K,V> descendingMap;

  comparator用于对map中的键进行排序,root指向红黑树的根节点,size表示键值对的数量,modCount相信已经不陌生了,表示内部结构被修改的次数,RED和BLACK是两个内部常量,即红黑两种颜色,false表示红,true表示黑。entrySet是键值对的集合,navigableKeySet是键的集合,最后一个descendingMap是当前map的一个倒序map。

  在TreeMap中有很多内部类,可以先看图了解一下:

  前前后后一共18个内部类,不过不要慌,其实里面跟迭代器相关的类就占了一半多(10个),跟子Map相关的类占4个,剩下4个就是跟内部集合相关的了。接下来还是一起来看看那些最常用的方法吧:

    // 插入元素
    public V put(K key, V value) {
        TreeMap.Entry<K,V> t = root;
        if (t == null) {
            // 检查类型以及key是否为null
            // 如果外部比较器为null,且key也为null则会抛出空指针异常
            // 如果TreeMap未设置外部比较器,且传入的对象未实现Comparable接口
            // 则会抛出ClassCastException异常
            compare(key, key); // type (and possibly null) check

            // 如果根节点不存在,则用传入的键值对信息生成一个根节点
            root = new TreeMap.Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        TreeMap.Entry<K,V> parent;
        // split comparator and comparable paths
        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
                    // 找到相等的key则替换其value
                    return t.setValue(value);
                // 一直循环,直到待比较的节点为null
            } while (t != null);
        }
        else {
            // 如果外部比较器为null
            // 如果key为null则抛出空指针
            if (key == null)
                throw new NullPointerException();
            // 如果key未实现comparable接口则会抛出异常
            @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                // 跟上面逻辑类似,只是用key的compareTo方法进行比较,而不是用外部比较器的compare方法
                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);
        }
        // 生成键值对
        TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);
        // 连接到当前map的左孩子位置或者右孩子位置
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        // 插入后的调整
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

  其实这里的逻辑跟HashMap中TreeNode的插入逻辑十分类似,也是先找到要插入的位置,然后再进行结构调整。这里的结构调整即红黑树的结构调整,在前面HashMap中已经详细介绍过了,这里就不重复介绍了,调整过程是完全一样的。

    /**
     * 插入后的调整
     */
    private void fixAfterInsertion(TreeMap.Entry<K,V> x) {
        // 将插入的节点初始化为红色节点
        x.color = RED;

        // 如果x不为null且x不是根节点,且x的父节点是红色,此时祖父节点一定为黑色
        while (x != null && x != root && x.parent.color == RED) {
            // 如果x的父节点为祖父节点的左孩子
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                // y指向x的叔叔节点
                TreeMap.Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                // 如果叔叔节点也是红色,则进行变色处理
                if (colorOf(y) == RED) {
                    // 父节点变成黑色
                    setColor(parentOf(x), BLACK);
                    // 叔叔节点变成黑色
                    setColor(y, BLACK);
                    // 祖父节点变成黑色
                    setColor(parentOf(parentOf(x)), RED);
                    // 将x指向祖父节点,继续往上调整
                    x = parentOf(parentOf(x));
                } else {
                    // 如果叔叔节点是黑色节点
                    // 如果x是父节点的右孩子
                    if (x == rightOf(parentOf(x))) {
                        // 将x指向其父节点
                        x = parentOf(x);
                        // 左旋
                        rotateLeft(x);
                    }
                    // 将x的父节点置为黑色
                    setColor(parentOf(x), BLACK);
                    // 将x的祖父节点置为红色
                    setColor(parentOf(parentOf(x)), RED);
                    // 将祖父节点右旋
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                // 这里类似操作
                TreeMap.Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

  说完了插入,再来看看删除操作。

    // 删除节点
    public V remove(Object key) {
        // 先找到该key对应的键值对
        TreeMap.Entry<K,V> p = getEntry(key);
        if (p == null)
            // 如果未找到则返回null
            return null;

        V oldValue = p.value;
        // 找到后删除该键值对
        deleteEntry(p);
        return oldValue;
    }
    final TreeMap.Entry<K,V> getEntry(Object key) {
        // 为了性能,卸载了比较器的版本
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        TreeMap.Entry<K,V> p = root;
        // 使用compareTo方法进行查找
        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;
    }

    // 使用比较器的getEntry版本。 从getEntry分离以获得性能。
    // (对于大多数方法而言,这不值得做,这些方法较少依赖于比较器性能,但在这里是值得的。)
    final TreeMap.Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
        K k = (K) key;
        Comparator<? super K> cpr = comparator;
        // 使用比较器进行二分查找
        if (cpr != null) {
            TreeMap.Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

    /**
     * 删除节点,并调整红黑树以保持它的平衡
     */
    private void deleteEntry(TreeMap.Entry<K,V> p) {
        modCount++;
        size--;

        // 如果p的左右孩子均不为空,则找到p的后继节点,并且将p指向该后继节点
        if (p.left != null && p.right != null) {
            TreeMap.Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // 修复替补节点
        // 用替补节点替换待删除的节点后,需要对其原来所在位置结构进行修复
        TreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            p.left = p.right = p.parent = null;

            // 如果p的颜色是黑色,则进行删除后的修复
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) {
            root = null;
        } else {
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

    /**
     * 返回指定节点的后继节点
     */
    static <K,V> TreeMap.Entry<K,V> successor(TreeMap.Entry<K,V> t) {
        if (t == null)
            return null;
        else if (t.right != null) {
            TreeMap.Entry<K,V> p = t.right;
            // 如果右子树不为空,则找到右子树的最左节点作为后继节点
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            TreeMap.Entry<K,V> p = t.parent;
            TreeMap.Entry<K,V> ch = t;
            // 如果右子树为空且当前节点为其父节点的左孩子,则直接返回
            // 如果为其父节点的右孩子,则一直往上找,直到找到根节点或者当前节点为其父节点的左孩子时,用其做为后继节点
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

    /**
     * 进行删除后的结构修复
     * @param x
     */
    private void fixAfterDeletion(TreeMap.Entry<K,V> x) {
        while (x != root && colorOf(x) == BLACK) {
            // 如果x是父节点的左孩子
            if (x == leftOf(parentOf(x))) {
                // sib指向x的兄弟节点
                TreeMap.Entry<K,V> sib = rightOf(parentOf(x));

                // 如果sib是红色,则进行变色处理
                if (colorOf(sib) == RED) {
                    // 兄弟节点改为黑色
                    setColor(sib, BLACK);
                    // 父节点改为红色
                    setColor(parentOf(x), RED);
                    // 父节点左旋
                    rotateLeft(parentOf(x));
                    // sib指向x的父节点的右孩子
                    sib = rightOf(parentOf(x));
                }

                // 如果sib的左孩子和右孩子都是黑色,则进行变色处理
                if (colorOf(leftOf(sib))  == BLACK &&
                        colorOf(rightOf(sib)) == BLACK) {
                    // 将sib置为红色
                    setColor(sib, RED);
                    // x指向其父节点
                    x = parentOf(x);
                } else {
                    // 如果sib的右孩子是黑色而左孩子是红色,则变色右旋
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    // 变色左旋
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } else { // symmetric
                // 跟上面操作类似
                TreeMap.Entry<K,V> sib = leftOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }

                if (colorOf(rightOf(sib)) == BLACK &&
                        colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }

        setColor(x, BLACK);
    }

  嗯,对比一下HashMap的删除操作,核心步骤是完全一样的,所以可以对照前面的HashMap红黑树详解进行食用。

  到此,这一篇就很水的讲完啦= =

  最近这段时间烦心事比较多,对发展方向也考虑了很多,想做的事情很多,反而让我止步不前,不过很多事情是急不来的,还是好好写写博客,多做总结分享吧。

  机会只留给有准备的人。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

树堆(Treap)图文详解与实现

树堆(Treap)是二叉排序树(Binary Sort Tree)与堆(Heap)结合产生的一种拥有堆性质的二叉排序树。

2421
来自专栏Java爬坑系列

【Java入门提高篇】Day30 Java容器类详解(十二)TreeMap详解

  今天来看看Map家族的另一名大将——TreeMap。前面已经介绍过Map家族的两名大将,分别是HashMap,LinkedHashMap。HashMap可以...

785
来自专栏数据结构与算法

约瑟夫环 队列+链表

设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编...

3867
来自专栏机器学习入门

LWC 62:742. Closest Leaf in a Binary Tree

LWC 62:742. Closest Leaf in a Binary Tree 传送门:742. Closest Leaf in a Binary Tree...

30610
来自专栏Pythonista

Golang之Struct(二叉树定义)

992
来自专栏拭心的安卓进阶之路

重温数据结构:二叉树的常见方法及三种遍历方式 Java 实现

树的分类有很多种,但基本都是 二叉树 的衍生,今天来学习下二叉树。 ? 什么是二叉树 Binary Tree 先来个定义: 二叉树是有限个节点的集合,这个集合...

3056
来自专栏Java爬坑系列

【Java入门提高篇】Day30 Java容器类详解(十二)TreeMap详解

  今天来看看Map家族的另一名大将——TreeMap。前面已经介绍过Map家族的两名大将,分别是HashMap,LinkedHashMap。HashMap可以...

764
来自专栏尾尾部落

[剑指offer] 二叉树的镜像

通过对以上两棵树的观察,我们可以总结出这两棵树的根节点相同,但它们的左、右两个子节点交换了位置。所以我们可以得出求一棵树的镜像的过程:先前序遍历这棵树的每个节点...

1472
来自专栏算法channel

二叉树非递归版的后序遍历算法

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

41810
来自专栏小樱的经验随笔

51 Nod 1008 N的阶乘 mod P【Java大数乱搞】

1008 N的阶乘 mod P 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 输入N和P(P为质数),求N! Mod P ...

2776

扫码关注云+社区

领取腾讯云代金券