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 + '}'; } }