实现Set接口的HashSet

HashSet 的底层实现实际上依赖于 HashMap，而 HashMap 的底层结构确实是 数组+链表+红黑树 的组合。

在这里插入图片描述
存储过程

计算哈希值: 当向 HashSet 添加一个元素时，首先会使用该元素的 hashCode() 方法计算其哈希值。
这个哈希值是一个整数，代表了元素在哈希表中的位置。
确定数组索引: 然后，哈希值会被进一步处理以确定元素应该存储在数组的哪个索引位置。通常，这个过程包括取模运算，例如：
int index = hashCode % array.length;
这样可以确保哈希值被转化为有效的数组索引。
处理哈希冲突: 如果两个不同的元素计算出的索引相同（即发生哈希冲突），HashSet 会在该索引位置使用链表（或在 Java 8 之后可能使用红黑树）来存储这些冲突的元素。例如，如果 A 和 B 的哈希值都映射到数组索引 2，那么 B 会被添加到 A所在链表的后面。

当向 HashSet 中添加重复的元素时，HashSet 会检测到并拒绝添加该元素。具体来说，这是通过以下几个步骤实现的：

计算哈希值: 首先，计算新元素的哈希值。
确定数组索引: 使用哈希值确定该元素应该存储在数组中的哪个索引位置。
查找冲突链表: 在确定的索引位置上，检查是否已经存在一个链表或树结构。
比较元素: 遍历链表或树结构，使用 equals 方法比较新元素和已存在的每个元素。如果发现有一个元素与新元素相等（equals方法返回 true），则认为新元素已经存在于 HashSet 中，不会将其添加。

基本使用：

package study;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class Collection_Set {
    public static void main(String[] args) {
        /*
            Iterable<E> (接口)
                   ↑
            Collection<E> (接口) - 继承自 Iterable<E>
                   ↑
            Set<E> (接口) - 继承自 Collection<E>
                   ↑
            AbstractCollection<E> (抽象类) - 部分实现 Collection<E>
                   ↑
            AbstractSet<E> (抽象类) - 继承自 AbstractCollection<E> 并部分实现 Set<E>
                   ↑
            HashSet<E> (类) - 继承自 AbstractSet<E> 并实现 Set<E> 和 Collection<E>

            HashSet 类除了实现 Set 接口的方法外，还提供了一些独有的方法。这些方法在 Set<> set 中无法直接使用:
            clone(): 创建并返回此 HashSet 的浅表副本。
            spliterator(): 创建一个后期绑定且故障迅速的 Spliterator，用于遍历此 Set 中的元素。

            HashSet 内部使用 HashMap 来存储其元素。
        */
        // TODO 集合 - Collection - Set
        // HashSet: Hash + Set
        // Hash: 哈希算法，散列算法
        // TODO 增加数据
        HashSet set = new HashSet();
//        set.add("zhangsan");
//        set.add("zhangsan");
//        set.add("lisi");
//        set.add("wangwu");
        set.addAll(Arrays.asList("zhangsan", "lisi", "wangwu"));

        Object[] array = set.toArray();
        System.out.println(array);    // 打印数组中元素的类型和哈希码
        for (Object item : array)   // 打印数组中的元素
            System.out.println(item); // 这会调用每个元素的 toString() 方法
        System.out.println(Arrays.toString(array));  // 使用 Arrays.toString() 打印数组内容
        System.out.println(set);
        // [lisi, zhangsan, wangwu]
        // 会发现打印顺序和存储顺序不一样

        // TODO 修改数据 ，先删除数据再增加

        // TODO 删除数据
        // set.remove("wangwu");

        // TODO 查询数据
        for (Object o : set) {
            System.out.println(o);
        }
        System.out.println(set.isEmpty());
        System.out.println(set.contains("lisi"));
        System.out.println(set.size());
        Object clone_set = set.clone();
        System.out.println(clone_set);

    }
}

实践任务：创建一个程序，使用HashSet去除重复的元素

package study;

import java.util.HashSet;

public class day01_Collection_Set_进阶 {
    public static void main(String[] args) {
        // 在不指定泛型类型参数时，集合类被视为原始类型，可以存储任何类型的对象，但没有编译时的类型安全保障
        HashSet set = new HashSet();

        User user1 = new User();
        user1.id = 1001;
        user1.name = "zhangsan";
        User user2 = new User();
        user2.id = 1001;
        user2.name = "zhangsan";
        User user3 = new User();
        user3.id = 1003;
        user3.name = "wangwu";

        set.add(user1);
        set.add(user2);
        set.add(user3);

        System.out.println(set);  // 只是属性指一样，HashSet并不认为user1和user2是一样的
        // [User [id=1001, name=zhangsan], User [id=1001, name=zhangsan], User [id=1003, name=wangwu]]

        System.out.println(user1.hashCode());  // 990368553 可以简单类比成对象在内存中的地址
        System.out.println(user2.hashCode()); // 1096979270

        HashSet set1 = new HashSet();
        User1 user4 = new User1();
        user4.id = 1001;
        user4.name = "zhangsan";
        User1 user5 = new User1();
        user5.id = 1001;
        user5.name = "zhangsan";
        User1 user6 = new User1();
        user6.id = 1003;
        user6.name = "wangwu";

        set1.add(user4);
        set1.add(user5);
        set1.add(user6);

        System.out.println(set1);
        // [User1 [id=1001, name=zhangsan], User1 [id=1003, name=wangwu]]


    }
}

class User {
    public int id;
    public String name;

    @Override
    public String toString() {
        return "User [id=" + id + ", name=" + name + "]";
    }
}

class User1 {
    public int id;
    public String name;

    @Override
    // 类似于内存地址
    // 如果HashCode相同，在HashSet计算元素存储的数组索引时，就会相同
    public int hashCode() {
//        return super.hashCode();
        return id;
    }

    @Override
    // 当HashSet计算元素存储的数组索引时相同，就会用这个equals函数来判断这两个元素是否相同
    public boolean equals(Object obj) {
//        return super.equals(obj);
        // instanceof 操作符用于测试一个对象是否是一个特定类的实例，或者是该类的子类的实例
        if (obj instanceof User1) {  // 保证要比较的类型相同
            User1 otherUser = (User1) obj;  //强制类型转换
            if (otherUser.id == this.id && otherUser.name.equals(this.name)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        return "User1 [id=" + id + ", name=" + name + "]";
    }
}