5.5（java学习笔记）TreeSet和TreeMap

1.treemap

treemap是可排序的map类，使用这个类时，treemap会对存放的数据进行排序。

排序是根据key来排序的，排序规则是key实现comparable接口中的compareto()方法

或指定一个排序规则类实现comparator接口中的compare()方法，将其实例化的对象传入tree。

 

我们来看下tree排序的执行过程。

treemap还有其他构造方法，我们就看这两两个。

第一个是没有使用排序规则类的构造方法，那么作为key必须实现了comparable接口中的compareto()方法。

第二个是使用了排序规则类的构造方法。

 

我们接着来看tree中的put方法

 public v put(k key, v value) {
        entry<k,v> t = root;
        if (t == null) {
            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<? super k> cpr = comparator;
        if (cpr != null) {//判断是否有排序规则，有就用排序规则进行排序
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);//实现了comparator接口的比较规则类中的compare方法
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setvalue(value);
            } while (t != null);
        }
        else {                                  //没有排序规则就使用key实现的compareto方法比较
            if (key == null)
                throw new nullpointerexception();
            @suppresswarnings("unchecked")
                comparable<? super k> k = (comparable<? super k>) key;
            do {                   //实现了comparable接口中的compareto方法
                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;
    }

我们可以看到上面代码，首先判断是否有排序规则类的实例化对象，有就用这个对象中的compare方法，

没有就用key中的compareto方法。

排序的依据是key。

treemap底层排序的实现是红黑树，有兴趣可以参阅：

 

所以使用tree排序，其中的key必须实现一种接口（comparable或comparator都可以）

 

news类：

import java.text.dateformat;
import java.text.simpledateformat;
import java.util.date;


public class news implements comparable<news>{
    private string newsname;
    private date date;
    private int click;
    private string times;
    public news(){}
    public news(string newsname, date date, int click){
        setnewsname(newsname);
        setdate(date);
        setclick(click);
    }
    public string getnewsname() {
        return newsname;
    }

    public void setnewsname(string newsname) {
        this.newsname = newsname;
    }

    public date getdate() {
        return date;
    }

    public void setdate(date date) {
        this.date = date;
        dateformat china_time = new simpledateformat("yyyy-mm-dd hh-mm-ss");
       times = china_time.format(date);
        
    }
    public int getclick() {
        return click;
    }

    public void setclick(int click) {
        this.click = click;
    }
    public int compareto(news o) {//用于比较的compareto方法
        // todo auto-generated method stub
        if(this.getdate().after(o.getdate()))//先判断时间，按时间降序排列
            return -1;
        else if(this.getdate().gettime()-o.getdate().gettime()==0){//如果时间相同按点击量降序排序
            if(this.getclick() > o.click)
                return -1;
            else if(this.getclick()==o.getclick())
                return 0;
        }              
        return 1; //
    }
        
    public string tostring(){
        return "标题：" + this.newsname + "时间" + times
        + "点击量" + this.click + "\n";
    }
}

 

treemap +comparable +compareto实现排序

import javax.swing.text.html.htmldocument.iterator;

public class testcompare {
    public static void main(string[] args) {
        map<news,object> newsmap = new treemap<>();//调用本身的compareto方法
        newsmap.put(new news("国庆高峰堵车，各景点爆满！",new date(),1000),new object());//设置为当前时间
        newsmap.put(new news("国庆仍有大部分家里蹲！",new date(system.currenttimemillis()-60*60*1000),10000),new object());//设置为当前时间前一小时
        newsmap.put(new news("惊呆，游客竟在做这种事！！！",new date(),5000),new object());//设置为当前时间，点击量10000
        set<map.entry<news, object>> set_m = newsmap.entryset();//将map封装成变为set接口对象
        java.util.iterator<entry<news, object>> ite = set_m.iterator();//使用set接口中的迭代器
        while(ite.hasnext()){
            map.entry<news, object> en = ite.next();//然后将其中的键取出。
            system.out.println(en.getkey());
        }
    }
}

运行结果：
标题：惊呆，游客竟在做这种事！！！时间2018-10-14 10-50-58点击量5000

标题：国庆高峰堵车，各景点爆满！时间2018-10-14 10-50-57点击量1000

标题：国庆仍有大部分家里蹲！时间2018-10-14 09-50-58点击量10000

先按时间排序，再按点击量排序。

 

treemap + comparator+compare实现排序(news类中的comparable及compareto方法可以去掉也可以不去)

import java.util.arraylist;
import java.util.arrays;
import java.util.collections;
import java.util.comparator;
import java.util.date;
import java.util.map;
import java.util.map.entry;
import java.util.set;
import java.util.treemap;
import java.util.treeset;

import javax.swing.text.html.htmldocument.iterator;

public class testcompare {
    public static void main(string[] args) {
        map<news,object> newsmap = new treemap<>(new newsclicksort());//将排序规则传递进去
        newsmap.put(new news("国庆高峰堵车，各景点爆满！",new date(),1000),new object());//设置为当前时间
        newsmap.put(new news("国庆仍有大部分家里蹲！",new date(system.currenttimemillis()-60*60*1000),10000),new object());//设置为当前时间前一小时
        newsmap.put(new news("惊呆，游客竟在做这种事！！！",new date(),5000),new object());//设置为当前时间，点击量10000
        set<map.entry<news, object>> set_m = newsmap.entryset();
        java.util.iterator<entry<news, object>> ite = set_m.iterator();
        while(ite.hasnext()){
            map.entry<news, object> en = ite.next();
            system.out.println(en.getkey());
        }
    }
}

class newsclicksort implements comparator<news>{//排序规则类，按点击量降序

    @override
    public int compare(news o1, news o2) {
        if(o1.getclick() < o2.getclick()){
            return 1;
        }else{
            return -1;
        }
    }
}

运行结果：
标题：国庆仍有大部分家里蹲！时间2018-10-14 10-11-51点击量10000

标题：惊呆，游客竟在做这种事！！！时间2018-10-14 11-11-51点击量5000

标题：国庆高峰堵车，各景点爆满！时间2018-10-14 11-11-51点击量1000

可以看到上面是按点击量降序排列。

 

2.treeset

理解了treemap之后理解treeset就简单了。

我们先来看下treeset的初始化构造函数和添加函数add（）

一开始treeset直接创建一个treemap对象，只不过把键是需要存放的数据类型，值是一个object对象。

我们接着来看add方法

直接调用treemap中的put方法，将元素放入键中，值里面放入一个objcet对象。

后面就是调用treemap的代码了。

我们看下treeset的例子

运行函数：（使用compareto进行排序）

import java.util.arraylist;
import java.util.arrays;
import java.util.collections;
import java.util.comparator;
import java.util.date;
import java.util.linkedlist;
import java.util.list;
import java.util.map;
import java.util.set;
import java.util.treemap;
import java.util.treeset;

public class testcompare {
    public static void main(string[] args) {
        set<news> newsset = new treeset<>();
        newsset.add(new news("国庆高峰堵车，各景点爆满！",new date(),1000));//设置为当前时间
        newsset.add(new news("国庆仍有大部分家里蹲！",new date(system.currenttimemillis()-60*60*1000),10000));//设置为当前时间前一小时
        newsset.add(new news("惊呆，游客竟在做这种事！！！",new date(),5000));//设置为当前时间，点击量10000
        system.out.println(newsset);//treeset
    }
}

 

运行结果：//先比较时间（按时间降序排列），时间相同再比较点击量（按第点击量升序排列）

[标题：惊呆，游客竟在做这种事！！！时间2018-10-14 10-14-04点击量5000
, 标题：国庆高峰堵车，各景点爆满！时间2018-10-14 10-14-04点击量1000
, 标题：国庆仍有大部分家里蹲！时间2018-10-14 09-14-04点击量10000
]

我们可以看到上面结果是首先按时间降序，即最近发生的新闻品牌在最前面，时间相同时再按点击量排名。

 

运行函数：（使用compare进行排序）。news类与上面相同，可以去掉其中实现的comparable接口及compareto方法，不去也可以。

import java.util.arraylist;
import java.util.arrays;
import java.util.collections;
import java.util.comparator;
import java.util.date;
import java.util.linkedlist;
import java.util.list;
import java.util.map;
import java.util.set;
import java.util.treemap;
import java.util.treeset;

public class testcompare {
    public static void main(string[] args) {
        set<news> newsset = new treeset<>(new newsclicksort());
        newsset.add(new news("国庆高峰堵车，各景点爆满！",new date(),1000));//设置为当前时间
        newsset.add(new news("国庆仍有大部分家里蹲！",new date(system.currenttimemillis()-60*60*1000),10000));//设置为当前时间前一小时
        newsset.add(new news("惊呆，游客竟在做这种事！！！",new date(),5000));//设置为当前时间，点击量10000
        system.out.println(newsset);//treeset
    }
}

class newsclicksort implements comparator<news>{//指定的排序规则类，按点击量排名

    @override
    public int compare(news o1, news o2) {
        if(o1.getclick() < o2.getclick()){//按点击量降序
            return 1;
        }else{
            return -1;
        }
    }
}

运行结果：//可以看到只是按点击量进行降序排列
[标题：国庆仍有大部分家里蹲！时间2018-10-14 09-21-36点击量10000
, 标题：惊呆，游客竟在做这种事！！！时间2018-10-14 10-21-36点击量5000
, 标题：国庆高峰堵车，各景点爆满！时间2018-10-14 10-21-35点击量1000
]

 

 3.注意事项

treemap是在放入时比较，根据比较结果确定放入的位置。那么当数据放完后，再次修改已经放入的数据会怎么样，数据的位置会发生变化吗？

person类

public class person implements comparable<person>{
    private string name;
    private int age;
    public person(){}
    public person(string name,int age){
        setname(name);
        setage(age);
    }
    public string getname() {
        return name;
    }
    public void setname(string name) {
        this.name = name;
    }
    public int getage() {
        return age;
    }
    public void setage(int age) {
        this.age = age;
    }
    public string tostring(){
        return "姓名：" + name + "年龄：" + age;
    }
    @override
    public int compareto(person o) {
        if(this.getage() > o.getage())
            return 1;
        else if(this.getage() == o.getage())
            return 0;
        else
            return -1;
    }
    
    
}

运行代码

import java.util.comparator;
import java.util.iterator;
import java.util.map;
import java.util.set;
import java.util.treemap;
import java.util.treeset;


public class testtreemap {
    public static void main(string[] args) {
        set<person> s_per = new treeset<>();
        person p3 = new person("张三", 30);
        person p4 = new person("李四", 40);
        person p5 = new person("王五", 50);
        s_per.add(p5);
        s_per.add(p3);
        s_per.add(p4);
        iterator<person> ite = s_per.iterator();//输出排序后顺序，（按年龄升序）
        system.out.println("-------排序顺序-------");
        while(ite.hasnext()){
            system.out.println(ite.next());
        }
        p3.setage(100);//修改张三年龄为100
        system.out.println("-------修改年龄后-------");//输出修改后的顺序
        ite = s_per.iterator();
        while(ite.hasnext()){
            system.out.println(ite.next());
        }
    }
}

运行结果：
-------排序顺序-------
姓名：张三年龄：30
姓名：李四年龄：40
姓名：王五年龄：50
-------修改年龄后-------
姓名：张三年龄：100
姓名：李四年龄：40
姓名：王五年龄：50

可以看到最后即使修改了张三的年龄，顺序依然没有变化，因为treeset是在添加时排序，

treeset是在添加数据时排序，后来修改它的值，不会影响原来的排序。

就像一开始确定张三在第一位，后来确定李四在第二位，然后确定王五在第三位，此时位置已经拍好了。

这时我修改张三的年龄，并不会改变位置，只会改变张三的年龄。

由此可见，treeset中排序发生在添加时，后面修改数据不会导致顺序出现变化。

 

treeset添加完数据后修改可能会导致数据重复，我们知道set不能放入重复的数据，它只会在放入时检查。

一旦我们把数据放入了（放入的数据肯定是不会重复的）之后再次修改已经放入的数据可能会导致数据重复。

我们先来看下map的，set的也就很好理解了。

 

这个例子要在person类中重写hashcode和equals方法，用于判断键是否重复。（前面为了简洁就没有重写，如果是自定义类要指定相等规则，即重写euqasl，hashcode）

public class person implements comparable<person>{
    private string name;
    private int age;
    public person(){}
    public person(string name,int age){
        setname(name);
        setage(age);
    }
    public string getname() {
        return name;
    }
    public void setname(string name) {
        this.name = name;
    }
    public int getage() {
        return age;
    }
    public void setage(int age) {
        this.age = age;
    }
    public string tostring(){
        return "姓名：" + name + "年龄：" + age;
    }
    @override
    public int compareto(person o) {
        if(this.getage() > o.getage())
            return 1;
        else if(this.getage() == o.getage())
            return 0;
        else
            return -1;
    }
    @override //重写hashcode和equals方法，用于判断键是否重复
    public int hashcode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashcode());
        return result;
    }
    @override
    public boolean equals(object obj) {
        if (this == obj)
            return true;//如果是同一个对象肯定是相等的。
        if (obj == null)
            return false;
        if (getclass() != obj.getclass())
            return false;
        person other = (person) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;//person类如果名字和年龄都相同就认为是同一个人。
    }
    
}

//运行函数
import java.util.hashmap;
import java.util.iterator;
import java.util.map;
import java.util.set;
import java.util.treemap;
import java.util.treeset;


public class testtreemap {
    public static void main(string[] args) {
        string s1 = "三";
        string s2 = "四";
        string s3 = "五";
        person p1 = new person("张三",30);
        person p2 = new person("李四",40);
        person p3 = new person("王五",50);
        person p4 = new person("李四",40);
        map<person,object> m = new hashmap<>();
        m.put(p1, new object());
        m.put(p2, new object());
        m.put(p3, new object());
        m.put(p4, new object());
        system.out.println("---放入时会检查重复的key---");
        set<map.entry<person, object>> m_s = m.entryset();
        iterator<map.entry<person, object>> ite = m_s.iterator();
        while(ite.hasnext()){
            map.entry<person, object> en = ite.next();
            system.out.println(en.getkey());
        }
        p1.setage(40);
        p1.setname("李四");
        ite = m_s.iterator();
        system.out.println("---将张三修改为李四后---");
        while(ite.hasnext()){
            map.entry<person, object> en = ite.next();
            system.out.println(en.getkey());
        }
    }
}

运行结果：
---放入时会检查重复的key---
姓名：王五年龄：50
姓名：张三年龄：30
姓名：李四年龄：40
---将张三修改为李四后---
姓名：王五年龄：50
姓名：李四年龄：40
姓名：李四年龄：40

可以看到，一开始添加的时候排除了重复的李四，但是添加完后进行修改导致了元素重复。

treeset底层就是用的treemap的键，思想和上述一样，所以使用treemap和treeset拍完序后，

可能会导致元素重复，就违背了最初的不允许放入重复元素的思想。

可以用关键字final来限制修改数据，避免这一问题。