经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » Java相关 » Java » 查看文章
5.5(java学习笔记)TreeSet和TreeMap
来源:cnblogs  作者:gcmh  时间:2018/10/16 9:40:22  对本文有异议

1.TreeMap

TreeMap是可排序的Map类,使用这个类时,TreeMap会对存放的数据进行排序。

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

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

 

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

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

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

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

 

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

  1. public V put(K key, V value) {
  2. Entry<K,V> t = root;
  3. if (t == null) {
  4. compare(key, key); // type (and possibly null) check
  5. root = new Entry<>(key, value, null);
  6. size = 1;
  7. modCount++;
  8. return null;
  9. }
  10. int cmp;
  11. Entry<K,V> parent;
  12. // split comparator and comparable paths
  13. Comparator<? super K> cpr = comparator;
  14. if (cpr != null) {//判断是否有排序规则,有就用排序规则进行排序
  15. do {
  16. parent = t;
  17. cmp = cpr.compare(key, t.key);//实现了comparator接口的比较规则类中的compare方法
  18. if (cmp < 0)
  19. t = t.left;
  20. else if (cmp > 0)
  21. t = t.right;
  22. else
  23. return t.setValue(value);
  24. } while (t != null);
  25. }
  26. else { //没有排序规则就使用key实现的compareTo方法比较
  27. if (key == null)
  28. throw new NullPointerException();
  29. @SuppressWarnings("unchecked")
  30. Comparable<? super K> k = (Comparable<? super K>) key;
  31. do { //实现了Comparable接口中的compareTo方法
  32. parent = t;
  33. cmp = k.compareTo(t.key);
  34. if (cmp < 0)
  35. t = t.left;
  36. else if (cmp > 0)
  37. t = t.right;
  38. else
  39. return t.setValue(value);
  40. } while (t != null);
  41. }
  42. Entry<K,V> e = new Entry<>(key, value, parent);
  43. if (cmp < 0)
  44. parent.left = e;
  45. else
  46. parent.right = e;
  47. fixAfterInsertion(e);
  48. size++;
  49. modCount++;
  50. return null;
  51. }

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

没有就用key中的compareTo方法。

排序的依据是key。

TreeMap底层排序的实现是红黑树,有兴趣可以参阅:https://blog.csdn.net/a616413086/article/details/52586006

 

所以使用Tree排序,其中的Key必须实现一种接口(Comparable或Comparator都可以)

 

News类:

  1. import java.text.DateFormat;
  2. import java.text.SimpleDateFormat;
  3. import java.util.Date;
  4. public class News implements Comparable<News>{
  5. private String newsName;
  6. private Date date;
  7. private int click;
  8. private String timeS;
  9. public News(){}
  10. public News(String newsName, Date date, int click){
  11. setNewsName(newsName);
  12. setDate(date);
  13. setClick(click);
  14. }
  15. public String getNewsName() {
  16. return newsName;
  17. }
  18. public void setNewsName(String newsName) {
  19. this.newsName = newsName;
  20. }
  21. public Date getDate() {
  22. return date;
  23. }
  24. public void setDate(Date date) {
  25. this.date = date;
  26. DateFormat china_time = new SimpleDateFormat("yyyy-MM-dd hh-mm-ss");
  27. timeS = china_time.format(date);
  28. }
  29. public int getClick() {
  30. return click;
  31. }
  32. public void setClick(int click) {
  33. this.click = click;
  34. }
  35. public int compareTo(News o) {//用于比较的compareTo方法
  36. // TODO Auto-generated method stub
  37. if(this.getDate().after(o.getDate()))//先判断时间,按时间降序排列
  38. return -1;
  39. else if(this.getDate().getTime()-o.getDate().getTime()==0){//如果时间相同按点击量降序排序
  40. if(this.getClick() > o.click)
  41. return -1;
  42. else if(this.getClick()==o.getClick())
  43. return 0;
  44. }
  45. return 1; //
  46. }
  47. public String toString(){
  48. return "标题:" + this.newsName + "时间" + timeS
  49. + "点击量" + this.click + "\n";
  50. }
  51. }

 

TreeMap +Comparable +CompareTo实现排序

  1. import javax.swing.text.html.HTMLDocument.Iterator;
  2. public class TestCompare {
  3. public static void main(String[] args) {
  4. Map<News,Object> newsMap = new TreeMap<>();//调用本身的compareTo方法
  5. newsMap.put(new News("国庆高峰堵车,各景点爆满!",new Date(),1000),new Object());//设置为当前时间
  6. newsMap.put(new News("国庆仍有大部分家里蹲!",new Date(System.currentTimeMillis()-60*60*1000),10000),new Object());//设置为当前时间前一小时
  7. newsMap.put(new News("惊呆,游客竟在做这种事!!!",new Date(),5000),new Object());//设置为当前时间,点击量10000
  8. Set<Map.Entry<News, Object>> set_m = newsMap.entrySet();//将Map封装成变为Set接口对象
  9. java.util.Iterator<Entry<News, Object>> ite = set_m.iterator();//使用set接口中的迭代器
  10. while(ite.hasNext()){
  11. Map.Entry<News, Object> en = ite.next();//然后将其中的键取出。
  12. System.out.println(en.getKey());
  13. }
  14. }
  15. }
  1. 运行结果:
  2. 标题:惊呆,游客竟在做这种事!!!时间2018-10-14 10-50-58点击量5000
  3. 标题:国庆高峰堵车,各景点爆满!时间2018-10-14 10-50-57点击量1000
  4. 标题:国庆仍有大部分家里蹲!时间2018-10-14 09-50-58点击量10000

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

 

TreeMap + comparator+compare实现排序(News类中的Comparable及compareTo方法可以去掉也可以不去)

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.Comparator;
  5. import java.util.Date;
  6. import java.util.Map;
  7. import java.util.Map.Entry;
  8. import java.util.Set;
  9. import java.util.TreeMap;
  10. import java.util.TreeSet;
  11. import javax.swing.text.html.HTMLDocument.Iterator;
  12. public class TestCompare {
  13. public static void main(String[] args) {
  14. Map<News,Object> newsMap = new TreeMap<>(new NewsClickSort());//将排序规则传递进去
  15. newsMap.put(new News("国庆高峰堵车,各景点爆满!",new Date(),1000),new Object());//设置为当前时间
  16. newsMap.put(new News("国庆仍有大部分家里蹲!",new Date(System.currentTimeMillis()-60*60*1000),10000),new Object());//设置为当前时间前一小时
  17. newsMap.put(new News("惊呆,游客竟在做这种事!!!",new Date(),5000),new Object());//设置为当前时间,点击量10000
  18. Set<Map.Entry<News, Object>> set_m = newsMap.entrySet();
  19. java.util.Iterator<Entry<News, Object>> ite = set_m.iterator();
  20. while(ite.hasNext()){
  21. Map.Entry<News, Object> en = ite.next();
  22. System.out.println(en.getKey());
  23. }
  24. }
  25. }
  26. class NewsClickSort implements Comparator<News>{//排序规则类,按点击量降序
  27. @Override
  28. public int compare(News o1, News o2) {
  29. if(o1.getClick() < o2.getClick()){
  30. return 1;
  31. }else{
  32. return -1;
  33. }
  34. }
  35. }
  1. 运行结果:
  2. 标题:国庆仍有大部分家里蹲!时间2018-10-14 10-11-51点击量10000
  3. 标题:惊呆,游客竟在做这种事!!!时间2018-10-14 11-11-51点击量5000
  4. 标题:国庆高峰堵车,各景点爆满!时间2018-10-14 11-11-51点击量1000

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

 

2.TreeSet

理解了TreeMap之后理解TreeSet就简单了。

我们先来看下TreeSet的初始化构造函数和添加函数add()

一开始TreeSet直接创建一个TreeMap对象,只不过把键是需要存放的数据类型,值是一个Object对象。

我们接着来看add方法

直接调用TreeMap中的put方法,将元素放入键中,值里面放入一个Objcet对象。

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

我们看下TreeSet的例子

运行函数:(使用compareTo进行排序)

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.Comparator;
  5. import java.util.Date;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.Map;
  9. import java.util.Set;
  10. import java.util.TreeMap;
  11. import java.util.TreeSet;
  12. public class TestCompare {
  13. public static void main(String[] args) {
  14. Set<News> newsSet = new TreeSet<>();
  15. newsSet.add(new News("国庆高峰堵车,各景点爆满!",new Date(),1000));//设置为当前时间
  16. newsSet.add(new News("国庆仍有大部分家里蹲!",new Date(System.currentTimeMillis()-60*60*1000),10000));//设置为当前时间前一小时
  17. newsSet.add(new News("惊呆,游客竟在做这种事!!!",new Date(),5000));//设置为当前时间,点击量10000
  18. System.out.println(newsSet);//TreeSet
  19. }
  20. }

 

  1. 运行结果://先比较时间(按时间降序排列),时间相同再比较点击量(按第点击量升序排列)

[标题:惊呆,游客竟在做这种事!!!时间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方法,不去也可以。

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.Comparator;
  5. import java.util.Date;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.Map;
  9. import java.util.Set;
  10. import java.util.TreeMap;
  11. import java.util.TreeSet;
  12. public class TestCompare {
  13. public static void main(String[] args) {
  14. Set<News> newsSet = new TreeSet<>(new NewsClickSort());
  15. newsSet.add(new News("国庆高峰堵车,各景点爆满!",new Date(),1000));//设置为当前时间
  16. newsSet.add(new News("国庆仍有大部分家里蹲!",new Date(System.currentTimeMillis()-60*60*1000),10000));//设置为当前时间前一小时
  17. newsSet.add(new News("惊呆,游客竟在做这种事!!!",new Date(),5000));//设置为当前时间,点击量10000
  18. System.out.println(newsSet);//TreeSet
  19. }
  20. }
  21. class NewsClickSort implements Comparator<News>{//指定的排序规则类,按点击量排名
  22. @Override
  23. public int compare(News o1, News o2) {
  24. if(o1.getClick() < o2.getClick()){//按点击量降序
  25. return 1;
  26. }else{
  27. return -1;
  28. }
  29. }
  30. }
  1. 运行结果://可以看到只是按点击量进行降序排列
  2. [标题:国庆仍有大部分家里蹲!时间2018-10-14 09-21-36点击量10000
  3. , 标题:惊呆,游客竟在做这种事!!!时间2018-10-14 10-21-36点击量5000
  4. , 标题:国庆高峰堵车,各景点爆满!时间2018-10-14 10-21-35点击量1000
  5. ]

 

 3.注意事项

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

Person类

  1. public class Person implements Comparable<Person>{
  2. private String name;
  3. private int age;
  4. public Person(){}
  5. public Person(String name,int age){
  6. setName(name);
  7. setAge(age);
  8. }
  9. public String getName() {
  10. return name;
  11. }
  12. public void setName(String name) {
  13. this.name = name;
  14. }
  15. public int getAge() {
  16. return age;
  17. }
  18. public void setAge(int age) {
  19. this.age = age;
  20. }
  21. public String toString(){
  22. return "姓名:" + name + "年龄:" + age;
  23. }
  24. @Override
  25. public int compareTo(Person o) {
  26. if(this.getAge() > o.getAge())
  27. return 1;
  28. else if(this.getAge() == o.getAge())
  29. return 0;
  30. else
  31. return -1;
  32. }
  33. }

运行代码

  1. import java.util.Comparator;
  2. import java.util.Iterator;
  3. import java.util.Map;
  4. import java.util.Set;
  5. import java.util.TreeMap;
  6. import java.util.TreeSet;
  7. public class TestTreeMap {
  8. public static void main(String[] args) {
  9. Set<Person> s_per = new TreeSet<>();
  10. Person p3 = new Person("张三", 30);
  11. Person p4 = new Person("李四", 40);
  12. Person p5 = new Person("王五", 50);
  13. s_per.add(p5);
  14. s_per.add(p3);
  15. s_per.add(p4);
  16. Iterator<Person> ite = s_per.iterator();//输出排序后顺序,(按年龄升序)
  17. System.out.println("-------排序顺序-------");
  18. while(ite.hasNext()){
  19. System.out.println(ite.next());
  20. }
  21. p3.setAge(100);//修改张三年龄为100
  22. System.out.println("-------修改年龄后-------");//输出修改后的顺序
  23. ite = s_per.iterator();
  24. while(ite.hasNext()){
  25. System.out.println(ite.next());
  26. }
  27. }
  28. }
  1. 运行结果:
  2. -------排序顺序-------
  3. 姓名:张三年龄:30
  4. 姓名:李四年龄:40
  5. 姓名:王五年龄:50
  6. -------修改年龄后-------
  7. 姓名:张三年龄:100
  8. 姓名:李四年龄:40
  9. 姓名:王五年龄:50

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

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

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

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

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

 

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

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

我们先来看下Map的,Set的也就很好理解了。

 

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

  1. public class Person implements Comparable<Person>{
  2. private String name;
  3. private int age;
  4. public Person(){}
  5. public Person(String name,int age){
  6. setName(name);
  7. setAge(age);
  8. }
  9. public String getName() {
  10. return name;
  11. }
  12. public void setName(String name) {
  13. this.name = name;
  14. }
  15. public int getAge() {
  16. return age;
  17. }
  18. public void setAge(int age) {
  19. this.age = age;
  20. }
  21. public String toString(){
  22. return "姓名:" + name + "年龄:" + age;
  23. }
  24. @Override
  25. public int compareTo(Person o) {
  26. if(this.getAge() > o.getAge())
  27. return 1;
  28. else if(this.getAge() == o.getAge())
  29. return 0;
  30. else
  31. return -1;
  32. }
  33. @Override //重写hashCode和equals方法,用于判断键是否重复
  34. public int hashCode() {
  35. final int prime = 31;
  36. int result = 1;
  37. result = prime * result + age;
  38. result = prime * result + ((name == null) ? 0 : name.hashCode());
  39. return result;
  40. }
  41. @Override
  42. public boolean equals(Object obj) {
  43. if (this == obj)
  44. return true;//如果是同一个对象肯定是相等的。
  45. if (obj == null)
  46. return false;
  47. if (getClass() != obj.getClass())
  48. return false;
  49. Person other = (Person) obj;
  50. if (age != other.age)
  51. return false;
  52. if (name == null) {
  53. if (other.name != null)
  54. return false;
  55. } else if (!name.equals(other.name))
  56. return false;
  57. return true;//Person类如果名字和年龄都相同就认为是同一个人。
  58. }
  59. }
  1. //运行函数
    import
    java.util.HashMap;
  2. import java.util.Iterator;
  3. import java.util.Map;
  4. import java.util.Set;
  5. import java.util.TreeMap;
  6. import java.util.TreeSet;
  7. public class TestTreeMap {
  8. public static void main(String[] args) {
  9. String s1 = "三";
  10. String s2 = "四";
  11. String s3 = "五";
  12. Person p1 = new Person("张三",30);
  13. Person p2 = new Person("李四",40);
  14. Person p3 = new Person("王五",50);
  15. Person p4 = new Person("李四",40);
  16. Map<Person,Object> m = new HashMap<>();
  17. m.put(p1, new Object());
  18. m.put(p2, new Object());
  19. m.put(p3, new Object());
  20. m.put(p4, new Object());
  21. System.out.println("---放入时会检查重复的key---");
  22. Set<Map.Entry<Person, Object>> m_s = m.entrySet();
  23. Iterator<Map.Entry<Person, Object>> ite = m_s.iterator();
  24. while(ite.hasNext()){
  25. Map.Entry<Person, Object> en = ite.next();
  26. System.out.println(en.getKey());
  27. }
  28. p1.setAge(40);
  29. p1.setName("李四");
  30. ite = m_s.iterator();
  31. System.out.println("---将张三修改为李四后---");
  32. while(ite.hasNext()){
  33. Map.Entry<Person, Object> en = ite.next();
  34. System.out.println(en.getKey());
  35. }
  36. }
  37. }
  1. 运行结果:
  2. ---放入时会检查重复的key---
  3. 姓名:王五年龄:50
  4. 姓名:张三年龄:30
  5. 姓名:李四年龄:40
  6. ---将张三修改为李四后---
  7. 姓名:王五年龄:50
  8. 姓名:李四年龄:40
  9. 姓名:李四年龄:40

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

TreeSet底层就是用的TreeMap的键,思想和上述一样,所以使用TreeMap和TreeSet拍完序后,

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

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

 

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号