java源码分析之HashSet

时间:2022-01-19 17:54:06

http://blog.csdn.net/jzhf2012/article/details/8540696

 

 Java容器类的用途是“保存对象”,分为两类:Map——存储“键值对”组成的对象;Collection——存储独立元素。Collection又可以分为List和Set两大块。List保持元素的顺序,而Set不能有重复的元素。

     本文分析Set中最常用的HashSet类,并简单介绍和对比LinkedHashSet。

     首先对Set接口进行简要的说明。 

     存入Set的每个元素必须是惟一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set不保证维护元素的次序。Set与Collection有完全一样的接口。

     在没有其他限制的情况下需要Set时应尽量使用HashSet,因为它对速度进行了优化。

     下面是HashSet的定义: 

1 public class HashSet<E>
2 extends AbstractSet<E>
3 implements Set<E>, Cloneable, java.io.Serializable

     HashSet继承了AbstractSet,实现了Set接口。其实AbstractSet已经实现Set接口了。AbstractSet继承自AbstractCollection,而AbstractCollection实现了Collection接口的部分方法,而Set接口和Collection接口完全一致,所以AbstractSet只是实现了AbstractCollection没有实现的Set接口的方法和重写了部分AbstractCollection已经实现的方法。

     下面是HashSet定义的属性:

1 private transient HashMap<E,Object> map;
2 private static final Object PRESENT = new Object();

     为什么会有一个HashMap<E,Object>定义的属性?

     想一下HashMap有什么特点:基于哈希表,存储键值对,Key不能相同等等。Key不能相同!这个特点是不是和Set的元素不能相同和类似?如果将Set的元素当成Map的Key,是否就保证了元素的不重复?!答案是肯定的。但是Map存储键值对,Key有了,那么Value呢?这正是第二个属性PERSENT的意义。看到PERSENT属性时一个Object对象,且是static和final的,它的用途就是当做Value存进map中。

     总结一下,HashSet的实现方式大致如下,通过一个HashMap存储元素,元素是存放在HashMap的Key中,而Value统一使用一个Object对象。

     这样看来HashSet应该很简单,应该只是使用了HashMap的部分内容来实现。

     下面看具体的其它代码来验证上面的猜想。

     构造方法:

java源码分析之HashSet
 1 // 构造方法一:调用默认的HashMap构造方法初始化map
2 public HashSet() {
3 map = new HashMap<E,Object>();
4 }
5 // 构造方法二:根据给定的Collection参数调用HashMap(int initialCapacity)的构造方法创建一个HashMap(这个构造方法的HashMap的源码分析里已经描述过了)
6 // 调用addAll方法将c中的元素添加到HashSet对象中
7 public HashSet(Collection<? extends E> c) {
8 map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
9 addAll(c);
10 }
11 // 构造方法三:构造一个指定初始化容量和负载因子的HashMap
12 public HashSet(int initialCapacity, float loadFactor) {
13 map = new HashMap<E,Object>(initialCapacity, loadFactor);
14 }
15 // 构造方法四:构造一个指定初始化容量的HashMap
16 public HashSet(int initialCapacity) {
17 map = new HashMap<E,Object>(initialCapacity);
18 }
19 // 构造方法五:构造一个指定初始化容量和负载因子的LinkedHashMap
20 // dummy参数被忽略,只是用于区分其他的,包含一个int、float参数的构造方法
21 HashSet(int initialCapacity, float loadFactor, boolean dummy) {
22 map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
23 }
java源码分析之HashSet

     上面的构造方法都很简单,只有构造方法二中调用了addAll(Collection<? extends E> c)方法。该方法在AbstractCollection中定义,HashSet通过继承拥有该方法。

java源码分析之HashSet
1 public boolean addAll(Collection<? extends E> c) {
2 boolean modified = false;
3 Iterator<? extends E> e = c.iterator();
4 while (e.hasNext()) {
5 if (add(e.next()))
6 modified = true;
7 }
8 return modified;
9 }
java源码分析之HashSet

     这个方法通过遍历c中的元素,然后调用add(E e)方法添加元素。

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

     看add(E e)方法只是调用了HashMap(构造方法中提供了创建LinkedHashMap的方式,但是LinkedHashMap是继承HashMap的,put方法也是调用HashMap的put方法)的put方法将e当做Key,PERSENT当做Value加入到map中并根据返回值判断是否添加成功。

     因为HashMap的put方法在Key已经存在的情况下返回的是对应的Value值,若Key不存在则返回的是null,所以根据返回的是null可以确定新元素被添加到HashSet中了,如果返回的是其他值则说明Key已经存在,即元素已经在HashSet中已经存在,add(E e)返回的结果为false。虽然add(E e)返回false说明了HashSet添加元素失败,但实际上其中的map中的内容已经被替换,原先的值被PERSENT代替。

     如果原先的值就是null呢?其实不用考虑这个问题,因为通过HashSet添加的元素,Value的内容都是PERSENT,不会出现null的情况。

     iterator()

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

     很清楚了,返回的是HashMap中KeySet的迭代器。

     size()

1 public int size() {
2 return map.size();
3 }

     size()方法同样返回的是map的大小,所以HashSet根本就没定义size属性。

1 public boolean isEmpty() {
2 return map.isEmpty();
3 }

     既然size()用的是map的大小,那么isEmpty()自然也是判断map。

java源码分析之HashSet
 1 public boolean contains(Object o) {
2 return map.containsKey(o);
3 }
4 public void clear() {
5 map.clear();
6 }
7 public Object clone() {
8 try {
9 HashSet<E> newSet = (HashSet<E>) super.clone();
10 newSet.map = (HashMap<E, Object>) map.clone();
11 return newSet;
12 } catch (CloneNotSupportedException e) {
13 throw new InternalError();
14 }
15 }
java源码分析之HashSet

     这几个方法就不解释了。

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

     remove(Object o)为什么还要判断结果呢?因为通过HashSet存入的元素,所对应的Value值都是PERSENT,如果传入的o不存在,map的remove方法返回为null,则对应的结果是HashSet的remove操作应该放回false,所以这里根据返回的结果判断是否移除成功。

     只能感叹HashMap太强大了,HashSet是完全使用HashMap来实现的。