Java集合框架源码解析HashSet及LinkedHashSet

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

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

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

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

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

     下面是HashSet的定义&＃xff1a; 

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

     下面是HashSet定义的属性&＃xff1a;

     为什么会有一个HashMap定义的属性&＃xff1f;

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

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

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

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

     构造方法&＃xff1a;

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

     上面的构造方法都很简单&＃xff0c;只有构造方法二中调用了addAll(Collection c)方法。该方法在AbstractCollection中定义&＃xff0c;HashSet通过继承拥有该方法。

1 public boolean addAll(Collectionextends E> c) {
2 boolean modified &＃61; false;
3 Iteratorextends E> e &＃61; c.iterator();
4 while (e.hasNext()) {
5 if (add(e.next()))
6 modified &＃61; true;
7 }
8 return modified;
9 }

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

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

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

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

     iterator()

     很清楚了&＃xff0c;返回的是HashMap中KeySet的迭代器。

     size()

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

     既然size()用的是map的大小&＃xff0c;那么isEmpty()自然也是判断map。

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 newSet &＃61; (HashSet) super.clone();
10 newSet.map &＃61; (HashMap) map.clone();
11 return newSet;
12 } catch (CloneNotSupportedException e) {
13 throw new InternalError();
14 }
15 }

     这几个方法就不解释了。

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

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

---------------------------------------------------------------------------------------------------------------------------------

     LinkedHashSet源码分析

     LinkedHashSet具有HashSet的查询速度&＃xff0c;且内部使用链表维护元素的顺序&＃xff08;插入的次序&＃xff09;。于是在使用迭代器遍历Set时&＃xff0c;结果会按照元素的插入次序显示。

     看LinkedHashSet的内容。

1 public class LinkedHashSet
2 extends HashSet
3 implements Set, Cloneable, java.io.Serializable {
4
5 public LinkedHashSet(int initialCapacity, float loadFactor) {
6 super(initialCapacity, loadFactor, true);
7 }
8
9 public LinkedHashSet(int initialCapacity) {
10 super(initialCapacity, .75f, true);
11 }
12
13 public LinkedHashSet() {
14 super(16, .75f, true);
15 }
16
17 public LinkedHashSet(Collectionextends E> c) {
18 super(Math.max(2*c.size(), 11), .75f, true);
19 addAll(c);
20 }
21 }

     LinkedHashSet继承自HashSet&＃xff0c;HashSet基于HashMap实现&＃xff0c;看LinkedHashSet类只是定义了四个构造方法&＃xff0c;也没看到和链表相关的内容&＃xff0c;为什么说LinkedHashSet内部使用链表维护元素的插入顺序&＃xff08;插入的顺序&＃xff09;呢&＃xff1f;

    注意这里的构造方法&＃xff0c;都调用了父类HashSet的第五个构造方法&＃xff1a;HashSet(int initialCapacity, float loadFactor, boolean dummy)。如果还记得上面的内容应该明白为什么是基于链表&＃xff0c;下面再给出这个构造方法的内容。

     区别于其他的HashSet的构造方法&＃xff0c;这个方法创建的是一个LinkedHashMap。LinkedHashMap继承自HashMap&＃xff0c;同时自身有一个链表结构用于维护元素顺序&＃xff0c;默认情况使用的是插入元素&＃xff08;见《LinkedHashMap源码分析》&＃xff09;&＃xff0c;所以LinkedHashSet既有HashSet的访问速度&＃xff08;因为访问的时候都是通过HashSet的方法访问的&＃xff09;&＃xff0c;同时可以维护顺序。

    下面是一个HashSet和LinkedHashSet维护元素顺序的例子。

1 Set linkedSet &＃61; new LinkedHashSet();
2 linkedSet.add("First");
3 linkedSet.add("Second");
4 linkedSet.add("Thrid");
5 linkedSet.add("Fourth");
6 System.out.println("LinkedHashSet:"&＃43;linkedSet);
7 Set hashSet &＃61; new HashSet();
8 hashSet.add("First");
9 hashSet.add("Second");
10 hashSet.add("Thrid");
11 hashSet.add("Fourth");
12 System.out.println("HashSet:"&＃43;hashSet);
13 // LinkedHashSet:[First, Second, Thrid, Fourth]
14 // HashSet:[Fourth, Second, Thrid, First]