HashSet（Set接口实现类）

发表于 更新于 分类于 ， 阅读次数： Valine：

HasSet说明

HasSet的底层其实调用了HasMap

1
2
3
public HashSet() {
    map = new HashMap<>();
}

Hashset可以存放null，只能存放一个

HashSet不保证元素是有序的，取决与hash后，在确定索引的结果

练习1

简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

public class Test {
    public static void main(String [] args){
        HashSet hashSet=new HashSet();
        System.out.println(hashSet.add(1));
        System.out.println(hashSet.add(1));
        System.out.println(hashSet.add(1));
        System.out.println(hashSet.add(1));
        System.out.println(hashSet.add(2));
        System.out.println(hashSet.add(3));
        System.out.println(hashSet.add(4));
        System.out.println(hashSet);
        hashSet.remove(1);
        System.out.println(hashSet);
    }
}

image-20220704181147390

进阶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Test {
    public static void main(String [] args){
        HashSet hashSet=new HashSet();
        System.out.println(hashSet.add("jack"));
        System.out.println(hashSet.add("jack"));
        System.out.println(hashSet.add(new Dog("jack")));
        System.out.println(hashSet.add(new Dog("jack")));
        System.out.println(hashSet.add(new String("rose")));
        System.out.println(hashSet.add(new String("rose")));
        System.out.println(hashSet.add("jack"));

        //new操作之后，地址不同
        System.out.println(hashSet);
    }
}
class Dog{
    String name;

    public Dog(String name) {
        this.name = name;
    }
}

image-20220704181243139

HashSet的底层机制

HashSet的底层机制是HashMap，HashMap的底层是（数组+链表+红黑树）

数组+链表：提高存储的效率

image-20220704181253005而红黑树则是数组的存储到达64时，并且链表存储到达8时，形成层次性更强的树

HasSet的扩容机制

  1. 添加一个元素的时候，会先得到hash值，根据此值转成索引值
  2. 找到存放数据的表，看这个索引值对应的位置是否已经存放元素
  3. 如果没有则直接加入，如果有则调用equals比较，如果相同，就放弃添加（这也就解释了为什么不能添加相同的元素的原因），如果不相同，则添加到最后
  4. 在java8中如果一条链表个数超过8，并且table的大小>=64,会变成红黑树
1
2
3
4
5
6
7
8
9
10
import java.util.*;

public class Test {
    public static void main(String [] args){
        HashSet hashSet=new HashSet();
        hashSet.add("java");
        hashSet.add("lili");
        hashSet.add("java");
    }
}

在debug的模式下尝试第一次add，首先进入add方法

image-20220704181309618调用put方法，value是一个占位符，用于满足hashmap的方法

image-20220704181321325而这里的算法得到的值是将key.hashcode右移16位

image-20220704181334435而我们第一刺进putVal方法时，此时的table[]为空，调用resize方法进行扩容为16位，同时该方法也会检测table数组的使用是否达到了12（16*加载因子（0.75）)位，如果达到，就再一次进行扩容达到32，而检测是树也达到了24

image-20220704181410967

image-20220704181525397

而当我们进行第二次扩容，经过内置的算法计算出lili应该放在8号索引位置，步骤与上述的相同

image-20220704181438068但是当我们进行第三次扩容时，由于加入相同的字符串对象，算法算出的hash值相等，得出同样都在3的索引位置，然后进行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
import java.util.*;

public class Test {
    public static void main(String [] args){
        String str1="jack";
        String str2="jack";
        String str3=new String("lili");
        String str4=new String("lili");
        Dog dog1=new Dog("as");
        Dog dog2=new Dog("as");
        System.out.println(str1.hashCode());
        System.out.println(str2.hashCode());
        System.out.println(str3.hashCode());
        System.out.println(str4.hashCode());
        System.out.println(dog1.hashCode());
        System.out.println(dog2.hashCode());
    }
}
class Dog{
    String name;

    public Dog(String name) {
        this.name = name;
    }
}

image-20220704181543608所以说hashset能否允许新元素的加入，key.hashCode()决定了它在数组的索引位置，而最终的比较还需要看equals方法的定义，当然在比较的过程中系统调用了equals方法，程序员也可以自己定义重写equals方法，改变比较的规则，比较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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.*;

public class Test {

    public static void main(String [] args){

        String str1="jack";
        String str2="jack";
        String str3=new String("lili");
        String str4=new String("lili");
        Dog dog1=new Dog("as");
        Dog dog2=new Dog("as");
        System.out.println(str1.hashCode());
        System.out.println(str2.hashCode());
        System.out.println(str3.hashCode());
        System.out.println(str4.hashCode());
        System.out.println(dog1.hashCode());
        System.out.println(dog2.hashCode());
        HashSet hashSet=new HashSet();
        hashSet.add(dog1);
        hashSet.add(dog2);
        hashSet.add(str1);
        hashSet.add(str2);
        hashSet.add(str3);
        hashSet.add(str4);
        System.out.println(hashSet);
    }
}
class Dog{
    String name;

    public Dog(String name) {
        this.name = name;
    }

    @Override
    public int hashCode(){
        return 100;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {return true;}
        if (o == null || getClass() != o.getClass()) {return false;}
        Dog dog = (Dog) o;
        return Objects.equals(name, dog.name);
    }
}

image-20220704181952021练习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
import java.util.HashSet;
import java.util.Objects;

public class Test {
    public static void main(String[] args) {
        HashSet hashSet=new HashSet();
        hashSet.add(new E("DSC","12"));
        hashSet.add(new E("DSC","12"));
        hashSet.add(new E("DSC","12"));
        System.out.println(hashSet);
    }
}
class E{
    String name;
    String age;

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

    /*@Override
    public boolean equals(Object obj){
        if (obj==null){
            retur
        }
    }*/
    //比较两个的值是否相同

    @Override
    public boolean equals(Object o) {
        if (o==this){
            return true;
        }
        E e=(E) o;
        if (Objects.equals(age,e.age)&&Objects.equals(name,e.name)){
            return true;
        }
        else{return  false;}
    }
//将所有员工放入到一个数组格格中
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

image-20220704182022266练习2

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
import java.time.LocalDate;
import java.util.HashSet;
import java.util.Objects;

public class Test {
    public static void main(String[] args) {
        LocalDate localDate1= LocalDate.parse("2021-02-03");
        Employee employee1=new Employee("阿硕",12,localDate1);
        LocalDate localDate2= LocalDate.parse("2021-02-03");
        Employee employee2=new Employee("阿硕",12,localDate2);
        HashSet hashSet=new HashSet();
        hashSet.add(employee1);
        hashSet.add(employee2);
        System.out.println(hashSet.toString());
    }
}
class Employee{
    String name;
    int age;
    LocalDate birthday;

    public Employee(String name, int age, LocalDate birthday) {
        this.name = name;
        this.age = age;
        this.birthday = birthday;
    }
    @Override
    public int hashCode(){
        return Objects.hash(name,birthday);
    }
    @Override
    public boolean equals(Object o){
        if (o==this){
            return true;
        }
        Employee employee=(Employee) o;
        if (Objects.equals(this.birthday,employee.birthday)&&Objects.equals(this.name,employee.name)){
            return true;
        }
        else {
            return false;
        }
    }

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

image-20220704182104594练习3

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

public class Test {
    public static void main(String[] args) {
        Person p1=new Person("花花","12");
        Person p2=new Person("猫猫","25");
        HashSet hashSet=new HashSet();
        hashSet.add(p1);
        hashSet.add(p2);
        System.out.println(p1.hashCode());
        p1.name="ahua";
        System.out.println(p1.hashCode());
        System.out.println(hashSet);
        System.out.println(hashSet.remove(p1));
        System.out.println(hashSet);
    }
}
class Person{
    public String name;
    public String id;

    public Person(String name, String id) {
        this.name = name;
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Person person = (Person) o;
        return Objects.equals(name, person.name) && Objects.equals(id, person.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }

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

image-20220704182141502