Java基础之HashSet和TreeSet

单列集合

Collection是单列集合的根接口

Collection有两个重要的子接口，分别是List和Set

Set集合的特点

无序：元素存入和取出的顺序无法保证一致性

不重复：重复的元素不会被存入

无索引：集合中没有索引，无法通过索引操作元素
(因为无索引，只能是迭代器，增强for遍历)

HashSet

HashSet集合会默认根据对象的地址去除重复

如果需要根据属性去重，需要重写元素的hashCode和equals方法

HashSet底层结构

HashSet的底层使用了哈希表存储元素

哈希表

哈希表也叫散列表，常用数组+链表实现，元素根据哈希值计算在哈希表（数组）中的存储位置

如果元素出现哈希冲突（在哈希表中存储位置相同），则采用链表挂载元素。

哈希值

哈希值代表对象的某种特征，使用int整数表示。

Object类中提供了hashCode()方法，可以根据对象的内存地址计算出哈希值。

Java类可以重写hashCode()方法，自定义哈希值的计算规则。

元素添加流程

1.先调用元素的hashCode()方法，计算出在数组中的位置

2.如果存储位置为空，直接存入元素

3.如果存储位置不为空，调用equals方法进行比较和该位置的所有元素逐一比较，如果为true，表示要存入的元素已经存在，元素将不再重复添加。

扩容机制

优化方式：将数组变长

哈希数组的默认初始长度为16

当存储元素个数超过阈值时，进行扩容（阈值 = 数组长度 * 扩容因子）

扩容因子默认是0.75，超过阈值进行扩容，每次扩容为原先的2倍

扩容是为了降低哈希冲突，以便缩短链表的长度，提高元素比较和查找的性能。

树化

优化方式：链表进行树化

从JDK8开始，哈希表优化为数组+链表+红黑树实现。

当某个链表元素超过8个，并且数组长度>=64，链表会转为红黑树进行存储。

树化的目的和扩容一样，也是为了提高元素比较和查找的能力。

TreeSet集合特点

TreeSet是Set接口下的集合

元素无索引，不重复

TreeSet集合会自动对元素进行排序

排序规则

元素为数字时，默认按照升序排序。

元素为字符串时，按照字符的编码值升序排序。

如果元素为自定义类型，需要指定排序规则。

public static void main(String[] args) {
        //升序
        TreeSet<Integer> set = new TreeSet<>();
        set.add(1);
        set.add(7);
        set.add(5);
        set.add(2);
        set.add(9);

        //按字符的编码值排序，若首字母相同，则比较第二位，依次类推
        TreeSet<String> set1 = new TreeSet<>();
        set1.add("abc");
        set1.add("bbb");
        set1.add("aaa");
        set1.add("好");
        set1.add("大家");

        //字符转int查看编码值
        System.out.println((int)'黑');

        for (Integer i :
                set) {
            System.out.println(i);
        }

        for (String s :
                set1) {
            System.out.println(s);
        }
    }
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

Comparable

存自定义数据

public class Student {
    private String name;
    private int age;

    public Student() {
    }

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

    /**
     * 获取
     * @return name
     */
    public String getName() {
        return name;
    }

    /**
     * 设置
     * @param name
     */
    public void setName(String name) {
        this.name = name;
    }

    /**
     * 获取
     * @return age
     */
    public int getAge() {
        return age;
    }

    /**
     * 设置
     * @param age
     */
    public void setAge(int age) {
        this.age = age;
    }

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


}
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

自定义的数据不具备比大小的能力，必须去实现 Comparable

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

    @Override
    public int compareTo(Student o) {
        //return this.age - o.age;//升序
        return o.age - this.age;//降序
    }

    public Student() {
    }

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

    /**
     * 获取
     * @return name
     */
    public String getName() {
        return name;
    }

    /**
     * 设置
     * @param name
     */
    public void setName(String name) {
        this.name = name;
    }

    /**
     * 获取
     * @return age
     */
    public int getAge() {
        return age;
    }

    /**
     * 设置
     * @param age
     */
    public void setAge(int age) {
        this.age = age;
    }

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


}
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

public static void main(String[] args) {
        Student s1 = new Student("张三", 16);
        Student s2 = new Student("李四", 3);
        Student s3 = new Student("王五", 54);

        //使用TreeSet集合保存自定义的学生对象
        //并且根据年龄进行排序
        TreeSet<Student> treeSet = new TreeSet<>();
        treeSet.add(s1);
        treeSet.add(s2);
        treeSet.add(s3);

        //会报错
        //Student cannot be cast to class java.lang.Comparable
        for (Student s :
                treeSet) {
            System.out.println(s);
        }

        //因为TreeSet集合对元素自动排序，前提是元素实现了Comparable
        //元素实现Comparable，就具备自动排序的能力


    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

在compareTo方法中，this代表当前要存入的元素；参数o代表集合已经存在的元素。

返回值整数：放在红黑树右边

返回值负数： 放在红黑树左边

返回值0： 要存入的元素重复，不存入。

使用比较器

在TreeSet的构造方法中，传入比较器对象（通常传匿名内部类）

注意不要和Comparable搞混，Comparable是元素实现这个接口（自然排序），Comparator是构造方法（比较器排序）。

public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>(new Comparator<Integer>() {
            @Override
            //Integer o1 要存入的元素
            //Integer o2 已经存在的元素
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        set.add(1);
        set.add(2);
        set.add(3);

        //默认是升序的
        //要求元素进行降序排序，可以在TreeSet的构造方法中，传入比较器对象（通常传匿名内部类）
        
        for (Integer i :
                set) {
            System.out.println(i);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Comparable 和 Comparator两种排序规则都存在时，Comparator比较器优先级更高

常见问题

public static void main(String[] args) {
        //要求降序，我们构造方法实现Comparator
        //因为返回值为int，我们相减的结果是Double类型，
        //又因为是重写不能改返回值
        //强转又会精度缺失
        TreeSet<Double> set = new TreeSet<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                Double result =  o2 - o1;
                if(result<0){
                    return  -1;
                }else if(result>0){
                    return 1;
                }else {
                    return 0;
                }
                //第二种写法
//                return Double.compare(o2 - o1);
            }
        });
        set.add(95.5);
        set.add(95.7);
        set.add(95.2);

        for (double d :
                set) {
            System.out.println(d);
        }
    }
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

最后

如果你对本文有疑问，你可以在文章下方对我留言，敬请指正，对于每个留言我都会认真查看。