HashSet 的底层原理（简单易懂）
在 Java 集合框架中，HashSet 是一个非常常用的集合类，它提供了快速的元素查找和插入操作。那么，HashSet 的底层是如何实现这些高效操作的呢？本文将深入探讨 HashSet 的底层原理。
一、HashSet 的基本概念
HashSet 是基于哈希表的 Set 接口的实现，它不允许集合中出现重复元素。当我们向 HashSet 中添加元素时，HashSet 会使用元素的哈希值来决定元素在集合中的存储位置，这样可以大大提高查找和插入的效率。
二、底层数据结构
HashSet 的底层实现依赖于 HashMap。在 HashSet 的源码中，可以看到它实际上是通过一个 HashMap 来存储元素的。当我们向 HashSet 中添加元素时，实际上是将元素作为键值对的键存入 HashMap 中，而值则是一个固定的 Object 对象（PRESENT）。
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}三、哈希值的作用
哈希值是 HashSet 实现高效操作的关键。当我们向 HashSet 中添加元素时，HashSet 首先会计算元素的哈希值，然后根据哈希值确定元素在哈希表中的存储位置。如果两个元素的哈希值相同，那么它们就会被存储在哈希表的同一个位置（称为哈希冲突）。
四、解决哈希冲突
在实际应用中，哈希冲突是不可避免的。为了解决哈希冲突，HashMap（HashSet 底层使用的是 HashMap）采用了链地址法。具体来说，当发生哈希冲突时，HashMap 会将冲突的元素存储在一个链表中，这个链表被称为桶（bucket）。在 Java 8 及以后的版本中，如果链表的长度超过一定阈值（默认为 8），链表会被转换为红黑树，以提高查找效率。
五、HashSet 的操作原理
- 添加元素：当我们调用 HashSet 的 add 方法添加元素时，HashSet 会先计算元素的哈希值，然后根据哈希值确定元素在哈希表中的存储位置。如果该位置为空，直接将元素存入；如果该位置已存在元素（即发生哈希冲突），则将新元素添加到链表或红黑树中。
- 查找元素：当我们调用 HashSet 的 contains 方法查找元素时，HashSet 同样会先计算元素的哈希值，然后根据哈希值确定元素在哈希表中的存储位置。如果该位置为空，说明元素不存在；如果该位置存在元素，则在链表或红黑树中查找该元素。
- 删除元素：当我们调用 HashSet 的 remove 方法删除元素时，HashSet 会先计算元素的哈希值，然后根据哈希值确定元素在哈希表中的存储位置。如果该位置存在元素，则在链表或红黑树中删除该元素。
六、总结
HashSet 的底层原理基于哈希表和 HashMap，通过哈希值来快速定位元素的存储位置，并使用链地址法解决哈希冲突。了解 HashSet 的底层原理，有助于我们在实际编程中更好地使用它，提高程序的性能。