java集合源码分析（九）：HashSet与TreeSet.md

发表于 | 分类于
字数统计: 864

概述

HashSet 是 Set 接口下一个不允许重复但允许 null、无序并且线程不安全的集合。它基于 HashMap 实现。

从数据结构来说，他与 HashMap 相同，但是由于 HashSet 借助 HashMap 的 key 来存储数据，因而 HashMap 的 value 在 HashSet 中无意义。

HashMap的数据结构

这是关于 java 集合类源码的第九篇文章。往期文章：

  1. java集合源码分析（一）：Collection 与 AbstractCollection
  2. java集合源码分析（二）：List与AbstractList
  3. java集合源码分析（三）：ArrayList
  4. java集合源码分析（四）：LinkedList
  5. java集合源码分析（五）：Map与AbstractMap
  6. java集合源码分析（六）：HashMap
  7. java集合源码分析（七）：LinkedHashMap
  8. java集合源码分析（八）：Set与AbstractSet

一、数据结构

HashSet 基于 HashMap 实现，也就是说，HashSet 用于存储数据的容器实际上就是一个 HashMap 实例。（关于 HashMap 的数据结构，可以参考前文java集合源码分析（六）：HashMap中的第一部分。）

HashSet 使用 HashMap 的 key 作为存储数据的位置，而 value 的位置使用一个默认的全局空对象填充。大部分方法通过直接包装调用 HashMap 的来实现，也就是说，我们可以把 HashSet 看成 HashMap 的一个大号包装器——或者说适配器类。

二、成员变量

由于直接基于 HashMap 实现，因而 HashSet 中只提供两个成员变量，一个 map 用于存放 HashMap 实例，一个 PRESENT 用于作为填充 value 的空对象。

1
2
3
private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

三、构造方法

HashSet 提供了五个构造方法：

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(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

没什么好说的，比较值得注意的是直接传入 Collection 集合的构造方法，这个方法取 HashMap 的默认容量16与传入容量除以默认负载系数的最大值，避免插入过程发生一次额外的扩容。

四、成员方法

Set 接口继承了 Collection 接口，但是 Set 接口并未提供一些新的抽象方法。因而 HashSet 内部的方法基本都重写自 AbstractCollection 抽象类，并且实现都是基于 HashMap 方法的再包装。

也正由于此，HashSet 集合元素允许 null 但是不允许重复，因为 HashMap 的 key 允许有一个 null，并且不允许重复。

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
26
27
28
29
30
31
32
33
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) {
    return map.put(e, PRESENT)==null;
}

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

public void clear() {
    map.clear();
}

public Object clone() {
    try {
        HashSet<E> newSet = (HashSet<E>) super.clone();
        newSet.map = (HashMap<E, Object>) map.clone();
        return newSet;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

五、总结

HashSet 基于 HashMap 实现，并且使用 HashMap 的 key 作为存储容器，将对应的 value 以一个 Object 对象常量进行充填。

HashSet 中的元素无序、不允许重复、允许一个 null 的特性皆来源于 HashMap 的 key 的特性。

实际上，HashSet 中的方法都来自于 Collection 接口，而真正的实现都来自于 HashMap，从这个角度来看，HashSet 其实就是 HashMap 与 Collection 接口之间的一种适配器。

0%