Set集合

第一章 Collections的 sort方法

1.2、Collections 工具类与 sort 方法概述

java.util.Collections是 Java 集合框架中的一个，它提供了一系列用于操作集合的静态方法，比如排序、查找、替换等。其中，sort方法专门用于对List集合进行排序，它有两种重载形式：

1
2
3
4
1.public static <T extends Comparable<? super T>> void sort(List<T> list)：该方法适用于元素实现了Comparable接口，具备自然排序能力的List集合。

2. public static <T> void sort(List<T> list, Comparator<? super T> c)：当元素没有自然排序能力时，通过传入一个自定义的Comparator比较器对象，来指定排序规则。

1.3、自然排序（实现 Comparable 接口）

原理
自然排序要求被排序的元素所属的类实现java.lang.Comparable接口，并实现该接口的compareTo方法。compareTo方法用于定义元素之间的自然顺序，它返回一个整数值：

  • 如果返回值小于 0，表示当前对象小于参数对象；
  • 如果返回值等于 0，表示当前对象等于参数对象；
  • 如果返回值大于 0，表示当前对象大于参数对象。
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
/*
    我们自定义的工具类,模拟 Arrays的sort方法,完成排序
 */
public class MyArrays {
    private MyArrays(){

    }

    // 使用冒泡排序,对 arr的元素进行升序排序
    public static void sort(Object[] arr){
        // 对数组进行合法性校验
        if(arr == null){
            return;
        }
        // 使用循环嵌套
        //n 个元素只需要排 n-1 轮（比如 5 个元素，排 4 轮就够了）。
        for (int i = 0; i < arr.length-1; i++) {
            //每一轮排序后，最大的元素会 “冒泡” 到数组末尾，下一轮不需要再比较它了（所以减去 i）
            for (int j = 0; j < arr.length - i - 1; j++) {
                // 判断当前元素和下一个元素的大小关系,如果当前元素大于了后面的元素,这进行交换

                // Comparable 是 Java 自带的接口，里面有一个 compareTo() 方法，专门用于定义 “对象比较大小的规则”。
                // 传入的数组元素必须实现 Comparable 接口。
    
                // 面向 Comparable 接口的对象,调用  compareTo 方法,通过返回的int值就可以知道大小关系了
                Comparable c1 = (Comparable) arr[j];
                Comparable c2 = (Comparable) arr[j+1];
                if(c1.compareTo(c2) > 0){
                    arr[j] = c2;
                    arr[j+1] = c1;
                }
            }
        }
    }
}
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
/*
    按 动物的年龄进行升序排序
 */
public class Dog implements Comparable<Dog>{
    private String name;
    private int age;

    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    ...

    // 这个方法就是 写排序规则的方法,由Arrays的sort方法内部负责调用,我们只负责写,不负责调
    // 返回大于0的数据,代表数据更大,小于0就是更小,等于0就是相同
    @Override
    public int compareTo(Dog o) {
        return   o.age - this.age;
        //this.age - o.age > 0 → 当前狗年龄更大 → 排在后面（升序）。
		//this.age - o.age < 0 → 当前狗年龄更小 → 排在前面（升序）。
    }
}

public class TestDog {
    public static void main(String[] args) {
        Dog[] arr = new Dog[3];
        arr[0] = new Dog("旺财",5);
        arr[1] = new Dog("小黑",3);
        arr[2] = new Dog("大黄",6);
        System.out.println(Arrays.toString(arr));

        // 排序
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));

/*
[Dog{name='旺财', age=5}, Dog{name='小黑', age=3}, Dog{name='大黄', age=6}]
-------------------------------
[Dog{name='小黑', age=3}, Dog{name='旺财', age=5}, Dog{name='大黄', age=6}]
*/
    }
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package com.shihanshuo.SetTest;

import java.util.Objects;

public class Book implements Comparable<Book> {
    private String name;
    private double price;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }

    public Book(String name, double price) {
        this.name = name;
        this.price = price;
    }

    @Override
    public int compareTo(Book o) {
        // 按价格升序排序,面向包装类,直接调用静态方法,让包装类帮我们进行比较
        return Double.compare(this.price, o.price);
        /*为什么不用 this.price - o.price？
        因为 price 是 double（浮点数），直接相减有两个问题：
        精度丢失：比如 2.0 - 1.9 理论是 0.1，但计算机算出来可能是 0.0999999999999996，导致判断错误。
        返回值类型不匹配：compareTo 要求返回 int，但 double 相减是 double，强转可能丢失信息。 */
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("equals..............");
        if (this == o) return true;

        if (o == null || getClass() != o.getClass()) return false;
        Book book = (Book) o;//强转
        /*
        传入对象 o
            ↓
        是 null 吗？ → 是 → 返回 false（不相等）
            ↓ 不是
        是同一个类吗？ → 不是 → 返回 false（不相等）
            ↓ 是
        安全强转为 Book 类型 → 可以放心访问 price 和 name 了
         */

        if (Double.compare(price, book.price) != 0) return false;
        return Objects.equals(name, book.name);
        //因为 name 是 String（引用类型），如果直接用 name.equals(book.name)，当 name 为 null 时会报空指针异常。Objects.equals(a, b) 会先判断 a 和 b 是否为 null，非常安全。
    }

    @Override
    public int hashCode() {
        System.out.println("hashCode..............");
        int result;
        long temp;
        // 1. 计算 name 的哈希码：如果 name 是 null，哈希码为 0
        result = name != null ? name.hashCode() : 0;
        // 2. 处理 double 类型的 price：先转成 long 类型的 bits（因为 double 不能直接算哈希）
        temp = Double.doubleToLongBits(price);
        // 3. 合并哈希码：用 31 这个质数乘以之前的结果，再加上 price 的哈希
        result = 31 * result + (int) (temp ^ (temp >>> 32));
        return result;
    }
}


public class TestBook {
    public static void main(String[] args) {
        Book[] books = new Book[3];
        books[0] = new Book("三国演义",19.88);
        books[1] = new Book("水浒传",19.8);
        books[2] = new Book("西游记",19.83);

        //Arrays.sort(books);
        // 使用自定义的工具测试排序
        MyArrays.sort(books);

        System.out.println(Arrays.toString(books));
    }
}

1.4、定制排序（使用 Comparator 接口）【重点】

原理

当被排序的元素所属的类没有实现Comparable接口，或者我们希望按照不同于自然排序的规则进行排序时，可以使用Comparator接口来自定义排序规则。

Comparator接口中有一个compare方法，它同样返回一个整数值，含义与Comparable接口中的compareTo方法类似，Collections.sort方法会根据这个返回值对元素进行排序。

代码思路

可以通过匿名内部类实现Comparator接口的compare方法

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
/*
    对 数组中的字符串,按字符串长度降序排序,如果字符串长度相同,则按照字典顺序排序

    思路:
    1: 利用 Arrays.sort(数组,比较器对象) 方法完成排序
    2: 我们需要自己写一个 比较器对象,在比较器对象中,完成 具体的规则描述

 */
public class MyTest06 {
    public static void main(String[] args) {
        String[] arr = {"bbb","a","dd","aa","dd","ccc","ff","aa"};
        // 写一个比较器对象 使用匿名内部类
        Comparator<String> bjq = new Comparator<String>(){
            /*
                compare 方法,我们只负责写,不负责调用,由 Arrays.sort方法内部负责调用,我们只需要在这个 compare 方法内,写"字符串的大小关系即可"
             */
            public int compare(String o1, String o2) {
                // 获取两个字符串的长度并相减
                int i = o2.length() - o1.length();
                // 如果 i == 0 说明两个字符串的长度一样,面向字符串对象,比较字典顺序!!!
                return i == 0? o1.compareTo(o2) :i;
            }
        };

        // 排序
        Arrays.sort(arr,bjq);
        System.out.println(Arrays.toString(arr));
    }
}

代码写法 排序方式 结果
o2 - o1 降序 大的 / 长的 / 晚的 排前面
o1 - o2 升序 小的 / 短的 / 早的 排前面
o1.compareTo(o2) 升序 字典序 a-z
o2.compareTo(o1) 降序 字典序 z-a

也可以使用 Java 8 的 Lambda 表达式简化代码实现。

注意事项
Comparable接口与Comparator接口的方法参数是不一样的,Comparable接口的compareTo方法只有一个参数,而Comparator接口的compare方法有两个参数 ,注意区分每个参数的含义及返回值的意义;

总结

Java中Collections工具类的sort方法是对List集合进行排序的重要工具。

使用该方法时，要确保被排序的元素拥有自然排序能力（实现Comparable接口），或者通过编写Comparator比较器对象来定制排序规则。

第二章 TreeSet集合

对比维度 自然排序（Comparable） 比较器排序（Comparator）
实现方式 元素类自身实现接口 外部传入 Comparator 对象
代码侵入性 需要修改元素类代码 无需修改元素类代码
灵活性 只能定义一种固定排序规则 可动态定义多种排序规则
典型场景 元素类的默认排序（如 Integer） 需自定义排序或元素类未实现接口

TreeSet 需要比较零

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
package com.itheima.p6_treeset;

import java.util.Comparator;
import java.util.TreeSet;
/*
    java.util.TreeSet<T>集合:
        特点:
            对存储的元素进行排序(升序/降序)
            内部采用红黑树的数据结构,存储数据时和哈希值没关系,判断数据的大小依赖Comparable接口的compareTo方法小的(compareTo方法返回值<0)放左侧,大的(compareTo方法返回值>0)放右侧
            compareTo方法返回值=0  元素是相同的,不再存储当前元素了
        要求:
            存储对象的所属的类具备排序能力,实现Comparable接口,重写compareTo方法(自然排序)

    java.lang.Comparable<T>接口:
        让自定义类的具备排序特性
        抽象方法:
            public int compareTo(T o): 指定排序规则的
                this(调用方法的对象) - o(参数对象): 升序
                o(参数对象) - this(调用方法的对象): 降序
                注意:
                    this和o都是引用类型不能直接向减的

    java.util.TreeMap<K,V>集合:
        和上面一样,因为TreeSet内部就是使用的TreeSet
        要求:
            键所属的类应该具备自然比较性,必须实现Comparable,覆盖重写compareTo方法
 */
/*
    练习TreeSet集合存图书数据
 */
public class MyTest08_2 {
    public static void main(String[] args) {
        // 实际使用 TreeSet 集合的时候,除了指定主要的排序条件以外,一定要添加一个"次要的排序条件",否则只要主要条件一样,就会当成重复的元素去重!
        TreeSet<Book> set = new TreeSet<>(
                new Comparator<Book>() {
                    @Override
                    public int compare(Book o1, Book o2) {
                        // 主要条件
                        int i = Double.compare(o1.getPrice(), o2.getPrice());
                        // 次要条件
                        return i == 0? o1.getName().compareTo(o2.getName()):i;
                    }
                }
        );
        set.add(new Book("水浒传",19.8));
        set.add(new Book("红楼梦",19.8));
        set.add(new Book("红楼梦",19.8));
        set.add(new Book("红楼梦",19.8));
        set.add(new Book("三国演示",29.8));
        System.out.println(set);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
    练习TreeSet集合存数据
 */
public class MyTest08 {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(2);
        set.add(6);
        set.add(15);
        set.add(18);
        set.add(19);
        System.out.println(set);

        TreeSet<Pai> set2 = new TreeSet<>(new Comparator<Pai>() {
            @Override
            public int compare(Pai o1, Pai o2) {
                return o1.getZhi() - o2.getZhi();
            }
        });
        set2.add(new Pai("♠","A",7));
        set2.add(new Pai("♠","2",3));
        System.out.println(set2);
    }
}

第三章 Set集合

3.1 Set特点

Set集合是属于Collection体系下的另一个分支，它的特点如下图所示
null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
java.util.Collection<T>接口: 单列集合的根接口
    里面定义的方法,子接口/实现类 都有

常用子接口:
    java.util.List<T>接口:
    特点:
        1.有序: 保证存入和取出元素的顺序是一致的
        2.有索引: 可以通过索引的方式获取元素
        3.可重复: 可以存储相同的内容

    java.util.Set<T>接口:
    特点:
        1.无索引:	不可以通过索引的方式获取元素
        2.不可重复  元素唯一,研究如何保证元素唯一的,依赖hashCode方法和equals方法
        3.注意: 
			不能说Set集合是有序/无序的,因为到底有序/无序,
			要看实现类 HashSet就是无序的,LinkedHashSet就是有序的

    注意:
        Set接口中的方法和Collection中的方法一样
        Collection中的方法,已经学习过了

3.2 Set基本使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
    java.util.Set<T>接口常用实现类
    java.util.HashSet<T>集合
    特点:
        1.底层数据结构: 
            哈希表   数组 + 单向链表/红黑树(链表节点>8 并且 数组元素数量>=64,把链表变成红黑树)

        2.特点: 查询速度嗷嗷快,增删速度也不慢
        3.无序: 不保证存入和取出元素的顺序是一致的
        4.无索引
        5.不可重复  依赖于HashSet存储对象所属类的hashCode和equals方法
        6.线程不安全,不同步,但是效率高

    java.util.LinkedHashSet<T>集合
    特点:
        1.底层数据结构: 
            哈希表+链表   数组 + 双向链表/红黑树(链表节点>8 并且 数组元素数量>=64,链表变成红黑树)
        2.特点: 查询速度嗷嗷快,增删速度也不慢
        3.有序: 保证存入和取出元素的顺序是一致的
        4.无索引
        5.不可重复  依赖于HashSet存储对象所属类的hashCode和equals方法
*/
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
public class Demo03Set {
    public static void main(String[] args) {
        //创建HashSet集合对象
        Set<Integer> set = new HashSet<>();

        //add: 添加元素
        set.add(100);
        set.add(100);
        set.add(10000);
        set.add(10000);
        set.add(200);
        set.add(200);
        System.out.println(set);//证明: 无序,不可重复(唯一)
        //set.get(0);//证明: 没有索引

        Set<String> set2 = new LinkedHashSet<>();

        //add: 添加元素
        set2.add("zz");
        set2.add("hhh");
        set2.add("bbbb");
        set2.add("aaaaa");
        set2.add("dddddd");
        set2.add("zz");
        System.out.println(set2);//证明: 有序,,不可重复(唯一)

        //set2.get(3);//证明: 没有索引
    }
}

3.3 hashCode方法

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
java.lang.Object类,成员方法:
    public native int hashCode(): 返回该对象的哈希码值,就是一个int数字
    该方法是本地方法,根据系统资源计算一个int数字,叫做哈希值
    支持此方法是为了提高哈希表的性能。
注意:
    1.同一对象,多次调用hashCode方法,要保证获取到的哈希值是相同的
    2.Object类中的hashCode方法,根据系统资源计算一个哈希值(int数字),所以只要new创建对象,获取到的哈希值就是不同的
    3.如果自己定义了的类,没有覆盖重写Object类中的hashCode方法,根据系统资源计算一个哈希值(int数字),所以只要new创建对象,获取到的哈希值就是不同的
    4.根据对String的测试,发现String类覆盖重写了Object类中的hashCode方法,根据字符串内容按照一定算法(存在漏洞)获取哈希值
    假设:
        String根据每个字符的ASCII码值,简单相加获取哈希值

        "abc"   的 哈希值       97 + 98 + 99 = 294
        "cab"   的 哈希值       99 + 97 + 98 = 294
    总结:
        1.哈希值不同,能否说明内容一定不同?
            肯定的,必须的
        2.哈希值相同,能否说明内容一定相同?
            不能的
                继续调用equals方法
                    返回false: 内容不相同
                    返回true: 内容相同
改口:
    以前调用toString方法,说返回的是对象的地址值
    但本质是对象的哈希值
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
public class Demo04HashCode {
    public static void main(String[] args) {
        Object obj1 = new Object();
        int h1 = obj1.hashCode();
        int h2 = obj1.hashCode();
        System.out.println(h1);//1922154895
        System.out.println(h2);//1922154895

        Object obj2 = new Object();
        int h3 = obj2.hashCode();
        System.out.println(h3);//883049899

        System.out.println(obj1.toString());//java.lang.Object@7291c18f
        System.out.println(obj2.toString());//java.lang.Object@34a245ab

        //字符数组
        char[] chs = {'a','b','c'};

        //把字符数组转换成字符串
        String s1 = new String(chs);
        String s2 = new String(chs);
        System.out.println(s1.hashCode());
        System.out.println(s2.hashCode());

        System.out.println("重地".hashCode());//96354
        System.out.println("通话".hashCode());//96354
    }
}

3.4 String的哈希值算法

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
String的哈希值算法
    String内部是字符数组
    String s = "abc";
    String内部的字符数组 char[] value = {'a','b','c'}
    String 的hashCode方法:

    public int hashCode() {
        int h = hash;//hash是String的int类型成员变量,默认值0
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {//遍历String内部的字符数组
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

    h = 31 * 0 + 97 = 97

    h = 31 * 97 + 98 = 3105

    h = 31 * 3105 + 99 = 96354
public class Demo05StringHashCode {
    public static void main(String[] args) {
        String s = "abc";
        System.out.println(s.hashCode());//96354
    }
}

3.5 哈希表的结构

1601130037185

3.6 HashSet存储元素和去重原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
    HashSet集合存储元素的过程
        1.计算哈希值,使用哈希值%数组长度,计算在数组中存储的索引
        2.判断该索引下是否有元素
        3.没有元素: 直接存储
        4.如果有元素:
            调用equals方法
            true: 不存储
            false: 存储

    HashSet集合保证元素唯一: 依赖hashCode方法和equals方法
    要求:
        HashSet集合存储对象所属的类要覆盖重写hashCode方法和equals方法
 */

前面我们学习了HashSet存储元素的原理，依赖于两个方法：

要想保证在HashSet集合中没有重复元素，我们需要重写元素类的hashCode和equals方法。

一个是hashCode方法用来确定在底层数组中存储的位置，

另一个是用equals方法判断新添加的元素是否和集合中已有的元素相同。

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
/*
    练习 hashset去重
 */
public class Testqownfoq {

    public static void main(String[] args) {
        // 1: 创建集合
        HashSet<String> set = new HashSet<>();

        String s = "ab";
        String s1 = "abc";
        String s2 = "c";
        String s3 = s+s2;
        String s4 = new String("abc");
        String s5 = "ab"+"c";
        set.add(s1);
        set.add(s3);
        set.add(s4);
        set.add(s5);

        System.out.println(s1.hashCode()); //96354
        System.out.println(s3.hashCode()); //96354
        System.out.println(s4.hashCode()); //96354
        System.out.println(s5.hashCode()); //96354

        System.out.println(set); //[abc]
    }
}

比如以下面的Student类为例，假设把Student类的对象作为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
public class Student {
    private String name;
    private int age;

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", 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;
    }

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("equals执行了......");
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Student student = (Student) o;

        if (age != student.age) return false;
        return Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }
}

接着，写一个测试类，往HashSet集合中存储Student对象。

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
public class MyHashSet3 {
    public static void main(String[] args) {
        // 1: 创建集合
        HashSet<Student> set = new HashSet<>();

        Student s1 = new Student("张三",18);
        Student s2 = new Student("张三",18);
        Student s3 = new Student("李四",19);
        Student s4 = new Student("王五",19);
        Student s5 = new Student("张三",18);

        System.out.println(s1.hashCode()); //24021577
        System.out.println(s2.hashCode()); //24021577
        System.out.println(s3.hashCode()); //26103910
        System.out.println(s4.hashCode()); //29049034
        System.out.println(s5.hashCode()); //24021577

        set.add(s1);
        set.add(s2);
        set.add(s3);
        set.add(s4);
        set.add(s5);

        System.out.println(set);

    }
}

打印结果如下，我们发现存了两个蜘蛛精，当时实际打印出来只有一个，而且是无序的。

1
2
3
4
5
6
7
8
9
10
/**
        //24021577
        //24021577
        //26103910
        //29049034
        //24021577
         * equals执行了......
         * equals执行了......
         * [Student{name='王五', age=19}, Student{name='张三', age=18}, Student{name='李四', age=19}]
         */

1601130808210

HashSet集合底层是基于哈希表实现的，哈希表根据JDK版本的不同，也是有点区别的

  • JDK8以前：哈希表 = 数组+链表
  • JDK8以后：哈希表 = 数组+链表+红黑树

null

超过16 x 0.75 = 12 扩容

我们发现往HashSet集合中存储元素时，底层调用了元素的两个方法：

一个是hashCode方法获取元素的hashCode值（哈希值）；

另一个是调用了元素的equals方法，用来比较新添加的元素和集合中已有的元素是否相同。

  • 只有新添加元素的hashCode值和集合中以后元素的hashCode值相同、新添加的元素调用equals方法和集合中已有元素比较结果为true, 才认为元素重复。
  • 如果hashCode值相同，equals比较不同，则以链表的形式连接在数组的同一个索引为位置（如上图所示）

在JDK8开始后，为了提高性能，当链表的长度超过8时，就会把链表转换为红黑树，如下图所示：
null

null

null

null

null

3.7 LinkedHashSet底层原理

LinkedHashSet它底层采用的是也是哈希表结构，只不过额外新增了一个双向链表来维护元素的存取顺序。如下下图所示：

null

每次添加元素，就和上一个元素用双向链表连接一下。第一个添加的元素是双向链表的头节点，最后一个添加的元素是双向链表的尾节点。

把上个案例中的集合改成LinkedList集合，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Test{
    public static void main(String[] args){
        Set<Student> students = new LinkedHashSet<>();
        Student s1 = new Student("至尊宝",20, 169.6);
        Student s2 = new Student("蜘蛛精",23, 169.6);
        Student s3 = new Student("蜘蛛精",23, 169.6);
        Student s4 = new Student("牛魔王",48, 169.6);
        
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);
        
        for(Student s : students){
            System.out.println(s);
        }
    }
}

打印结果如下

1
2
3
Student{name='至尊宝', age=20, height=169.6}
Student{name='蜘蛛精', age=23, height=169.6}
Student{name='牛魔王', age=48, height=169.6}

3.11 LinkedHashSet集合的使用

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
/*
    LinkedHashSet集合存储自定义对象
    步骤:
        1.创建标准的Student类
        2.创建LinkedHashSet集合对象,泛型: Student
        3.向建LinkedHashSet集合对象存储多个Student对象
        4.遍历输出

    LinkedHashSet集合存储元素的过程
        1.计算哈希值,使用哈希值%数组长度,计算在数组中存储的索引
        2.判断该索引下是否有元素
        3.没有元素: 直接存储
        4.如果有元素:
            调用equals方法
            true: 不存储
            false: 存储

    LinkedHashSet集合保证元素唯一: 依赖hashCode方法和equals方法
    要求:
        LinkedHashSet集合存储对象所属的类要覆盖重写hashCode方法和equals方法
    特点:
        有序,无索引,不可重复
 */

public class Demo04LinkedHashSetStudent {
    public static void main(String[] args) {
        //1.创建HashSet集合对象,泛型: Student
        LinkedHashSet<Student> set = new LinkedHashSet<>();

        //2.向建HashSet集合对象存储多个Student对象
        set.add(new Student("zs",18));
        set.add(new Student("zs",18));
        set.add(new Student("ls",38));
        set.add(new Student("ls",38));
        set.add(new Student("ww",28));
        set.add(new Student("ww",28));
        //3.遍历输出
        System.out.println(set);
    }
}

第四章 Arrays

image-20260208154525754

image-20260208154510172

扩展-集合的交集,并集,差集

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
public class Test09 {
    public static void main(String[] args) {
        // 1: 创建两个集合并添加部分测试数据
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();

        Collections.addAll(list1,1,2,5,8,3,6,9,1,5);
        Collections.addAll(list2,2,4,6,8);

        // 并集
        ArrayList<Integer> clone = (ArrayList<Integer>) list1.clone();
        clone.addAll(list2);
        System.out.println(list1);
        System.out.println(list2);
        System.out.println(clone);

        // 交集
        ArrayList<Integer> clone2 = (ArrayList<Integer>) list1.clone();
        boolean b = clone2.retainAll(list2);
        System.out.println(clone2);

        // 差集
        ArrayList<Integer> clone3 = (ArrayList<Integer>) list1.clone();
        boolean b1 = clone3.removeAll(list2);
        System.out.println(clone3);

        // 转集合
        System.out.println(new HashSet<Integer>(clone3));

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Test09_2 {
    public static void main(String[] args) {
        // 1: 验证集合是浅克隆
        ArrayList<Book> list = new ArrayList<>();
        list.add(new Book("西游记",19.7));

        ArrayList<Book>  clone = (ArrayList<Book>) list.clone();
        clone.get(0).setName("红楼梦");

        System.out.println(list);
        System.out.println(clone);
    }
}

案例

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
import java.time.LocalDateTime;
import java.util.Comparator;
import java.util.TreeSet;

/*
    社团管理的核心业务类
    1: 加入社团
    2: 退团
    3: 查看指定的团的团员信息
    4: 查看多个社团的全部人员
    5: 查看社团的死忠粉
    6: 查看卷王


    查询信息的时候,按入团时间升序排序

 */
public class Manager {

    private Comparator<TuanYuan> bj = new Comparator<TuanYuan>() {
        @Override
        public int compare(TuanYuan o1, TuanYuan o2) {
            int i = o1.getJoinDate().compareTo(o2.getJoinDate());
            return i == 0 ? o1.getName().compareTo(o2.getName()) : i;
        }
    };

    // 准备两个社团
    private TreeSet<TuanYuan> engs = new TreeSet<>(bj);
    private TreeSet<TuanYuan> maths = new TreeSet<>(bj);


    public void showMenu() {
        System.out.println("----------------欢迎进入社团系统---------------");
        while (true) {
            System.out.println("请选择要执行的功能:");
            System.out.println("1: 入团");
            System.out.println("2: 退团");
            System.out.println("3: 查看指定的团的团员信息");
            System.out.println("4: 查看所有社团的全部团员信息");
            System.out.println("5: 查看社团的死忠粉");
            System.out.println("6: 查看卷王");
            System.out.println("0: 退出系统");
            int i = MyScannerUtils_v2.getInt();
            switch (i) {
                case 1 -> add();
                case 2 -> del();
                case 3 -> showTy();
                case 4 -> showAll();
                case 5 -> showSz();
                case 6 -> showJw();
                case 0 -> {
                    System.out.println("拜拜");
                    return;
                }
                default -> System.out.println("输入有误,请重新输入!");
            }
        }
    }

    private void showJw() {

    }

    private void showSz() {
        TreeSet<TuanYuan> clone = (TreeSet<TuanYuan>) engs.clone();
        TreeSet<TuanYuan> clone2 = (TreeSet<TuanYuan>) maths.clone();
        boolean b = clone.removeAll(clone2);
        System.out.println("英语团的死忠粉是:"+clone);
        clone2.removeAll(engs);
        System.out.println("数学团的死忠粉是:"+clone2);

    }

    private void showAll() {
        // 展示全部的人员
        TreeSet<TuanYuan> clone = (TreeSet<TuanYuan>) engs.clone();
        TreeSet<TuanYuan> clone2 = (TreeSet<TuanYuan>) maths.clone();
        clone.addAll(clone2);
        for (TuanYuan yuan : clone) {
            System.out.println(yuan);
        }
    }

    private void showTy() {
        System.out.println("请选择要查看的团:");
        System.out.println("1: 英语社团");
        System.out.println("2: 数学社团");
        int i = MyScannerUtils_v2.getInt();
        switch (i){
            case 1 -> {
                for (TuanYuan eng : engs) {
                    System.out.println(eng);
                }
            }
            case 2 -> System.out.println(maths);
            default -> System.out.println("有误");
        }
    }

    private void del() {
        System.out.println("请输入您的姓名:");
        String name = MyScannerUtils_v2.getString();
        // 分别从两个团中找对应的对象,并删除
        TuanYuan tuanYuan = findTyByName(name);
        if(tuanYuan == null){
            System.out.println("您不在任何社团中...");
        }else {
            engs.remove(tuanYuan);
            maths.remove(tuanYuan);
            System.out.println("退团成功!");
        }

    }

    public TuanYuan findTyByName(String name){
        for (TuanYuan eng : engs) {
            if(eng.getName().equals(name)){
                return eng;
            }
        }
        for (TuanYuan math : maths) {
            if(math.getName().equals(name)){
                return math;
            }
        }
        return null;
    }


    private void add() {
        System.out.println("请输入您的姓名:");
        String name = MyScannerUtils_v2.getString();
        System.out.println("请选择要入的团:");
        System.out.println("1: 英语社团");
        System.out.println("2: 数学社团");
        int i = MyScannerUtils_v2.getInt();
        if (i == 1) {
            boolean b = engs.add(new TuanYuan(name, LocalDateTime.now()));
            if (b) {
                System.out.println("英语社团欢迎您:" + name);
            } else {
                System.out.println("亲,您已经在社团了,别瞎搞!");
            }
        } else if (i == 2) {
            boolean b = maths.add(new TuanYuan(name, LocalDateTime.now()));
            if (b) {
                System.out.println("数学社团欢迎您:" + name);
            } else {
                System.out.println("亲,您已经在社团了,别瞎搞!");
            }
        } else {
            System.out.println("输入有误");
        }
    }
}

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
import java.util.Scanner;

/*
    在java的scanner的基础上,再次封装,解决键盘输入的数据不合法的问题,及nextLine丢失键盘输入的机会的问题
 */
public  class MyScannerUtils_v2 {
    private static  Scanner sc = new Scanner(System.in);
    private MyScannerUtils_v2(){

    }
    // 提供静态方法,让调用者直接使用
    public static int getInt(){
        // 让用户循环输入,直到输入整数为止
        while (true){
            try {
                String s = sc.nextLine();
                return Integer.parseInt(s);
            } catch (Exception e) {
                // 把残留在内存中的不是整数的数据"吃掉"
                System.out.println("请务必输入整数.....");
            }
        }
    }
    public static double getDouble(){
        // 让用户循环输入,直到输入整数为止
        while (true){
            try {
                String s = sc.nextLine();
                return Double.parseDouble(s);
            } catch (Exception e) {
                // 把残留在内存中的不是整数的数据"吃掉"
                System.out.println("请务必输入小数.....");
            }
        }
    }
    public static String getString(){
        return sc.nextLine();
    }

}

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
import java.time.LocalDateTime;
import java.util.Date;

/*
    社团的成员对象

    名称
    入团时间


 */
public class TuanYuan {
    private String name;
    private LocalDateTime joinDate;

    @Override
    public String toString() {
        return "团员:"+name+",入团时间是:"+joinDate;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public LocalDateTime getJoinDate() {
        return joinDate;
    }

    public void setJoinDate(LocalDateTime joinDate) {
        this.joinDate = joinDate;
    }

    public TuanYuan(String name, LocalDateTime joinDate) {
        this.name = name;
        this.joinDate = joinDate;
    }
}

1
2
3
4
5
6
public class Test {
    public static void main(String[] args) {
        new Manager().showMenu();
    }
}