Java集合框架深度解析:HashSet
Java集合框架深度解析:HashSet
一、从HashMap说起
在理解HashSet之前,我们需要先了解HashMap,因为HashSet的底层实现就是基于HashMap的。
1.1 HashMap简介
HashMap在博主之前的文章里面有过详解:
Java集合框架深度解析:HashMap
HashMap是Java中最常用的键值对存储结构,它的特点是:
- 基于哈希表实现
- 键(Key)不能重复
- 允许null键和null值
- 无序(不保证元素顺序)
- 时间复杂度:O(1)(理想情况下)
1.2 HashMap的核心结构
// HashMap的内部结构(简化版)
public class HashMap<K,V> {
// 存储数据的数组,每个元素是一个链表(或红黑树)
transient Node<K,V>[] table;
// 内部节点类
static class Node<K,V> {
final int hash; // 键的哈希值
final K key; // 键
V value; // 值
Node<K,V> next; // 指向下一个节点(链表)
}
}
HashMap的存储原理:
- 计算key的hashCode
- 通过hash算法确定存储位置(数组下标)
- 如果位置为空,直接存储
- 如果位置已有元素(哈希冲突),使用链表或红黑树存储
二、HashSet核心原理
2.1 HashSet的本质
HashSet就是HashMap的"简化版",它只使用HashMap的键(Key),而值(Value)是一个固定的占位对象。
// HashSet的源码(简化版)
public class HashSet<E> {
// 底层使用HashMap存储
private transient HashMap<E, Object> map;
// 所有值都使用这个固定对象(占位符)
private static final Object PRESENT = new Object();
// 构造方法
public HashSet() {
map = new HashMap<>();
}
// 添加元素:将元素作为HashMap的key,PRESENT作为value
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
// 删除元素:删除HashMap中的key
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
// 判断是否包含:判断HashMap中是否有这个key
public boolean contains(Object o) {
return map.containsKey(o);
}
}
关键点:
- HashSet存储的元素 = HashMap的键(Key)
- HashMap的值(Value)= 固定的PRESENT对象
- 因为HashMap的键不能重复,所以HashSet的元素也不能重复
2.2 为什么要用HashMap实现HashSet?
- 复用代码:HashMap已经实现了哈希表的所有逻辑,直接复用
- 保证唯一性:HashMap的键天然不重复
- 高效查找:继承HashMap的O(1)时间复杂度
2.3 哈希冲突与解决方案
什么是哈希冲突?
不同的元素计算出相同的哈希值,需要存储在同一个位置。
例如:
元素A的hashCode = 15,存储位置 = 15 % 16 = 15
元素B的hashCode = 31,存储位置 = 31 % 16 = 15
→ 冲突!两个元素要存储在同一个位置
解决方案:链表 + 红黑树(JDK 8优化)
// HashMap的内部结构
transient Node<K,V>[] table; // 数组
// 每个数组位置可以是:
// 1. 单个节点(无冲突)
// 2. 链表(冲突少,链表长度 < 8)
// 3. 红黑树(冲突多,链表长度 >= 8)
static class Node<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; // 链表指针
}
static class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // 红黑树指针
TreeNode<K,V> left;
TreeNode<K,V> right;
// ...
}
链表转红黑树的条件(JDK 8):
- 链表长度 >= 8
- 数组容量 >= 64
为什么要转红黑树?
- 链表查找:O(n)
- 红黑树查找:O(log n)
- 当冲突严重时,红黑树性能更好
图解:
数组索引 存储结构
[0] → null
[1] → Node("A") → Node("B") → Node("C") (链表)
[2] → TreeNode(红黑树根节点) (红黑树)
[3] → Node("D") (单节点)
...
[15] → null
2.4 负载因子(Load Factor)
负载因子 = 元素个数 / 数组容量
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 扩容阈值 = 容量 × 负载因子
int threshold = capacity * loadFactor;
// 例如:容量16,负载因子0.75
// 扩容阈值 = 16 × 0.75 = 12
// 当元素个数达到12时,触发扩容
为什么是0.75?
这是时间和空间的权衡:
- 太小(如0.5):频繁扩容,浪费时间,但空间利用率低
- 太大(如1.0):节省空间,但哈希冲突增多,查找变慢
- 0.75:经过泊松分布计算,是最优平衡点
注:这一部分在博主之前的Java集合框架深度解析:HashMap一文里有详细解释,因为HashSet是基于HashMap实现了,于是很多特性和HashMap相似。
2.5 扩容机制
什么时候扩容?
if (size > threshold) {
resize(); // 扩容
}
如何扩容?
// 1. 创建新数组(容量翻倍)
Node<K,V>[] newTable = new Node[oldCapacity * 2];
// 2. 重新计算每个元素的位置(rehash)
for (Node<K,V> node : oldTable) {
// 重新计算索引
int newIndex = hash(node.key) & (newCapacity - 1);
// 放入新数组
newTable[newIndex] = node;
}
// 3. 替换旧数组
table = newTable;
扩容的性能影响:
- 扩容需要重新计算所有元素的位置(rehash)
- 时间复杂度:O(n)
- 因此,预估容量很重要!
优化建议:
// 不好:频繁扩容
HashSet<String> set = new HashSet<>(); // 容量16
for (int i = 0; i < 1000; i++) {
set.add("item" + i); // 会扩容多次:16→32→64→128→256→512→1024
}
// 好:预估容量
int expectedSize = 1000;
int initialCapacity = (int) (expectedSize / 0.75) + 1; // 1334
HashSet<String> set = new HashSet<>(initialCapacity);
for (int i = 0; i < 1000; i++) {
set.add("item" + i); // 不会扩容
}
三、HashSet的特点
3.1 核心特性
| 特性 | 说明 |
|---|---|
| 元素唯一 | 不允许重复元素(通过hashCode和equals判断) |
| 无序 | 不保证元素的顺序(遍历顺序可能与插入顺序不同) |
| 允许null | 可以存储一个null元素 |
| 非线程安全 | 多线程环境需要外部同步 |
| 时间复杂度 | 添加、删除、查找:O(1)(理想情况) |
注:HashSet 本身完全不保证有序,也不会主动做任何排序操作,偶尔打印出来看着是 “排好序的”,纯粹是「巧合」,本质是哈希值和底层数组存储的偶然结果,不是它的特性。(例子见 4.3)
3.2 元素唯一性的判断
HashSet判断两个元素是否相同的步骤:
// 1. 先比较hashCode
if (e1.hashCode() != e2.hashCode()) {
return false; // hashCode不同,一定不是同一个对象
}
// 2. hashCode相同,再用equals比较
return e1.equals(e2); // equals返回true,才认为是同一个对象
示例:
public class Student {
private String name;
private int age;
// 必须重写hashCode和equals,否则HashSet无法正确判断重复
@Override
public int hashCode() {
return Objects.hash(name, age); // 根据name和age计算hash值
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Student student = (Student) obj;
return age == student.age && Objects.equals(name, student.name);
}
}
// 使用示例
HashSet<Student> students = new HashSet<>();
students.add(new Student("张三", 20));
students.add(new Student("张三", 20)); // 重复,不会添加
System.out.println(students.size()); // 输出:1
四、HashSet常用方法
4.1 构造方法
// 1. 默认构造(初始容量16,负载因子0.75)
HashSet<String> set1 = new HashSet<>();
// 2. 指定初始容量
HashSet<String> set2 = new HashSet<>(32);
// 3. 指定初始容量和负载因子
HashSet<String> set3 = new HashSet<>(32, 0.8f);
// 4. 从其他集合创建
List<String> list = Arrays.asList("A", "B", "C");
HashSet<String> set4 = new HashSet<>(list);
4.2 添加元素
HashSet<String> set = new HashSet<>();
// add(E e) - 添加元素,返回boolean
boolean added1 = set.add("Apple"); // true(添加成功)
boolean added2 = set.add("Apple"); // false(已存在,添加失败)
// addAll(Collection c) - 批量添加
set.addAll(Arrays.asList("Banana", "Cherry"));
4.3 删除元素
HashSet<String> set = new HashSet<>(Arrays.asList("A", "B", "C", "D"));
System.out.println(set);//输出["A", "B", "C", "D"]
// remove(Object o) - 删除指定元素
boolean removed = set.remove("B"); // true(删除成功)
// removeAll(Collection c) - 批量删除
set.removeAll(Arrays.asList("C", "D"));
// removeIf(Predicate filter) - 条件删除(Java 8+)
set.removeIf(s -> s.startsWith("A")); // 删除以A开头的元素
// clear() - 清空所有元素
set.clear();
4.4 查询元素
HashSet<String> set = new HashSet<>(Arrays.asList("Apple", "Banana", "Cherry"));
// contains(Object o) - 判断是否包含
boolean hasApple = set.contains("Apple"); // true
// containsAll(Collection c) - 判断是否包含所有元素
boolean hasAll = set.containsAll(Arrays.asList("Apple", "Banana")); // true
// isEmpty() - 判断是否为空
boolean empty = set.isEmpty(); // false
// size() - 获取元素个数
int size = set.size(); // 3
4.5 遍历元素
HashSet<String> set = new HashSet<>(Arrays.asList("Apple", "Banana", "Cherry"));
// 方式1:增强for循环
for (String fruit : set) {
System.out.println(fruit);
}
// 方式2:迭代器
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
String fruit = iterator.next();
System.out.println(fruit);
// 可以在遍历时删除
if (fruit.equals("Banana")) {
iterator.remove();
}
}
// 方式3:forEach(Java 8+)
set.forEach(fruit -> System.out.println(fruit));
// 方式4:Stream API(Java 8+)
set.stream()
.filter(fruit -> fruit.startsWith("A"))
.forEach(System.out::println);
4.6 集合运算
HashSet<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
HashSet<Integer> set2 = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));
// 并集(Union)- 所有元素
HashSet<Integer> union = new HashSet<>(set1);
union.addAll(set2); // {1, 2, 3, 4, 5, 6, 7, 8}
// 交集(Intersection)- 共同元素
HashSet<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2); // {4, 5}
// 差集(Difference)- set1有但set2没有的元素
HashSet<Integer> difference = new HashSet<>(set1);
difference.removeAll(set2); // {1, 2, 3}
五、HashSet使用场景
5.1 去重
// 场景:从列表中去除重复元素
List<String> list = Arrays.asList("A", "B", "A", "C", "B", "D");
HashSet<String> uniqueSet = new HashSet<>(list);
System.out.println(uniqueSet); // [A, B, C, D]
// 转回List
List<String> uniqueList = new ArrayList<>(uniqueSet);
5.2 快速查找
// 场景:判断元素是否存在(O(1)时间复杂度)
HashSet<String> blacklist = new HashSet<>(Arrays.asList("user1", "user2", "user3"));
// 快速判断用户是否在黑名单中
if (blacklist.contains("user1")) {
System.out.println("用户在黑名单中");
}
5.3 集合运算
// 场景:找出两个用户的共同好友
HashSet<String> user1Friends = new HashSet<>(Arrays.asList("Alice", "Bob", "Charlie"));
HashSet<String> user2Friends = new HashSet<>(Arrays.asList("Bob", "Charlie", "David"));
// 共同好友(交集)
HashSet<String> commonFriends = new HashSet<>(user1Friends);
commonFriends.retainAll(user2Friends);
System.out.println("共同好友:" + commonFriends); // [Bob, Charlie]
六、HashSet vs 其他Set实现
6.1 LinkedHashSet
LinkedHashSet = HashSet + 双向链表
// LinkedHashSet保持插入顺序
LinkedHashSet<String> linkedSet = new LinkedHashSet<>();
linkedSet.add("Banana");
linkedSet.add("Apple");
linkedSet.add("Cherry");
// 遍历顺序 = 插入顺序
for (String fruit : linkedSet) {
System.out.println(fruit); // Banana, Apple, Cherry
}
底层实现:
public class LinkedHashSet<E> extends HashSet<E> {
// 底层使用LinkedHashMap(HashMap + 双向链表)
public LinkedHashSet() {
super(16, .75f, true); // 调用HashSet的特殊构造方法
}
}
特点对比:
| 特性 | HashSet | LinkedHashSet |
|---|---|---|
| 底层实现 | HashMap | LinkedHashMap |
| 元素顺序 | 无序 | 保持插入顺序 |
| 性能 | 稍快 | 稍慢(维护链表) |
| 内存占用 | 较小 | 较大(额外链表) |
6.2 TreeSet
TreeSet基于红黑树实现,元素自动排序
// TreeSet自动排序
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(2);
treeSet.add(8);
treeSet.add(1);
System.out.println(treeSet); // [1, 2, 5, 8](自动升序)
// 自定义排序
TreeSet<String> customSet = new TreeSet<>((s1, s2) -> s2.compareTo(s1)); // 降序(Lambda表达式)
customSet.addAll(Arrays.asList("C", "A", "B"));
System.out.println(customSet); // [C, B, A]
特点对比:
| 特性 | HashSet | TreeSet |
|---|---|---|
| 底层实现 | HashMap(哈希表) | TreeMap(红黑树) |
| 元素顺序 | 无序 | 自动排序 |
| 时间复杂度 | O(1) | O(log n) |
| 是否允许null | 是 | 否 |
| 使用场景 | 快速查找、去重 | 需要排序的场景 |
七、HashMap与HashSet的关系总结
7.1 继承关系图
Collection (接口)
↓
Set (接口)
↓
HashSet (类) ----底层使用----> HashMap (类)
↓
LinkedHashSet (类) ----底层使用----> LinkedHashMap (类)
7.2 对应关系
| HashSet | HashMap |
|---|---|
| 存储元素 | 存储键值对 |
| 元素 = HashMap的Key | Key-Value对 |
| 不允许重复元素 | 不允许重复Key |
| 只关心元素本身 | 关心Key和Value的映射关系 |
7.3 源码对比
// HashSet的add方法
public boolean add(E e) {
return map.put(e, PRESENT) == null;
// e作为key,PRESENT作为value
}
// HashMap的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
// 存储key-value对
}
八、性能优化建议
8.1 初始容量设置
// 不好:频繁扩容,影响性能
HashSet<String> set1 = new HashSet<>(); // 默认容量16
for (int i = 0; i < 1000; i++) {
set1.add("item" + i); // 会触发多次扩容
}
// 好:预估容量,减少扩容
int expectedSize = 1000;
int initialCapacity = (int) (expectedSize / 0.75) + 1; // 考虑负载因子
HashSet<String> set2 = new HashSet<>(initialCapacity);
for (int i = 0; i < 1000; i++) {
set2.add("item" + i); // 不会扩容或扩容次数少
}
8.2 正确重写hashCode和equals
// 不好:没有重写hashCode和equals
public class BadStudent {
private String name;
private int age;
// 没有重写hashCode和equals,HashSet无法正确判断重复
}
// 好:正确重写
public class GoodStudent {
private String name;
private int age;
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
GoodStudent that = (GoodStudent) obj;
return age == that.age && Objects.equals(name, that.name);
}
}
8.3 避免在遍历时修改
这点也在博主之前的Java集合框架深入解析:ArrayList & LinkedList一文中提到。就是Fail-Fast 机制。ArrayList,LinkedList和HashMap都实现了这一机制。
HashSet<String> set = new HashSet<>(Arrays.asList("A", "B", "C"));
// 错误:会抛出ConcurrentModificationException
for (String s : set) {
if (s.equals("B")) {
set.remove(s); // 不能在增强for循环中直接修改
}
}
// 正确:使用迭代器
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
if (s.equals("B")) {
iterator.remove(); // 使用迭代器的remove方法
}
}
// 或者使用removeIf(Java 8+)
set.removeIf(s -> s.equals("B")); // 更简洁
九、常见面试题
问题1: HashSet如何保证元素唯一?
答: HashSet底层使用HashMap,将元素作为HashMap的key。当添加元素时,先计算hashCode确定位置,如果位置为空则直接添加;如果位置已有元素,再用equals比较,相同则不添加。
问题2: HashSet和HashMap的区别?
答:
- HashMap存储键值对,HashSet只存储元素
- HashMap的key不能重复,HashSet的元素不能重复
- HashSet底层就是用HashMap实现的,元素作为HashMap的key
问题3: HashSet是线程安全的吗?
答: 不是。多线程环境需要使用:
// 方式1:使用Collections.synchronizedSet
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
// 方式2:使用ConcurrentHashMap.newKeySet()(推荐)
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();
问题4: HashSet可以存储null吗?
答: 可以,但只能存储一个null(因为元素不能重复)。
问题5: 为什么重写equals必须重写hashCode?
答: 如果两个对象equals返回true,它们的hashCode必须相同,否则HashSet会认为它们是不同的对象,导致重复元素。
只重写 equals () 未重写 hashCode (),违反了「相等对象必须有相同哈希值」的核心约定,导致 HashSet 的「先 hash 找位置,后 equals 判重」逻辑完全走不到 equals () 这一步,最终把两个业务上相等的对象当成不同元素存储
问题6: HashSet的时间复杂度是多少?
答:
- 理想情况(无冲突):O(1)
- 最坏情况(全部冲突,JDK 7链表):O(n)
- 最坏情况(全部冲突,JDK 8红黑树):O(log n)
问题7: 为什么负载因子是0.75?
答: 这是时间和空间的权衡。太小会频繁扩容浪费时间,太大会增加哈希冲突降低性能。0.75是经过泊松分布计算的最优值。
十、常见陷阱与注意事项
10.1 陷阱1:忘记重写hashCode和equals
// 错误示例
public class Student {
private String name;
private int age;
// 没有重写hashCode和equals
}
HashSet<Student> set = new HashSet<>();
set.add(new Student("张三", 20));
set.add(new Student("张三", 20));
System.out.println(set.size()); // 输出:2(应该是1)
// 正确示例
public class Student {
private String name;
private int age;
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Student student = (Student) obj;
return age == student.age && Objects.equals(name, student.name);
}
}
10.2 陷阱2:在遍历时修改集合
HashSet<String> set = new HashSet<>(Arrays.asList("A", "B", "C"));
// 错误:抛出ConcurrentModificationException
for (String s : set) {
if (s.equals("B")) {
set.remove(s); // 不能在增强for中直接修改
}
}
// 正确方式1:使用迭代器
Iterator<String> it = set.iterator();
while (it.hasNext()) {
if (it.next().equals("B")) {
it.remove(); // 使用迭代器的remove
}
}
// 正确方式2:使用removeIf
set.removeIf(s -> s.equals("B"));
10.3 陷阱3:可变对象作为元素
// 危险:可变对象
public class MutableStudent {
private String name;
public void setName(String name) {
this.name = name; // 可以修改
}
@Override
public int hashCode() {
return Objects.hash(name); // hashCode依赖name
}
}
HashSet<MutableStudent> set = new HashSet<>();
MutableStudent student = new MutableStudent("张三");
set.add(student);
// 修改对象后,hashCode改变,导致无法找到
student.setName("李四");
System.out.println(set.contains(student)); // false!找不到了
// 建议:使用不可变对象
public final class ImmutableStudent {
private final String name; // final,不可修改
public ImmutableStudent(String name) {
this.name = name;
}
// 只有getter,没有setter
public String getName() {
return name;
}
}
10.4 陷阱4:初始容量设置不当
// 不好:容量太小,频繁扩容
HashSet<String> set1 = new HashSet<>(10);
for (int i = 0; i < 10000; i++) {
set1.add("item" + i); // 会扩容多次
}
// 不好:容量太大,浪费内存
HashSet<String> set2 = new HashSet<>(1000000);
set2.add("A"); // 只存1个元素,浪费99.9999%的空间
// 好:根据实际需求设置
int expectedSize = 1000;
int capacity = (int) (expectedSize / 0.75) + 1;
HashSet<String> set3 = new HashSet<>(capacity);
10.5 陷阱5:误用HashSet排序
// 错误:HashSet不保证顺序
HashSet<Integer> set = new HashSet<>();
set.add(3);
set.add(1);
set.add(2);
System.out.println(set); // 输出顺序不确定:可能是[1, 2, 3]或[3, 1, 2]
// 需要排序用TreeSet
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(1);
treeSet.add(2);
System.out.println(treeSet); // 输出:[1, 2, 3](自动排序)
// 需要保持插入顺序用LinkedHashSet
LinkedHashSet<Integer> linkedSet = new LinkedHashSet<>();
linkedSet.add(3);
linkedSet.add(1);
linkedSet.add(2);
System.out.println(linkedSet); // 输出:[3, 1, 2](插入顺序)
10.6 陷阱6:性能误区
// 误区:认为HashSet总是比ArrayList快
// 场景1:少量元素(< 100)
List<String> list = new ArrayList<>();
Set<String> set = new HashSet<>();
// ArrayList的contains可能更快(顺序查找,缓存友好)
list.contains("item"); // 可能比set.contains更快
// 场景2:大量元素(> 1000)
// HashSet的contains明显更快
set.contains("item"); // O(1) vs ArrayList的O(n)
// 建议:根据数据量选择
if (dataSize < 100) {
// 使用ArrayList
} else {
// 使用HashSet
}
十一、性能测试对比
11.1 HashSet vs ArrayList
// 测试代码
public class PerformanceTest {
public static void main(String[] args) {
int size = 10000;
// 准备数据
List<Integer> arrayList = new ArrayList<>();
Set<Integer> hashSet = new HashSet<>();
for (int i = 0; i < size; i++) {
arrayList.add(i);
hashSet.add(i);
}
// 测试contains性能
long start1 = System.nanoTime();
for (int i = 0; i < size; i++) {
arrayList.contains(i);
}
long end1 = System.nanoTime();
System.out.println("ArrayList contains: " + (end1 - start1) / 1000000 + "ms");
long start2 = System.nanoTime();
for (int i = 0; i < size; i++) {
hashSet.contains(i);
}
long end2 = System.nanoTime();
System.out.println("HashSet contains: " + (end2 - start2) / 1000000 + "ms");
}
}
// 输出结果(数据量10000):
// ArrayList contains: 245ms (O(n²))
// HashSet contains: 2ms (O(n))
// HashSet快了100多倍!
11.2 性能对比表
| 操作 | ArrayList | HashSet | 说明 |
|---|---|---|---|
| add() | O(1) | O(1) | 都很快 |
| contains() | O(n) | O(1) | HashSet快很多 |
| remove() | O(n) | O(1) | HashSet快很多 |
| 遍历 | O(n) | O(n) | ArrayList稍快(缓存友好) |
| 内存占用 | 小 | 大 | HashSet需要额外空间 |
十二、总结
- HashSet本质:基于HashMap实现,元素作为HashMap的key
- 核心特点:元素唯一、无序、允许null、非线程安全
- 时间复杂度:添加、删除、查找都是O(1)
- 使用场景:去重、快速查找、集合运算
- 注意事项:必须正确重写hashCode和equals
- 变体:
- LinkedHashSet:保持插入顺序
- TreeSet:自动排序
选择建议:
- 需要去重、快速查找 → HashSet
- 需要保持插入顺序 → LinkedHashSet
- 需要自动排序 → TreeSet
- 需要线程安全 → ConcurrentHashMap.newKeySet()
作者:[识君啊]
适用Java版本: Java 8+
更多推荐


所有评论(0)