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替换旧的,但对于
H而言,它只关心元素是否存在,替换与否并不影响其唯一性保证。ashSet
同样地,
contains(Object o)方法会调用
map.containsKey(o)。这个过程同样依赖于
o的
hashCode()和
equals()方法来快速定位并判断元素是否存在。
remove(Object o)方法则调用
map.remove(o),也是基于哈希和相等性判断来移除元素。
所以,
HashSet的性能表现,以及它如何确保元素的唯一性,完全取决于其底层
HashMap的哈希算法和冲突解决机制。它不保证元素的顺序,因为哈希表本身就是无序的。
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的性能特点,坦白讲,就是快!在理想情况下,也就是哈希函数设计得当、冲突较少的情况下,它的
add、
remove和
contains操作的平均时间复杂度都是 O(1)。这得益于哈希表直接通过哈希值定位元素的特性。你可以想象一下,就像你有一个巨大的文件柜,每个抽屉都标着一个编号,你想找一份文件,直接根据文件的编号(哈希值)就能找到对应的抽屉,而不需要一个个抽屉地翻找。
然而,这种 O(1) 的理想情况并非绝对。如果哈希函数设计得不好,或者数据本身分布极端,导致大量元素哈希到同一个桶里,那么这个桶就可能变成一个很长的链表(或红黑树,Java 8 以后),此时操作的时间复杂度就会退化到 O(n),和
ArrayList查找的效率差不多了,甚至更差。这就像文件柜里所有文件都挤在一个抽屉里,你还是得从头翻到尾。
具体到适用场景:
HashSet最核心的用途。比如你需要统计一个文本文件中所有不重复的单词,或者在一个用户列表中找出所有唯一的 IP 地址。
HashSet的
contains()方法能提供极高的效率。比如,在游戏中检查一个玩家是否已经解锁了某个成就。
HashSet是一个非常好的选择,因为它避免了维护顺序带来的额外开销。
但要注意,
HashSet在内存使用上会比
ArrayList稍微多一点,因为它需要存储
HashMap的结构(桶数组、链表/红黑树节点等),以及每个元素对应一个
PRESENT占位符。不过,对于大多数应用来说,这点开销通常可以忽略不计。
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) 均摊。
contains)是 O(n),因为它需要遍历。
ArrayList是理想选择。
3. TreeSet
:有序、唯一、基于排序
TreeMap,本质上是一个红黑树。
Comparable接口)或自定义排序(提供
Comparator)进行排序。
add,
remove,
contains操作的时间复杂度都是 O(log n)。
TreeSet是不二之选。它能让你方便地获取集合中的最小/最大元素,或者进行范围查询。但代价是,它的操作速度不如
HashSet那么快,因为它需要维护树的平衡。
总的来说,选择哪个集合,关键在于你对“顺序”、“唯一性”和“性能”这三个维度的具体需求。没有哪个是“最好”的,只有“最适合”你当前场景的。