6.Set接口及其实现类
可怜人意,薄于云水,佳会更难重。
——晏几道《少年游》
Set接口及其实现类
1. Set接口介绍
java.util.Set
接口和java.util.List
接口一样,同样继承自Collection
接口,它与Collection
接口中的方法基本一致,并没有对Collection
接口进行功能上的扩充,只是比Collection
接口更加严格了。- 与
List
接口不同的是,Set
接口中元素无序,并且都会以某种规则保证存入的元素不出现重复。- Set 判断两个对象是否相同不是使用 == 运算符,而是根据 equals() 方法。
- Set集合取出元素的方式可以采用:迭代器、增强for。
Set
集合有多个子类,这里我们介绍其中的java.util.HashSet
、java.util.LinkedHashSet
、java.util.TreeSet
这三个集合。
2. Set接口的主要实现类
2.1 HashSet集合☆
java.util.HashSet
是Set
接口的一个典型实现类,它所存储的元素是不可重复
的,集合元素可以为null
,线程不安全
,并且元素都是无序的
(即存取顺序不能保证不一致)。HashSet
是根据对象的哈希值来确定元素在集合中的存储位置,因此具有良好的存储和查找性能。保证元素唯一性的方式依赖于:hashCode
与equals
方法。即两个对象通过 hashCode() 方法比较相等,并且两个对象的 equals() 方法返回值也相等。- 对于存放在Set容器中的对象,
对应的类一定要重写equals() 和hashCode(Object obj) 方法
,以实现对象相等规则 。即:“相等的对象必须具有相等的散列码”
。java.util.HashSet
底层的实现其实是一个java.util.HashMap
支持。
哈希值和哈希表
- 哈希值简介:是JDK根据
对象的地址
或者字符串
或者数字
算出来的int类型的数值
。- 如何获取哈希值:
Object类中的public int hashCode();返回对象的哈希码值。
- 哈希值的特点:
- 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
- 默认情况下,不同对象的哈希值是不同的。而重写hashCode()方法,可以实现让不同对象的哈希值相同。
- 什么是哈希表呢?哈希表是HashSet集合存储数据的结构
- 在
JDK1.8
之前,哈希表底层采用数组+链表
实现,即使用链表处理冲突,同一hash
值的链表都存储在一个链表里。但是当位于一个桶中的元素较多,即hash
值相等的元素较多时,通过key
值依次查找的效率较低。
- 而
JDK1.8
中,哈希表存储采用数组+链表+红黑树
实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。
底层也是数组,初始容量为16,当如果使用率超过0.75,(16*0.75=12)就会扩大容量为原来的2倍。
(16扩容为32,依次为64,128….等)。- 简单的来说,哈希表是由数组+链表+红黑树(
JDK1.8
增加了红黑树部分)实现的,如下图所示:
HashSet中添加元素的过程
- 当向 HashSet 集合中存入一个元素时,HashSet 会调用该对象的 hashCode() 方法来得到该对象hashCode 值,然后根据 hashCode 值,通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置。(
这个散列函数会与底层数组的长度相计算得到在数组中的下标,并且这种散列函数计算还尽可能保证能均匀存储元素,越是散列分布,该散列函数设计的越好
)- 如果两个元素的hashCode()值相等,会再继续调用equals方法,如果equals方法结果为true,添加失败;如果为false,那么会保存该元素,但是该数组的位置已经有元素了,那么会通过
链表的方式
继续链接。
重写 hashCode() 方法的基本原则
- 在程序运行时,同一个对象多次调用 hashCode() 方法应该返回相同的值。
- 当两个对象的 equals() 方法比较返回 true 时,这两个对象的 hashCode()方法的返回值也应相等。
- 对象中用作 equals() 方法比较的 Field,都应该用来计算 hashCode 值。
重写 equals() 方法的基本原则
以自定义的Student类为例,何时需要重写equals()?
当一个类有自己特有的“逻辑相等”概念,
当改写equals()的时候,总是要改写hashCode(),根据一个类的equals方法(改写后),两个截然不同的实例有可能在逻辑上是相等的,但是,根据Object.hashCode()方法,它们仅仅是两个对象。- 因此,违反了
“相等的对象必须具有相等的散列码”
。- 结论:复写equals方法的时候一般都需要同时复写hashCode方法。
通常参与计算hashCode 的对象的属性也应该参与到equals()。
HashSet存储自定义类型元素☆
给
HashSet
中存放自定义类型元素时,需要重写对象中的hashCode
和equals
方法,建立自己的比较方式,才能保证HashSet集合中的对象唯一。
1 | /** |
执行结果:
1 | Student [name=郭德纲, age=44] |
Objects.hash(name, age);执行细节如下:
1 | public static int hash(Object... values) { |
LinkedHashSet集合☆
我们知道
HashSet
保证元素唯一,可是元素存放进去是没有顺序的,那么我们要保证有序,怎么办呢?在HashSet
下面有一个子类java.util.LinkedHashSet
,它是链表和哈希表组合的一个数据存储结构。
LinkedHashSet 是 HashSet 的子类。
- LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,但它同时使用双向链表维护元素的次序,这使得元素看起来是
以插入顺序保存的
。- LinkedHashSet插入性能略低于 HashSet,但在迭代访问 Set 里的全部元素时有很好的性能。
- LinkedHashSet 不允许集合元素重复。
2.2 TreeSet集合
TreeSet 是 SortedSet 接口的实现类
,TreeSet 可以确保集合元素处于排序状态。- TreeSet底层使用 红黑树结构存储数据。
- 可以将元素按照规则进行排序。
- TreeSet():根据其元素的
自然排序进行排序。
- TreeSet(Comparator comparator) :根据指定的
比较器进行排序。
- 特点:
- 有序,查询速度比List快。
排序—自然排序
自然排序:TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系,然后将集合元素
按升序(默认情况)排列
。
如果试图把一个对象添加到 TreeSet 时,则该对象的类必须实现 Comparable接口。
实现 Comparable 的类必须实现 compareTo(Object obj) 方法,两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。
Comparable 的典型实现:
BigDecimal、BigInteger
以及所有的数值型对应的包装类:按它们对应的数值大小进行比较。Character:
按字符的 unicode值来进行比较。Boolean:true
对应的包装类实例大于 false 对应的包装类实例。String:
按字符串中字符的 unicode 值进行比较。Date、Time:
后边的时间、日期比前面的时间、日期大。向 TreeSet 中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较。
因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象。
对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj) 方法比较返回值。
当需要把一个对象放入 TreeSet 中,重写该对象对应的 equals() 方法时,应保证该方法与
compareTo(Object obj)
方法有一致的结果:如果两个对象通过equals() 方法比较返回 true,则通过compareTo(Object obj)
方法比较应返回 0。否则,让人难以理解。
排序—定制排序
- TreeSet的自然排序要求元素所属的类实现Comparable接口,如果元素所属的类没有实现Comparable接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。
定制排序,通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。
- 利用
int compare(T o1,T o2)
方法,比较o1
和o2
的大小:
如果方法返回正整数,则表示o1大于o2;
如果返回0,表示相等;
返回负整数,表示o1小于o2。
- 要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
此时,仍然只能向TreeSet中添加类型相同的对象,否则发生ClassCastException异常。
- 使用定制排序判断两个元素相等的标准是:通过Comparator比较
两个元素返回了0。