HashSet的实现原理

　　哈希表(实际上是HashMap实例)支持Hashset实现Set接口。它不能保证set的迭代顺序；特别是它不能保证顺序不变。这种元素允许使用null。Hashset中不允许重复元素，因为Hashset是基于Hashmap实现的，Hashset中的元素都存储在Hashmap的key上，而value中的值是统一的private。 static final Object PRESENT = new Object();。Hashset和Hashmap一样，都是存储链表的数组。

　　Hashset中的add方法调用底层Hashmap中的put()方法，如果在Hashmap中调用put，将首先判断key是否存在。如果key存在，则修改value值。如果key不存在，则插入此key-value。在set中，由于value值无用，因此没有修改value值的说法。因此，在hashset中添加元素，首先判断元素（即key）是否存在。如果没有此插入，如果没有插入，则hashset中没有重复值。

　　对于Hashset来说，它是基于Hashmap实现的，Hashset底层使用Hashmap来保存所有元素，更准确地说，Hashset中的元素，只存储在底层Hashmap的key上， 而value则使用staticc Object对象标识final。因此，Hashset的实现相对简单。相关Hashset的操作基本上是通过直接调用底层Hashmap的相关方法来完成的。Hashset的源代码如下：

public class HashSet<E>    extends AbstractSet<E>    implements Set<E>, Cloneable, java.io.Serializable{    static final long serialVersionUID = -5024744406713321676L;    // Hashmap用于保存Hashset中的所有元素。    private transient HashMap<E,Object> map;        // 将虚拟Object对象定义为Hashmap的value，并将其定义为statict final。    private static final Object PRESENT = new Object();    /**     * 默认无参构造器，构造空Hashset。    private static final Object PRESENT = new Object();    /**     * 默认无参构造器，构造空Hashset。     *      * 实际底层将初始化一个空的Hashmap，并使用默认初始容量为16和0.75加载因子。     */    public HashSet() {    map = new HashMap<E,Object>();    }    /**     * 构建包含指定collection元素的新set。     *     * 默认加载因子0.75和实际底层足以包含指定的加载因子     * 在collection中创建HashMap所有元素的初始容量。     * @param c 这个set中的collection将存储元素。     */    public HashSet(Collection<? extends E> c) {    map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));    addAll(c);    }    /**     * 用指定的initialCapacity和loadFactor构建一个空的Hashset。     *     * 实际底层用相应的参数构建一个空的Hashmap。     *     * 实际底层用相应的参数构建一个空的Hashmap。     * @param initialCapacity 初始容量。     * @param loadFactor 加载因子。     */    public HashSet(int initialCapacity, float loadFactor) {    map = new HashMap<E,Object>(initialCapacity, loadFactor);    }    /**     * 用指定的initialCapacity构建一个空的Hashset。     *     * 实际底层以相应的参数和加载因子loadFactor为0.75构建空Hashmap。     *     * 实际底层以相应的参数和加载因子loadFactor为0.75构建空Hashmap。     * @param initialCapacity 初始容量。     */    public HashSet(int initialCapacity) {    map = new HashMap<E,Object>(initialCapacity);    }    /**     * 用指定的initialCapacity和loadFactor构建一个新的空链接哈希集合。     * 这种构造函数是包访问权限，不公开，实际上只是对LinkedHashset的支持。     * 这种构造函数是包访问权限，不公开，实际上只是对LinkedHashset的支持。     *     * 实际底层将以指定的参数构建空LinkedHashMap实例。     * @param initialCapacity 初始容量。     * @param loadFactor 加载因子。     * @param dummy 标记。     */    HashSet(int initialCapacity, float loadFactor, boolean dummy) {    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);    }    /**     * 返回迭代器迭代这个set中的元素。返回元素的顺序不是特定的。返回元素的顺序不是特定的。     *      * 底层实际调用底层Hashmapkeyset返回所有key。     * 可见Hashset中的元素，只存储在底层Hashmap的key上，     * 使用staticcevalue Object对象标识final。     * @return Iterator迭代了set中的元素。     */    public Iterator<E> iterator() {    return map.keySet().iterator();    }    /**     * 返回此set中元素的数量(set的容量)。     *     * 实际调用HashMap的size()方法返回Entry的数量，从而获得Set中元素的数量。     * @return 这个set中元素的数量(set的容量)。     */    public int size() {    return map.size();    }    /**     * 如果set不包含任何元素，则返回true。     *     * 实际调用Hashmap的isempty()在底层判断Hashset是否为空。     * @return 如果set不包含任何元素，则返回true。     */    public boolean isEmpty() {    return map.isEmpty();    }    /**     * 如果set包含指定元素，则返回true。     * 更准确地说，当而且只有这个set包含一种满足感(o==null ? e==null : o.equals(e))     * e元素时，返回true。     *     * 实际调用Hashmap的底层containskey判断是否包含指定key。     * @param o 已测试的元素存在于这个set中。     * @return 如果set包含指定元素，则返回true。     */    public boolean contains(Object o) {    return map.containsKey(o);    }    /**     * 如果set中没有指定元素，则添加指定元素。     * 如果是这样的话，更准确地说 set 不包括满意度(e==null ? e2==null : e.equals(e2))     * 元素e2，向此set 添加指定元素e。     * 如果这个set已经包含了这个元素，则应该调用不更改set并返回false。     *     * 底层实际上把这个元素作为key放入Hashmap。     * 由于Hashmap的put()方法加入key-value对时，当新加入Hashmap的entrykey时     * 与集合中原Entry的key相同（hashCode()返回值相等，通过equals比较返回true)，     * 新添加的Entryvalue将覆盖原Entryvalue，但key不会有任何变化，     * 因此，如果将现有元素添加到Hashset中，新添加的集合元素将不会被放入Hashmap中，     * 原始元素不会有任何变化，这满足了Set中元素不重复的特点。     * @param e 在这个set中添加元素。     * @param e 在这个set中添加元素。     * @return 如果set没有包含指定元素，则返回true。     */    public boolean add(E e) {    return map.put(e, PRESENT)==null;    }    /**     * 若指定元素存在于此set中，则将其移除。     * 更准确地说，如果这个set包含满足感(o==null ? e==null : o.equals(e))的元素e，     * 将其移除。如果set已经包含了这个元素，则返回true     * (或者:如果set因调用而发生变化，则返回true)。(一旦调用返回，此set将不再包含该元素)。     *     * 底层实际调用Hashmapremove方法删除指定Entry。     * @param o 如果存在于此set中，则需要删除其对象。     * @return 如果set包含指定元素，则返回true。     */    public boolean remove(Object o) {    return map.remove(o)==PRESENT;    }    /**     * 从此，所有元素都被移除到set中。这个调用返回后，set将为空。     *     * 实际调用Hashmap的clear方法，底层清空Entry中的所有元素。     */    public void clear() {    map.clear();    }    /**     * 回到这个Hashset实例的浅表副本：没有复制这些元素本身。     *     * 实际调用Hashmap的clone()方法，在底层获取Hashmap的浅表副本，并将其设置为Hashset。     */    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();        }    }}

三、相关说明:

对于保存在Hashset中的对象，请注意正确重写其equals和hashcode方法，以确保放置对象的唯一性。