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来限制修改数据,避免这一问题。