1. 概述

如果需要自己手动实现一个Set类，我底层可能会选择List类
- 添加元素前，先通过contains() 方法判断是否已经存在重复的元素
HashSet，顾名思义，就是基于哈希表的set类
根据hashCode() 与 equals() 的联系，我们知道：两个对象的hashCode相同，其不一定等价
也就是说，哈希表中同一位置可能存在多个元素：hashCode相同，但不等价
瞬间就想起了HashMap中使用拉链法解决哈希冲突，HashSet也可以使用该方法
HashSet的实现，应该最起码是桶数组 + 链表

1.1 HashSet的特性

Hashset的类注释，提供了以下信息

HashSet基于哈希表实现了Set接口
- 所谓哈希表，就是HashMap实例。也就说，HashSet是基于HashMap实现的
- HashSet中，元素顺序是无序，甚至可能在一段时间内发生变化（rehash导致）
- 允许有且只有一个null值，多个null值与set的定义矛盾
HashSet不是线程安全的，多线程访问，可以使用Collections.synchronizedSet()方法转为线程安全的set类
使用fail-fast迭代器：一旦创建了迭代器，除非使用迭代器的remove方法，其他任何改变HashSet结构的方法都将使得迭代器抛出ConcurrentModificationException异常
关于HashSet的性能：
- 在散列均匀的情况下，add、remove、contains和size操作都是 $O (1)$ 的时间复杂度
- 基于迭代器的遍历，与元素个数、容量（桶数组大小）均有关系，不能将初始化容量设置的过大，或将loadFactor设置的过小

总结：
- 最重要的信息：HashSet基于哈希表实现了Set接口，确切地说，是基于HashMap实现了Set接口
- 其次，就是null值、元素无序、非线程安全、fail-fast迭代器、性能等问题

1.2 类图

HashSet类的声明如下

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

类图如下图所示
- 直观地看，HashSet继承了AbstractSet抽象类，实现了Set、Cloneable和Serializable接口
AbstractSet抽象类：对Set接口的骨架级实现，可以最小化实现Set接口所需的工作量
Set接口：不包含重复元素的集合，所谓重复元素，是指：① 存在元素e1、e2且e1.equals(e2)，② 至多只有一个null值
Cloneable接口：说明HashSet支持clone操作
Serializable接口：说明HashSet支持序列化与反序列化

1.3 数据结构

成员变量如下：
- map：HashMap实例作为哈希表，key对应HashSet中的元素
- PRESENT：key才是HashSet中的元素，value是无意义的，统一指向PRESENT这个类常量
```
private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();
```
从成员变量就可以看出，HashSet是基于HashMap实现的
后续，学习HashSet的关键方法时，我们可以看到HashSet是如何充分利用现有的HashMap类的

1.4 构造方法

构造函数如下：

// 无参构造函数，创建一个空的HashMap，初始化容量和loadFactor都使用默认值
public HashSet() {
    map = new HashMap<>();
}

// 创建包含指定元素的HashSet，HashMap的初始化容量由元素个数决定
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

// 指定HashMap的初始化容量和loadFactor，创建一个空的HashSet
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

// 指定HashMap的初始化容量，创建一个空的HashSet
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

2. 重要方法

2.1 add方法

HashSet的add 方法，实质对应HashMap的put 方法
- 插入时，key为元素e，value固定为PRESENT
- 只要存在重复的key，HashMap的put方法返回的oldValue一定为PRESENT
- 所以，只需要通过判断返回的oldValue是否为null，就可以确定添加操作是否成功
- 返回true，表示元素不重复；否则，元素重复，添加失败
```
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
```

2.2 contains 方法

判断HashSet中是否存在某个元素，就是判断HashMap中是否存在某个对应的key
```
public boolean contains(Object o) {
    return map.containsKey(o);
}
```

2.3 remove 方法

从HashSet中移除一个元素，就是从HashMap中移除对应的entry
- 返回的oldValue为PRESENT，说明存在key为o的entry，即HashSet中存在元素o
```
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}
```

2.4 iterator 方法

获取HashSet中元素的迭代器，实际是获取HashMap中keySet的迭代器

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

3. 总结

3.1 偷懒的HashSet实现

可以说，HashSet的实现十分偷懒
- 巧妙地借助HashMap构建了哈希表，元素对应key，value无意义使用类常量PRESENT
- 几乎所有方法的实现，都是基于HashMap中线程的方法，简直不费吹灰之力

参考文档：

3.2 为何需要同时重写equals和hashCode方法？

equals 方法

Java的超级父类Object中定义了equals 方法具有：自反性、对称性、传递性、一致性、非空性（任何非null对象，x.equals(null)返回false）

Object类中的equals方法实现十分简单：判断两个对象是否相同

public boolean equals(Object obj) {
    return (this == obj);
}

并且建议：重写类的equals方法，通常需要重写hashCode 方法，以维护hashCode 方法相等的对象必须具有相等的hash code的约定

hashCode 方法

三大约定：
- 幂等性：同一个程序中，多次调用对象的hashCode 方法应该返回相等的值
- 两个对象相等，hashCode方法的返回值相等
- hashCode 方法的返回值相等，两个对象不一定相等
Object类中，hashCode 方法返回的是对象的内存地址，以保证不同的对象有不同的hash code
```
public native int hashCode();
```

基于哈希表的类中，为什么同时使用equals 和 hashCode方法？

HashMap中判断key相等的代码如下，二者是同时使用的

if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))

hash code不相等，则两个对象肯定不相等；只有hash code相等了，两个对象才可能相等
hashCode方法的开销更小，可以率先判断两个对象不相等的情况
当hash code相等时，再继续调用equals方法，用于判断两个对象是否真正相等
可以说，hashCode方法保证时效性，equals方法保证可靠性

若只重写equals方法，有什么后果？

Student类，判断两个学生是否为同一个人：
- 是否为同一个对象？
- 不是同一个对象，其关键信息是否相同？
如果我们判断两个学生对象相同，但是其hashCode由于未重写，而返回不同的值
- 不仅违反了相等的对象必须具有相等的hash code的约定
- 在基于哈希表的类中，还会出现严重的bug：
  - 已存入的键值对，get时，由于key的hash code发生变化而发现不存在
  - 已存入的键值对，put时，由于key的hash code发生变化而成功新增，并非更新oldValue；

总结