HashSet源码解析（基于JDK1.8）

目录

一、概述

二、PRESENT 值 

三、构造方法

四、把HashSet写入流中（也就是序列化）

五、从流中读取数据，组装HashSet（反序列化）

六、其他简单方法

---

一、概述

HashSet是一个无序并且不重复的集合，它是基于HashMap来实现的，UML图如下：



1）集合分成了两类，一类是继承了Collection接口的，一类是继承了Map接口的。

2）实现了Serializable接口，表明它支持序列化。 
3）实现了Cloneable接口，表明它支持克隆，可以调用超类的clone（）方法进行浅拷贝。 
4）实现了Set接口。
5）继承了AbstractSet抽象类，和ArrayList和LinkedList一样，在他们的抽象父类中，都提供了equals（）方法和hashCode（）方法。它们自身并不实现这两个方法，只要元素的个数和集合中元素相同，即使他们是AbstractSet不同的子类，他们equals（）相互比较的后的结果仍然是true。

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection<?> c = (Collection<?>) o;
        //必须保证元素的个数相等。
        if (c.size() != size())
            return false;
        try {
        //调用了AbstractCollection的方法。
            return containsAll(c);
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }


    public boolean containsAll(Collection<?> c) {
    //只需要逐个判断集合是否包含其中的元素。
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }

二、PRESENT 值 

HashSet内部通过使用HashMap的键来存储集合中的元素，而且内部的HashMap的所有值都是null，因为在为HashSet添加元素的时候，内部HashMap的值都是PRESENT。

    //序列化ID
    static final long serialVersionUID = -5024744406713321676L;
    //底层使用了HashMap存储数据。
    private transient HashMap<E,Object> map;
    //用来填充底层数据结构HashMap中的value，因为HashSet只用key存储数据。
    private static final Object PRESENT = new Object();

三、构造方法

//其实只是实例化了HashMap
    public HashSet() {
        map = new HashMap<>();
    }

//还是关于
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    //调用的AbstractCollection中的方法。然后调用HashSet的add（）方法把集合中的
    //所有元素添加到了集合中。（因为）
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }
    //底层并不支持直接在AbstractCollection类中调用add（）方法，而是调用add（）方法
    //的自身实现。
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }


    //初始化HashSet仍然是关于HashMap的知识。
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

   //初始化HashSet仍然是关于HashMap的知识。
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

   //这次初始化底层使用了LinkedHashMap实现。
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

四、把HashSet写入流中（也就是序列化）

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out HashMap capacity and load factor
        //把HashMap的容量写入流中。
        s.writeInt(map.capacity());
        //把HashMap的装载因子写入流中。
        s.writeFloat(map.loadFactor());
        //把HashMap中键值对的个数写入流中。
        s.writeInt(map.size());

        // 按正确的顺序把集合中的所有元素写入流中。
        for (E e : map.keySet())
            s.writeObject(e);
    }

五、从流中读取数据，组装HashSet（反序列化）

// 序列化读取，将容量，加载因子，长度一次读出
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read capacity and verify non-negative.
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }

        // Read load factor and verify positive and non NaN.
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }

        // Read size and verify non-negative.
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }

        // Set the capacity according to the size and load factor ensuring that
        // the HashMap is at least 25% full but clamping to maximum capacity.
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);
        // 创建HashMap
        // Create backing HashMap
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // Read in all elements in the proper order.
        // 按写入流中的顺序再把元素依次读取出来放到map中。
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }

六、其他简单方法

    /**
     * 通过keySet方法取得所有的key(set集合)，接着调用iterator方法
     */
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    /**
     * 获取map的长度，也就是HashSet的长度
     */
    public int size() {
        return map.size();
    }

    /**
     * 判断是否为空
     */
    public boolean isEmpty() {
        return map.isEmpty();
    }

    /**
     * 判断HashSet中某个元素是否存在
     * 存在返回true
     */
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    /**
     * 添加元素，调用map的put方法
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    /**
     * 移除元素，调用map的remove方法
     */
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

    /**
     * 清空集合，调用map的clear方法
     */
    public void clear() {
        map.clear();
    }

    /**
     * 浅克隆，实际并没有复制元素本身，调用map的克隆方法
     */
    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();
        }
    }