JavaSE进阶——Day06 TreeSet、排序查找算法、Map集合、集合嵌套

发表于 更新于 分类于 阅读次数： Changyan： 本文字数： 1.3k 阅读时长 ≈ 5 分钟

JavaSE进阶——Day06 该篇主要讲解Java中的TreeSet集合、排序查找算法、Map集合

整体框架

Collection（接口）

Collection(接口).png)

泛型：

1
2
//在开发中使用泛型最多的就是：创建集合时使用泛型约束所存储元素的类型
List<Student> studentList = new ArrayList<>();

Set集合（续）

TreeSet

知识点：

  • 具有对所存储元素进行排序的功能
  • TreeSet集合存储：String、Interger、Double、Character时，JDK已经默认实现了java.lang.Comparable接口（即自带自然排序）
  • TreeSet集合存储：自定义类型（自己写的）
    • 必须保证自定义类型有实现java.lang.Comparable接口，并重写CompareTo方法
    • 如果自定义类型未实现该接口，在存储到TreeSet集合中时，会引发异常

compareTo方法：

1
2
3
4
5
6
//比较大小：  0表示相同  、 负数表示小    正数表示大
public int compareTo(E e){ 
    自然排序规则
    
    //返回值有三种： 正数 、 负数 、 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
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
package io.github.ethanliu6.set;

import java.util.TreeSet;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 00:07
 * @Project JavaCode_SE_Advance
 * @Theme TreeSet集合
 */
public class TreeSetDemo2 {
    //使用TreeSet集合存储自定义对象
    public static void main(String[] args) {
        //创建集合对象
        TreeSet<Student> set = new TreeSet<>();

        //添加元素
        set.add(new Student("Ethan", 21));
        set.add(new Student("Qiu", 21));
        set.add(new Student("Liu", 21));
        set.add(new Student("Qiu", 20));
        set.add(new Student("Qiu", 20)); //这种匿名对象在这也会去重
        set.add(new Student("Qiu", 18));
        set.add(new Student("qiu", 22));

        for (Student student : set) {
            System.out.println(student);
        }
    }
}

class Student implements Comparable<Student>{
    private String name;
    private int age;

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

    public Student() {
    }

    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 int compareTo(Student stu) {
        //先按照姓名排序,姓名相同再按照年龄排序

        //this: 当前对象
        //stu: 传递过来的对象

        //String类本身实现Comparable接口, 并重写了compareTo方法
        //即: String类自带自然排序
        int result = this.name.compareTo(stu.name);
        if (result==0){
            result = this.age - stu.age;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int compareTo(Student2 student) {
    //先按照age排序,age相同再按照name排序

    //this: 当前对象
    //stu: 传递过来的对象

    //String类本身实现Comparable接口, 并重写了compareTo方法
    //即: String类自带自然排序
    int res = this.age - student.age;
    if (res == 0) {
        res = this.name.compareTo(student.name);
    }
    return res;
}

更换排序方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int compareTo(Student2 student) {
    //先按照age排序,age相同再按照name排序

    //this: 当前对象
    //stu: 传递过来的对象

    //String类本身实现Comparable接口, 并重写了compareTo方法
    //即: String类自带自然排序
    int res = this.age - student.age;
    if (res == 0) {
        res = this.name.compareTo(student.name);
    }
    return res;
}

二叉树

知识点

javascript 二叉树(Trees)算法与说明_二叉树算法详解 js-CSDN博客

  • 以根节点为坐标，小于根节点的数据存储在左边，大于根节点的数据存储在右边

二叉查找树

  • 小左大右

平衡二叉树

  • 树子节点之间的深度差不大于1

  • 使用旋转算法

红黑树

（补充）

比较器

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
package io.github.ethanliu6.set;

import java.util.Comparator;
import java.util.TreeSet;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 15:24
 * @Project JavaCode_SE_Advance
 * @Theme Comparator接口实现比较器
 */
public class TreeSetDemo4 {
    /*
    按照字符串长度从大到小排序, 长度相同按照字母顺序排序
     */
    public static void main(String[] args) {
        //在创建TreeSet集合时, 制定了排序规则
        TreeSet<String> set = new TreeSet<>(new MyComparator());

        //String类本身具有自然排序规则
        set.add("asdfvd");
        set.add("word");
        set.add("implenemts");
        set.add("myblog");

        System.out.println(set);
    }
}

//创建子类, 实现Comparator接口
class MyComparator implements Comparator<String>{

    //重写compare方法
    @Override
    public int compare(String str1, String str2) {
        //str1: 要存储的字符串数据
        //str2: 已存在的字符串数据
        int res = str2.length() - str1.length();
        if (res == 0){
            res = str1.compareTo(str2);
        }
        return res;
    }
}

使用匿名内部类实现比较器

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
package io.github.ethanliu6.set;

import java.util.Comparator;
import java.util.TreeSet;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 15:44
 * @Project JavaCode_SE_Advance
 * @Theme Comparator接口: 匿名内部类自定义排序
 */
public class TreeSetDemo5 {

    //按照年龄从小到大排序, 年龄相同,按照名字顺序从小到大排序
    public static void main(String[] args) {
        //创建TreeSet集合，并指定比较器排序规则
        //无需再构建子类继承和重写,直接使用匿名内部类重写
        TreeSet<Teacher> teacherTreeSet = new TreeSet<>(new Comparator<Teacher>() {
            @Override
            public int compare(Teacher teacher1, Teacher teacher2) {
                int res = teacher1.getAge() - teacher2.getAge();
                if (res == 0) {
                    res = teacher1.getName().compareTo(teacher2.getName());
                }
                return res;
            }
        });

        teacherTreeSet.add(new Teacher("ethan", 21));
        teacherTreeSet.add(new Teacher("ethan", 25));
        teacherTreeSet.add(new Teacher("qiu", 21));
        teacherTreeSet.add(new Teacher("qiu", 22));
        teacherTreeSet.add(new Teacher("ethan", 25));

        for (Teacher teacher : teacherTreeSet) {
            System.out.println(teacher);
        }
    }
}

class Teacher {
    private String name;
    private int age;

    @Override
    public String toString() {
        return "Teacher{" +
                "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 Teacher(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Teacher() {
    }
}

可变参数

  • 可变参数只能放在参数列表最后面
  • 可变参数本质就是数组, 所以方法重载上不能够用数组格式写相同的, 如下面的int… 就不能再出现int[]

基本使用

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
package io.github.ethanliu6.genericity.changeable_param;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 16:21
 * @Project JavaCode_SE_Advance
 * @Theme 可变参数
 */
public class ChangeParamDemo1 {
    public static void main(String[] args) {
        int res = numSum("nums", 1, 2, 3, 5, 7);
        System.out.println(res);
    }

    //可变参数只能放在参数列表最后面
    //可变参数本质就是数组, 所以方法重载上不能够用数组格式写相同的, 如下面的int... 就不能再出现int[]
    public static int numSum(String sNum, int... nums) {
        int sum = 0;

        //把可变参数当作数组使用
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return sum;
    }
}

带有泛型的可变参数

例如Collections类的addAll方法

image-20240421164429521

案例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package io.github.ethanliu6.genericity.changeable_param;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 16:35
 * @Project JavaCode_SE_Advance
 * @Theme 带有泛型的可变参数
 */
public class Demo2 {
    public static void main(String[] args) {
        //生成List集合对象
        List<String> list = new ArrayList<>();

        //带有泛型<String>的可变参数
        Collections.addAll(list, "Java", "MySql", "Ethan", "Qiu");

        System.out.println(list); //[Java, MySql, Ethan, Qiu]
    }
}

排序查找算法

冒泡排序

  • 原理：相邻的数据两两比较，小的放前，大的放后

  • 轮次：长度-1

  • 每轮：每轮减少一个（已排序/已冒泡的）

代码：

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
package io.github.ethanliu6.genericity.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 16:57
 * @Project JavaCode_SE_Advance
 * @Theme 冒泡排序
 */
public class BubbSort1 {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();

        //使用泛型可变参数添加集合数据
//        Collections.addAll(list, 4, 6, 2, 8, 1, 5, 9, 4, 3);
        Collections.addAll(list, 1, 2, 3, 4, 5, 5, 9, 4, 3);
        System.out.println("排序前:" + list);
        bullSort(list);
        System.out.println("排序后:" + list);
    }

    //冒泡排序算法
    public static List<Integer> bullSort(List<Integer> list) {

        if (list.size() == 0) {
            return list;
        }
        for (int i = 0; i < list.size() - 1; i++) { //轮次
            //优化
            boolean flag = false; //记录排序后状态
            for (int j = 0; j < list.size() - i - 1; j++) { //每轮比较对象
                if (list.get(j) > list.get(j + 1)) { //相邻数据进行比较
                    int temp = list.get(j + 1);
                    list.set(j + 1, list.get(j));
                    list.set(j, temp);
                    flag = true; //说明发生过变化
                }
            }
            // 如果一轮比较中没有发生交换，说明已经排序完成
            if (!flag) {
                break;
            }
        }
        return list;
    }
}

选择排序

  • 原理：拿当前元素与其后面的所有元素进行比较，如果有比当前元素小的，就跟当前元素交换位置，直到所有元素比较完

  • 轮次：长度-1

  • 每轮：从当前元素之后一个开始，每轮减少一个即前一轮已排好的

代码：

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
package io.github.ethanliu6.genericity.sort;

import java.util.Arrays;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 17:34
 * @Project JavaCode_SE_Advance
 * @Theme 选择排序
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] nums = {2, 6, 3, 5, 1, 7};
        System.out.println("排序前:" + Arrays.toString(nums));
        selectSort(nums);
        System.out.println("排序后:" + Arrays.toString(nums));
    }

    private static int[] selectSort(int[] nums) {
        if (nums == null) {
            return nums;
        } else {
            for (int i = 0; i < nums.length - 1; i++) { //轮次
                for (int j = i + 1; j < nums.length; j++) { //与后面所有元素比
                    if (nums[i] > nums[j]) {
                        int temp = nums[j];
                        nums[j] = nums[i];
                        nums[i] = temp;
                    }
                }
            }
        }
        return nums;
    }
}

二分查找

  • 原理：定义头和尾（小—>大），每次选择中值并与头尾比较，中值小换头、大换尾，直到头尾相交

  • 前提：数组元素有序

  • 每轮：元素减半

代码：

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
package io.github.ethanliu6.genericity.sort;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 17:51
 * @Project JavaCode_SE_Advance
 * @Theme 二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        //前提是数组有序
        int[] nums = {1, 2, 3, 5, 6, 7};
        System.out.println(binarySearch(nums, 6));
        System.out.println(binarySearch(nums, 4));
    }

    private static int binarySearch(int[] arr, int num) {
        int left = 0;
        int right = arr.length - 1;
        int mid = (left + right) / 2;

        while (left <= right) { //查找非终止条件
            if (arr[mid] > num) {
                right = mid - 1;
            }else if (arr[mid] < num) {
                left = mid + 1;
            }
            else {
                return mid;
            }
            mid = (left + right) / 2;
        }
        return -1; //找不到返回-1
    }
}

Map结合

map集合的特点：

  1. 可以存储两个元素（键值对元素）
  2. key元素不能重复， value元素允许重复
  3. 一个key元素只能对应一个value元素（一一对应）//通过key可以找到value
  4. 存取元素不保证顺序
  5. 没有索引

java.util.Map（接口）

  • HashMap：底层使用哈希表
  • LinkedHashMap：底层使用哈希表+链表
  • TreeMap：底层使用红黑树

Map集合遍历方式：

Map集合不能直接遍历（只能间接性实现遍历操作）

  1. 键找值

    • 获取Map集合中所有的key元素，遍历所有的key元素，通过key元素找到对应的value元素
    1
    Set  存储所有key的Set集合对象 =  map集合.keySet();

    例：

    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
    package io.github.ethanliu6.map;

    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Map;
    import java.util.Set;

    /**
     * @Author EthanLiu 16693226842@163.com
     * @Date 2024/4/21 19:11
     * @Project JavaCode_SE_Advance
     * @Theme 遍历键去找值
     */
    public class MapDemo2 {
        public static void main(String[] args) {
            //创建Map集合对象
            Map<String, String> map = new HashMap<>();

            //添加集合中的元素
            map.put("爱辉", "珠珠");
            map.put("小刚", "小卢");
            map.put("小谭", "不认识");
            map.put("阿子", "没有");

            //遍历键去找值
            Set<String> keys = map.keySet();  // 获取集合所有key
            for (String key : keys) {
                System.out.println("Key=" + key + "\t Values=" + map.get(key) /* 键找值 */);
            }
        }
    }

  1. 键值对

    • 获取Map集合中所有的Map.Entry， 遍历所有的Map.Entry，通过Entry中的API方法获取到key、value
    1
    2
    3
    4
    5
    Set<Map.Entry>  存储所有键值对对象的Set集合对象 =  map集合.entrySet();

    Map.Entry：
        Object  getKey()
        Object  getValue()

    例：

    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
    package io.github.ethanliu6.map;

    import java.util.HashMap;
    import java.util.Map;
    import java.util.Set;

    /**
     * @Author EthanLiu 16693226842@163.com
     * @Date 2024/4/21 19:11
     * @Project JavaCode_SE_Advance
     * @Theme 键值对找键值
     */
    public class MapDemo3 {
        public static void main(String[] args) {
            //创建Map集合对象
            Map<String, String> map = new HashMap<>();

            //添加集合中的元素
            map.put("爱辉", "珠珠");
            map.put("小刚", "小卢");
            map.put("小谭", "不认识");
            map.put("阿子", "没有");
    				
           //获取所有的键值对对象
            Set<Map.Entry<String, String>> set = map.entrySet();
           //遍历每个键值对对象并获取键和值
            for (Map.Entry<String, String> stringStringEntry : set) {
                System.out.println("keys=" + stringStringEntry.getKey() +"\t" +
                                   "values=" + stringStringEntry.getValue());
            }
        }
    }

HashMap存储自定义对象（key）

在Map集合中当key存储的是自定义对象时，要保证对象存储数据的唯一性，需要：自定义对象中重写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
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
package io.github.ethanliu6.map;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 19:41
 * @Project JavaCode_SE_Advance
 * @Theme HashMap存储自定义对象（key）
 */
public class MapDemo4 {
    public static void main(String[] args) {
        //创建Map集合对象(存储自定义对象)
        Map<Student, String> studentMap = new HashMap<>();
        studentMap.put(new Student("Ethan", 21), "甘肃");
        studentMap.put(new Student("QiuZhu", 21), "广西");
        studentMap.put(new Student("Ethan", 21), "广西"); //去重后这里相当于修改

        //使用Map.Entry获取键值对对象
        Set<Map.Entry<Student, String>> entries = studentMap.entrySet();

        //遍历键值对对象
        for (Map.Entry<Student, String> entry : entries) {
            System.out.println(entry.getKey() + "\tPlace--" + entry.getValue());
        }

        //为了去重,我们还需要重写HashCode和equals方法
        // Student{name='Ethan', age=21}	Place--广西
        // Student{name='QiuZhu', age=21}	Place--广西

    }
}

class Student {
    private String name;
    private int 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);
    }

    @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;
    }

    public Student() {
    }
}

LinkedHashMap集合

  • 有序：链表
  • 去重：Hash

代码略

TreeMap集合

  • 特点：存储的key元素，会按照指定规则排序
    • 排序方式：
      1. 自然排序： 元素自身实现Comparable接口
      2. 比较器排序：在创建集合对象时，指定比较器（需要重写Comparator接口的compare方法）
1
2
3
4
TreeMap<String,String> map = new TreeMap<>(); //String类要具备自然排序
TreeMap<Student,String> map = new TreeMap<>();//Student类要具备自然排序

TreeMap<Student,String> map = new TreeMap<>( Comparator对象 );//指定比较器对象

image-20240421204029945

例：

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
package io.github.ethanliu6.map;

import java.util.*;

/**
 * @Author EthanLiu 16693226842@163.com
 * @Date 2024/4/21 20:19
 * @Project JavaCode_SE_Advance
 * @Theme TreeMap集合
 */
public class TreeMapDemo {
    public static void main(String[] args) {
        //创建TreeMap集合对象
        //TreeMap<Student, String> treeMap = new TreeMap<>();
        //重写Comparator接口
        TreeMap<Student, String> treeMap = new TreeMap<>(new Comparator<Student>() {
            @Override
            public int compare(Student stu1, Student stu2) {
                //先按年龄小到大排, 再按字母从小到大排
                int res = stu1.getAge() - stu2.getAge();
                //if(res == 0){
                //    res = stu1.getName().compareTo(stu2.getName());
                //}
                return res == 0 ? stu1.getName().compareTo(stu2.getName()) : res;
            }
        });

        //添加自定义类型元素
        treeMap.put(new Student("Ethan", 21), "甘肃");
        treeMap.put(new Student("QiuZhu", 21), "广西");
        treeMap.put(new Student("aihui", 18), "湖南");
        treeMap.put(new Student("qiu", 17), "广西");
        treeMap.put(new Student("aaa", 28), "四川");
        treeMap.put(new Student("Ethan", 21), "广西"); //去重后这里相当于修改

        //会有ClassCastException异常,需要重写Comparator接口
        //System.out.println(treeMap);

        //使用Map.Entry获取键值对对象
        Set<Map.Entry<Student, String>> entries = treeMap.entrySet();

        //遍历键值对对象
        for (Map.Entry<Student, String> entry : entries) {
            System.out.println(entry.getKey() + "\tPlace--" + entry.getValue());
        }
    }
}