hashset内部使用hashmap存储元素，元素作为key，值为固定占位符，利用hashmap键的唯一性保证元素不重复；2. 其add、remove、contains操作依赖hashcode()和equals()方法正确实现，否则会导致逻辑重复或查找失败；3. 性能平均o(1)，适用于需快速判断存在性且无需顺序的场景；4. 与arraylist（有序可重复，索引访问快）和treeset（有序唯一，o(log n)性能）相比，hashset在无序唯一集合中查找最快。
HashSet
的核心原理在于它内部使用了一个
HashMap
来存储所有元素。具体来说，当你往
HashSet
里添加一个元素时，它实际上是把这个元素作为
HashMap
的键（key），而值（value）则是一个共享的、无意义的占位符对象（通常是
java.lang.Object
的一个静态实例，比如
PRESENT
）。这种设计巧妙地利用了
HashMap
键的唯一性来保证
HashSet
中元素的唯一性，并且借用了
HashMap
基于哈希表的查找机制，实现了快速的添加、删除和查找操作。
解决方案
HashSet
的运作机制，其实就是
HashMap
的一个简化应用。当你调用
add(E e)
方法时，
HashSet
会转而调用其内部
map
对象的
put(e, PRESENT)
方法。
HashMap
在处理
put
操作时，会先计算
e
的
hashCode()
，根据这个哈希值找到对应的桶（bucket）。如果该桶为空，或者桶内没有与
e
相等的元素（通过
equals()
方法判断），那么
e
就会被放入该桶。如果桶内已经存在一个与
e
相等的元素，
HashMap
会用新的
e
替换旧的，但对于
HashSet
而言，它只关心元素是否存在，替换与否并不影响其唯一性保证。
同样地，
contains(Object o)
方法会调用
map.containsKey(o)
。这个过程同样依赖于
o
的
hashCode()
和
equals()
方法来快速定位并判断元素是否存在。
remove(Object o)
方法则调用
map.remove(o)
，也是基于哈希和相等性判断来移除元素。
所以，
HashSet
的性能表现，以及它如何确保元素的唯一性，完全取决于其底层
HashMap
的哈希算法和冲突解决机制。它不保证元素的顺序，因为哈希表本身就是无序的。
为什么说
hashCode()
hashCode()
和
equals()
对
HashSet
至关重要？
在我看来，如果你想让
HashSet
真正为你工作，并且不出岔子，那么正确地实现自定义对象的
hashCode()
和
equals()
方法，简直是基石中的基石。这不只是一个“最佳实践”，而是一个严格的契约。
简单来说，Java 规范要求：
- 如果两个对象通过
equals()
方法判断是相等的，那么它们的
hashCode()
方法返回的值必须是相同的。
- 如果两个对象通过
equals()
方法判断是不相等的，那么它们的
hashCode()
方法返回的值可以相同，也可以不同。但为了性能，最好是不同。
现在我们想想，如果这个契约被打破了，会发生什么？ 假设你有一个
Person
类，里面有
name
和
age
字段，你只重写了
equals()
方法，让同名同龄的人被认为是相等，但忘记重写
hashCode()
。当你把两个同名同龄的
Person
对象 A 和 B 加入
HashSet
时，会发生什么？ 因为没有重写
hashCode()
，它们会继承
Object
默认的
hashCode()
，这个哈希值通常是基于对象的内存地址生成的。所以，即使 A 和 B
equals()
返回
true
，它们的
hashCode()
却很可能是不同的。这会导致
HashSet
认为它们是两个不同的对象，把它们放到了
HashMap
的不同桶里，结果就是你的
HashSet
里出现了“逻辑上重复”的元素，这显然不是你想要的。
反过来，如果你只重写了
hashCode()
，但
equals()
没重写，那更糟糕。两个哈希值相同的对象，如果
equals()
却返回
false
（因为默认的
equals
比较的是内存地址），
HashSet
仍然会把它们当成不同对象处理。
所以，每一次当你创建一个自定义类，并且打算将它的实例作为
HashSet
（或
HashMap
的键）的元素时，花点时间思考并正确地重写
hashCode()
和
equals()
，这能避免很多难以察觉的运行时问题。这不光是为了
HashSet
，也是为了整个 Java 集合框架的正确性。
HashSet
HashSet
的性能特点和适用场景是什么？
HashSet
的性能特点，坦白讲，就是快！在理想情况下，也就是哈希函数设计得当、冲突较少的情况下，它的
add
、
remove
和
contains
操作的平均时间复杂度都是 O(1)。这得益于哈希表直接通过哈希值定位元素的特性。你可以想象一下，就像你有一个巨大的文件柜，每个抽屉都标着一个编号，你想找一份文件，直接根据文件的编号（哈希值）就能找到对应的抽屉，而不需要一个个抽屉地翻找。
然而，这种 O(1) 的理想情况并非绝对。如果哈希函数设计得不好，或者数据本身分布极端，导致大量元素哈希到同一个桶里，那么这个桶就可能变成一个很长的链表（或红黑树，Java 8 以后），此时操作的时间复杂度就会退化到 O(n)，和
ArrayList
查找的效率差不多了，甚至更差。这就像文件柜里所有文件都挤在一个抽屉里，你还是得从头翻到尾。
具体到适用场景：
- 需要存储不重复元素时： 这是
HashSet
最核心的用途。比如你需要统计一个文本文件中所有不重复的单词，或者在一个用户列表中找出所有唯一的 IP 地址。
- 需要快速判断元素是否存在时： 如果你的应用场景需要频繁地检查某个元素是否已经存在于一个集合中，
HashSet
的
contains()
方法能提供极高的效率。比如，在游戏中检查一个玩家是否已经解锁了某个成就。
- 对元素顺序没有要求时： 如果你不在乎元素的插入顺序或任何排序，只关心其存在性，那么
HashSet
是一个非常好的选择，因为它避免了维护顺序带来的额外开销。
但要注意，
HashSet
在内存使用上会比
ArrayList
稍微多一点，因为它需要存储
HashMap
的结构（桶数组、链表/红黑树节点等），以及每个元素对应一个
PRESENT
占位符。不过，对于大多数应用来说，这点开销通常可以忽略不计。
HashSet
HashSet
和
ArrayList
、
TreeSet
有何不同？
当我们谈论 Java 集合时，
HashSet
、
ArrayList
和
TreeSet
是三个非常基础且常用的实现，它们各自有其独特的设计哲学和适用场景。理解它们的差异，能帮助我们更明智地选择合适的工具。
1.
HashSet
：无序、唯一、快速
- 底层实现： 基于
HashMap
。
- 元素特性： 存储的元素是唯一的，不保证任何插入顺序或排序。
- 性能：
add
,
remove
,
contains
操作的平均时间复杂度为 O(1)。
- 适用场景： 当你只需要一个快速的集合来存储不重复的元素，并且不关心元素的顺序时，
HashSet
是首选。它利用哈希表的高效查找机制，非常适合需要频繁进行元素存在性检查的场景。
2.
ArrayList
：有序、可重复、基于索引
- 底层实现： 基于动态数组。
- 元素特性： 存储的元素可以重复，并且保持元素的插入顺序。你可以通过索引访问元素。
- 性能：
- 按索引访问（
get(index)
）是 O(1)。
- 在末尾添加（
add(element)
）是 O(1) 均摊。
- 在中间插入或删除元素是 O(n)，因为需要移动后续元素。
- 查找元素（
contains
）是 O(n)，因为它需要遍历。
- 按索引访问（
- 适用场景： 当你需要一个可以存储重复元素的列表，并且对元素的顺序有严格要求，或者需要频繁通过索引访问元素时，
ArrayList
是理想选择。
3.
TreeSet
：有序、唯一、基于排序
- 底层实现： 基于
TreeMap
，本质上是一个红黑树。
- 元素特性： 存储的元素是唯一的，并且会按照自然排序（元素实现
Comparable
接口）或自定义排序（提供
Comparator
）进行排序。
- 性能：
add
,
remove
,
contains
操作的时间复杂度都是 O(log n)。
- 适用场景： 当你需要一个存储不重复元素的集合，并且这些元素必须保持排序状态时，
TreeSet
是不二之选。它能让你方便地获取集合中的最小/最大元素，或者进行范围查询。但代价是，它的操作速度不如
HashSet
那么快，因为它需要维护树的平衡。
总的来说，选择哪个集合，关键在于你对“顺序”、“唯一性”和“性能”这三个维度的具体需求。没有哪个是“最好”的，只有“最适合”你当前场景的。
评论（已关闭）
评论已关闭