康夺的个人博客

半日闲来半日谈

0%

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

发表于 分类于 阅读次数： Valine：

​ 关于集合，实则是分为两大类的：List 和 Set ，Map 只是另类的集合，并不是 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 来实现。是偷懒了，但是很巧妙。

总结