关键词:
一、TreeSet 概述
-
1、
TreeSet
是SortedSet
接口的实现类,TreeSet
可以确保集合元素处于排序状态。 -
2、
TreeSet
顾名思义他内部维护的是一个TreeMap
,底层是红黑二叉树,他使得集合内都是有序的序列。 -
3、
Tree
可以按照添加对象的指定属性,进行排序,所以向TreeSet
中添加的数据,要求是相同类的对象。 -
4、两种排序方式:自然排序(实现
Comparable接口
) 和 定制排序(Comparator
); -
5、自然排序中,比较两个对象是否相同的标准为:
compareTo()
返回0.不再是equals()
; -
6、定制排序中,比较两个对象是否相同的标准为:
compare()
返回0.不再是equals()
; -
7、对
TreeSet
进行遍历的时候,默认是使用自然排序的规则来排序的; -
8、
TreeSet
添加自定义类的对象时候,必须要有自然排序或定制排序,否则抛出异常:cannot cast to java.lang.Comparable
;
二、TreeSet 结构
1、TreeSet 声明
1 public class TreeSet<E> extends AbstractSet<E>
2 implements NavigableSet<E>, Cloneable, java.io.Serializable
2、TreeSet 类继承结构
3、红黑树
TreeSet
和后要的TreeMap
采用红黑树的存储结构
特点:有序,查询速度比List快
三、TreeSet 创建
1、构造器
TreeSet
是基于红黑树结构实现的,会对元素进行排序,TreeSet 提供了五种构造器:
public TreeSet()
this(new TreeMap<E,Object>());
TreeSet(NavigableMap<E,Object> m)
this.m = m;
public TreeSet(Comparator<? super E> comparator)
this(new TreeMap<>(comparator));
public TreeSet(Collection<? extends E> c)
this();
addAll(c);
public TreeSet(SortedSet<E> s)
this(s.comparator());
addAll(s);
里面的 m 属性是什么:
/**
* The backing map.
*/
private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
//加入Java开发交流君样:593142328一起吹水聊天
可以看到里面是维护了一个 NavigableMap。
2、通过 Comparator 实例创建 TreeSet
上面的四个构造函数中着重要介绍第三个,它通过Comparator
实例来创建TreeMap
,那么Comparator
到底是何方神圣呢?
通过阅读Comparator
的源码发现,这是一个用于集合类排序的辅助接口,用户需要实现compare方法。
如果用户用了这种方式创建TreeSet
,那么集合元素就不需要做额外处理,否则集合元素都需要实现Comparable
接口,因为Tree
在排序的时候会调用compare
或者compareTo
方法(介绍TreeMap
的时候会具体讲解)。
下面来看看写的一个样例代码:
public class MyComparator implements Comparator<Person>
@Override
public int compare(Person o1, Person o2)
return o1.age - o2.age;
public class Person
public Integer age;
public Person(Integer value)
this.age = value;
public static void TreeSetTest()
// TreeMap在底层put元素的时候会判断是否存在Comparator实例,如果存在,则每次添加元素排序比较的时候会调用compare接口。
TreeSet<Person> set = new TreeSet<Person>(new MyComparator());
Person p1 = new Person(1);
Person p2 = new Person(1);
Person p3 = new Person(5);
Person p4 = new Person(9);
Person p5 = new Person(10);
set.add(p1);
set.add(p2);
set.add(p3);
set.add(p4);
set.add(p5);
Iterator<Person> i = set.iterator();
while (i.hasNext())
Person p = (Person) i.next();
System.out.println(p.age);
//加入Java开发交流君样:593142328一起吹水聊天
打印结果:
1
5
9
10
四、TreeSet 方法
五、NavigableSet接口介绍
常用方法:
// 返回比当前元素小的最近的一个元素
public E lower(E e)
return m.lowerKey(e);
// 返回小于等于当前元素的最近一个元素
public E floor(E e)
return m.floorKey(e);
// 返回大于等于当前元素的最近一个元素
public E ceiling(E e)
return m.ceilingKey(e);
//加入Java开发交流君样:593142328一起吹水聊天
// 返回大于当前元素的最近一个元素
public E higher(E e)
return m.higherKey(e);
六、TreeSet 与 比较器
1、自然排序
-
(1)自然排序:
TreeSet
会调用集合元素的compareTo(Object obj)
方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列。 -
(2)如果试图把一个对象添加到
TreeSet
时,则该对象的类必须实现Comparable
接口。
实现Comparable
的类必须实现compareTo(Object obj)
方法,两个对象即通过compareTo(Object obj)
方法的返回值来比较大小。 -
(3)
Comparable
的典型实现:
①BigDecimal
、BigInteger
以及所有的数值型对应的包装类:按它们对应的数值大小进行比较;
②Character
:按字符的unicode
值来进行比较;
③Boolean:true
对应的包装类实例大于false
对应的包装类实例;
④String
:按字符串中字符的unicode
值进行比较
⑤Date
、Time
:后边的时间、日期比前面的时间、日期大 -
(4)向 TreeSet 中添加元素时,只有第一个元素无须比较
compareTo()
方法,后面添加的所有元素都会调用compareTo()
方法进行比较。 -
(5)因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象。
-
(6)对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过
compareTo(Object obj)
方法比较返回值。 -
(7)当需要把一个对象放入
TreeSet
中,重写该对象对应的equals()
方法时,应保证该方法与compareTo(Object obj)
方法有一致的结果:如果两个对象通过
equals() 方法比较返回 true,则通过compareTo(Object obj)
方法比较应返回 0。否则,让人难以理解。
2、定制排序
(1)TreeSet
的自然排序要求元素所属的类实现Comparable
接口,如果元素所属的类没有实现Comparable
接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。定制排序,通过Comparator
接口来实现。需要重写compare(T o1,T o2)
方法。
(2)利用int compare(T o1,T o2)
方法,比较o1和o2的大小:如果方法返回正整数,则表示o1大于o2;如果返回0,表示相等;返回负整数,表示o1小于o2。【面试资料】
(3)要实现定制排序,需要将实现Comparator
接口的实例作为形参传递给TreeSet的构造器。
(4)此时,仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
(5)使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0。
七、案例
1、自定义类的自然排序
案例:
public class User implements Comparable
private String name;
private int age;
public User()
public User(String name, int age)
this.name = name;
this.age = 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;
@Override
public String toString()
return "User" +
"name='" + name + '\\'' +
", age=" + age +
'';
@Override
public boolean equals(Object o)
System.out.println("User equals()....");
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
if (age != user.age) return false;
return name != null ? name.equals(user.name) : user.name == null;
@Override
public int hashCode() //return name.hashCode() + age;
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
//按照姓名从大到小排列,年龄从小到大排列
@Override
public int compareTo(Object o)
if(o instanceof User)
User user = (User)o;
// return -this.name.compareTo(user.name);
int compare = -this.name.compareTo(user.name);
if(compare != 0)
return compare;
else
return Integer.compare(this.age,user.age);
else//加入Java开发交流君样:593142328一起吹水聊天
throw new RuntimeException("输入的类型不匹配");
使用TreeSet保存:
@Test
public void test1()
TreeSet set = new TreeSet();
set.add(new User("Tom",12));
set.add(new User("Jerry",32));
set.add(new User("Jim",2));
set.add(new User("Mike",65));
set.add(new User("Jack",33));
set.add(new User("Jack",56));
Iterator iterator = set.iterator();
while(iterator.hasNext())
System.out.println(iterator.next());
注意:如果在自然比较器中并没有对年龄进行比较,当姓名一样时,就会认为这两个对象一样,不会再次存放;
如果在比较器中对两个属性都进行了比较,当有一个属性不一样就会放入 TreeSet中。面试资料
可以发现,这里对两个对象的比较并不是使用 equals() 方法,而是使用比较器来进行比较的。
2、自定义类的定制排序
定制排序:
@Test
public void test2()
Comparator com = new Comparator()
//按照年龄从小到大排列
@Override
public int compare(Object o1, Object o2)
if(o1 instanceof User && o2 instanceof User)
User u1 = (User)o1;
User u2 = (User)o2;
return Integer.compare(u1.getAge(),u2.getAge());
else
throw new RuntimeException("输入的数据类型不匹配");
;
TreeSet set = new TreeSet(com); //按照给定的比较器进行排序
set.add(new User("Tom",12));
set.add(new User("Jerry",32));
set.add(new User("Jim",2));
set.add(new User("Mike",65));
set.add(new User("Mary",33));
set.add(new User("Jack",33));
set.add(new User("Jack",56));
Iterator iterator = set.iterator();
while(iterator.hasNext())
System.out.println(iterator.next());
最后,祝大家早日学有所成,拿到满意offer,快速升职加薪,走上人生巅峰。
可以的话请给我一个三连支持一下我哟???【白嫖资料】
一个问题让我直接闭门思过!!!拼多多面试必问项之list实现类:linkedlist(代码片段)
一、LinkedList概述1、对于频繁的插入或删除元素的操作,建议使用LinkedList类,效率较高。2、LinkedList是一个实现了List接口和Deque接口的双端链表。3、LinkedList底层的链表结构使它支持高效的插入和删除操作,另外它实... 查看详情
android大厂面试必问的androidframework如何学习,如何深入了解framework层?
前言对于大多数Android开发工程师来说,掌握AndroidFramework一定是一个不光要熟练而且还要精通的技能。高级Android工程师岗位的一些技术面试也离不开Framework。一般会针对下面几个面试题进行提问:1.Android中多进程通信的... 查看详情
大厂高级工程师面试必问系列:java动态代理机制和实现原理详解(代码片段)
代理模式Java动态代理运用了设计模式中常用的代理模式代理模式:目的就是为其他对象提供一个代理用来控制对某个真实对象的访问代理类的作用:为委托类预处理消息过滤消息并转发消息进行消息被委托类执行后的后续处理通过... 查看详情
大厂面试必问!java知识点思维导图
什么是CAPCAP定理最初是由加州大学伯克利分校的计算机科学家埃里克·布鲁尔(EricBrewer)在2000年的ACMPODC上提出的一个猜想,也因此被叫做布鲁尔定理。后来在2002年,麻省理工学院的赛斯·吉尔伯特(SethGilbert&... 查看详情
android大厂面试必问的androidframework如何学习,如何深入了解framework层?
前言对于大多数Android开发工程师来说,掌握AndroidFramework一定是一个不光要熟练而且还要精通的技能。高级Android工程师岗位的一些技术面试也离不开Framework。一般会针对下面几个面试题进行提问:1.Android中多进程通信的... 查看详情
大厂java核心面试题出炉:阿里巴巴java开发工程师待遇
所以,我认为在你选择之前不妨好好想想什么是Java?你适不适合从事这份工作?Java开发是近20多年来最热门的编程语言,就业市场确实比较大,入门的难度也比C和C++要低,结合各方面来说,你选... 查看详情
bat大厂面试官必问的hashmap相关面试题及部分源码分析
BAT大厂面试官必问的HashMap相关面试题及部分源码分析0引言1JDK8中的HashMap与JDK7的HashMap有什么不一样?2HashMap中put方法流程3HashMap的get方法流程4HashMap扩容流程是怎样的?5谈谈你对红黑树的理解为什么HashMap的数组的大小是2的幂次方... 查看详情
2018网易的初级游戏开发工程师的面经
2018网易的初级游戏开发工程师的面经自我介绍:先是自我介绍,简单介绍了一下自己的项目经历,会什么技术(自己认怂,说了非科班出身,技术不咋地);然后问我,有看那些计算机相关的书籍;自己却只回答了一本书,简直是失败呀;好的... 查看详情
java面试必问:threadlocal终极篇淦!
...程序员。本文GitHubhttps://github.com/JavaFamily已收录,有一线大厂面试完整考点、资料以及我的系列文章。开场白张三最近天气很热心情不是很好,所以他决定出去面试跟面试官聊聊天排解一下,结果刚投递简历就有人约了面试。我... 查看详情
java面试必问的hashmap,java工程师视频教程
5节创建者模式第1节:工厂方法模式第2节:抽象工厂模式第3节:建造者模式第4节:原型模式第5节:单例模式7节结构型模式第1节:适配器模式第2节:桥接模式第3节:组合模式第4节:装饰器模... 查看详情
java注解原理面试题,跳槽大厂必看!
...发编程都掌握不好,你凭什么写出优质的代码?大厂必问并发编程技术栈,都在 查看详情
浅谈java后端开发工程师腾讯面试经历分享总结
最近一段时间考虑到换工作,打算整理一下网络上曾经面试者分享的的面试经历并结合自己以往的面试经历和经验,帮助大家获取到互联网大厂的入职通知书,也就是入职offer。 本文整理网络面试者和本人的面试经历和面试... 查看详情
80%大厂必问的面试题,附答案
面向对象的三个特征封装,继承,多态多态的好处,代码中如何实现多态,虚拟机中如何实现多态允许不同类对象对同一消息作出相应,好处如下:可替换性:多态对已存在的代码具有可替换性可扩充... 查看详情
大厂面试必问!hashmap怎样解决hash冲突?(代码片段)
HashMap冲突解决方法比较考验一个开发者解决问题的能力。下文给出HashMap冲突的解决方法以及原理分析,无论是在面试问答或者实际使用中,应该都会有所帮助。在Java编程语言中,最基本的结构就是两种,一种是数组,一种是模... 查看详情
handler面试必问八大题:如何深挖原理进大厂?1万+字带你详细剖析!(代码片段)
Handler一直是面试过程中的常客,我们今天来看看围绕Handler究竟能玩出那些花儿来。Handler机制几乎是Android面试时必问的问题,虽然看过很多次handler源码,但是有些面试官问的问题却不一定能够回答出来,趁着机... 查看详情
大厂二面:应对千亿级高并发场景,mysql如何分库分表?
大厂二面:应对千亿级高并发场景,MySQL如何分库分表?你回答得出来吗?前两天看到字节一个老哥写的帖子,提到高阶开发者必须掌握的技能,其中他明确提出了“精通MySQL”。为啥MySQL对开发人员如此重... 查看详情
前端面试指南|230页前端初级工程师面试题精编解析大全
目录前言前端初级工程师面试题HTML篇CSS篇JavaScript篇浏览器篇服务端与网络Vue框架算法篇前言初级前端工程师如何有计划的学习前端?前端基础是第一步也是非常重要的一步,从初学前端到成长为一名架构师,会经历... 查看详情
初级javaweb攻城狮面试指导
一、概要 初级JavaWeb工程师的面试准备 Java基础知识面试指导 Java面向对象面试指导 JSP面试指导 MySQL数据库基础面试指导 &n 查看详情