HashSet是Java中常用的去重集合，它的核心能力是快速判断元素是否存在，避免重复数据存入。但去重功能的实现并非没有代价，除了存储元素本身之外，HashSet还会额外存储很多辅助变量，这些变量的空间开销直接影响整体的空间复杂度。
HashSet的内部存储结构
HashSet的底层其实是基于HashMap实现的，它的大部分操作都会委托给内部的HashMap实例。当我们往HashSet中添加一个元素时，这个元素会作为HashMap的key，而value则是一个固定的静态空对象。我们可以先看HashSet的核心成员变量定义：
// HashSet内部持有的HashMap实例 private transient HashMap<E,Object> map; // 作为HashMap所有key对应的统一value private static final Object PRESENT = new Object();
而HashMap的底层是一个Node数组，每个Node节点封装了哈希值、key、value以及指向下一个节点的引用，当哈希冲突严重时，链表会转化为红黑树节点TreeNode。这些结构本身就会带来额外的存储开销。
额外存储的变量类型
1. 底层数组的冗余空间
HashMap的底层数组默认初始容量是16，负载因子是0.75。也就是说当数组使用了12个位置之后，就会触发扩容，扩容后的数组容量会翻倍。这意味着底层数组永远会有一定的空闲空间，这部分空闲空间就是额外的存储代价。比如我们往HashSet中只存10个元素，底层数组容量是16，就有6个位置是空闲的，白占了空间。
2. 节点封装的额外字段
每个存入HashSet的元素都会被封装成HashMap的Node节点，Node的结构如下：
static class Node<K,V> {
final int hash; // 元素的哈希值
final K key; // 实际存储的元素
V value; // 固定为PRESENT的空对象
Node<K,V> next; // 指向下一个节点的引用，解决哈希冲突
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
可以看到，除了我们实际要存储的key之外，每个节点还多了hash、value、next三个字段的存储开销。如果是红黑树节点TreeNode，还会有更多指向父节点、左子节点、右子节点、颜色标识的字段，额外开销会更大。
3. 静态空对象的共享开销
HashSet中所有元素对应的value都是同一个PRESENT静态对象，这个对象本身会占用一份固定的内存空间，不过因为是共享的，所以整体来看这部分开销很小，属于一次性的固定代价。
4. 扩容相关的阈值变量
HashMap中还有threshold（扩容阈值）、loadFactor（负载因子）等变量，这些变量本身占用的空间很小，属于可以忽略的固定开销。
空间复杂度量化分析
假设我们往HashSet中存入n个元素，每个元素本身的大小是S，我们来分析整体的空间占用：
- 元素本身的存储总大小是n * S
- 底层数组的大小：假设扩容了k次，数组最终容量是16 * 2^k，且要满足16 * 2^k * 0.75 >= n，所以数组的空闲空间至少是25%，这部分冗余空间的大小是0.25 * 16 * 2^k * 引用大小（64位虚拟机下引用大小是4或8字节，开启指针压缩是4字节）
- 每个节点的额外字段开销：每个Node除了key之外的字段，在开启指针压缩的情况下，hash是4字节，value引用是4字节，next引用是4字节，总共12字节，n个元素就是12 * n字节，如果是TreeNode的话额外开销会更高
所以整体的空间复杂度是O(n)，但是常数系数会比直接存储n个元素大很多。如果元素本身很小，比如存储的是int类型的包装类Integer，Integer本身占用16字节（对象头12字节+int值4字节），加上Node的12字节额外开销，还有数组的冗余空间，实际存储一个Integer元素可能需要占用几十字节的空间，额外代价非常明显。
不同场景下的代价对比
我们可以通过一个简单的小例子来直观感受不同去重方案的空间差异，比如我们要对10000个Integer元素去重：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
public class SpaceTest {
public static void main(String[] args) {
// 准备10000个随机Integer元素，假设有重复
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
list.add((int) (Math.random() * 8000));
}
// 使用HashSet去重
HashSet<Integer> hashSet = new HashSet<>(list);
System.out.println("HashSet去重后元素数量：" + hashSet.size());
// 使用List手动去重，空间只需要存储不重复的元素本身
List<Integer> distinctList = new ArrayList<>();
for (Integer num : list) {
if (!distinctList.contains(num)) {
distinctList.add(num);
}
}
System.out.println("List手动去重后元素数量：" + distinctList.size());
}
}
在这个例子中，HashSet的底层数组容量会远大于实际去重后的元素数量，加上每个节点的额外封装开销，整体占用的空间会比distinctList大很多，但是HashSet的contains操作是O(1)，而List的contains是O(n)，两者是时间和空间的 trade-off。
使用建议
在实际开发中，我们可以根据场景选择是否使用HashSet：
- 如果去重的元素数量很少，或者对空间非常敏感，比如内存受限的嵌入式场景，可以优先考虑更省空间的方案，比如排序后去重，虽然时间复杂度高一些，但是空间复杂度是O(n)，没有额外的节点封装开销
- 如果元素数量大，且需要频繁判断元素是否存在，HashSet的额外空间开销是可以接受的，因为它的时间优势能带来更好的整体性能
- 如果存储的元素本身很小，比如是基础类型的包装类，要特别注意HashSet的额外开销可能会被放大，这时候可以考虑使用专门的基础类型集合，比如IntHashSet，避免包装类和节点封装的双重开销
总的来说，HashSet的额外存储代价主要来自底层数组的冗余、节点封装的额外字段，虽然空间复杂度仍然是O(n)，但是常数系数较高，使用时需要结合场景权衡时间和空间成本。