课程咨询 :186 8716 1620      qq:2066486918

昆明Java培训 > 达内新闻 > java培训:容器--TreeMap
  • java培训:容器--TreeMap

    发布:昆明Java培训      来源:达内新闻      时间:2016-09-27

  • 昆明Java培训班的老师给大家讲:容器--TreeMap

    一、概述

    在Map的实现中,除了我们最常见的KEY值无序的HashMap之外,还有KEY有序的Map,比较常用的有两类,一类是按KEY值的大小有序的Map,这方面的代表是TreeMap,另外一种就保持了插入顺序的Map,这类的代表是LinkedHashMap.本文介绍TreeMap.

    Java提供了两种可以用来排序的接口,分别是Comparable和Comparactor,两者分别说明如下:

    1. Comparable

    目前这是一个泛型接口,只有一个方法compareTo, 参与比较的类需要实现这个接口,这样该类便具备了可比较性,该方法的参数表示用来比较的对象。根据这个接口的返回值是> 0,小于0还是等于0决定了两个比较对象之间的大 关系。

    如果一个类实现了这个接口,则该类的所有对象都是可比较的,也就是说,自身具备了比较的能力。JDK中的自带的一些类,比如Integer, Long等都具备比较的能力,原因就是它们实现了这个接口。

    这种方式适合那些比较功能是类的特点之一的类,比如昆明Java培训班的老师前面说到的Integer.

    2. Comparator

    除了Comparable,JDK还提供了一个接口用来比较,这就是Comparator,其接口定义如下:

    定义了两个方法,其中equals方法可以理解为是Object.equals的增加版本,功能和equal类似,用于比较的方法是compare,其接收两个参数,这两个参数不需要实现任何接口,本方法负责根据一定的规则来比较两个对象的大小。

    打个比较,这个接口的实现者好比是裁判,两个待比较的对象找它来比较大小,它根据自己定义的规则,结合两个对象的自身的数据,通过计算得出一个值,从而来决定哪个对象大哪个对象小。其本身并不参与比较。

    有的时候待比较的对象并不需要具备可比较性,只是在某些场合下需要对它们的一个序列进行比较,或者说,可能会按多种规则对同一组序列进行比较,这个时候,用comparator构造构建器就非常合适,首先它不会侵入原类,另外 多种规则就是多个比较器,非常方便。

    在JAVA里有关比较的下操作中,如集合排序等都提供了这两种方式的比较,我们可以根据情况进行选择。

    二、实现原理分析

    顾名思议,TreeMap的实现是基于Tree的数据结构,JAVA中可以用来排序的Tree,最有名的莫过于红黑树,而TreeMap的实现也正是基于红黑树。本文昆明Java培训班的老师主要从各个方面分析TreeMap的构建和使用。

    1.创建

    创建一个TreeMap,总共有四种方式,如下:

    我们可以看到,TreeMap的这四种方式中其实主要分了两种,一是comparator为null的,一种是不为null的,作为一个有序的Map,如果comparator不为NULL,则自然是使用这个来比较,否则,KEY应该继承Comparable接口,这个也是前面解释过的。

    作为一个红黑树,那么整个数据的存储则必是一颗树,TreeMap的实现也遵守了这一点,我们可以看一下对于树的构造。

    首先,有一个表示根节点的变量。

    其次,我们看一下节点的定义,也具备红黑树节点的性质

    可以看到节点的定义中除了有key和value之外,还有左孩子,右孩子,父节点,以及节点的颜色,根据这三个属性,我们可以很方便的从任何一个节点向上一级或者向下一级导航。通过对节点设置颜色,很容易实现红黑树的相关算 法。

    2.添加

    添加指添加一个新节点到树的合适位置。那么这个分类两个部分,首先是要找到合适的节点,这个可以通过二叉树的查找算法来完成,查找之后有两个结果,如果找到相同的KEY了,则做更新操作,如果没有找到,则需要把节点 原来的树关联,关联之后,由于可能会破坏红黑树的性质,所以还要根据情况再做一次调整。

    具体的算法如下:

    1 public V put(K key, V value) {

    2        Entry<K,V> t = root;

    3        if (t == null) {

    4            compare(key, key); // type (and possibly null) check

    5

    6            root = new Entry<>(key, value, null);

    7            size = 1;

    8            modCount++;

    9            return null;

    10        }

    11        int cmp;

    12        Entry<K,V> parent;

    13        // split comparator and comparable paths

    14        Comparator<? super K> cpr = comparator;

    15        if (cpr != null) {

    16            do {

    17                parent = t;

    18                cmp = cpr.compare(key, t.key);

    19                if (cmp < 0)

    20                    t = t.left;

    21                else if (cmp > 0)

    22                    t = t.right;

    23                else

    24                    return t.setValue(value);

    25            } while (t != null);

    26        }

    27        else {

    28            if (key == null)

    29                throw new NullPointerException();

    30            Comparable<? super K> k = (Comparable<? super K>) key;

    31            do {

    32                parent = t;

    33                cmp = k.compareTo(t.key);

    34                if (cmp < 0)

    35                    t = t.left;

    36                else if (cmp > 0)

    37                    t = t.right;

    38                else

    39                    return t.setValue(value);

    40            } while (t != null);

    41        }

    42        Entry<K,V> e = new Entry<>(key, value, parent);

    43        if (cmp < 0)

    44            parent.left = e;

    45        else

    46            parent.right = e;

    47        fixAfterInsertion(e);

    48        size++;

    49        modCount++;

    50        return null;

    51    }

    上面的代码就是整个添加的过程,关键的地方进行了加粗显示,可以看到,在查找的时候,实现时根据比较器是否存在来决定采用哪一种方式进行比较,如果比较之后没有找到对应的节点,则parent变量记录了最后一个不为叶子 点的节点,该节点即为新节点的父节点。新增后,需要对树重新做调整。

    调整算法已经在红黑树部分介绍过了,所以这里就不再细说。

    3.删除

    删除的话同样也是先通过二叉树的查找算法找到对应的节点,如果节点有两个孩子节点,则需要进一步查找其直接后继,然后针对其后继节点做删除操作。这样可以保证被删除的元素只有最多不超过一个节点。

    删除完成后,根据被删除节点的后继节点的情况做相应的删除修复操作,以保证删除后,原树还是一个红黑树,删除的完整代码如下:

    private void deleteEntry(Entry<K,V> p) {

    modCount++;

    size--;

    // If strictly internal, copy successor's element to p and then make p

    // point to successor.

    if (p.left != null && p.right != null) {

    Entry<K,V> s = successor(p);

    p.key = s.key;

    p.value = s.value;

    p = s;

    } // p has 2 children

    // Start fixup at replacement node, if it exists.

    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {

    // Link replacement to parent

    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;

    // Null out links so they are OK to use by fixAfterDeletion.

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

    // Fix replacement

    if (p.color == BLACK)

    fixAfterDeletion(replacement);

    } else if (p.parent == null) { // return if we are the only node.

    root = null;

    } else { // No children. Use self as phantom replacement and unlink.

    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;

    }

    }

    }

    修复的操作在前面的红黑树中已经介绍了,就不再详细分析了。

    4.遍历操作

    和普通的Map相比,作为一个排序Map,TreeMap也提供了各种遍历的操作,如headMap, tailMap,descendingMap等,我们可以方便的进行正序或倒序的遍历,这得益于节点的双向关联。

    三、总结

    至此,基于红黑数的TreeMap就算是完全分析完了,这是一种很经典的实现,通过昆明Java培训班的老师对其源码的分析我们可以更深刻的理解红黑树,也可以学习到一些好的设计思想。同时,也有助于我们正确地使用红黑树。

    推荐文章

上一篇:昆明Java培训:JAVA基础,字符串

下一篇:java培训:java数据类型

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:11/30

Java--零基础业余班

Java--零基础业余班

开班日期:11/30

Java--周末提升班

Java--周末提升班

开班日期:11/30

Java--零基础周末班

Java--零基础周末班

开班日期:11/30

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:186 8716 1620      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56