文档章节

java集合框架(四):TreeMap

chenzanjin
 chenzanjin
发布于 2017/11/07 19:30
字数 2758
阅读 56
收藏 5

        TreeMap的数据结构与HashMap、LinkedHashMap不同,其整个结构就是一颗红黑树,所以我们要研究TreeMap就得先从红黑树开始。对于红黑树的算法,我在本文章不详细展开,有兴趣的同学可以点击这里学习。本文主要是剖析红黑树的原理,以及解读TreeMap是如何运用红黑树实现的。

        红黑树是什么?我们可以从《数据结构与算法分析》这本书找到解析:红黑树是具有着色性质的二叉查找树,是AVL树(自平衡二叉查找树)的一个变种。接下来我从它的基本定义中来讲解红黑树。

一、二叉查找树

        二叉查找树,也可以叫做二叉排序树,他具有排序的功能。二叉树要成为二叉查找树需满足以下条件:

  1. 若左子树不空,则左子树上所有节点的值均小于父节点的值。
  2. 若右子树不空,则右子树上所有节点的值均大于父节点的值。
  3. 左、右子树也分别为二叉查找树。

        由以上条件可知,下图左边为二叉查找树,右边为普通二叉树。二叉查找树的平均深度为O(log2 n)。深度是指对于任何一个节点,根节点到其本身的唯一路径长。根节点的深度为0,如下图所示,节点值为2的深度是1,节点值为4的深度是2。

二、AVL树(自平衡二叉查找树

        二叉查找树的平均深度是为O(log2 n), 但是也会出现一些极端的情况,如果插入的节点集本身就是有序的,要么从大到小排序,要么从小到大排序,就会出现如下图的结果。在这种情况下,排序二叉树就变成了普通链表,其查找效率就会很差。

        为了解决这种极端情况,两位科学家 G.M. Adelson-Velsky 和 E.M. Landis就提出了自平衡的二叉查找树,AVL树也就来自于他们两个的名字组合。AVL树能保持自平衡的条件是二叉查找树每个节点的左子树和右子树的高度最多差1。其中高度是指一个节点到叶子节点的最长路径,因此任何一个叶子节点的高度为0.如下图所示,左图根节点的左子树的高度为2,右子树的高度为1,相差为1,所以是AVL树。右图根节点左子树的高度为2,右子树高度为0,相差为2,所以不是AVL树。

                        左图.AVL树                                        右图.非AVL树

        AVL树能够保证树的深度为O(log2 n),因此它能够提供较好的查找性能。它的缺点是为了保持平衡,添加或者删除节点时需要进行复杂的平衡操作,需要很大的性能开销。

三、红黑树

        红黑树是二叉查找树,它不追求“完全平衡”,只要求部分达到平衡,其在添加或者删除节点时不需要太多复杂的旋转操作就可以保持平衡,任何不平衡在三次旋转内解决。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。

        红黑树就是牺牲了高度平衡的性质换取了较高性能的插入和删除操作,为了保持其自身的部分平衡,着色需要满足下面条件:

  1. 每一个节点要么着成红色,要么着成黑色。
  2. 根是黑色的。
  3. 如果一个节点时红色的,那么它的子节点必须是黑色的。
  4. 从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。

        上图为红黑树的例图。当插入或者删除节点时,红黑树是通过变色和旋转来同时保证4个条件满足的,读者如果有兴趣研究他们的变换原理,可以点击此处在线构建红黑树。

四、类的定义

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

        TreeMap实现了NavigableMap(导航map,里面定义了一些接口,很少用到),而NavigableMap则继承了SortMap接口(要求实现类需要对key排序),故TreeMap间接实现了SortMap,也就会实现在SortMap中定义的对key排序的接口。类关系图如下所示:

五、构造器

public TreeMap() {
    // 比较器为空
    comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
     // 对比较器赋值,插入节点到红黑树中会用到这个比较器来比较key的大小,提前是key要实现这个比较器
     // 对key的排序规则可以通过这个比较器来指定(大到小或者小到大)
     this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    // 把外面传进来的key-value加入到红黑树
    putAll(m);
}
// 该构造器是把已经排序好的SortMap节点重新构造成红黑树,并把SortMap的比较器赋值给TreeMap
public TreeMap(SortedMap<K, ? extends V> m) {
        // 使用SortMap的比较器
        comparator = m.comparator();
        try {
            // 构造红黑树
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
}

六、存储的实现

1.put方法

        put方法就是把节点加到红黑树中,从源码中可以看到,key不能为空。为了插入红黑树时对key作比较,key要么实现Comparator接口,要么实现Comparable接口

public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            // 对key判空和类型检查
            compare(key, key);

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        Comparator<? super K> cpr = comparator;
        // 比较器不为空就使用Comparator来对key做比较
        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);
        }
        // 使用Comparable接口作比较
        else {
            // key不能为空,否则抛出异常
            if (key == null)
                throw new NullPointerException();
            // 这里做了强转型,如果key没有实现Comparable接口会抛异常
            @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++;
        // fast-fail机制
        modCount++;
        return null;
}

2.get操作

        get操作是比较容易理解的,它从根节点查找key,找到就返回value。它分开了两种比较器查找过程。

public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
        // 用Comparator比较器获取
        if (comparator != null)
            return getEntryUsingComparator(key);
        // 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;
}
// 用Comparator比较器查找
final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            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;
}

七、遍历的实现

        TreeMap的遍历操作是在内部抽象类PrivateEntryIterator中完成的,其调用外部类的successor方法对红黑树进行遍历,根据key值大小的顺序(大到小或者小到大,由比较器决定)遍历,其实就是从左往右遍历红黑树。在使用中,如果我们有根据key值大小的顺序遍历map的需求,可以使用TreeMap,但是key必须实现Comparator或者Comparable接口

abstract class PrivateEntryIterator<T> implements Iterator<T> {
        Entry<K,V> next;
        Entry<K,V> lastReturned;
        int expectedModCount;
        // 构造器参数first是红黑树最左边的节点,也就是key最小的节点
        PrivateEntryIterator(Entry<K,V> first) {
            expectedModCount = modCount;
            lastReturned = null;
            next = first;
        }

        public final boolean hasNext() {
            return next != null;
        }

        final Entry<K,V> nextEntry() {
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            // fast-fail机制
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 这个方法就是遍历红黑树的
            next = successor(e);
            lastReturned = e;
            return e;
        }
}
// 返回红黑树的下一个节点,t为当前遍历的节点。遍历的key是从小到大
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        if (t == null)
            return null;
        // 如果右边节点不为空继续遍历右边节点
        else if (t.right != null) {
            Entry<K,V> p = t.right;
            // 返回右边节点的最左边节点
            while (p.left != null)
                p = p.left;
            return p;
        } 
        // 右边节点为空
        else {
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            // 判断右边的节点是否已经遍历完了
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
}

八、排序的例子

1.升序排序:

    public static void main(String[] args) {

        InnerClass inner1 = new InnerClass(1);
        // 把比较器传到构造函数
        Map<InnerClass,String> map = new TreeMap<InnerClass, String>(inner1);

        InnerClass inner2 = new InnerClass(2);
        InnerClass inner3 = new InnerClass(3);
        InnerClass inner4 = new InnerClass(4);
        InnerClass inner5 = new InnerClass(5);

        map.put(inner1,"1");
        map.put(inner2,"2");
        map.put(inner3,"3");
        map.put(inner4,"4");
        map.put(inner5,"5");

        for(Map.Entry<InnerClass,String> entry:map.entrySet()){
            System.out.print(entry.getValue() + ",");
        }

    }

    // 内部类实现比较器
    static class InnerClass implements Comparator{
        int num = 0;
        public InnerClass(int num) {
            this.num = num;
        }

        public int getNum() {
            return num;
        }

        public void setNum(int num) {
            this.num = num;
        }

        @Override
        public int compare(Object o1, Object o2) {
            InnerClass inner1 = (InnerClass)o1;
            InnerClass inner2 = (InnerClass)o2;
            // 对key升序排
            if(inner1.getNum() > inner2.getNum()){
                return 1;
            }else if (inner1.getNum() < inner2.getNum()){
                return -1;
            }else {
                return 0;
            }
        }
    }

升序排序结果:1,2,3,4,5,

2.降序排序

    // 内部类实现比较器
    static class InnerClass implements Comparator{
        int num = 0;
        public InnerClass(int num) {
            this.num = num;
        }

        public int getNum() {
            return num;
        }

        public void setNum(int num) {
            this.num = num;
        }

        @Override
        public int compare(Object o1, Object o2) {
            InnerClass inner1 = (InnerClass)o1;
            InnerClass inner2 = (InnerClass)o2;
            // 对key降序排
            if(inner1.getNum() < inner2.getNum()){
                return 1;
            }else if (inner1.getNum() > inner2.getNum()){
                return -1;
            }else {
                return 0;
            }
        }
    }

降序排序结果:5,4,3,2,1,

九、总结

  1. TreeMap里面还有很多方法在本文中没有提及,我觉得只要把TreeMap的结构和原理理解清楚了,以后使用中如果有操作TreeMap方面的需要可以到jdk的api或者到源码中找。
  2. TreeMap的数据结构就是红黑树,红黑树的高度最多是2log2(n+1),它牺牲了avl树的高度平衡特性,换取了高效的插入、删除、搜索性能(时间复杂度都是O(log2n)),构建红黑树的时候任何不满足红黑树条件最多3次旋转变色会解决。
  3. TreeMap相对于HashMap而言,插入节点的时候不用考虑扩容,消除了扩容的性能开销。
  4. TreeMap可以根据key值的大小顺序遍历节点,在对key-value遍历有做顺序要求的场合可以考虑使用TreeMap。
  5. TreeMap的key值不能为空,且key必须实现Comparator接口或者Comparable接口,否则使用的时候会抛出异常。

以上就是我对红黑树的理解,如有不足之处,请批评和指正!

参考资料:

        博客园:http://www.cnblogs.com/wzyxidian/p/5204879.html

© 著作权归作者所有

chenzanjin
粉丝 17
博文 13
码字总数 18417
作品 0
广州
程序员
私信 提问
加载中

评论(1)

一个成为架构师的男人
嗯,写的很好,感谢博主
Java核心(四)你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧! Java中的集合通常指的是Collection下的三个集合框架List、Set、Q...

王磊的博客
2018/11/28
102
0
java集合入门和深入学习,看这篇就差不多了

集合框架: Java中的集合框架大类可分为Collection和Map;两者的区别: Collection是单列集合;Map是双列集合 Collection中只有Set系列要求元素唯一;Map中键需要唯一,值可以重复 Collecti...

sihailoveyan
2018/05/04
184
2
再谈Java数据结构—分析底层实现与应用注意事项

在回顾js数据结构,写《再谈js对象数据结构底层实现原理-object array map set》系列的时候,在来整理下java的数据结构。 java把内存分两种:一种是栈内存,另一种是堆内存 基本类型在栈区分...

zhoulujun
05/17
50
0
Java 容器 & 泛型:五、HashMap 和 TreeMap的自白

Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket Java 容器的文章这次应该是最后一篇了:Java 容器 系列。 今天泥瓦匠聊下 Maps。 一、Map回顾 Map,又称映射表,是将键映...

泥沙砖瓦浆木匠
2015/05/05
1K
0
泥沙砖瓦浆木匠/java-core-learning-example

感谢赞助的ta们 Java 核心系列教程,关于Java核心技术学习积累的例子,是初学者及核心技术巩固的最佳实践。 包括基础语法,OOP,字符串,集合,IO,反射,线程,网络等。 未完成模块:阿里J...

泥沙砖瓦浆木匠
04/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

最简单的获取相机拍照的图片

  import android.content.Intent;import android.graphics.Bitmap;import android.os.Bundle;import android.os.Environment;import android.provider.MediaStore;import andr......

MrLins
今天
6
0
说好不哭!数据可视化深度干货,前端开发下一个涨薪点在这里~

随着互联网在各行各业的影响不断深入,数据规模越来越大,各企业也越来越重视数据的价值。作为一家专业的数据智能公司,个推从消息推送服务起家,经过多年的持续耕耘,积累沉淀了海量数据,在...

个推
今天
9
0
第三方支付-返回与回调注意事项

不管是支付宝,微信,还是其它第三方支付,第四方支付,支付机构服务商只要涉及到钱的交易都要进行如下校验,全部成功了才视为成功订单 1.http请求是否成功 2.校验商户号 3.校验订单号及状态...

Shingfi
今天
5
0
简述Java内存分配和回收策略以及Minor GC 和 Major GC(Full GC)

内存分配: 1. 栈区:栈可分为Java虚拟机和本地方法栈 2. 堆区:堆被所有线程共享,在虚拟机启动时创建,是唯一的目的是存放对象实例,是gc的主要区域。通常可分为两个区块年轻代和年老代。更...

DustinChan
今天
7
0
Excel插入批注:可在批注插入文字、形状、图片

1.批注一直显示:审阅选项卡-------->勾选显示批注选项: 2.插入批注快捷键:Shift+F2 组合键 3.在批注中插入图片:鼠标右键点击批注框的小圆点【重点不可以在批注文本框内点击】----->调出批...

东方墨天
今天
7
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部