HashSet源码分析-JDK1.8

浅析JDK1.8 HashSet源码。

写在开篇

HashSet源码比较简单，所以文章就会比较过水。

先简单介绍一下HashSet：

1. 实现了Set接口,不允许元素重复
2. 底层实现是基于HashMap的，它利用HashMap中的key存储数据，使用成员变量PRESENT来填充value
3. 是线程不安全的

类的继承关系

HashSet继承AbstractSet抽象类，实现了Set（规定了Set的操作规范）、Cloneable（可拷贝）、Serializable（可序列化）这几个接口。

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

成员变量

// 使用HashMap来保存HashSet的元素
private transient HashMap<E,Object> map;

   // 由于Set只使用到了HashMap的key，所以此处定义一个静态的常量Object类，来充当HashMap的value
   private static final Object PRESENT = new Object();

构造方法

/**
    * 使用HashMap的默认容量大小16和默认加载因子0.75初始化map，构造HashSet
    */
   public HashSet() {
       map = new HashMap<>();
   }

   /**
    * 以实现了Collection接口的集合类初始化map，来构造HashSet
    */
   public HashSet(Collection<? extends E> c) {
       map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
       addAll(c);
   }

   /**
    * 使用指定的初始容量大小和加载因子初始化map，构造HashSet使用指定的初始容量大小和默认的加载因子0.75初始化map，构造一个HashSet
    */
   public HashSet(int initialCapacity, float loadFactor) {
       map = new HashMap<>(initialCapacity, loadFactor);
   }

   /**使用指定的初始容量大小和默认的加载因子0.75初始化map，构造HashSet
    * 
    */
   public HashSet(int initialCapacity) {
       map = new HashMap<>(initialCapacity);
   }

   /**
    * 不对外公开的一个构造方法（默认default修饰）
    * 底层构造的是LinkedHashMap
    * dummy只是一个标示参数，无具体意义
    */
   HashSet(int initialCapacity, float loadFactor, boolean dummy) {
       map = new LinkedHashMap<>(initialCapacity, loadFactor);
   }

Set接口的实现

add()

HashSet将添加的元素通过map中的key来保存，当有相同的key时，也就是添加了相同的元素，那么map会讲value给覆盖掉，而key还是原来的key。

public boolean add(E e) {
       return map.put(e, PRESENT)==null;
   }

remove()

HashSet通过删除map中key的返回值是否为PRESENT判断set中是否有该值。

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

contains()

直接调用map中containsKey()。

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

isEmpty()

public boolean isEmpty() {
       return map.isEmpty();
   }

size()

public int size() {
       return map.size();
   }

iterator()

// 重点看一下这个迭代器，这个迭代器在HashMap中就已经构建好了。
public Iterator<E> iterator() {
       return map.keySet().iterator();
   }
   
   // 实例化KeySet
   public Set<K> keySet() {
       Set<K> ks = keySet;
       if (ks == null) {
           ks = new KeySet();
           keySet = ks;
       }
       return ks;
   }
   
   // KeySet类是HashMap中的一个内部类
   private final class KeySet extends AbstractSet<K> {
       public Iterator<K> iterator() {
           return newKeyIterator();
       }
       public int size() {
           return size;
       }
       public boolean contains(Object o) {
           return containsKey(o);
       }
       public boolean remove(Object o) {
           return HashMap.this.removeEntryForKey(o) != null;
       }
       public void clear() {
           HashMap.this.clear();
       }
   }
   
   // 实例化KeyIterator
   Iterator<K> newKeyIterator()   {
       return new KeyIterator();
   }
   
   // 对key进行迭代的迭代器（重点）
   // 因为set存放的元素就是存放在HashMap中的key，所以为了能够迭代set，HashMap就实现了这个专门遍历key的迭代器
   private final class KeyIterator extends HashIterator<K> {
       public K next() {
           return nextEntry().getKey();
       }
   }