首页 > > 程序设计 > Java技术 >

5.5（java学习笔记）TreeSet和TreeMap

2018-10-19 06:29:52来源：博客园阅读 ()

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底层排序的实现是红黑树，有兴趣可以参阅：https://blog.csdn.net/a616413086/article/details/52586006

所以使用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来限制修改数据，避免这一问题。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：数据库的批量操作

下一篇：git实用操作

国外程序员整理的Java资源大全（全部是干货） 2020-06-12
2020年深圳中国平安各部门Java中级面试真题合集（附答案） 2020-06-11
2020年java就业前景 2020-06-11
04.Java基础语法 2020-06-11
Java--反射(框架设计的灵魂)案例 2020-06-11

IDC资讯：主机资讯注册资讯托管资讯 vps资讯网站建设

网站运营：建站经验策划盈利搜索优化网站推广免费资源

网站联盟：联盟新闻联盟介绍联盟点评网赚技巧

行业资讯：搜索引擎网络游戏电子商务广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器安全防护

软件技巧：其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识：网络协议网络安全网络管理组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条

最新资讯

热门关注

热门标签