18. HashSet是如何实现去重的？为什么HashSet的元素顺序不固定？

PangHu大约 3 分钟

HashSet 是基于 HashMap 实现的，HashSet 中的元素实际上是存储在一个 HashMap 中的键（key）。HashSet 通过 HashMap 的键来确保集合中的元素不重复。具体而言，HashSet 是通过 hashCode() 和 equals() 方法来判断元素是否重复的：

hashCode() 方法：
- 当你向 HashSet 中添加一个元素时，HashSet 首先会调用该元素的 hashCode() 方法，计算元素的哈希值。这个哈希值决定了元素在 HashMap 中的存储位置（即桶 bucket）。
equals() 方法：
- 如果两个元素的 hashCode() 值不同，它们肯定是不同的元素，HashSet 会将新元素存储到对应的桶中。
- 如果两个元素的 hashCode() 值相同（发生哈希冲突），HashSet 会进一步使用 equals() 方法来比较这些元素。如果 equals() 方法返回 true，表示两个元素相同，不会将新元素添加到集合中；如果返回 false，则认为它们是不同的元素，将新元素存储到桶中的链表或红黑树中（在 Java 8 之后，链表长度超过一定阈值时，会转换为红黑树）。

通过这种机制，HashSet 能够确保集合中的每个元素都是唯一的。

为什么 `HashSet` 的元素顺序不固定？

HashSet 的元素顺序不固定，原因在于它的底层实现基于 HashMap，而 HashMap 的实现并不保证键值对的顺序。

1. 基于哈希表的存储：

HashSet 是基于 HashMap 实现的，HashMap 中元素的存储位置由键的 hashCode() 值决定。由于哈希表的特性，元素插入到 HashSet 时，其位置完全由元素的哈希值决定，而不是插入顺序。
当元素被添加到 HashSet 时，它们会根据哈希值散列到不同的桶中。桶的顺序和元素在桶中的顺序都是不确定的，因为它们依赖于哈希算法的计算结果。

2. 哈希冲突：

在发生哈希冲突时，不同的元素可能会被存储在同一个桶中，形成一个链表或红黑树。在这种情况下，链表或树中的元素顺序也不会按照插入顺序排列。
如果 HashMap 进行了再哈希操作（即扩容），所有元素会被重新分配到新的桶中，这通常会导致元素顺序的变化。

3. 无序性设计：

HashSet 和 HashMap 的设计目标是高效的查找、插入和删除操作，而不是保持元素的顺序。因此，在多次操作之后，HashSet 中元素的顺序可能会变化。

总结

去重实现：HashSet 通过调用元素的 hashCode() 和 equals() 方法来判断元素是否重复，从而实现去重。
顺序不固定：HashSet 的元素顺序不固定是因为它基于 HashMap 实现，而 HashMap 中元素的存储顺序由哈希值决定，并且在哈希冲突和再哈希操作时，元素的顺序可能会发生变化。

在需要保证元素唯一性但不关心顺序的场景下，HashSet 是非常合适的选择。如果你需要保持元素的插入顺序，可以考虑使用 LinkedHashSet；如果需要对元素排序，可以使用 TreeSet。