5.5(java学习笔记)TreeSet和TreeMap

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

新老客户大回馈,云服务器低至5折

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实用操作