可怜人意,薄于云水,佳会更难重。

——晏几道《少年游》

Set接口及其实现类

1. Set接口介绍

  1. java.util.Set 接口和 java.util.List 接口一样,同样继承自 Collection 接口,它与 Collection 接口中的方法基本一致,并没有对 Collection 接口进行功能上的扩充,只是比 Collection 接口更加严格了。
  2. List 接口不同的是, Set 接口中元素无序,并且都会以某种规则保证存入的元素不出现重复。
  3. Set 判断两个对象是否相同不是使用 == 运算符,而是根据 equals() 方法。
  4. Set集合取出元素的方式可以采用:迭代器、增强for。
  5. Set 集合有多个子类,这里我们介绍其中的 java.util.HashSetjava.util.LinkedHashSetjava.util.TreeSet 这三个集合。

image-20201113163538117

2. Set接口的主要实现类

2.1 HashSet集合☆

  1. java.util.HashSetSet 接口的一个典型实现类,它所存储的元素是不可重复的,集合元素可以为null线程不安全,并且元素都是无序的(即存取顺序不能保证不一致)。
  2. HashSet 是根据对象的哈希值来确定元素在集合中的存储位置,因此具有良好的存储和查找性能。保证元素唯一性的方式依赖于: hashCodeequals 方法。即两个对象通过 hashCode() 方法比较相等,并且两个对象的 equals() 方法返回值也相等。
  3. 对于存放在Set容器中的对象, 对应的类一定要重写equals() 和hashCode(Object obj) 方法,以实现对象相等规则 。即: “相等的对象必须具有相等的散列码”
  4. java.util.HashSet 底层的实现其实是一个 java.util.HashMap 支持。
哈希值和哈希表
  1. 哈希值简介:是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值
  2. 如何获取哈希值:Object类中的public int hashCode();返回对象的哈希码值。
  3. 哈希值的特点:
    • 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
    • 默认情况下,不同对象的哈希值是不同的。而重写hashCode()方法,可以实现让不同对象的哈希值相同。
  4. 什么是哈希表呢?哈希表是HashSet集合存储数据的结构
  5. JDK1.8之前,哈希表底层采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。
    • 14_JKD8以前哈希表
  6. JDK1.8中,哈希表存储采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。
    • 15_JKD8以后哈希表
  7. 底层也是数组,初始容量为16,当如果使用率超过0.75,(16*0.75=12)就会扩大容量为原来的2倍。(16扩容为32,依次为64,128….等)。
  8. 简单的来说,哈希表是由数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,如下图所示:

1563700294020

HashSet中添加元素的过程
  1. 当向 HashSet 集合中存入一个元素时,HashSet 会调用该对象的 hashCode() 方法来得到该对象hashCode 值,然后根据 hashCode 值,通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置。(这个散列函数会与底层数组的长度相计算得到在数组中的下标,并且这种散列函数计算还尽可能保证能均匀存储元素,越是散列分布,该散列函数设计的越好
  2. 如果两个元素的hashCode()值相等,会再继续调用equals方法,如果equals方法结果为true,添加失败;如果为false,那么会保存该元素,但是该数组的位置已经有元素了,那么会通过链表的方式继续链接。
重写 hashCode() 方法的基本原则
  1. 在程序运行时,同一个对象多次调用 hashCode() 方法应该返回相同的值。
  2. 当两个对象的 equals() 方法比较返回 true 时,这两个对象的 hashCode()方法的返回值也应相等。
  3. 对象中用作 equals() 方法比较的 Field,都应该用来计算 hashCode 值。
重写 equals() 方法的基本原则

以自定义的Student类为例,何时需要重写equals()?

  1. 当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候,总是要改写hashCode(),根据一个类的equals方法(改写后),两个截然不同的实例有可能在逻辑上是相等的,但是,根据Object.hashCode()方法,它们仅仅是两个对象。
  2. 因此,违反了“相等的对象必须具有相等的散列码”
  3. 结论:复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode 的对象的属性也应该参与到equals()。
HashSet存储自定义类型元素☆

HashSet中存放自定义类型元素时,需要重写对象中的hashCodeequals方法,建立自己的比较方式,才能保证HashSet集合中的对象唯一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
*创建自定义Student类
*/
public class Student {
private String name;
private int age;
public Student() {
}
public Student(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 boolean equals(Object o) {
if (this == o)
return true;
if (o == null || getClass() != o.getClass())
return false;
Student student = (Student) o;
return age == student.age &&
Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}

public class HashSetDemo {
public static void main(String[] args) {

//创建集合对象 该集合中存储 Student类型对象
HashSet<Student> stuSet = new HashSet<Student>();
//存储
Student stu = new Student("于谦", 43);
stuSet.add(stu);
stuSet.add(new Student("郭德纲", 44));
stuSet.add(new Student("于谦", 43));
stuSet.add(new Student("郭麒麟", 23));
stuSet.add(stu);
for (Student stu2 : stuSet) {
System.out.println(stu2);
}
}
}

执行结果:

1
2
3
4
5
Student [name=郭德纲, age=44]

Student [name=于谦, age=43]

Student [name=郭麒麟, age=23]

Objects.hash(name, age);执行细节如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int hash(Object... values) {
return Arrays.hashCode(values);
}

public static int hashCode(Object a[]) {
if (a == null)
return 0;

int result = 1;

for (Object element : a)
result = 31 * result + (element == null ? 0 : element.hashCode());

return result;
}
LinkedHashSet集合☆

我们知道HashSet保证元素唯一,可是元素存放进去是没有顺序的,那么我们要保证有序,怎么办呢?在HashSet下面有一个子类 java.util.LinkedHashSet ,它是链表和哈希表组合的一个数据存储结构。

  1. LinkedHashSet 是 HashSet 的子类。
  2. LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入顺序保存的
  3. LinkedHashSet插入性能略低于 HashSet,但在迭代访问 Set 里的全部元素时有很好的性能。
  4. LinkedHashSet 不允许集合元素重复。

2.2 TreeSet集合

  1. TreeSet 是 SortedSet 接口的实现类,TreeSet 可以确保集合元素处于排序状态。
  2. TreeSet底层使用 红黑树结构存储数据。
  3. 可以将元素按照规则进行排序
    • TreeSet():根据其元素的自然排序进行排序。
    • TreeSet(Comparator comparator) :根据指定的比较器进行排序。
  4. 特点:
    • 有序,查询速度比List快。
排序—自然排序
  1. 自然排序:TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列

  2. 如果试图把一个对象添加到 TreeSet 时,则该对象的类必须实现 Comparable接口。

  3. 实现 Comparable 的类必须实现 compareTo(Object obj) 方法,两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。

  4. Comparable 的典型实现:

    • BigDecimal、BigInteger 以及所有的数值型对应的包装类:按它们对应的数值大小进行比较。
    • Character:按字符的 unicode值来进行比较。
    • Boolean:true 对应的包装类实例大于 false 对应的包装类实例。
    • String:按字符串中字符的 unicode 值进行比较。
    • Date、Time:后边的时间、日期比前面的时间、日期大。
  5. 向 TreeSet 中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较。

  6. 因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象。

  7. 对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj) 方法比较返回值。

  8. 当需要把一个对象放入 TreeSet 中,重写该对象对应的 equals() 方法时,应保证该方法与compareTo(Object obj) 方法有一致的结果:如果两个对象通过equals() 方法比较返回 true,则通过 compareTo(Object obj) 方法比较应返回 0。否则,让人难以理解。

排序—定制排序
  1. TreeSet的自然排序要求元素所属的类实现Comparable接口,如果元素所属的类没有实现Comparable接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。
    • 定制排序,通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。
  2. 利用int compare(T o1,T o2)方法,比较o1o2的大小:
    • 如果方法返回正整数,则表示o1大于o2;
    • 如果返回0,表示相等;
    • 返回负整数,表示o1小于o2。
  3. 要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
  4. 此时,仍然只能向TreeSet中添加类型相同的对象,否则发生ClassCastException异常。
  5. 使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0。