Part8

目录

• HashSet的全面说明
• HashSet案例说明
• HashSet底层机制说明
• • 模拟简单的数组+链表结构
  • 分析HashSet的添加元素的底层是如何实现的( hash() + equals() )
• 源码剖析
• • 分析HashSet的扩容和转成红黑树机制
  • HashSet课堂 练习1
  • HashSet课堂 练习2

HashSet的全面说明

1. HashSet实现了Set接口

2. HashSet实际上是HashMap

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

3. 可以存放null值，但是只能有一个null

4. HashSet不保证元素是有序的，取决于hash后，再确定索引的结果（即不保证数据存放和取出的顺序一致）

5. 不能有重复的元素/对象

HashSet案例说明

public class HashSet_ {
    public static void main(String[] args) {
        Set set = new HashSet();
        //执行add方法后，会返回一个boolean值
        //如果添加成功，返回true，否则返回false
        //可以通过remove指定删除哪个对象
        System.out.println(set.add("joan"));
        System.out.println(set.add("lucky"));
        System.out.println(set.add("summer"));
        System.out.println(set.add("null"));
        System.out.println(set.add("joan"));// false: 不能添加重复元素
        System.out.println(set.add("jack"));
        System.out.println(set.add("null"));// false: 不能添加重复元素

        System.out.println("=====删除前=====");
        System.out.println(set);

        set.remove("null");// 将会删掉null
        System.out.println("=====删除后=====");
        System.out.println(set);
    }
}

true
true
true
true
false
true
false
=====删除前=====
[lucky, joan, null, summer, jack]
=====删除后=====
[lucky, joan, summer, jack]

HashSet底层机制说明

1. HashSet底层是HashMap， HashMap底层是数组+链表+红黑树
2. 添加一个元素时，先得到Hash值，会转换成索引值
3. 找到存储数据表table，看这个索引位置是否已经存放有元素
4. 如果没有，直接加入
5. 如果有，调用equals方法比较，如果相同，就放弃添加，如果不相同，则添加到最后
6. 在Java8中，如果一条链表的元素个数到TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（红黑树）

模拟简单的数组+链表结构

public class HashSetStructure {
    public static void main(String[] args) {
        // 1. 创建一个数组，数组的类型是Node[]
        // 2. 有些人，直接把Node[] 数组称为 表
        Node[] table = new Node[16];
        // 3. 创建节点
        Node summer = new Node("summer", null);
        table[2] = summer;
        Node ada = new Node("ada", null);
        summer.next = ada;// 将ada挂载到summer
        Node cara = new Node("cara", null);
        ada.next = cara;// 将cara挂载到jack

        Node lucky = new Node("lucky", null);
        table[3] = lucky;
        for (Node node : table) {
            System.out.println(node);
        }
    }
}

class Node {// 节点，存储数据，可以指向下一个节点，从而形成链表
    Object item;// 存放数据
    Node next;// 指向下一个节点

    public Node(Object item, Node next) {
        this.item = item;
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "item=" + item +
                ", next=" + next +
                '}';
    }
}

null
null
Node{item=summer, next=Node{item=ada, next=Node{item=cara, next=null}}}
Node{item=lucky, next=null}
null
null
null
null
null
null
null
null
null
null
null
null

分析HashSet的添加元素的底层是如何实现的( hash() + equals() )

源码剖析

public class HashSetSource {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("php");
        hashSet.add("java");
        System.out.println(hashSet);
    }
}

分析上面的代码：

执行构造器

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

执行add()方法

// 这里的PRESENT是 private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public V put(K key, V value) {// key: java value: PRESENT(object)
    return putVal(hash(key), key, value, false, true);
}

执行hash(key) 方法会得到key对应的hash值，这个hash值不是hashCode，是根据算法(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)得到对应的hash值.(这个hash值就是table表对应的索引值)

static final int hash(Object key) {// key: java
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 无符号右移16位
}

hashCode()

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

核心代码（重点中的重点）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //定义辅助变量
    Node[] tab; Node p; int n, i;
    //如果当前table是null，或者大小等于0，就第一次扩容，扩到16个空间
    if ((tab = table) == null || (n = tab.length) == 0)//table是hashMap的一个属性，这个table就是放node节点的一个数组。类型是：Node[]
        n = (tab = resize()).length;
    //(1)根据key，得到hash，去计算该key应该存放到table表的哪个索引位置，并让p指向这个索引位置的对象
    //(2)判断p指向的索引位置的对象是否为null
    //(2.1)如果p指向的索引位置的对象为null，表示还没有存放元素，就创建一个Node(key="java", value="PRESENT")
    //     就放在该位置tab[i] = newNode(hash, key, value, null);
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);//(set_pic_2)
    //(2.2)如果p指向的索引位置的对象不为null
    else {
        //一个开发技巧：在需要局部变量（辅助变量）的时候，再创建
        Node e; K k;
        //如果当前索引位置对应的链表的第一个元素的hash值和准备添加的key的hash值一样。并且满足下面两个条件之一：
        //(1) 准备加入的key和p指向的Node节点的k是同一个对象(set_pic_3)
        //(2) p指向的Node节点的对象k和准备加入的key经equals()方法比较后相同(set_pic_4)
        //如果满足上面两个条件之一，那么就不能加入
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 再判断p是不是一颗红黑树，如果是红黑树，就调用putTreeVal来进行添加
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        //如果table对应索引位置，已经是一个链表，就使用for循环比较
        //(1) 依次和链表的每一个元素比较后，都不相同，则加入到该链表最后(set_pic_5)
        //(2) 在依次和该链表的每一个元素比较的过程中，如果有相同情况，就直接break
        else {
            //set_pic_6
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // TREEIFY_THRESHOLD=8
                    //注意：在把元素添加到链表后，会立即进行判断，判断该链表是否已经达到8个节点,
		           // 如果达到8个节点，就调用treeifyBin(tab, hash)对当前链表进行树化（转成红黑树）
        		   // 在转成红黑树时，还会进行一个判断，如果该table数组的大小小于MIN_TREEIFY_CAPACITY（64），
	       		   // 判断条件如下：
    	  	       // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
	        	   //     resize();
        		   // 如果上面条件成立，不会马上转成红黑树，会先进行table扩容
        		   // 只有当上面的条件不成立的时候，才进行转成红黑树
                        treeifyBin(tab, hash);
                    break;//添加到节点后面然后退出
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;//放弃添加然后退出
                // 这句代码，p依次指向它自己的下一个节点，这样就达到了循环每一个节点
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //onlyIfAbsent是put方法调用putVal的时候传入进来的参数，永远为false
            //public V put(K key, V value) {
            //    return putVal(hash(key), key, value, false[这个参数对应的就是onlyIfAbsent], true);
            //}
            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);
    //返回null表示添加成功
    return null;
}

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //DEFAULT_INITIAL_CAPACITY: 1<<4 2*2*2*2=16
        newCap = DEFAULT_INITIAL_CAPACITY;
        //DEFAULT_LOAD_FACTOR: 0.75
        //临界值0.75*16=12（缓冲层）
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //辅助变量newTable执行完下面这行代码后，就会变成有16个位置的空数组
    Node[] newTab = (Node[])new Node[newCap];
    //hashMap的table变成有16个位置的空数组（(set_pic_1)）
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

set_pic_1：

set_pic_2：刚开始创建一个空table, 接着，当插入一个数据之后

set_pic_3：插入数据时，判断能不能插入根据：即将要插入的key对应的对象和p所指向的Node对应的key的对象是否一样

set_pic_4：添加数据时，equals()方法存在的意义

set_pic_5：

set_pic_6：

Node newNode(int hash, K key, V value, Node next) {
    return new Node<>(hash, key, value, next);
}

分析HashSet的扩容和转成红黑树机制

1. HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子（loadFactor）是0.75 = 12
2. 如果table数组使用到了临界值12，就会扩容到162 = 32， 新的临界值就是 320.75 = 24, 以此类推
3. 在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD（默认是8），并且table的大小 >= MIN_TREEIFY_CAPACITY（默认是64），就会进行树化（转成红黑树），否则仍然采用数组扩容机制

public class HashSetIncrement {
    public static void main(String[] args) {
        // HashSet底层是HashMap，第一次添加时，table数组扩容到16，
        // 临界值（threshold）是16*加载因子（loadFactor）是0.75 = 12
        // 如果table数组使用到了临界值12，就会扩容到16*2 = 32， 新的临界值就是 32*0.75 = 24, 以此类推

        HashSet hashSet = new HashSet();
//        for (int i = 0; i < 100; i++) {
//            hashSet.add(i);
//        }

        // 在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD（默认是8），
        // 并且table的大小 >= MIN_TREEIFY_CAPACITY（默认是64），就会进行树化（转成红黑树），
        // 否则仍然采用数组扩容机制
//        for (int i = 0; i < 12; i++) {
//            hashSet.add(new A(i));
//        }

        // 当我们向hashSet增加一个元素，这个元素在底层封装了一个数据Node，加入到了table，就算是size++，
        // 而不是说非得增加到table表的第一个才算是增加size++
        for (int i = 0; i < 7; i++) {
            hashSet.add(new A(i));
        }

        for (int j = 0; j < 7; j++) {
            hashSet.add(new B(j));
        }
    }
}

class A {
    private int i;

    public A(int i) {
        this.i = i;
    }

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

    @Override
    public String toString() {
        return "A{" +
                "i=" + i +
                '}';
    }
}

class B{
    private int n;

    public B(int n) {
        this.n = n;
    }

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

    @Override
    public String toString() {
        return "B{" +
                "n=" + n +
                '}';
    }
}

HashSet课堂 练习1

我的代码：

public class HashSetExercise {
    public static void main(String[] args) {
        // 定义一个Employee类，name，age
        // 创建3个Employee对象放入HashSet中
        // name和age相同时，认为是相同员工，不能添加到HashSet中
        HashSet hashSet = new HashSet();
        Employee jack = new Employee("jack", 10);
        Employee jack2 = new Employee("jack", 10);
        Employee lucky = new Employee("lucky", 10);
        hashSet.add(jack);
        hashSet.add(jack2);
        hashSet.add(lucky);
        System.out.println(hashSet);
    }
}

class Employee {
    private String name;
    private int age;

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

    @Override
    public int hashCode() {
        return (name + age).hashCode();
    }
    // 刚开始我没有重写equals方法，导致虽然名字和年龄相同了，但是还是插入到了HashSet里面
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return age == employee.age && Objects.equals(name, employee.name);
    }

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

运行结果：

[Employee{name='jack', age=10}, Employee{name='lucky', age=10}]

老师的代码

public class HashSetExercise {
    public static void main(String[] args) {
        // 定义一个Employee类，name，age
        // 创建3个Employee对象放入HashSet中
        // name和age相同时，认为是相同员工，不能添加到HashSet中
        HashSet hashSet = new HashSet();
        Employee jack = new Employee("jack", 10);
        Employee jack2 = new Employee("jack", 10);
        Employee lucky = new Employee("lucky", 10);
        hashSet.add(jack);
        hashSet.add(jack2);
        hashSet.add(lucky);
        System.out.println(hashSet);
    }
}

class Employee {
    private String name;
    private int age;

    public Employee(String name, int age) {
        this.name = name;
        this.age = age;
    }
    // 老师的代码和我的代码的主要区别就在equals()和hashCode()方法这里
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return age == employee.age && Objects.equals(name, employee.name);
    }

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

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

[Employee{name='lucky', age=10}, Employee{name='jack', age=10}]

HashSet课堂 练习2

我的代码：

import java.util.HashSet;
import java.util.Objects;

public class HashSetExercise {
    public static void main(String[] args) {
        // 定义一个Employee类，name，sal, birthday(MyDate类型，属性包括：year，month，day)
        // 创建3个Employee对象放入HashSet中
        // name和birthday相同时，认为是相同员工，不能添加到HashSet中
        HashSet hashSet = new HashSet();
        hashSet.add(new Employee("jack", 18000, new MyDate(1989, 3, 5)));
        hashSet.add(new Employee("lucky", 9000, new MyDate(1996, 7, 1)));
        hashSet.add(new Employee("jack", 26000, new MyDate(1989, 3, 5)));
        System.out.println(hashSet);
    }
}

class Employee {
    private String name;
    private int sal;
    private MyDate date;

    public Employee(String name, int sal, MyDate date) {
        this.name = name;
        this.sal = sal;
        this.date = date;
    }

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

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

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + ''' +
                ", sal=" + sal +
                ", date=" + date +
                '}';
    }
}

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 Objects.hash(year, month, day);
    }

    @Override
    public String toString() {
        return "MyDate{" +
                "year=" + year +
                ", month=" + month +
                ", day=" + day +
                '}';
    }
}

[Employee{name='lucky', sal=9000, date=MyDate{year=1996, month=7, day=1}}, Employee{name='jack', sal=18000, date=MyDate{year=1989, month=3, day=5}}]