Java集合分析之Set-以HashSet为例

​ 关于集合,实则是分为两大类的:ListSetMap 只是另类的集合,并不是 Collection 类的一个子类。List 不去重,Map 是键值对,而 Set 则是去重的无序列表。Set 的各个实现类基本都是借助 Map 来实现的,基本原理都一样,这里以 HashSet 为例,其它的实现类可以举一反三。

注:本文基于jdk_1.8.0_162

HashSet

内部结构

总览

HashSet 的实现依赖于 HashMap ,以其 Key 来存储数据,并以一个固定值在 Value 位置占位,用来实现其去重及无序特性。

主要成员

​ 主要成员如下:

1
2
3
4
5
6
7
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
//存放元素的hashmap
private transient HashMap<E,Object> map;
//用来占位的值
private static final Object PRESENT = new Object();
}

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//默认构造器
public HashSet() {
map = new HashMap<>();
}

//集合当参数的构造器
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}

//带有容量及负载因子的构造器
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}

//带有初始容量的构造器
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}

​ 是不是很惊喜,HashSet 竟然这么偷懒,直接使用了 HashMap 来存储元素。

重点方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int size() {
return map.size();
}

public boolean isEmpty() {
return map.isEmpty();
}

public boolean contains(Object o) {
return map.containsKey(o);
}

public boolean add(E e) {
//看这里,用已经初始化的一个Object来占位
return map.put(e, PRESENT)==null;
}

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

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

​ 看,没错了,就是这么简单,初始化了 HashMap 之后,主要的方法实现全靠 HashMap 来实现。是偷懒了,但是很巧妙。

总结