Java类集框架 —— HashSet、LinkedHashSet源码分析

前言

HashSet实现了Set接口，它的底层是由HashMap来支持的。HashSet的元素实际上是存储在底层HashMap的key上的。由于HashMap的无序不重复特性，HashSet存储的元素也是无序的，并且元素也不能重复，同时也只允许存储一个null元素。

HashSet源码分析

主要属性：

// HashSet底层map
private transient HashMap<E,Object> map;
// 虚拟对象
private static final Object PRESENT = new Object();

HashSet是通过HashMap来保存元素，由于只需要在key中保存，所以采用虚拟对象PRESENT对应map中插入key-value的value值的引用。每次向map中添加元素时，键值对对应的value都是PRESENT。

构造函数：

// 默认无参构造
public HashSet() {
    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) {
    map = new HashMap<>(initialCapacity);
}
// 给定初始容量和加载因子
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
// 这个构造函数外部不能调用，供LinkedHashSet复写
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

构造函数都是初始map，以便加入元素的时候存储。

重要方法：

// 集合大小
public int size() {
    return map.size();
}

// 集合是否为空
public boolean isEmpty() {
    return map.isEmpty();
}

// 添加元素
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();
}

// 集合中是否有元素o
public boolean contains(Object o) {
    return map.containsKey(o);
}

HashSet的增删改查，同时直接操作map来完成的，代码都非常简单。

LinkedHashSet

LinkedHashSet继承自HashSet，它的构造方法：

public LinkedHashSet() {
    super(16, .75f, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

LinkedHashSet构造方法调用了父类HashSet的这个构造方法：

// LinkedHashSet复写，初始化LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

所以，它的底层是一个LinkedHashMap，元素的所有操作都是由LinkedHashMap来维护。LinkedHashSet与HashSet的区别和LinkedHashMap与HashMap的区别一样，LinkedHashMap和LinkedHashSet是有序的，内部由双向链表来记录顺序，而HashMap和HashSet都是无序的。

最后

对于HashSet/LinkedHashSet，只要阅读过HashMap/LinkedHashMap的源码，基本上就能完全了解它的实现原理。HashSet/LinkedHashSet中数据的存入、删除、访问都是都是直接操作内部的HashMap，可以说HashSet/LinkedHashSet是在HashMap/LinkedHashMap的基础上加了一层壳。他们唯一的区别就是HashSet/LinkedHashSet保存的元素时单个的数据或对象，而HashMap/LinkedHashMap保存的元素时键值对。