• 非零基础自学Java (老师：韩顺平) 第14章 集合 14.10 Set 接口实现类 - HashSet

    非零基础自学Java (老师：韩顺平)

    ✈【【零基础 快速学Java】韩顺平 零基础30天学会Java】

    第14章 集合

    文章目录

    14.10 Set 接口实现类 - HashSet
    14.10.1 HashSet 的全面说明

    • HashSet实现了Set接口

    • HashSet实际上是HashMap

      在这里插入图片描述

    • 可以存放null值,但是只能有一个null

    • HashSet不保证元素是有序的,取决于hash后，再确定索引的结果.(即，不保证存放元素的顺序和取出顺序一致)

    • 不能有重复元素/对象

    【举个栗子】

    package com.dingjiaxiong.set_;

import java.util.HashSet;
import java.util.Set;

/**
 * ClassName: HashSet_
 * date: 2022/9/5 19:12
 *
 * @author DingJiaxiong
 */

@SuppressWarnings({"all"})
public class HashSet_ {
    public static void main(String[] args) {
        Set hashSet = new HashSet();

        hashSet.add(null);
        hashSet.add(null);
        System.out.println("hashSet = " + hashSet);
    }
}

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

    运行结果

    在这里插入图片描述

    14.10.2 HashSet 案例说明

    【第一个】

    package com.dingjiaxiong.set_;

import com.sun.source.doctree.SeeTree;

import java.util.HashSet;

/**
 * ClassName: HashSet01
 * date: 2022/9/5 19:14
 *
 * @author DingJiaxiong
 */

@SuppressWarnings({"all"})
public class HashSet01 {
    public static void main(String[] args) {
        HashSet set = new HashSet();

        //在执行add方法后，会返回一个boolean值，添加成功true、添加失败false
        System.out.println(set.add("john"));
        System.out.println(set.add("lucy"));
        System.out.println(set.add("john")); //F
        System.out.println(set.add("jack"));
        System.out.println(set.add("Rose"));

        set.remove("john"); //指定删除哪个

        System.out.println("set = " + set);

        set = new HashSet();
        System.out.println("set = " + set);

        //Hashset 真的不能添加相同的元素/数据 吗？
        set.add("lucy"); //添加成功
        set.add("lucy"); //确实加入不了

        set.add(new Dog("tom")); //添加成功
        set.add(new Dog("tom")); //也成功了
        System.out.println("set = " + set);

        set.add(new String("dingjiaxiong"));//添加成功
        set.add(new String("dingjiaxiong")); //不行

        System.out.println("set = " + set);
    }
}

class Dog{
    private String name;

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

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

    • 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

    运行结果

    在这里插入图片描述

    add到底发生了什么？

    14.10.3 HashSet 底层机制说明

    HashSet底层是HashMap，HashMap底层是(数组 + 链表 + 红黑树)

    【HashSet的添加元素底层到底是如何实现的？(hash() + equals())】

    韩老师的图解

    在这里插入图片描述

    【举个栗子】

    package com.dingjiaxiong.set_;

import java.util.HashSet;
import java.util.Set;

/**
 * ClassName: HashSetSource
 * date: 2022/9/5 19:24
 *
 * @author DingJiaxiong
 */

@SuppressWarnings({"all"})
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("set = " + hashSet);
    }
}

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

    运行结果

    在这里插入图片描述

    韩老师的源码解读

    1. 执行HashSet() 构造方法

      在这里插入图片描述

    2. 执行add()

    在这里插入图片描述

    1. 执行put()，该方法会执行 hash(key) 得到 key 对应的 hash 值 算法 h = key.hashCode()) ^ (h >>> 16)

      在这里插入图片描述

    2. 执行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;
    
    //(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 - 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
      • 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

      啊这…看看韩老师的注释。

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

    韩老师图解

    在这里插入图片描述

    【举个栗子】

    package com.dingjiaxiong.set_;

import java.util.HashSet;

/**
 * ClassName: HashSetIncrement
 * date: 2022/9/5 19:35
 *
 * @author DingJiaxiong
 */

@SuppressWarnings({"all"})
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 , 依次类推
        * */

        HashSet hashSet = new HashSet();
        //在 Java8 中, 如果一条链表的元素个数到达 TREEIFY_THRESHOLD(默认是 8 )，
        //并且 table 的大小 >= MIN_TREEIFY_CAPACITY(默认 64),就会进行树化(红黑树), 否则仍然采用数组扩容机制

//        当向 hashset 增加一个元素，-> Node -> 加入 table , 就算是增加了一个 size++

        for (int i = 0; i <= 7; i++) { 在 table 的某一条链表上添加了 7 个 A 对象
            hashSet.add(new A(i));
        }

        for (int i = 0; i <= 7; i++) { //在 table 的另外一条链表上添加了 7 个 B 对象
            hashSet.add(new B(i));
        }

        System.out.println("hashSet = " + hashSet);
    }
}


class B{
    private int n;

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

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

class A{

    private int n;

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

    @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

    运行结果

    在这里插入图片描述

  • 相关阅读:
    使用 Ruby 语言来解析开放文档格式 OOXML 文件
    精品基于Python房源爬虫实现数据可视化分析
    数据结构与算法分析1
    react 脚手架
    【C++ 科学计算】介绍 C++线性代数和科学计算库 Armadillo
    Win10配置IIS与 C#/.net项目的发布与IIS部署
    03【MySQL字符集】
    C++进阶篇5-哈希
    解决sass问题：npm ERR! node-sass@9.0.0 postinstall: `node scripts/build.js`
    【毕业设计】基于javaEE+SSH+SqlServer的企业车辆管理系统设计与实现（毕业论文+程序源码）——车辆管理系统
  • 原文地址：https://blog.csdn.net/weixin_44226181/article/details/126949131