JDK1.8源码-08-java.util.HashSet

在JDK1.8中，HashMap是用 数组+链表+红黑树构成，相对于早期版本的JDK HashMap实现，新增了红黑树作为底层的数据结构，在数据量较大且哈希碰撞较多的时候，能够极大的增加检索的效率。

了解了HashMap的具体实现后，再来了解HashMap作为底层数据结构的HashSet。

(如果不了解 HashMap 的实现原理，建议先看看 HashMap，不然直接看 HashSet 是很难看懂的）

1. 定义

HashSet是一个由HashMap实现的集合。元素无序且不能重复

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

和前面介绍的大多数集合一样，HashSet 也实现了 Cloneable 接口和 Serializable 接口，分别用来支持克隆以及支持序列化。还实现了 Set 接口，该接口定义了 Set 集合类型的一套规范。

2. 字段属性

   // HashSet集合中的内容是通过 HashMap 数据结构来存储的
private transient HashMap<E,Object> map;

   // Dummy value to associate with an Object in the backing Map
// 向Hashset添加数据的时候，数据在上面的map结构是作为key存在的，
// 而value统一都是PRESENT
   private static final Object PRESENT = new Object();

• 第一个定义一个 HashMap，作为实现 HashSet 的数据结构；
• 第二个定义的PRESENT对象，因为前面讲过的HashMap 是作为键值对key-value进行存储的，而HashSet不是键值对，那么选择HashMap作为实现，其原理就是存储在HashSet中的数据作为Map的key,而Map的value同一为PRESENT（下面介绍具体实现时会了解）。

3. 构造函数

1. 无参构造

public HashSet() {
    map = new HashMap<>();
}

直接new一个HashMap 的对象出来，采用无参的HashMap 构造函数，具有默认初始容量（16）和加在因子（0.75）。

2. 指定初始容量

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * the specified initial capacity and default load factor (0.75).
 *
 * @param      initialCapacity   the initial capacity of the hash table
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero
 */
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

3. 指定初始容量和加载因子

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * the specified initial capacity and the specified load factor.
 *
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

4. 构造包含指定集合中的元素

    /**
     * Constructs a new set containing the elements in the specified
     * collection.  The <tt>HashMap</tt> is created with default load factor
     * (0.75) and an initial capacity sufficient to contain the elements in
     * the specified collection.
     *
     * @param c the collection whose elements are to be placed into this set
     * @throws NullPointerException if the specified collection is null
     */

// 容量的大小是（c.size()/0.75 +1） 和 默认初始容量16的最大值
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

集合容量很好理解，这里再次介绍一下什么是加载因子。

• 在HashMap中，能够存储元素的数量是：总的容量*加载因子
• 新增一个元素的时候，如果HashMap集合中的元素大于前面计算公式的结果了，那么就必须进行扩容的操作，从时间和和空间考虑，加载因子一般都默认选0.75.

4. 添加元素

//   HashSet 的 add(E e) 方法
// 会将e作为key, PRESENT作为value值插入到map集合中
// 如果e不存在,则插入成功并且返回true,如果存在，则返回false  
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

通过map.put()方法来添加元素，在上一篇已经介绍过此方法。

• 该方法如果新插入的key不存在,则返回null,

• 如果新插入的key存在，则返回key对应的value值（注意新插入的value会覆盖原来的value值）

也就是说HashSet 的 add(E e) 方法，会将e作为key, PRESENT作为value值插入到map集合中，如果e不存在,则插入成功并且返回true,如果存在，则返回false

5. 删除元素

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

调用HashMap 的remove(Object o)方法，该方法会首先查找map集合中是否存在o，如果存在则删除，并返回该值，如果不存在则返回null。

也就是说HashSet的remove(Object o)方法，删除成功返回true,删除的元素不存在会返回false。

6. 查找元素

public boolean contains(Object o) {
    return map.containsKey(o);
}

调用HashMap的containsKey(Object o)方法，找到了返回true,找不到返回false。

7. 遍历元素

public static void main(String[] args) {
    HashSet<Integer> set = new HashSet<>();

    set.add(1);
    set.add(2);

    // 增强for循环
    for (Integer i : set) {
        System.out.println(i);
    }


    // 普通for循环
    Iterator<Integer> iterator = set.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());
    }
}

HashSet底层源码不多，只有短短354行，最重要的还是HashSet的底层数据结构HashMap的实现。

打赏