概述
在上一篇文章中,我们介绍了 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); 只有不存在时,才会添加,并返回true */ boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c); 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+" "); } } } 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; } } }
|
输出结果为:
tip: 现代的 IDE 能够非常智能的生成类的重写 hashCode 和 equals 方法,例如 IntelliJ IDEA ,具体方式使用快捷键 cmd + N
,在弹出的窗口上选择 equals() and 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 ,它可以排序。我们将在后续的文章中介绍。