HashSet 是 Set 接口的典型实现，由哈希表（实际上是一个HashMap 实例）支持，大多数时候使用 Set 集合时都使用这个实现类。HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取和查找性能。
【1】HashSet基础概念
HashSet 具有以下特点：
不能保证元素的排列顺序
HashSet 不是线程安全的
集合元素可以是 null
当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后通过 hashCode 值计算得到hash值决定该对象在 HashSet 中的存储位置。
HashSet 集合判断两个元素相等的标准：两个对象通过 hashCode() 方法比较相等，并且两个对象的 equals() 方法返回值也相等。
HashSet类继承图
HashSet方法概览
hashCode()与equals()的相关规定
如果两个对象相等，则hashcode一定也是相同的。
两个对象相等，对两个对象分别调用equals方法都返回true。
即使两个对象有相同的hashcode值，它们也不一定是相等的。
因此，equals 方法被覆盖过，则 hashCode 方法也必须被覆盖。hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指 向相同的数据）。
对象的相等与指向他们的引用相等，两者有什么不同？
对象的相等 比的是内存中存放的内容是否相等而 引用相等 比较的是他们指向的 内存地址是否相等。
【2】HashSet的实现
对于HashSet 而言，它是基于HashMap 实现的，HashSet 底层使用HashMap 来保存所有元素，因此HashSet 的实现比较简单，相关HashSet 的操作，基本上都是直接调用底层HashMap 的相关方法来完成。
① 核心属性和构造方法
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，将此对象定义为static final。 private static final Object PRESENT = new Object(); /* 默认的无参构造器，构造一个空的HashSet。 实际底层会初始化一个空的HashMap，并使用默认初始容量为16 和加载因子0.75。 */ public HashSet() { map = new HashMap<>(); } /* 构造一个包含指定collection 中的元素的新set。 实际底层使用默认的加载因子0.75 和足以包含指定 collection 中所有元素的初始容量来创建一个HashMap。 @param c 其中的元素将存放在此set 中的collection。 */ public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } /* 以指定的initialCapacity 和loadFactor 构造一个空的HashSet。 实际底层以相应的参数构造一个空的HashMap。 */ public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } /* 以指定的initialCapacity 构造一个空的HashSet。 实际底层以相应的参数及加载因子loadFactor 为0.75 构造一个空的HashMap。 */ public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } /* 以指定的initialCapacity 和loadFactor 构造一个新的空链接哈希集合。 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet 的支持。 实际底层会以指定的参数构造一个空LinkedHashMap 实例来实现。 */ HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } /* 返回对此set 中元素进行迭代的迭代器。返回元素的顺序并不是特定的。 底层实际调用底层HashMap 的keySet 来返回所有的key。 可见HashSet 中的元素，只是存放在了底层HashMap 的key 上， value 使用一个static final 的Object 对象标识。 @return 对此set 中元素进行迭代的Iterator */ public Iterator<E> iterator() { return map.keySet().iterator(); } /* 返回此set 中的元素的数量（set 的容量）。 底层实际调用HashMap 的size()方法返回Entry 的数量，就得到该Set 中元素的个数。 */ public int size() { return map.size(); } /* 如果此set 不包含任何元素，则返回true。 底层实际调用HashMap 的isEmpty()判断该HashSet 是否为空。 */ public boolean isEmpty() { return map.isEmpty(); } /* 如果此set 包含指定元素，则返回true。 更确切地讲，当且仅当此set 包含一个满足(o==null ? e==null : o.equals(e))的 e 元素时，返回true。 底层实际调用HashMap 的containsKey 判断是否包含指定key。 */ public boolean contains(Object o) { return map.containsKey(o); }
② 添加和移除方法
底层实际将将该元素作为key 放入HashMap。由于HashMap 的put()方法添加key-value 对时，当新放入HashMap 的Entry 中key与集合中原有Entry 的key 相同（hashCode()返回值相等，通过equals 比较也返回true）则新添加的Entry 的value 会将覆盖原来Entry 的value，但key 不会有任何改变。
因此如果向HashSet 中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap 中，原来的元素也不会有任何改变，这也就满足了Set 中元素不重复的特性。
// 如果e的hash结果相等或者equals方法相等，表示已经存在 public boolean add(E e) { return map.put(e, PRESENT)==null; } //底层实际调用HashMap 的remove 方法删除指定Entry 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 中。
@SuppressWarnings("unchecked") 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(e); } }
④ 序列化和反序列化
两个概念
序列化：将数据结构或对象转换成二进制字节流的过程
反序列化：将在序列化过程中所生成的二进制字节流的过程转换成数据结构或者对象的过程
这里使用了ObjectOutputStream 来实现 序列化，
首先是map.capacity，
然后是map.loadFactor，
接着是map.size,
最后是set中的每个元素(map.keySet)
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out HashMap capacity and load factor s.writeInt(map.capacity()); s.writeFloat(map.loadFactor()); // Write out size s.writeInt(map.size()); // Write out all elements in the proper order. for (E e : map.keySet()) s.writeObject(e); }
反序列化
反序列化的本质就是从ObjectInputStream 读取数据。
- 读取capacity
- 读取loadFactor
- 读取size
- 计算capacity
- 实例化map
- 读取每一个key并放入map
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read capacity and verify non-negative. int capacity = s.readInt(); if (capacity < 0) { throw new InvalidObjectException("Illegal capacity: " + capacity); } // Read load factor and verify positive and non NaN. float loadFactor = s.readFloat(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) { throw new InvalidObjectException("Illegal load factor: " + loadFactor); } // Read size and verify non-negative. 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); // Create backing HashMap map = (((HashSet<?>)this) instanceof LinkedHashSet ? new LinkedHashMap<E,Object>(capacity, loadFactor) : new HashMap<E,Object>(capacity, loadFactor)); // Read in all elements in the proper order. for (int i=0; i<size; i++) { @SuppressWarnings("unchecked") E e = (E) s.readObject(); map.put(e, PRESENT); } }
对于HashSet 中保存的对象，请注意正确重写其equals 和hashCode 方法，以保证放入的对象的唯一性。
