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