java学习日记20230414-HashSet源码

HashSet

• HashSet底层是HashMap
• 添加一个元素时，先得到Hash值，会转化成索引值；
• 找到存储数据表table，看这个索引位置是否存放元素；
• 如果没有直接加入
• 如果有，调用equals比较，如果相同放弃添加，如果不同，则添加到最后
• 在java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)（table表扩容），并且table的大小>=MIN_TREEIFY_CAPACITY(64),就会进行树化——红黑树
• 原理：
  • 先获取元素的哈希值
  • 对哈希值进行运算，得到索引值，即存放在哈希表中的位置号
  • 如果该位置没有元素，则添加，如果有，则需要通过该元素的equals方法进行判断，相等不添加，不想等，以链表的方式添加

  • public class HashSetSource {
        public static void main(String[] args) {
    
            /**
             *
             *     public HashSet() {
             *         map = new HashMap<>();
             *     }
             *
             *     public boolean add(E e) {
             *         return map.put(e, PRESENT)==null;//private static final Object PRESENT = new Object();
             *     }
             *     public V put(K key, V value) {
             *         return putVal(hash(key), key, value, false, true);
             *     }
             *
             *     static final int hash(Object key) {
             *         int h;
             *         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
             *     }
             *
             *     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;
             *         //根据key得到hash，去计算key应该存放到table表的索引位置
             *         //并把对象赋给p
             *         //判断p是否为null，如果为null，表示没有存放元素，就创建一个Node
             *         //就放在该位置
             *         if ((p = tab[i = (n - 1) & hash]) == null)
             *             tab[i] = newNode(hash, key, value, null);
             *         else {
             *             Node<K,V> e; K k;//辅助变量，代码块定义
             *             //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样 p.hash ==hash
             *             //（1）并且满足准备加入的key和p指向的node结点的对象是同一个对象
             *             //（2）或者p指向的Node结点的key的equals方法和准备加入的key比较后，相同（equeals是添加对象的equals方法，由程序员选择）
             *             // 则认为是相同对象，无法进行添加
             *             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对应的索引是一个链表
             *                  //依次跟该链表的每隔元素比较
             *                  //比较Node结点是否存在该对象，如果存在则不进行添加，如果不存在则添加到最后
             *                  //在添加后立即判断链表是否到达8个结点，如果达到调用treeifyBin()对当前链表进行树化
             *                  //在进行树化时，进行判断，table的size小于64，对表进行扩容，大于64则进行树化
             *                  // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
             *                  // resize();
             *                 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;
             *         if (++size > threshold)
             *             resize();
             *         afterNodeInsertion(evict);
             *         return null;
             *     }
             */
            HashSet hashSet = new HashSet();
            hashSet.add("java");
            hashSet.add("php");
            hashSet.add("java");
            System.out.println("hashSet="+hashSet);
        }

    HashSet底层机制说明：

    • HashSet底层时HashMap，第一次添加时，table数组扩容到16，临界值threshold是16*加载因子loadFactory0.75
    • 如果table数组使用到了临界值就会自动触发扩容16*2=32个，新的临界值时32*0.75=24
    • 在java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD默认是8并且table的大小>=MIN_TREEIFY_CAPACITY(默认是64)，就会进行红黑树，否则任然采用数组扩容。
    • 无论是链表还是数组，每新增一个元素，都会新增一个节点，都会计算到临界值中

  • package com.study.set_;
    
    import java.util.HashSet;
    import java.util.Objects;
    
    /**
     * @author jay
     * @version 1.0
     * @date 2023/4/18
     */
    public class HashSetHomework {
        public static void main(String[] args) {
            HashSet hashSet = new HashSet();
            hashSet.add(new EmployeeHome("Jack",200,new MyDate(2022,10,10)));
            hashSet.add(new EmployeeHome("Jack",200,new MyDate(2022,10,10)));
            hashSet.add(new EmployeeHome("Jack",200,new MyDate(2022,10,20)));
            System.out.println(hashSet);
        }
    }
    
    
    class EmployeeHome{
        @Override
        public String toString() {
            return "EmployeeHome{" +
                    "name='" + name + '\'' +
                    ", sal=" + sal +
                    ", birthDay=" + birthDay +
                    '}';
        }
    
        private String name;
        private double sal;
        private MyDate birthDay;
    
        public EmployeeHome(String name, double 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;
            EmployeeHome that = (EmployeeHome) o;
            return Objects.equals(name, that.name) && Objects.equals(birthDay, that.birthDay);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(name, birthDay);
        }
    }
    
    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;
        }
    
        public int getYear() {
            return year;
        }
    
        public void setYear(int year) {
            this.year = year;
        }
    
        public int getMonth() {
            return month;
        }
    
        public void setMonth(int month) {
            this.month = month;
        }
    
        public int getDay() {
            return day;
        }
    
        public void setDay(int day) {
            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 +
                    '}';
        }
    }