HashSet源码分析

yPhantom 2019年10月17日 40次浏览

推荐先看HashMap源码分析

HashSet一般使用在要求元素不能重复或者要达到去重效果的场景。这个类的源码总的来说比较简单,因为其实际是通过一个HashMap来存放数据,实现元素不重复的效果的。

类图

image.png

MapCollection两个类是Java集合框架的两大类型,存放一个元素以及存放键值对。

源码分析

public class HashSet<E>  extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable
{
    // 用来存放元素的 HashMap
    private transient HashMap<E,Object> map;

    // 因为 HashMap 是存放键值对的,而 HashSet 只会存放其中的key,即当做 HashMap 的key,
    // 而value 就是这个 Object 对象了,HashMap 中所有元素的 value 都是它
    private static final Object PRESENT = new Object();

    // 无参构造,创建 HashMap 对象,初始大小为 16
    public HashSet() {
        map = new HashMap<>();
    }

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    // 根据初始大小和加载因子创建 HashSet
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    // 根据初始大小创建 HashSet
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    // 迭代器
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
........................
}

因为HashSet内部使用HashMap实现的,而HashMap是存放键值对的,那么HashSet里面的value是什么呢?

HashSet所有的值都是作为key存储在map中,它们共用一个value,就是一个static final Object PRESENT对象。

add方法

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

HashMap的put的时候,如果已经存在结点,会将map中对应的key替换为新value之后,返回旧value。

保证元素不重复

HashMap利用hashcode计算出来的key保证了HashSet不会重复

小结

  1. HashSet 底层是使用 HashMap 来保存元素的

  2. 它不保证集合中存放元素的顺序,即是无序的,且这种顺序可能会随着时间的推移还会改变

  3. 允许 null 值,且只有一个

  4. HashSet 不是线程安全的,底层的 HashMap 不是线程安全的,它自然就不是啦,可以使用 Collections.synchronizedSet(new HashSet()) 来创建线程安全的 HashSet

  5. 集合中的元素不会重复

参考资料

掘金