【某大厂一面】HashSet底层怎么实现的

HashSet 是 Java 集合框架中的一个非常常用的集合类，它实现了 Set 接口，并且底层通常是通过 哈希表（HashMap）来实现的。要理解 HashSet 的底层实现，我们需要从哈希表的工作原理开始讲起。下面是对 HashSet 底层实现的详细解析。

1. HashSet 的基本特性

• 无重复元素：HashSet 不允许存储重复的元素。如果向 HashSet 中添加一个已经存在的元素，插入操作会失败。
• 不保证元素的顺序：HashSet 不保证元素的顺序，它会根据元素的哈希值决定元素存储的顺序。
• 支持 null 元素：HashSet 允许存储一个 null 元素。

2. HashSet 底层实现原理

HashSet 实际上是基于 哈希表 实现的，而哈希表的实现是通过 HashMap 类来完成的。其基本结构和工作原理如下：

• HashSet 使用了 HashMap 作为底层存储结构。
• 每个 HashSet 中的元素都会作为 HashMap 的 key 存储，而 HashMap 的 value 部分则始终使用一个固定的对象（通常是 Object）作为占位符。

哈希表（HashMap）工作原理：

1. 哈希值计算：当元素被插入到 HashSet 中时，首先会计算该元素的哈希值（使用元素的 hashCode() 方法）。哈希值决定了元素应该存放在哈希表的哪个位置。
2. 冲突处理：如果两个不同的元素有相同的哈希值（即哈希冲突），HashMap 会通过链表（在 Java 8 之后，也可能是红黑树）来处理这些冲突。链表或树结构会存储多个哈希值相同的元素。
3. 键值存储：在 HashMap 中，每个 key 对应着一个值（value）。在 HashSet 中，value 部分是固定的，通常不关心具体的值。

HashSet 依赖 HashMap 的特点：

• 插入操作时，HashSet 会调用 HashMap.put(key, value) 方法来将元素作为 key 存储。
• 查找操作时，HashSet 会调用 HashMap.containsKey(key) 方法来判断该元素是否存在。
• 删除操作时，HashSet 会调用 HashMap.remove(key) 方法来删除元素。

3. HashSet 的常用操作分析

1. 添加元素（add()）

当调用 HashSet 的 add() 方法时，底层实际上调用的是 HashMap 的 put() 方法：

• 计算元素的哈希值。
• 判断该元素是否已经存在于哈希表中（即是否有相同的哈希值且相等的元素）。
• 如果元素不存在，插入元素并返回 true；如果元素已经存在，返回 false。

public boolean add(E e) {return map.put(e, PRESENT) == null; // map.put() 返回值为 null 表示插入成功
}

在 HashSet 中，PRESENT 是一个常量，通常是 new Object()。

2. 查找元素（contains()）

查找操作会调用 HashMap 的 containsKey() 方法：

• 计算元素的哈希值。
• 判断该哈希值对应的桶中是否存在元素。
• 如果存在，进一步比较元素是否相等（使用 equals() 方法），如果相等返回 true，否则返回 false。

public boolean contains(Object o) {return map.containsKey(o); // 调用 HashMap 的 containsKey()
}

3. 删除元素（remove()）

删除操作会调用 HashMap 的 remove() 方法：

• 计算元素的哈希值。
• 查找该元素并删除。

public boolean remove(Object o) {return map.remove(o) == PRESENT; // 调用 HashMap 的 remove() 删除元素
}

4. 获取集合大小（size()）

返回 HashSet 中存储的元素数量，底层是通过 HashMap 的 size() 方法获取的：

public int size() {return map.size(); // 调用 HashMap 的 size() 获取大小
}

4. HashSet 和 HashMap 的关系

• HashSet 本质上是对 HashMap 的包装，HashSet 的元素会作为 HashMap 的 key 存储，而 value 部分固定不变。
• HashMap 的 key 使用 hashCode() 和 equals() 方法来判断元素是否相等，所以 HashSet 中的元素也必须重写 hashCode() 和 equals() 方法。
• HashSet 具有与 HashMap 相同的效率特性，所有常用操作（插入、查找、删除）的时间复杂度均为 O(1)，但在最坏情况下（哈希冲突严重）为 O(n)。

5. HashSet 性能特点

由于 HashSet 底层是基于哈希表的，因此它在大多数情况下提供非常高效的性能：

• 插入操作：O(1)，在没有哈希冲突的情况下，插入一个元素是常数时间。
• 查找操作：O(1)，由于哈希表是基于哈希值查找元素，查找操作通常是常数时间。
• 删除操作：O(1)，与查找操作类似，删除操作也基于哈希值进行快速定位。
• 最坏情况下：如果所有元素都发生哈希冲突（即所有元素都被分配到同一个桶中），则所有操作的时间复杂度会退化到 O(n)。

为了减少哈希冲突，HashSet 和 HashMap 都采用了动态扩容和哈希重哈希机制。当哈希表的负载因子（实际存储的元素数与数组容量之比）超过某个阈值时，会进行扩容（通常会将数组大小扩展为原来的 2 倍），并重新计算所有元素的哈希值并重新分配到新的数组位置。

6. HashSet 的扩容机制

HashSet 会根据负载因子和容量来动态调整内部存储数组的大小。默认情况下，HashSet 的初始容量为 16，负载因子为 0.75。

• 容量：是哈希表的数组大小。
• 负载因子：是哈希表的填充程度，默认值为 0.75。当哈希表中存储的元素个数超过容量的 75% 时，哈希表会进行扩容。

扩容操作会导致重新计算所有元素的哈希值，因此在性能方面可能会有一定的开销。

7. 总结

特性	HashSet
底层实现	基于 HashMap
是否允许重复元素	不允许
是否保证顺序	不保证
存储元素的方式	元素作为 HashMap 的 key 存储，value 固定
插入操作时间复杂度	O(1)，最坏情况 O(n)
查找操作时间复杂度	O(1)，最坏情况 O(n)
删除操作时间复杂度	O(1)，最坏情况 O(n)

HashSet 是一个高效的集合类，适用于需要去重、无序存储的场景。它的性能与哈希表的设计紧密相关，能够提供快速的插入、查找和删除操作。

小伙伴们在开发过程中有使用心得可以再评论区一块讨论哦