“我报名参加金石计划1期应战——分割10万奖池,这是我的第3篇文章,点击检查活动详情”

概述

TreeMap是Map宗族中的一员,也是用来存放key-value键值对的。平常在作业中运用的或许并不多,它最大的特点是遍历时是有次序的,依据key的排序规矩来,那么它具体是怎么运用,又是怎么完成的呢?本文依据jdk8做一个讲解。

TreeMap介绍

TreeMap是一个依据key有序的key value散列表。

  • map依据其键的天然次序排序,或许依据map创立时供给的Comparator排序
  • 不是线程安全的
  • key 不能够存入null
  • 底层是依据红黑树完成的

以上是TreeMap的类结构图:

  1. 完成了NavigableMap接口,NavigableMap又完成了Map接口,供给了导航相关的办法。
  2. 承继了AbstractMap,该办法完成Map操作的主干逻辑。
  3. 完成了Cloneable接口,符号该类支撑clone办法仿制
  4. 完成了Serializable接口,符号该类支撑序列化

结构办法

  • TreeMap()

阐明:运用键的天然排序结构一个新的空树映射。

  • TreeMap(Comparator<? super K> comparator)

阐明:结构一个新的空树映射,依据给定的比较器排序。

  • TreeMap(Map<? extends K,? extends V> m)

阐明:结构一个新的树映射,包括与给定映射相同的映射,依照键的天然次序排序。

  • TreeMap(SortedMap<K,? extends V> m)

阐明:结构一个新的树映射,包括相同的映射,并运用与指定排序映射相同的次序。

关键办法

这边首要讲解下NavigableMap和SortedMap供给的一些办法,Map相关的办法咱们应该都很熟悉了。

SortedMap接口:

  • Comparator<? super K> comparator()

回来用于排序此映射中的键的比较器,假如此映射运用其键的天然排序,则回来null。

  • Set<Map.Entry<K,V>> entrySet()

回来此映射中包括的映射的Set视图。

  • K firstKey()

回来当时映射中的第一个(最低)键。

  • K lastKey()

回来当时映射中的最终(最高)键。

NavigableMap接口:

  • Map.Entry<K,V> ceilingEntry(K key)

回来与大于或等于给定键的最小键相相关的键值映射,假如没有这样的键则回来null。

  • K ceilingKey(K key)

回来大于或等于给定键的最小键,假如没有这样的键,则回来null。

  • NavigableMap<K,V> descendingMap()

回来此映射中包括的映射的倒序视图。

  • Map.Entry<K,V> firstEntry()

回来与该映射中最小的键相关的键值映射,假如映射为空,则回来null。

  • Map.Entry<K,V> floorEntry(K key)

回来与小于或等于给定键的最大键相相关的键值映射,假如没有这样的键则回来null。

  • SortedMap<K,V> headMap(K toKey)

回来该映射中键严厉小于toKey的部分的视图。

  • Map.Entry<K,V> higherEntry(K key)

回来与严厉大于给定键的最小键相关的键值映射,假如没有这样的键,则回来null。

  • Map.Entry<K,V> lastEntry()

回来与此映射中最大键相关的键值映射,假如映射为空,则回来null。

  • Map.Entry<K,V> lowerEntry(K key)

回来与严厉小于给定键的最大键相关的键值映射,假如没有这样的键,则回来null。

  • Map.Entry<K,V> pollFirstEntry()

删去并回来与该映射中最小的键相关的键值映射,假如映射为空,则回来null。

  • Map.Entry<K,V> pollLastEntry()

删去并回来与此映射中最大键相关的键值映射,假如映射为空,则回来null。

  • SortedMap<K,V> subMap(K fromKey, K toKey)

回来该映射中键规模从fromKey(包括)到toKey(独占)的部分的视图。

  • SortedMap<K,V> tailMap(K fromKey)

回来该映射中键大于或等于fromKey的部分的视图。

运用事例

  • 验证次序性
@Test
    public void test1() {
        Map<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(16, "a");
        treeMap.put(1, "b");
        treeMap.put(4, "c");
        treeMap.put(3, "d");
        treeMap.put(8, "e");
        // 遍历
        System.out.println("默许排序:");
        treeMap.forEach((key, value) -> {
            System.out.println("key: " + key + ", value: " + value);
        });
        // 结构办法传入比较器
        Map<Integer, String> tree2Map = new TreeMap<>((o1, o2) -> o2 - o1);
        tree2Map.put(16, "a");
        tree2Map.put(1, "b");
        tree2Map.put(4, "c");
        tree2Map.put(3, "d");
        tree2Map.put(8, "e");
        // 遍历
        System.out.println("倒序排序:");
        tree2Map.forEach((key, value) -> {
            System.out.println("key: " + key + ", value: " + value);
        });
    }

运转成果:

  • 验证不能存储null
@Test
    public void test2() {
        Map<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(null, "a");
    }

运转成果:

  • 验证NavigableMap相关办法
@Test
    public void test3() {
        NavigableMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(16, "a");
        treeMap.put(1, "b");
        treeMap.put(4, "c");
        treeMap.put(3, "d");
        treeMap.put(8, "e");
        // 获取大于等于5的key
        Integer ceilingKey = treeMap.ceilingKey(5);
        System.out.println("ceilingKey 5 is " + ceilingKey);
        // 获取最大的key
        Integer lastKey = treeMap.lastKey();
        System.out.println("lastKey is " + lastKey);
    }

运转成果:

中心机制

完成原理

咱们有想过TreeMap的底层是怎么完成的吗,是怎么保护key的次序呢?答案便是依据红黑树完成的。

那什么是红黑树呢?咱们在这里简略的认识一下,了解一下红黑树的特点:红黑树是一颗自平衡的排序二叉树。咱们就先从二叉树开始说起。

  • 二叉树

二叉树很容易了解,便是一棵树分俩叉。

上面这颗便是一颗最普通的二叉树。但是你会发现看起来不那么美观,由于你以H为根节点,发现左右两头高低不平衡,高度相差达到了2。所以呈现了平衡二叉树,使得左右两头高低差不多。

  • 平衡二叉树

这下子应该能看到,不管是从任何一个字母为根节点,左右两头的深度差不了2,最多是1。这便是平衡二叉树。不过好景不长,有一天,忽然要把字母变成数字,还要坚持这种特性怎么办呢?所以又呈现了平衡二叉排序树。

  • 平衡二叉排序树

不管是从长相(平衡),仍是从规矩(排序)感觉这棵树超级完美。但是有一个问题,那便是在增加删去节点的时分,你要时间去让这棵树坚持平衡,需求做太多的作业了,旋转的次数超级多,所以乎呈现了红黑树。

  • 红黑树

这便是传说中的红黑树,和平衡二叉排序树的区别便是每个节点涂上了色彩,他有下列五条性质:

  1. 每个节点都只能是赤色或许黑色
  2. 根节点是黑色
  3. 每个叶节点(NIL节点,空节点)是黑色的。
  4. 假如一个结点是红的,则它两个子节点都是黑的。也便是说在一条途径上不能呈现相邻的两个赤色结点。
  5. 从任一节点到其每个叶子的所有途径都包括相同数目的黑色节点。

这些性质有什么优点呢?便是刺进效率超级高。由于在刺进一个元素的时分,最多只需三次旋转,O(1)的复杂度,但是有一点需求阐明他的查询效率略微差劲于平衡二叉树,由于他比平衡二叉树会略微不平衡最多一层,也便是说红黑树的查询功能只比相同内容的avl树最多多一次比较。怎么去旋转呢?如下图所示。

首先是左旋:

然后是右旋:

红黑树更详细的内容能够参考这篇文章:segmentfault.com/a/119000001…

源码解析

成员变量

//这是一个比较器,便利刺进查找元素等操作
private final Comparator<? super K> comparator;
//红黑树的根节点:每个节点是一个Entry
private transient Entry<K,V> root;
//调集元素数量
private transient int size = 0;
//调集修正的记载
private transient int modCount = 0;
  • comparator是一个排序器,作为key的排序规矩
  • root是红黑树的根节点,阐明确实底层用的红黑树作为数据结构。
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;
        }
    }

查找get办法

TreeMap依据红黑树完成,而红黑树是一种自平衡二叉查找树,所以 TreeMap 的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的,先将目标值和根节点的值进行比较,假如目标值小于根节点的值,则再和根节点的左孩子进行比较。假如目标值大于根节点的值,则持续和根节点的右孩子比较。在查找过程中,假如目标值和二叉树中的某个节点值持平,则回来 true,否则回来 false。TreeMap 查找和此类似,只不过在 TreeMap 中,节点(Entry)存储的是键值对<k,v>。在查找过程中,比较的是键的巨细,回来的是值,假如没找到,则回来null。TreeMap 中的查找办法是get。

public V get(Object key) {
        //调用 getEntry办法查找
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p. value);
}
final Entry<K,V> getEntry(Object key) {
    / 假如比较器为空,仅仅用key作为比较器查询
    if (comparator != null) 
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    Comparable<? super K> k = (Comparable<? super K>) key;
    // 获得root节点
    Entry<K,V> p = root;
   //中心来了:从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;
    }

刺进put办法

咱们来看下关键的刺进办法,在刺进时分是怎么保护key的。

public V put(K key, V value) {
        Entry<K,V> t = root;
       // 1.假如根节点为 null,将新节点设为根节点
        if (t == null) {
            compare(key, key); // type (and possibly null) check
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
      //假如root不为null,阐明已存在元素 
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
    //假如比较器不为null 则运用比较器
        if (cpr != null) {
            //找到元素的刺进方位
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                 //当时key小于节点key 向左子树查找
                if (cmp < 0)
                    t = t.left;
                    //当时key大于节点key 向右子树查找
                else if (cmp > 0)
                    t = t.right;
                else
                    //持平的状况下 直接更新节点值
                    return t.setValue(value);
            } while (t != null);
        }
            //假如比较器为null 则运用默许比较器
        else {
            //假如key为null  则抛出异常
            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;
    }

比较关键的便是fixAfterInsertion办法, 看懂这个办法需求你对红黑树的机制比较了解。

private void fixAfterInsertion(Entry<K,V> x) {
    // 将新刺进节点的色彩设置为赤色
    x. color = RED;
    // while循环,保证新刺进节点x不是根节点或许新刺进节点x的父节点不是赤色(这两种状况不需求调整)
    while (x != null && x != root && x. parent.color == RED) {
        // 假如新刺进节点x的父节点是祖父节点的左孩子
        if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {
            // 获得新刺进节点x的叔叔节点
            Entry<K,V> y = rightOf(parentOf (parentOf(x)));
            // 假如新刺进x的父节点是赤色
            if (colorOf(y) == RED) {
                // 将x的父节点设置为黑色
                setColor(parentOf (x), BLACK);
                // 将x的叔叔节点设置为黑色
                setColor(y, BLACK);
                // 将x的祖父节点设置为赤色
                setColor(parentOf (parentOf(x)), RED);
                // 将x指向祖父节点,假如x的祖父节点的父节点是赤色,依照上面的步奏持续循环
                x = parentOf(parentOf (x));
            } else {
                // 假如新刺进x的叔叔节点是黑色或短少,且x的父节点是祖父节点的右孩子
                if (x == rightOf( parentOf(x))) {
                    // 左旋父节点
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // 假如新刺进x的叔叔节点是黑色或短少,且x的父节点是祖父节点的左孩子
                // 将x的父节点设置为黑色
                setColor(parentOf (x), BLACK);
                // 将x的祖父节点设置为赤色
                setColor(parentOf (parentOf(x)), RED);
                // 右旋x的祖父节点
                rotateRight( parentOf(parentOf (x)));
            }
        } else { // 假如新刺进节点x的父节点是祖父节点的右孩子和上面的相似
            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;
}

删去remove办法

删去remove是最复杂的办法。

public V remove(Object key) {
        // 依据key查找到对应的节点对象
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;
        // 记载key对应的value,供回来运用
        V oldValue = p. value;
        // 删去节点
        deleteEntry(p);
        return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
        modCount++;
        //元素个数减一
        size--;
        // 假如被删去的节点p的左孩子和右孩子都不为空,则查找其代替节
        if (p.left != null && p. right != null) {
            // 查找p的代替节点
            Entry<K,V> s = successor (p);
            p. key = s.key ;
            p. value = s.value ;
            p = s;
        }
        Entry<K,V> replacement = (p. left != null ? p.left : p. right);
        if (replacement != null) { 
            // 将p的父节点复制给代替节点
            replacement. parent = p.parent ;
            // 假如代替节点p的父节点为空,也便是p为跟节点,则将replacement设置为根节点
            if (p.parent == null)
                root = replacement;
            // 假如代替节点p是其父节点的左孩子,则将replacement设置为其父节点的左孩子
            else if (p == p.parent. left)
                p. parent.left   = replacement;
            // 假如代替节点p是其父节点的左孩子,则将replacement设置为其父节点的右孩子
            else
                p. parent.right = replacement;
            // 将代替节点p的left、right、parent的指针都指向空
            p. left = p.right = p.parent = null;
            // 假如代替节点p的色彩是黑色,则需求调整红黑树以坚持其平衡
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            // 假如要代替节点p没有父节点,代表p为根节点,直接删去即可
            root = null;
        } else {
            // 假如p的色彩是黑色,则调整红黑树
            if (p.color == BLACK)
                fixAfterDeletion(p);
            // 下面删去代替节点p
            if (p.parent != null) {
                // 解除p的父节点对p的引证
                if (p == p.parent .left)
                    p. parent.left = null;
                else if (p == p.parent. right)
                    p. parent.right = null;
                // 解除p对p父节点的引证
                p. parent = null;
            }
        }
    }

最终仍是落到了对红黑树节点的删去上,需求维持红黑树的特性,做一系列的作业。

总结

本文首要 从基本的运用到源码讲解了Map宗族中一个比较冷门的容器TreeMap,期望对咱们有帮助。

参考

/post/684490…

segmentfault.com/a/119000001…