Java-HashSet实现原理

HashSet 实现 Set 接口,由哈希表(实际上是一个 HashMap 实例)支持。它不保证 set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

对于 HashSet 而言,它是基于 HashMap 实现的, HashSet 底层使用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,相关 HashSet 的操作,基本上都是直接调用底层 HashMap 的相关方法来完成, HashSet 的源代码如下:

public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable {

    static final long serialVersionUID = -5024744406713321676L;

    // 底层使用 HashMap 来保存 HashSet 中所有元素。
    private transient HashMap map;

    // 定义一个虚拟的 Object 对象作为 HashMap 的 value,将此对象定义为 static final。
    private static final Object PRESENT = new Object();

    
    public HashSet() {
        map = new HashMap();
    }
    
    
    public HashSet(Collection c) {
        map = new HashMap(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    
    
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap(initialCapacity, loadFactor);
    }
    
    
    public HashSet(int initialCapacity) {
        map = new HashMap(initialCapacity);
    }
    
    
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new linkedHashMap(initialCapacity, loadFactor);
    }
    
    
    public Iterator 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);
    }
    
    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();
    }
    
    
    public Object clone() {

        try {
            HashSet newSet = (HashSet) super.clone();
            newSet.map = (HashMap) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();

        }
    }
}

1. 相关 HashMap 的实现原理,请参考我的总结:HashMap 的实现原理。

2. 对于 HashSet 中保存的对象,请注意正确重写其 equals 和 hashCode 方法,以保证放入的对象的唯一性。