源码分析之HashSet

概念

HashSetJava Collections FrameworkSet接口的一种实现了。HashSet底层是基于HashMap来实现的,之前已经分析过HashMap的源码,这时候再来看HashSet的源码相对来说是很轻松的。

类结构

HashSet继承AbstractSet类,实现了Set接口。由于HashSet是用HashMap实现的,所以HashMap在数据存储上也是无序的。

类成员

PRESENT

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

HashMap是键值对K-V模型的,HashSet则是普通的集合类型。这里的PRESENT就是用来填充HashMap中的value的。

构造函数

HashSet提供了4种构造函数。

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
// 默认无参构造函数
public HashSet() {
map = new HashMap<>();
}
// 以现有集合构造
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
// 带参构造 initialCapacity: 初始大小 loadFactor:加载因子
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
// 带参构造 initialCapacity: 初始大小
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
// 仅用来构造LinkedHashSet使用
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

add 方法

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

add方法很简单,直接调用HashMapput方法实现。value则是用PRESENT进行填充。

remove 方法

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

remove方法也是同样,调用HashMapremove方法。

HashSet大多数的方法都是通过HashMap的方法来实现的。

hashCode方法 & equals方法

如果我们在使用HashSet来存储自定义的对象时候,要记得重写hashCode方法和equals方法。这里将通过一个示例来说明重写的必要性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Test {
String a;
public Test(String a) {
this.a = a;
}
public static void main(String[] args) {
Set set = new HashSet();
Test o1 = new Test("abc");
Test o2 = new Test("abc");
set.add(o1);
set.add(o2);
System.out.println(o1.equals(o2));
System.out.println(set.size());
}

上面程序输出应该是:

1
2
false
2

默认equals方法是通过比较引用是否来判断2个对象是否一致的。o1o2显然是2个对象,他们是不相等的,他们各自的hashcode显然是不同的,所以HashSet会把他们当做2个不同对象来处理。

我们想要a相同的对象都是同一个对象的话,使用默认的equalshashcode方法显然无法满足我们要求的,这时候就需要重写equalshashcode方法。

1
2
3
4
5
6
7
8
9
10
11
12
@Override
public int hashCode() {
return 123 * 31 + a.hashCode();
}
@Override
public boolean equals(Object o) {
Test test = (Test) o;
return test.a.equals(this.a);
}

这里再运行main的结果就是:

1
2
true
1

总结

HashSet存储元素,是将元素作为HashMapkey进行操作,所以不保证元素顺序。HashSet不会有重复数据,重复数据都被覆盖。