10.2 剖析HashSet
10.2 剖析HashSet
10.1节提到了Set接口,Map接口的两个方法keySet和entrySet返回的都是Set,本节介绍Set接口的一个重要实现类HashSet。与HashMap类似,字面上看,HashSet由两个单词组成:Hash和Set。其中,Set表示接口,实现Set接口也有多种方式,各有特点,Hash-Set实现的方式利用了Hash。下面,我们先来看HashSet的用法,然后看实现原理,最后总结分析HashSet的特点。
10.2.1 用法
我们先介绍Set接口,然后介绍HashSet的使用和应用场景。
Set表示的是没有重复元素、且不保证顺序的容器接口,它扩展了Collection,但没有定义任何新的方法,不过,对于其中的一些方法,它有自己的规范。Set接口的完整定义如代码清单10-3所示。
1 | public interface Set<E> extends Collection<E> { |
与HashMap类似,HashSet的构造方法有:
1 | public HashSet() |
initialCapacity和loadFactor的含义与HashMap中的是一样的。
HashSet的使用也很简单,比如:
1 | Set<String> set = new HashSet<String>(); |
输出为:
1 | hello 老马 world |
“hello”被添加了两次,但只会保存一份,输出也没有什么特别的顺序。
与HashMap类似,HashSet要求元素重写hashCode和equals方法,且对于两个对象,如果equals相同,则hashCode也必须相同,如果元素是自定义的类,需要注意这一点。比如,有一个表示规格的类Spec,有大小和颜色两个属性:
1 | class Spec { |
Spec的Set为:
1 | Set<Spec> set = new HashSet<Spec>(); |
输出为:
1 | [[size=M, color=red], [size=M, color=red]] |
同一个规格输出了两次,为避免这一点,需要为Spec重写hashCode和equals方法。利用IDE开发工具往往可以自动生成这两个方法,比如Eclipse中,可以通过”Source”->”Generate hashCode() and equals() …”,我们就不赘述了。
HashSet有很多应用场景,比如:
1)排重,如果对排重后的元素没有顺序要求,则HashSet可以方便地用于排重;
2)保存特殊值,Set可以用于保存各种特殊值,程序处理用户请求或数据记录时,根据是否为特殊值判断是否进行特殊处理,比如保存IP地址的黑名单或白名单;
3)集合运算,使用Set可以方便地进行数学集合中的运算,如交集、并集等运算,这些运算有一些很现实的意义。比如,用户标签计算,每个用户都有一些标签,两个用户的标签交集就表示他们的共同特征,交集大小除以并集大小可以表示他们的相似程度。
10.2.2 实现原理
HashSet内部是用HashMap实现的,它内部有一个HashMap实例变量,如下所示:
1 | private transient HashMap<E, Object> map; |
我们知道,Map有键和值,HashSet相当于只有键,值都是相同的固定值,这个值的定义为:
1 | private static final Object PRESENT = new Object(); |
理解了这个内部组成,它的实现方法也就比较容易理解了,我们来看下代码。
HashSet的构造方法,主要就是调用了对应的HashMap的构造方法,比如:
1 | public HashSet(int initialCapacity, float loadFactor) { |
接受Collection参数的构造方法稍微不一样,代码为:
1 | public HashSet(Collection<? extends E> c) { |
也很容易理解,c.size()/.75f
用于计算initialCapacity
,0.75f
是loadFactor的默认值。
我们看add方法的代码:
1 | public boolean add(E e) { |
就是调用map的put方法,元素e用于键,值就是固定值PRESENT, put返回null表示原来没有对应的键,添加成功了。HashMap中一个键只会保存一份,所以重复添加HashMap不会变化。
检查是否包含元素,代码为:
1 | public boolean contains(Object o) { |
就是检查map中是否包含对应的键。
删除元素的代码为:
1 | public boolean remove(Object o) { |
就是调用map的remove方法,返回值为PRESENT表示原来有对应的键且删除成功了。
迭代器的代码为:
1 | public Iterator<E> iterator() { |
就是返回map的keySet的迭代器。
10.2.3 小结
本节介绍了HashSet的用法和实现原理,它实现了Set接口,内部实现利用了HashMap,有如下特点:
1)没有重复元素;
2)可以高效地添加、删除元素、判断元素是否存在,效率都为O(1);
3)没有顺序。
HashSet可以方便高效地实现去重、集合运算等功能。如果要保持添加的顺序,可以使用HashSet的一个子类LinkedHashSet。Set还有一个重要的实现类TreeSet,它可以排序。这两个类,我们在后续小节介绍。