Java集合(五) —— HashSet源码分析

Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析

0.总结（稍微改变一下，先来个总体概括）

1.HashSet内部是使用HashMap来存储数据的，具体来说是使用HashMap中的key存储数据的(这就是HashSet不能存储重复的元素的原因)，而HashMap中所有的值存储的都将是PRESENT对象（PRESENT对象是在类加载时就已经初始化好了，并且不允许改变的）。
2.HashSet对外提供的方法，最终都是通过HashMap操作完成的。
3.HashSet不能保存重复的元素(前面已经说过了)。
4.HashSet不保证插入的顺序（通过hash()函数将对象映射到散列表(实际就是数组)中，所以数据在数组中不是连续存储的）。
5.HashSet的默认容量是16（事实上是HashMap的默认容量），负载因子为0.75，也就是说默认当元素数量达到16*0.75=12之后就会发生扩容。

1.HashSet继承关系图

HashSet.png

2.数据结构

// HashSet使用的是HashMap存储数据，至于HashMap的数据结构，会在HashMap一章中详解
private transient HashMap<E,Object> map;

3.源码分析

3.1成员变量

// HashSet用于保存数据的HashMap
private transient HashMap<E,Object> map;
// PRESENT是map默认存储的value，基本上没什么用，我们应该也不会用到
private static final Object PRESENT = new Object();

3.2构造方法

/**
 * 默认构造方法
 */
public HashSet() {
    // 使用map存储数据
    map = new HashMap<>();
}

/**
 * 使用指定集合构建HashSet
 */
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);
}

3.3常用方法

1.新增元素add

public boolean add(E e) {
    // 实际上调用了map的put()方法保存数据；这里不再展开HashMap的源码
    return map.put(e, PRESENT)==null;
}

图解HashSet(HashMap)存储数据的过程

HashSet_HashMap存储.png

2.删除元素

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

4.Tips

其实HashSet并没有什么好说的，因为处理数据时，其内部基本都是调用HashMap的方法。我们只需要知道HashSet不能保存重复元素，不保证元素顺序等特性就够了（其实这些还是HashMap的特性）。