• java基础 集合(2) Set接口


    目录

    1、Set类

    1.1 set接口的遍历方式

    2、HashSet

    1、底层机制

    2、总结

    3、LinkedHashSet

    3.1 底层源码


    1、Set类

    1. 无序(添加和取出的顺序不一致),没有索引

      注意:取出的顺序虽然不是添加的顺序,但是是固定的

    2. 不允许重复元素,所以最多包含一个null

    3. Set中常用的实现类有 HashSet 和 TreeSet

    1.1 set接口的遍历方式

    有两种 1、迭代器 2、增强for循环 (但是不能使用索引方式来获取 没有索引)

    2、HashSet

    1. HashSet实现了Set接口

    2. HashSet实际上底层是HashMap

       public HashSet() {
              map = new HashMap<>();
          }
    3. 可以存放null值,但是只能有一个null

    4. HashSet不保证元素是有序的,取决于hash值 来确定存放在数组中索引的位置(底层源码)

    5. 不能有重复的元素 add添加如果成功就返回true 否则返回false

    经典的面试题

    1. public class HashSet_ {
    2.    public static void main(String[]args){  
    3.        Set set = new HashSet();
    4.        set.add("lucy");  //ok
    5.        set.add("lucy");  //加入不了
    6.        set.add(new Dog("tom")); //ok
    7.        set.add(new Dog("tom"));//ok
    8.        //String这个比较特殊   要看源码才能解析
    9.        //主要是因为String重写了hashCode和equals 导致hashMap认为这两个是同一个所以失败
    10.        set.add(new String("jack"));  //ok
    11.        set.add(new String("jack"));  //这个是不成功的
    12.   }
    13. }
    14. class  Dog {
    15.    private  String name ;
    16.    public Dog(String name) {
    17.        this.name = name;
    18.   }
    19. }

    1、底层机制

    HashSet底层是HashMap ,而HashMap的底层是 数组+链表+红黑树

    • 执行add方法

    1. HashSet的底层是HashMap

    2. 添加一个元素,先得到hash值, 通过公式转换成索引值

    3. 找到存储数据的数组 --表table,看这个索引位置是否已经有元素吗

    4. 如果没有直接加入

    5. 如果有,调用equalse比较,如果相同,就放弃添加,如果不相同,则添加到最后

    6. java8中 如果一条链表元素个数 >=(默认是8),并且数组的长度 >=64的时候,这个链表就进行树化(变成红黑树)

    1. package com.sofwin.controller;
    2. import java.util.HashSet;
    3. /**
    4. * @packageName: com.sofwin.controller
    5. * @author: wentao
    6. * @date: 2022/10/31 21:34
    7. * @version: 1.0
    8. * @email 1660420659@qq.com
    9. * @description: TODO
    10. */
    11. public class HashSetSource {
    12. public static void main(String[]args){
    13. HashSet hashSet = new HashSet();
    14. hashSet.add("java");
    15. hashSet.add("php");
    16. hashSet.add("java");
    17. System.out.println(hashSet);
    18. /**
    19. * 源码解读
    20. * 1、 执行HashSet()
    21. * public HashSet() {
    22. * map = new HashMap<>();
    23. * }
    24. *2、执行add方法
    25. *
    26. * public boolean add(E e) {
    27. * // PRESENT --> private static final Object PRESENT = new Object();
    28. * return map.put(e, PRESENT)==null;
    29. * }
    30. *
    31. * 3.执行put() 该方法会执行hash(key)方法
    32. * public V put(K key, V value) {
    33. * //key是java value是PRESENT 是共享的
    34. * return putVal(hash(key), key, value, false, true);
    35. * }
    36. *4.hash(key) 方法是通过对象的hashCode方法获取的
    37. * static final int hash(Object key) {
    38. * int h;
    39. * return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    40. * }
    41. *
    42. * 5、核心代码 putVal
    43. * final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    44. * boolean evict) {
    45. * Node[] tab; Node p; int n, i; //定义辅助变量
    46. * //table是hashMap的一个属性 是Node[]
    47. * //如果table为空 或者长度为0 就进行第一次扩容
    48. * if ((tab = table) == null || (n = tab.length) == 0)
    49. * //设置创建了一个容量为·16的Node数组赋值给table 并且设置了临界值
    50. * n = (tab = resize()).length;
    51. * // (n - 1) & hash 通过hash计算该元素在数组中的索引
    52. * //判断在该索引位置的数组是否有元素 如果没有元素,就进行创建一个新的元素并且添加
    53. * if ((p = tab[i = (n - 1) & hash]) == null)
    54. * tab[i] = newNode(hash, key, value, null);
    55. * else {
    56. * //开发技巧提示, 在需要局部变量在创建 是比较好的
    57. * Node e; K k; //定义辅助变量
    58. * //如果当前索引位置链表对应的第一个元素和准备添加的key哈希值一样
    59. * //并且满足准备加入的key和p指向的node节点的key一样 或者 满足key != null && key.equals(k)
    60. * //就不能加入
    61. * if (p.hash == hash &&
    62. * ((k = p.key) == key || (key != null && key.equals(k))))
    63. *
    64. * e = p;
    65. * //p是不是一颗红黑树 用红黑树进行putTreeVal 进行添加
    66. * else if (p instanceof TreeNode)
    67. * e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    68. * else {
    69. * //否则 就加入到链表中
    70. * //for循环比较 (1)依次和该链表每个元素比较后 都不相同,说明不相同 进行尾插
    71. * for (int binCount = 0; ; ++binCount) {
    72. * if ((e = p.next) == null) {
    73. * p.next = newNode(hash, key, value, null);
    74. * //(3)如果链表大于等于8的时候 就判断是否转换为红黑树
    75. * //注意:在进行转换红黑树的方法时候,还进行一个判断
    76. * //1,如果table数组为空,或者大小未超过64,则重置table大小
    77. * //扩容table table变大了碰撞就更小了,使得链表不容易继续加长
    78. * // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    79. * // resize();
    80. * if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    81. * treeifyBin(tab, hash); //下面有具体注释
    82. * break;
    83. * }
    84. * //(2)在依次比较过程中如果有相等的就走人
    85. * if (e.hash == hash &&
    86. * ((k = e.key) == key || (key != null && key.equals(k))))
    87. * break;
    88. * p = e;
    89. * }
    90. * }
    91. * if (e != null) { // existing mapping for key
    92. * V oldValue = e.value;
    93. * if (!onlyIfAbsent || oldValue == null)
    94. * e.value = value;
    95. * afterNodeAccess(e);
    96. * return oldValue;
    97. * }
    98. * }
    99. * ++modCount;
    100. * //加入完毕后 是否超过阀值 如果超过就进行扩容
    101. * if (++size > threshold)
    102. * resize(); //第一次是16 12 第二次都是扩大二倍
    103. * afterNodeInsertion(evict); //这个方法是一个空方法,是留给HashMap的子类扩展功能的
    104. * return null;
    105. * }
    106. *
    107. */
    108. }
    109. }

     

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

        1. HashSet底层是HashMap,第一次添加的时候,table数组扩容到16,临界值(threshold)是16*0.75 =12
        2. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //default initial capacity 初始化的容量 必须是2的倍数   开始为16
        3. static final int MAXIMUM_CAPACITY = 1 << 30;     // 最大容量
        4. static final float DEFAULT_LOAD_FACTOR = 0.75f;   //加载因子、负载因子等等  
        5. static final int TREEIFY_THRESHOLD = 8;  //treeify threshold判断链表是否转化为红黑树的临界值,值为8
        6. static final int UNTREEIFY_THRESHOLD = 6;  //untree判断是否应该由红黑树退回链表的临界值,值为6
        7.  static class Node implements Map.Entry {   //这个是节点的类 --- 存放元素的信息  
        8.        final int hash;
        9.        final K key;
        10.        V value;
        11.        Node next;
        12. }
        13. static final class TreeNode extends LinkedHashMap.Entry {  //红黑树的类
        14.        TreeNode parent;  // red-black tree links
        15.        TreeNode left;
        16.        TreeNode right;
        17.        TreeNode prev;    // 需要在下一次删除时断开链接
        18.        boolean red;
        19. }
        20. transient Node[] table; //存放链表的数组
        21. transient int size;//已存元素的个数
        22. int threshold;//表示下次扩容的临界值 初始为0,当size>=threshold时,扩容   threshold=集合的容量*负载因子(加载因子)
        23. final float loadFactor;//加载因子
        24. public HashMap() {
        25.        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        26.   }
        27. Node[] oldTab = table;
        28.        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        29.        int oldThr = threshold;
        30.        int newCap, newThr = 0;
        31.        else {
        32.          // 第一次的时候 table容量为16  
        33.            //阀值为 16*0.75
        34.            newCap = DEFAULT_INITIAL_CAPACITY;
        35.            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        36.       }

      1. 如果table数组中数据(数据不管是数组中还是链表中),只要个数到达临界值12,就会扩容到16*2 = 32 ,新的临界值是原来的2 12×2 = 24

        1. //加入完毕后 是否超过阀值 如果超过就进行扩容
        2.  // 注意 这个size是每次加入一个元素都会增加
        3.  //因此 即使 数组中有一个链表是12的长度 在加入元素的时候也会进行扩容
        4.                if (++size > threshold)
        5.                     resize();
        6. resize() :扩容方法  
        7. if (oldCap > 0) {
        8.            if (oldCap >= MAXIMUM_CAPACITY) {
        9.                threshold = Integer.MAX_VALUE;
        10.                return oldTab;
        11.           }
        12.     //oldCap大于等于12的时候 扩容2倍
        13.            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
        14.                     oldCap >= DEFAULT_INITIAL_CAPACITY)
        15.                //阀值也变成二倍
        16.                newThr = oldThr << 1; // double threshold
        17.       }

      2. 在java8中,如果一条链表的元素个数到达8 并且table的大小大于等于64就会进行树化(红黑树),否则仍然采取数组扩容机制

    *     
    1. //树化代码
    2.         *     final void treeifyBin(Node[] tab, int hash) {
    3.         *     int n, index; Node e;
    4.         *     //1,如果table数组为空,或者大小未超过64,则重置table大小
    5.         *     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    6.         *         resize();
    7.         *     //2,如果table大小超过64,把当前链表转换成红黑树
    8.         *     else if ((e = tab[index = (n - 1) & hash]) != null) {
    9.         *         TreeNode hd = null, tl = null;
    10.         *         do {
    11.         *         //2.1,循环链表,把每一个对象转换成红黑树,并绑定上下级关系
    12.         *             TreeNode p = replacementTreeNode(e, null);
    13.         *             if (tl == null)
    14.         *                 hd = p;
    15.         *             else {
    16.         *             //并绑定上下级关系
    17.         *                 p.prev = tl;
    18.         *                 tl.next = p;
    19.         *             }
    20.         *             tl = p;
    21.         *         } while ((e = e.next) != null);
    22.         *         //2.2 重置红黑树相关信息
    23.         *         if ((tab[index] = hd) != null)
    24.         *             hd.treeify(tab);
    25.         *     }
    26.         * }
    27. //通过这个代码debug来看,能很清晰的看见什么时候树化的
    28. public class TreeNode_ {
    29.    public static void main(String[]args){
    30.        HashSet hashSet = new HashSet();
    31.        for (int i = 1; i <= 12; i++){
    32.            hashSet.add(new Acb(i));
    33.       }
    34.   }
    35. }
    36. class  Acb {
    37.    private  int a;
    38.    public Acb(int a) {
    39.        this.a = a;
    40.   }
    41.    @Override
    42.    public int hashCode() {
    43.        return 1;
    44.   }
    45. }

    2、总结

    HashSet底层添加机制

    1、 先获取元素的哈希值(程序员可以重写)  通过hash值来计算在数组中的索引位置
    2、 如果该位置上没有其他元素,就直接进行添加
    3、 如果该位置有元素就进行判断  进行equals判断(程序员可以重写)  
           如果相等,则不添加
           如果不相等,就加入到链表中尾插
    ​

    面试题

    1. public class HashSet_ {
    2.    public static void main(String[]args){  
    3.        Set set = new HashSet();
    4.        set.add("lucy");  //ok  
    5.        set.add("lucy");  //加入不了
    6.        set.add(new Dog("tom")); //ok
    7.        set.add(new Dog("tom"));//ok
    8.        set.add(new String("jack"));  //ok
    9.        set.add(new String("jack"));  //这个是不成功的
    10.         //String这个类重写了hashCode和equals方法
    11.        /*
    12.        思路分析:
    13.        //1、先通过hash值来计算在数组中的索引
    14.        //有因为String重写了hashCode方法,是通过字符串来计算hashCode的  
    15.        // 因此new String("jack") 这两个hash值是一样的,所以得到数组中索引是一样的
    16.        //2、第一次添加数组位置没有元素 添加成功
    17.        //3、第二次添加的时候有元素了, 如果进行equals比较
    18.        //4.结果String重写了equals是比较字符串,字符串相等 因此添加不成功
    19.        hashCode()
    20.                public int hashCode() {
    21.                int h = hash;
    22.                if (h == 0 && value.length > 0) {
    23.                    char val[] = value;
    24.                    for (int i = 0; i < value.length; i++) {
    25.                        h = 31 * h + val[i];
    26.                    }
    27.                    hash = h;
    28.                }
    29.                return h;
    30.            }
    31.        
    32.        equals方法:
    33.             public boolean equals(Object anObject) {
    34.            if (this == anObject) {
    35.                return true;
    36.            }
    37.            if (anObject instanceof String) {
    38.                String anotherString = (String)anObject;
    39.                int n = value.length;
    40.                if (n == anotherString.value.length) {
    41.                    char v1[] = value;
    42.                    char v2[] = anotherString.value;
    43.                    int i = 0;
    44.                    while (n-- != 0) {
    45.                        if (v1[i] != v2[i])
    46.                            return false;
    47.                        i++;
    48.                    }
    49.                    return true;
    50.                }
    51.            }
    52.            return false;
    53.    }
    54.        */
    55.   }
    56. }
    57. class  Dog {
    58.    private  String name ;
    59. public Dog(String name) {
    60.    this.name = name;
    61. }
    62. }

    练习题

    定义一个Employee类 该类包含private成员属性 name、sal、birthday(MyDate类型),

    其中birthday为MyDate类 (属性包含year、month、day)

    要求:创建三个Employee放入HashSet中

    当name和birthday的值相同时,认为是相同员工,不能添加到HashSet集合中

    1. package com.sofwin.controller;
    2. import java.util.HashSet;
    3. import java.util.Objects;
    4. /**
    5. * @author: wentao
    6. * @date: 2022/11/1 10:26
    7. * @version: 1.0
    8. */
    9. public class Employee {
    10.    private String name;
    11.    private String sal;
    12.    private  MyDate brithday;
    13.    public static void main(String[]args){
    14.        HashSet set = new HashSet();
    15.        set.add(new Employee("张三","nan",new MyDate(2022,1,1)));
    16.        set.add(new Employee("李四","nan",new MyDate(2022,1,1)));
    17.        set.add(new Employee("王五","nan",new MyDate(2022,1,1)));
    18.        set.add(new Employee("张三","nv",new MyDate(2022,1,1)));
    19.        System.out.println(set);
    20. //[Employee{name='张三', sal='nan', brithday=MyDate{year=2022, month=1, day=1}},
    21. // Employee{name='王五', sal='nan', brithday=MyDate{year=2022, month=1, day=1}},
    22. // Employee{name='李四', sal='nan', brithday=MyDate{year=2022, month=1, day=1}}]
    23.   }
    24.    @Override
    25.    public boolean equals(Object o) {
    26.        if (this == o) return true;
    27.        if (o == null || getClass() != o.getClass()) return false;
    28.        Employee employee = (Employee) o;
    29.        return Objects.equals(name, employee.name) &&
    30.                Objects.equals(brithday, employee.brithday);
    31.   }
    32.    public Employee(String name, String sal, MyDate brithday) {
    33.        this.name = name;
    34.        this.sal = sal;
    35.        this.brithday = brithday;
    36.   }
    37.    @Override
    38.    public int hashCode() {
    39.        return Objects.hash(name, brithday);
    40.   }
    41.    @Override
    42.    public String toString() {
    43.        return "Employee{" +
    44.                "name='" + name + '\'' +
    45.                ", sal='" + sal + '\'' +
    46.                ", brithday=" + brithday +
    47.                '}';
    48.   }
    49. }
    50. class MyDate {
    51.    private int year;
    52.    private int month;
    53.    private  int day;
    54.    @Override
    55.    public boolean equals(Object o) {
    56.        if (this == o) return true;
    57.        if (o == null || getClass() != o.getClass()) return false;
    58.        MyDate myDate = (MyDate) o;
    59.        return year == myDate.year &&
    60.                month == myDate.month &&
    61.                day == myDate.day;
    62.   }
    63.    public MyDate(int year, int month, int day) {
    64.        this.year = year;
    65.        this.month = month;
    66.        this.day = day;
    67.   }
    68.    @Override
    69.    public int hashCode() {
    70.        return Objects.hash(year, month, day);
    71.   }
    72.    @Override
    73.    public String toString() {
    74.        return "MyDate{" +
    75.                "year=" + year +
    76.                ", month=" + month +
    77.                ", day=" + day +
    78.                '}';
    79.   }
    80. }

    3、LinkedHashSet

    1. LinkedHashSet 是HashSet的子类

    2. LinkedHashSet底层是一个LinkedHashMap,底层维护了一个数组+双向链表+红黑树

    3. LinkedHashSet根据元素的hashCode值来决定元素的存储位置,同时使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的

    4. LinkedHashSet不允许添加重复元素

    3.1 底层源码

    1. 在LinkedHashSet中维护了一个hash表(数组table)和双向链表 (LinkedHashSet有head和tail 头结点和尾结点)

    2. 每个结点都有before和after属性 (前一个节点 后一个节点),这样就可以形成双向链表

    3. 在添加一个元素的时候,先求hash值,在求索引,确定该元素在table的位置,然后将添加的元素加入到双向链表中(如果已经存在,相同不添加,不相同加入到链表中(next指向 跟hashSet一样))

    4. 加入双向链表中利用before和after进行指向,这样就确保了插入顺序和遍历顺序一样

      ​
      ​
      
      1. /**
      2. * @author: wentao
      3. * @date: 2022/11/1 12:20
      4. * @version: 1.0
      5. * @description: LinkedHashSet的底层机制
      6. */
      7. public class LinkedHashSetSource {
      8.    public static void main(String[]args){
      9.        //分析一下 LinkedHashSet的底层机制
      10.        Set set = new LinkedHashSet();
      11.        set.add(new String("aa"));
      12.        set.add(456);
      13.        set.add(456);
      14.        set.add(new Customer("刘",1001));
      15.        set.add(123);
      16.        set.add("HSP");
      17.        //得出结果 添加和输出顺序一样
      18.        System.out.println(set);
      19.        /*
      20.           1. LinkedHashSet 加入顺序和取出元素/数据一致
      21.           2.LinkedHashSet 底层维护的 LinkedHashMap 的底层是HashMap
      22.           Set set = new LinkedHashSet();
      23.               public LinkedHashSet() {
      24.                    super(16, .75f, true);
      25.                  }
      26.                HashSet(int initialCapacity, float loadFactor, boolean dummy) {
      27.                     map = new LinkedHashMap<>(initialCapacity, loadFactor);
      28.                }
      29.                  public LinkedHashMap(int initialCapacity, float loadFactor) {
      30.                    super(initialCapacity, loadFactor);
      31.                    accessOrder = false;
      32.                 }
      33.                  public HashMap(int initialCapacity, float loadFactor)
      34.           3、 底层是HashMap 因此初始化16 阈值是12 以后扩容跟HashMap 也可以说HashSet一致
      35.           4、注意存放的结点类型不在是 Node 而是LinkedHashMap$Entry
      36.           5、数组是HashMap$Node[]     存放的元素类型是LinkedHashMap$Entry 多态现象
      37.              //继承关系在内部类完成
      38.              static class Entry extends HashMap.Node {
      39.                     Entry before, after;
      40.                     Entry(int hash, K key, V value, Node next) {
      41.                     super(hash, key, value, next);
      42.                }
      43.            }
      44.          6、
      45.        */
      46.   }
      47. }
      48. class  Customer {
      49.    private String name;
      50.    private  int num;
      51.    public Customer(String name, int num) {
      52.        this.name = name;
      53.        this.num = num;
      54.   }
      55.    @Override
      56.    public String toString() {
      57.        return "Customer{" +
      58.                "name='" + name + '\'' +
      59.                ", num=" + num +
      60.                '}';
      61.   }
      62. }

      Set调用的底层其实是Map,这里Set只是用来Map中的key存储数据了 value是固定一个值(PRESENT)  

  • 相关阅读:
    照亮夜晚的台灯:户外空间的闪亮之选
    餐厅点菜管理系统C语言课程设计
    【Spring系列】- Spring事务底层原理
    vector中的迭代器失效问题
    HCM 初学 ( 一 ) - 简介
    针对JavaScript混淆加密,JShaman推出新功能
    VS2019 添加afxdisp.h文件后提示CString不明确 解决方法
    深度学习实战07-卷积神经网络(Xception)实现动物识别
    讲一讲VS Code配置GoLang语言开发环境
    傅里叶分析概述
  • 原文地址:https://blog.csdn.net/weixin_52574640/article/details/127652493