AnthonyZero's Bolg

Java学习系列：HashSet实现原理

发表于 | 分类于

HashSet概述

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

成员变量

// 序列化ID
static final long serialVersionUID = -5024744406713321676L;

// 底层使用HashMap来保存HashSet的元素
private transient HashMap<E,Object> map;

// 没有实际意义 由于Set只使用到了HashMap的key，所以此处定义一个静态的常量Object类，来充当HashMap的value 
private static final Object PRESENT = new Object();

构造函数

// 默认无参构造
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);
}

上面便是HashSet的构造器，非常简单，由于底层是使用了HashMap的数据结构，所以它的构造器就是初始化HashMap的代码，只有最后一个构造方法有些区别，这里构造的是LinkedHashMap，该方法不对外公开，实际上是提供给LinkedHashSet使用的，而第三个参数dummy是无意义的，只是为了区分其他构造方法。

增加元素

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

添加一个元素，如果Map中存在，返回false，否则返回true

为什么使用一个静态的常量Object类来充当HashMap的value: 既然这里map的value是没有意义的，为什么不直接使用null值来充当value呢？从根源上避免NullPointerException的出现(new Object()是占用堆内存的,一个空的Object对象占用8byte，而null值我们知道，是不会在堆空间分配内存的)

删除元素

public boolean remove(Object o) {
      //直接调用map的方法
    return map.remove(o)==PRESENT;
}

其他方法

//迭代器
public Iterator<E> iterator() {
    // 因为不需要value，所以只是调用了keySet的iterator
    return map.keySet().iterator();
}

 //容量
public int size() {
    return map.size();
}

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

 //是否包含一个元素
public boolean contains(Object o) {
    return map.containsKey(o);
}

底层实现都是在调用HashMap的方法

总结

HashSet实现了Set接口，内部是通过HashMap实现的，这决定了它有如下特点：

  1. 没有重复元素,不保证元素的顺序，而且HashSet允许使用 null 元素，HashSet是非同步的。
  2. 可以高效的添加、删除元素、判断元素是否存在，效率都为O(1)。