说一下 HashSet 的实现原理？-Java面试题-PHP中文网

hashset内部使用hashmap存储元素，元素作为key，值为固定占位符，利用hashmap键的唯一性保证元素不重复；2. 其add、remove、contains操作依赖hashcode()和equals()方法正确实现，否则会导致逻辑重复或查找失败；3. 性能平均o(1)，适用于需快速判断存在性且无需顺序的场景；4. 与arraylist（有序可重复，索引访问快）和treeset（有序唯一，o(log n)性能）相比，hashset在无序唯一集合中查找最快。

说一下 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

登录后复制

操作时，会先计算

登录后复制

的

hashCode()

登录后复制

，根据这个哈希值找到对应的桶（bucket）。如果该桶为空，或者桶内没有与

登录后复制

相等的元素（通过

equals()

登录后复制

方法判断），那么

登录后复制

就会被放入该桶。如果桶内已经存在一个与

登录后复制

相等的元素，

HashMap

登录后复制

会用新的

登录后复制

替换旧的，但对于

HashSet

登录后复制

而言，它只关心元素是否存在，替换与否并不影响其唯一性保证。

同样地，

contains(Object o)

登录后复制

方法会调用

map.containsKey(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)。这得益于哈希表直接通过哈希值定位元素的特性。你可以想象一下，就像你有一个巨大的文件柜，每个抽屉都标着一个编号，你想找一份文件，直接根据文件的编号（哈希值）就能找到对应的抽屉，而不需要一个个抽屉地翻找。

一键职达

AI全自动批量代投简历软件，自动浏览招聘网站从海量职位中用AI匹配职位并完成投递的全自动操作，真正实现'一键职达'的便捷体验。

查看详情

然而，这种 O(1) 的理想情况并非绝对。如果哈希函数设计得不好，或者数据本身分布极端，导致大量元素哈希到同一个桶里，那么这个桶就可能变成一个很长的链表（或红黑树，Java 8 以后），此时操作的时间复杂度就会退化到 O(n)，和

ArrayList

登录后复制

查找的效率差不多了，甚至更差。这就像文件柜里所有文件都挤在一个抽屉里，你还是得从头翻到尾。

具体到适用场景：

需要存储不重复元素时： 这是
```
HashSet
```
登录后复制
最核心的用途。比如你需要统计一个文本文件中所有不重复的单词，或者在一个用户列表中找出所有唯一的 IP 地址。
需要快速判断元素是否存在时： 如果你的应用场景需要频繁地检查某个元素是否已经存在于一个集合中，
```
HashSet
```
登录后复制
的
```
contains()
```
登录后复制
方法能提供极高的效率。比如，在游戏中检查一个玩家是否已经解锁了某个成就。
对元素顺序没有要求时： 如果你不在乎元素的插入顺序或任何排序，只关心其存在性，那么
```
HashSet
```
登录后复制
是一个非常好的选择，因为它避免了维护顺序带来的额外开销。

但要注意，

HashSet

登录后复制

在内存使用上会比

ArrayList

登录后复制

稍微多一点，因为它需要存储

HashMap

登录后复制

的结构（桶数组、链表/红黑树节点等），以及每个元素对应一个

PRESENT

登录后复制

占位符。不过，对于大多数应用来说，这点开销通常可以忽略不计。

HashSet

登录后复制

和

ArrayList

登录后复制

、

TreeSet

登录后复制

有何不同？

当我们谈论 Java 集合时，

HashSet

登录后复制

、

ArrayList

登录后复制

和

TreeSet

登录后复制

是三个非常基础且常用的实现，它们各自有其独特的设计哲学和适用场景。理解它们的差异，能帮助我们更明智地选择合适的工具。

HashSet

登录后复制

：无序、唯一、快速

底层实现： 基于
```
HashMap
```
登录后复制
。
元素特性： 存储的元素是唯一的，不保证任何插入顺序或排序。
性能：
```
add
```
登录后复制
,
```
remove
```
登录后复制
,
```
contains
```
登录后复制
操作的平均时间复杂度为 O(1)。
适用场景： 当你只需要一个快速的集合来存储不重复的元素，并且不关心元素的顺序时，
```
HashSet
```
登录后复制
是首选。它利用哈希表的高效查找机制，非常适合需要频繁进行元素存在性检查的场景。

ArrayList

登录后复制

：有序、可重复、基于索引

底层实现： 基于动态数组。
元素特性： 存储的元素可以重复，并且保持元素的插入顺序。你可以通过索引访问元素。
性能：
- 按索引访问（
```
get(index)
```
  登录后复制
  ）是 O(1)。
- 在末尾添加（
```
add(element)
```
  登录后复制
  ）是 O(1) 均摊。
- 在中间插入或删除元素是 O(n)，因为需要移动后续元素。
- 查找元素（
```
contains
```
  登录后复制
  ）是 O(n)，因为它需要遍历。
适用场景： 当你需要一个可以存储重复元素的列表，并且对元素的顺序有严格要求，或者需要频繁通过索引访问元素时，
```
ArrayList
```
登录后复制
是理想选择。

TreeSet

登录后复制

：有序、唯一、基于排序

底层实现： 基于
```
TreeMap
```
登录后复制
，本质上是一个红黑树。
元素特性： 存储的元素是唯一的，并且会按照自然排序（元素实现
```
Comparable
```
登录后复制
接口）或自定义排序（提供
```
Comparator
```
登录后复制
）进行排序。
性能：
```
add
```
登录后复制
,
```
remove
```
登录后复制
,
```
contains
```
登录后复制
操作的时间复杂度都是 O(log n)。
适用场景： 当你需要一个存储不重复元素的集合，并且这些元素必须保持排序状态时，
```
TreeSet
```
登录后复制
是不二之选。它能让你方便地获取集合中的最小/最大元素，或者进行范围查询。但代价是，它的操作速度不如
```
HashSet
```
登录后复制
那么快，因为它需要维护树的平衡。