HashSet--阅读源码从jdk开始

基于HashMap实现

 

HashSet内部实现是基于HashMap的，这是阅读和理解HashSet源码的关键，只要理解了HashMap的实现原理，再来看HashSet的源码就简单了。对于HashMap源码的阅读可以看之前的一篇文章。

 

首先看两个重要的成员变量：

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();//HashMap的value存放的都是这个对象

 

HashSet内部的主要成员变量是一个HashMap，使用这个HashMap的key进行数据存放（利用HashMap的key的不重复，保证HashSet的不可重复），HashMap的value对HashSet没啥意义，所以统一存放的同一个对象PRESENT的引用。

 

构造方法

 

HashSet的构造方法的目的只有一个：实例化自己的HashMap成员变量（实际上就是调用HashMap的各个构造方法进行实例化）。

 

默认构造方法：

public HashSet() {//默认构造方法，实际上调用的HashMap的默认构造方法进行实例化
        map = new HashMap<>();
}

 

 

指定容量的构造方法：

public HashSet(int initialCapacity) {//调用HashMap的指定容量构造方法
        map = new HashMap<>(initialCapacity);
}

 

 

指定容量和增长因子构造方法：

public HashSet(int initialCapacity, float loadFactor) {//调用HashMap的指定容量和增长因子构造方法
        map = new HashMap<>(initialCapacity, loadFactor);
    }

 

 

参数为集合的构造方法

public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));//根据集合的大小，调用HashMap的指定容量和增长因子构造方法
        addAll(c); 实际上循环调用的是HashSet的add方法
    }

 

 

包保护的构造方法

HashSet(int initialCapacity, float loadFactor, boolean dummy) {//该构造方法普通用户无法使用
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

 

这个构造方法只跟HashSet同一个包下的类才可以见，即：java.util包中类才有权使用。目前发现只有在LinkedHashSet的构造方法中调用过该方法，LinkedHashSet是HashSet的子类。

 

其他主要方法：

 

HashSet的逻辑处理方法，都是直接调用HashMap的相关方法进行处理。比如add方法调用的HashMap的put方法，remove方法调用的HashMap的remove 等等：

 

public boolean add(E e) {
    return map.put(e, PRESENT)==null; //hashMap中的每个value都是存放的同一个PRESENT对象的引用
}
 
public boolean remove(Object o) {
        return map.remove(o)==PRESENT; //调用的HashMap的remove方法
    }
 

 

其他方法不再一一列举，都是直接调用HashMap的相对应方法。

 

接下来看看两个特殊的方法。

 

writeObject 和readObject方法

 

HashSet实现了Serializable序列化接口，我们都知道实现了该接口其实就是可序列化的。重写writeObject 和readObject方法可以实现自定义序列化。

    

/**
     * 重写的序列化方法
     * @param s
     * @throws java.io.IOException
     */
    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
        // 调用默认序列化方法
        s.defaultWriteObject();
 
        // 序列化HashMap的容量和增长因子
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());
 
        // 序列化HashMap的大小
        s.writeInt(map.size());
 
        // 序列化HashSet的每一个节点
        for (E e : map.keySet())
            s.writeObject(e);
    }
}
 
/**
     * 重写反序列化方法
     * @param s
     * @throws java.io.IOException
     * @throws ClassNotFoundException
     */
    private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
        // 调用默认的序列化方法
        s.defaultReadObject();
 
        // 反序列化容量
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                    capacity);
        }
 
        // 反序列化增长因子.
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                    loadFactor);
        }
 
        // 反序列化大小.
        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
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
                new LinkedHashMap<E,Object>(capacity, loadFactor) :
                new HashMap<E,Object>(capacity, loadFactor));
 
        // 反序列化每个节点，并放入HashMap
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
            E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
}

 

 

我们再看下HashSet的HashMap成员变量定义：private transient HashMap<E,Object> map; transient修饰是不能被序列化的，这里所谓的不能被序列化 是指不能被默认的序列化方法序列化。但是HashSet采用重写writeObject 和readObject方法，自己对transient成员变量进行序列化和反序列化。

为什么HashSet要自定义序列化规则呢？个人理解：可以从源码上来看，序列化和反序列化里不同的地方，就是HashMap的容量capacity在反序列化时进行了重写计算。由于HashMap的容量是自动增长的，为了避免反序列化后重新生成HashMap空间浪费，需要重新进行容量计算。

 

其实ArrayList、HashMap、HashSet等他们的主要成员变量都是transien修饰的，都重写了writeObject 和readObject方法，重写的方式都类似（重新计算容量）。这些类都有一个共同的特征，就是容量会自动增长。

 

当然这只是表面上的理解，其实默认的序列化会遍历整个对象的拓扑关系，会消耗更多的空间和时间，自己实现的序列化方法则会简单得多。

 

关于java的序列化和反序列化，且听下回分解。