共计 5121 个字符，预计需要花费 13 分钟才能阅读完成。
起源：https://www.cnblogs.com/LiaHo…
一. HashSet 概述
HashSet 是 Java 汇合 Set 的一个实现类，Set 是一个接口，其实现类除 HashSet 之外，还有 TreeSet，并继承了 Collection，HashSet 汇合很罕用，同时也是程序员面试时常常会被问到的知识点，上面是结构图
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{}二. HashSet 结构
HashSet 有几个重载的构造方法，咱们来看一下
private transient HashMap<E,Object> map;
// 默认结构器
public HashSet() {map = new HashMap<>();
}
// 将传入的汇合增加到 HashSet 的结构器
public HashSet(Collection<? extends E> c) {map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
// 明确初始容量和装载因子的结构器
public HashSet(int initialCapacity, float loadFactor) {map = new HashMap<>(initialCapacity, loadFactor);
}
// 仅明确初始容量的结构器（装载因子默认 0.75）public HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);
}通过下面的源码，咱们发现了 HashSet 就 TM 是一个皮包公司，它就对外接活儿，活儿接到了就间接扔给 HashMap 解决了。因为底层是通过 HashMap 实现的，这里简略提一下:
HashMap 的数据存储是通过数组 + 链表 / 红黑树实现的，存储大略流程是通过 hash 函数计算在数组中存储的地位，如果该地位曾经有值了，判断 key 是否雷同，雷同则笼罩，不雷同则放到元素对应的链表中，如果链表长度大于 8，就转化为红黑树，如果容量不够，则需扩容（注：这只是大抵流程）。
如果对 HashMap 原理不太分明的话，能够先去理解一下。
汇合系列教程：https://www.javastack.cn/cate…
三. add 办法
HashSet 的 add 办法时通过 HashMap 的 put 办法实现的，不过 HashMap 是 key-value 键值对，而 HashSet 是汇合，那么是怎么存储的呢，咱们看一下源码
private static final Object PRESENT = new Object();
public boolean add(E e) {return map.put(e, PRESENT)==null;
}看源码咱们晓得，HashSet 增加的元素是寄存在 HashMap 的 key 地位上，而 value 取了默认常量 PRESENT，是一个空对象。
四. remove 办法
HashSet 的 remove 办法通过 HashMap 的 remove 办法来实现
//HashSet 的 remove 办法
public boolean remove(Object o) {return map.remove(o)==PRESENT;
}
//map 的 remove 办法
public V remove(Object key) {
Node<K,V> e;
// 通过 hash(key) 找到元素在数组中的地位，再调用 removeNode 办法删除
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
/**
*
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;
// 步骤 1. 须要先找到 key 所对应 Node 的精确地位，首先通过 (n - 1) & hash 找到数组对应地位上的第一个 node
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//1.1 如果这个 node 刚好 key 值雷同，运气好，找到了
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
/**
* 1.2 运气不好，在数组中找到的 Node 尽管 hash 雷同了，但 key 值不同，很显著不对，咱们须要遍历持续
* 往下找；*/
else if ((e = p.next) != null) {
//1.2.1 如果是 TreeNode 类型，阐明 HashMap 以后是通过数组 + 红黑树来实现存储的，遍历红黑树找到对应 node
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//1.2.2 如果是链表，遍历链表找到对应 node
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 通过后面的步骤 1 找到了对应的 Node, 当初咱们就须要删除它了
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
/**
* 如果是 TreeNode 类型，删除办法是通过红黑树节点删除实现的，具体能够参考【TreeMap 原理实现
* 及罕用办法】*/
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
/**
* 如果是链表的状况，当找到的节点就是数组 hash 地位的第一个元素，那么该元素删除后，间接将数组
* 第一个地位的援用指向链表的下一个即可
*/
else if (node == p)
tab[index] = node.next;
/**
* 如果找到的原本就是链表上的节点，也简略，将待删除节点的上一个节点的 next 指向待删除节点的
* next, 隔离开待删除节点即可
*/
else
p.next = node.next;
++modCount;
--size;
// 删除后可能存在存储构造的调整，可参考【LinkedHashMap 如何保障程序性】中 remove 办法
afterNodeRemoval(node);
return node;
}
}
return null;
}removeTreeNode 办法具体实现可参考 TreeMap 原理实现及罕用办法
五. 遍历
HashSet 作为汇合，有多种遍历办法，如一般 for 循环，加强 for 循环，迭代器，咱们通过迭代器遍历来看一下
public static void main(String[] args) {HashSet<String> setString = new HashSet<> ();
setString.add("星期一");
setString.add("星期二");
setString.add("星期三");
setString.add("星期四");
setString.add("星期五");
Iterator it = setString.iterator();
while (it.hasNext()) {System.out.println(it.next());
}
}打印进去的后果如何呢？
星期二
星期三
星期四
星期五
星期一 意料之中吧，HashSet 是通过 HashMap 来实现的，HashMap 通过 hash(key) 来确定存储的地位，是不具备存储程序性的，因而 HashSet 遍历出的元素也并非依照插入的程序。
六. 共计共计
依照我后面的布局，应该每一块次要的内容都独自写一下，如汇合 ArrayList，LinkedList，HashMap，TreeMap 等。不过我在写这篇对于 HashSet 的文章时，发现有后面对 HashMap 的解说后，的确简略，HashSet 就是一个皮包公司，在 HashMap 里面加了一个壳，那么 LinkedHashSet 是否就是在 LinkedHashMap 里面加了一个壳呢，而 TreeSet 是否是在 TreeMap 里面加了一个壳？咱们来验证一下
先看一下 LinkedHashSet
最开始的结构图曾经提到了 LinkedHashSet 是 HashSet 的子类，咱们来看源码
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{public LinkedHashSet(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {super(initialCapacity, .75f, true);
}
public LinkedHashSet() {super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
public Spliterator<E> spliterator() {return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
}
}下面就是 LinkedHashSet 的所有代码了，是不是感觉智商被否定了，这基本上没啥货色嘛，结构器还全副调用父类的，上面就是其父类 HashSet 的对此的构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
}大家也看进去，和咱们的猜想一样，没有深究上来的必要了。如果有趣味能够看看 LinkedHashMap 如何保障程序性。
在看一下 TreeSet
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{public TreeSet() {this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {this(s.comparator());
addAll(s);
}
}的确如咱们所猜想，TreeSet 也齐全依赖于 TreeMap 来实现，如果有趣味能够看看 TreeMap 原理实现及罕用办法。
七. 总结
原本想三章的内容，一章就算完了，尽管 Set 实现有点赖皮，毕竟他祖辈是 Collection 而不是 Map，在 Map 的实现类上穿了一层衣服就成了 Set，而后出于某种目标潜伏在 Collection 中，哈哈，开个玩笑，本文次要介绍了 HashSet 的原理以及次要办法，同时简略介绍了 LinkedHashSet 和 TreeSet，若有不对之处，请批评指正，望共同进步，谢谢！
近期热文举荐：
1.1,000+ 道 Java 面试题及答案整顿 (2022 最新版)
2. 劲爆！Java 协程要来了。。。
3.Spring Boot 2.x 教程，太全了！
4. 别再写满屏的爆爆爆炸类了，试试装璜器模式，这才是优雅的形式！！
5.《Java 开发手册（嵩山版）》最新公布，速速下载！
感觉不错，别忘了顺手点赞 + 转发哦！
