Java 集合类详解-HashSet

概述


在上一篇文章中,我们介绍了 HashMap ,其中 keySet 和 entrySet 返回的是 Set 接口。本篇文章中,我们重点介绍 Set 接口的另外一个重要的实现类 HashSet 。

Set 表示的是没有重复元素、且不保证顺序的容器接口,它扩展了 Collection ,但没有定义任何新的方法,不过,对于其中的一些方法,它有自己的规范。其接口定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public interface Set<E> extends Collection<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
/* 迭代遍历时,不要求元素之间有特别的顺序
HashSet的实现就是没有顺序,但有的Set实现可能会有特定的顺序,比如TreeSet */
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
/* 添加元素, 如果集合中已经存在相同元素了,则不会改变集合,直接返回false,
只有不存在时,才会添加,并返回true */
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
// 重复的元素不添加,不重复的添加,如果集合有变化,返回true,没变化返回false
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
}

与 HashMap 类似,HashSet 的构造方法有:

1
2
3
4
public HashSet()
public HashSet(int initialCapacity)
public HashSet(int initialCapacity, float loadFactor)
public HashSet(Collection<? extends E> c)

其中 initialCapacity 和 loadFactor 与 HashMap 保持一致。

下面用一个简单的示例来进行说明:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
public class HashSetTester {
public static void main(String [] args) {
Set<String> set = new HashSet<String>();
set.add("hello");
set.add("golang");
set.add("world");
set.addAll(Arrays.asList(new String[]{"hello","java"}));
for(String s : set) {
System.out.print(s+" ");
}
}
}
// Output
hello golang java world

与 HashMap 类似, HashSet 要求元素重写 Object 类的 hashCode 和 equals 方法,并且判断两个对象是否相等,必须 equals 和 hashCode 都相同才行。让我们来看下面这个简单的示例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
public class OverrideTester {
public static void main(String [] args) {
Set<Spec> set = new HashSet<Spec>();
set.add(new Spec("M","red"));
set.add(new Spec("M","red"));
System.out.println(set);
}
private static class Spec {
String size;
String color;
public Spec(String size, String color) {
this.size = size;
this.color = color;
}
@Override
public String toString() {
return "[size=" + size + ", color=" + color + "]";
}
}
}

Spec 包括了 size 和 color 两个字段,虽然我们在向 HashSet 添加了 2 个 Spec 对象的 size 和 color 都相同,但是你会看到执行结果为:

1
[[size=M, color=red], [size=M, color=red]]

显然,Spec 对象才向 HashSet 当中添加时,没有达到过滤掉重复键值对的目的。正确的做法是重写 Object 类的 hashCode 和 equals 方法 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
public class OverrideTester {
public static void main(String [] args) {
Set<Spec> set = new HashSet<Spec>();
set.add(new Spec("M","red"));
set.add(new Spec("M","red"));
System.out.println(set);
}
private static class Spec {
String size;
String color;
public Spec(String size, String color) {
this.size = size;
this.color = color;
}
@Override
public String toString() {
return "[size=" + size + ", color=" + color + "]";
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Spec spec = (Spec) o;
if (size != null ? !size.equals(spec.size) : spec.size != null) return false;
return color != null ? color.equals(spec.color) : spec.color == null;
}
@Override
public int hashCode() {
int result = size != null ? size.hashCode() : 0;
result = 31 * result + (color != null ? color.hashCode() : 0);
return result;
}
}
}

输出结果为:

1
[[size=M, color=red]]

tip: 现代的 IDE 能够非常智能的生成类的重写 hashCode 和 equals 方法,例如 IntelliJ IDEA ,具体方式使用快捷键 cmd + N ,在弹出的窗口上选择 equals() and hashCode()

可以参考如下图示:
generate-equals-hashcode

HashSet 的应用场景

  • 排重:如果对排重后的元素没有顺序要求,则 HashSet 可以方便地用于排除重复数据。
  • 保存特殊值:Set 可以用于保存各种特殊值,程序处理用户请求或数据记录时,根据是否为特殊值判断是否进行特殊处理,比如保存IP地址的黑名单或白名单。
  • 集合运算:使用 Set 可以方便地进行数学集合中的运算,如交集、并集等运算,这些运算有一些很现实的意义。比如,用户标签计算,每个用户都有一些标签,两个用户的标签交集就表示他们的共同特征,交集大小除以并集大小可以表示他们的相似程度。

实现原理


内部构造

HashSet 内部是用 HashMap 实现的,维护了一个 HashMap 实例变量:

1
private transient HashMap<E,Object> map;

虽然内部维护的是一个 HashMap 的结构,但是 HashSet 没有键值对,而只有键,值都是固定的值,值的定义为:

1
private static final Object PRESENT = new Object();

构造函数

HashSet 的构造方法,主要就是调用了 HashMap 的构造方法:

1
2
3
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}

而接受 Collection 参数的构造方法有一些区别:

1
2
3
4
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}

其中 c.size()/.75f 用于计算 initialCapacity ,而 0.75f 为 loadFactor 的默认值。

添加元素 add

1
2
3
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

调用 map 的 put 方法,元素 e 用于键,值就是固定值 PRESENT , put 返回 null 表示原来没有对应的键,添加成功了。 HashMap 中一个键只会保存一份,所以重复添加 HashMap 不会变化。

检查是否包含元素 contains

1
2
3
public boolean contains(Object o) {
return map.containsKey(o);
}

删除元素 remove

1
2
3
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}

调用 map 的 remove 方法,返回值为 PRESENT 表示原来有对应的键且删除成功了。

迭代器

1
2
3
public Iterator<E> iterator() {
return map.keySet().iterator();
}

就是返回 map 的 keySet 的迭代器。

总结


HashSet 有如下 3 个最大的特点:

  • 没有重复元素。
  • 可以高效地添加、删除元素、判断元素是否存在,效率都为O(1) 。
  • 没有顺序。

HashSet 可以方便高效地实现去重、集合运算等功能。如果要保持添加的顺序,可以使用 HashSet 的一个子类 LinkedHashSet 。 Set 还有一个重要的实现类 TreeSet ,它可以排序。我们将在后续的文章中介绍。