B站 韩顺平 老师课程的笔记

HashSet

基本介绍

  • 实现了Set接口
  • 底层实际上是HashMap，HashMap的底层机制实际上是数组+链表+红黑树（目的是高效）（也就不能再用索引了）
  • 可以存放null值，但只能有一个null
  • HashSet不保证元素是有序的，取决于hash后，再确定索引的结果
  • 不能有重复的元素/对象。实现Set接口的类的共同点

方法

在执行add方法后，会返回一个boolean值，如果添加成功，返回true，如果添加失败返回false

1
2
3
4
5
6
7
8
9
Set set = new HashSet();//底层走的是HashMap

System.out.println(set.add("john"));//true
System.out.println(set.add("lucy"));//true
System.out.println(set.add("john"));//false
System.out.println(set.add("jack"));//true
System.out.println(set.add("mary"));//true
System.out.println(set.add(null));//true
System.out.println(set.add(null));//false

这样就知道为什么set中没有重复的元素了

添加机制

先获取哈希值（hashCode()方法），对哈希值进行运算，得出一个索引值为要存放在哈希标中的位置号，如果该位置上没有其他元素，则直接存放，若该位置上已经有其他元素了就需要调用equals判断，如果相等则不再添加
如果每次添加的元素都是新的对象那一般都能加进去，不管对象内容是否一样都可以（因为是不同对象）因为比较的是对象的equals（可以重写），如果添加对象的equals相同则添加失败
如果equals相等表示可以添加，如果hashCode值相同则放在同一链表上（因为计算出来的位置索引都是一样的）
由于要用hashCode计算索引值，所以元素再HashSet中不一定是从第一个位置开始排列
一般添加对象要求不能添加相同内容的对象，那么对象的hashCode()方法就要重写，返回相同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
import java.util.HashSet;
import java.util.Set;

public class HashSetExercise {
    public static void main(String[] args) {
        Set set = new HashSet();
        set.add(new Employee("牛人",13));
        set.add(new Employee("牛逼",13));
        set.add(new Employee("牛人",13));

        System.out.println("set= " + set);
    }
}
class Employee {
    private String name;
    private int age;

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

    @Override
    public boolean equals(Object o) {
        if(this == o){
            return true;
        }
        if(o instanceof Employee){
            Employee e = (Employee) o;
            if(((Employee) o).age == this.age && ((Employee) o).name.equals(this.name)){
                return false;
            }else
                return true;
        }else
            return false;
    }

    @Override
    public String toString() {
        return "{"+"name: " + this.name + " 年龄" + this.age+"}";
    }

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

进阶尝试：(如果姓名和生日相同就表示同一个人，不能再添加了，其中生日的数据要是另外一个类，重点就是这个类的引入增加了难度)

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

public class HashSetExercise02 {
    public static void main(String[] args) {
        Set set = new HashSet();
        set.add(new Employee2("牛逼",2500,new MyDate(2003,7,20)));
        set.add(new Employee2("牛人",3500,new MyDate(2003,12,25)));
        set.add(new Employee2("牛逼",3500,new MyDate(2003,7,20)));
        System.out.println("set = " + set);
    }
}
class MyDate{
    private int year;
    private int month;
    private int day;

    public MyDate(int year, int month, int day) {
        this.year = year;
        this.month = month;
        this.day = day;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyDate myDate = (MyDate) o;
        return year == myDate.year && month == myDate.month && day == myDate.day;
    }

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

    @Override
    public String toString() {
        return "MyDate{" +
                "year=" + year +
                ", month=" + month +
                ", day=" + day +
                '}';
    }
}
class Employee2 {
    private String name;
    private int sal;
    private MyDate birthday;

    public Employee2(String name, int sal, MyDate birthday) {
        this.name = name;
        this.sal = sal;
        this.birthday = birthday;
    }

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

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

    @Override
    public String toString() {
        return "Employee2{" +
                "name='" + name + '\'' +
                ", sal=" + sal +
                ", birthday=" + birthday +
                "}\n";
    }
}

源码查看

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
public class HashSetSource {
    public static void main(String[] args) {

        HashSet hashSet = new HashSet();
        hashSet.add("java");//到此位置，第1次add分析完毕.
        hashSet.add("php");//到此位置，第2次add分析完毕
        hashSet.add("java");
        System.out.println("set=" + hashSet);

        /*
        1. 执行 HashSet()
            public HashSet() {
                map = new HashMap<>();
            }
        2. 执行 add()
           public boolean add(E e) {//e = "java"
                return map.put(e, PRESENT)==null;//(static) PRESENT = new Object();->PRESENT是静态共享的
           }
         3.执行 put() , 该方法会执行 hash(key) 得到key对应的hash值 算法h = key.hashCode()) ^ (h >>> 16)->[无符号右移16位]
             public V put(K key, V value) {//key = "java" value = PRESENT->共享
                return putVal(hash(key), key, value, false, true);
            }
         4.执行 putVal   (*核心代码*)
         final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                Node<K,V>[] tab; Node<K,V> p; int n, i; //定义了辅助变量
                //table 就是 HashMap 的一个数组，类型是 Node[]   (用来形成链表)
                //if 语句表示如果当前table 是null, 或者 大小=0
                //就是第一次扩容，到16个空间.
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;   ->resize()返回一个newtable

                //(1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置并把这个位置的对象，赋给 p
                //(2)判断p 是否为null
                //(2.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node (key="java",value=PRESENT)
                //(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)

                if ((p = tab[i = (n - 1) & hash]) == null)//比较能否添加
                    tab[i] = newNode(hash, key, value, null);
                else {
                    //一个开发技巧提示： 在需要局部变量(辅助变量)时候，在创建
                    Node<K,V> e; K k; 
                    //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
                    //并且满足 下面两个条件之一:
                    //(1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象
                    //(2)  p 指向的Node 结点的 key 的equals() 和准备加入的key比较后相同
                    //就不能加入
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;
                    //再判断 p 是不是一颗红黑树,
                    //如果是一颗红黑树，就调用 putTreeVal , 来进行添加
                    else if (p instanceof TreeNode)
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                    else {//如果table对应索引位置，已经是一个链表, 就使用for循环比较
                          //(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
                          //    注意在把元素添加到链表后，立即判断 该链表是否已经达到8个结点
                          //    , 就调用 treeifyBin() 对当前这个链表进行树化->(转成红黑树)
                          //    注意，在转成红黑树时，要进行判断, 判断条件
                          //    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(值为64))
                          //            resize();
                          //    如果上面条件成立，先table扩容.
                          //    只有上面条件不成立时，才进行转成红黑树
                          //(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break

                        for (int binCount = 0; ; ++binCount) {
                            if ((e = p.next) == null) {
                                p.next = newNode(hash, key, value, null);//加入到链表的最后
                                if (binCount >= TREEIFY_THRESHOLD【值为8】 - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
                                break;
                            }
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;
                            p = e;
                        }
                    }
                    if (e != null) { // existing mapping for key
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
                ++modCount;
                //size 就是我们每加入一个结点Node(k,v,h,next), size++
                if (++size > threshold)
                    resize();//扩容
                afterNodeInsertion(evict);
                return null;
            }
         */

    }
}

源码总结

  1. HashSet的底层实际上是HashMap，第一次添加时，table数扩容到16，临界值（threshold）[是16]*加载因子（loadFactor）[是0.75]=12
  2. 如果table数组使用到了临界值12，就会扩容到162 = 32，新的临界值就是320.75=24，以此类推（==只要是添加了对象size就会++==，即单个链表中添加一个结点，table的size就会++，到了临界值就扩容）
  3. 在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD（默认为8），并且table的大小 >= MIN_TREEIFY_CAPACITY（默认为64，即数组的大小），就进行树化（树化为红黑树）