我是风筝，公众号「古时的风筝」，一个兼具深度与广度的程序员鼓励师，一个本打算写诗却写起了代码的田园码农！
文章会收录在 JavaNewBee 中，更有 Java 后端知识图谱，从小白到大牛要走的路都在里面。
之前的7000 字说清楚 HashMap已经详细介绍了 HashMap 的原理和实现，本次再来说说他的同胞兄弟 HashSet，这两兄弟经常被拿出来一起说，面试的时候，也经常是两者结合着考察。难道它们两个的实现方式很类似吗，不然为什么总是放在一起比较。
实际上并不是因为它俩相似，从根本上来说，它俩本来就是同一个东西。再说的清楚明白一点， HashSet 就是个套了壳儿的 HashMap。所谓君子善假于物，HashSet 就假了 HashMap。既然你 HashMap 都摆在那儿了，那我 HashSet 何必重复造轮子，借你一样，何不美哉！
HashSet 是什么
下面是
HashSet
的继承关系图，还是老样子，我们看一个数据结构的时候先看它的继承关系图。与
HashSet
并列的还有
TreeSet
，另外
HashSet
还有个子类型
LinkedHashSet
，这个我们后面再说。
套壳 HashMap
为啥这么说呢，在我第一次看
HashSet
源码的时候，已经准备好了笔记本，拿好了圆珠笔，准备好好探究一下
HashSet
的神奇所在。可当我按着
Ctrl
+鼠标左键进入源码的构造函数的时候，我以为我走错了地方，这构造函数有点简单，甚至还有点神奇。new 了一个
HashMap
并且赋给了 map 属性。
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
再三确认没看错的情况下，我明白了，
HashSet
就是在
HashMap
的基础上套了个壳儿，我们用的是个
HashSet
，实际上它的内部存储逻辑都是
HashMap
的那套逻辑。
除了上面的那个无参类型的构造方法，还有其他的有参构造方法，一看便知，其实就是
HashMap
包装了一层而已。
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
用法
HashSet
应该算是众多数据结构中最简单的一个了，满打满算也就那么几个方法。
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
很简单对不对，就这么几个方法，而且你看每个方法其实都是对应的操作 map，也就是内部的
HashMap
，也就是说只要你懂了
HashMap
自然也就懂了
HashSet
。
保证不重复
Set
接口要求不能有重复项，只要继承了
Set
就要遵守这个规定。我们大多数情况下使用
HashSet
也是因为它有去重的功能。
那它是如何办到的呢，这就要从它的
add
方法说起了。
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashSet
的
add
方法其实就是调用了
HashMap
put
方法，但是我们都知道
put
进去的是一个键值对，但是
HashSet
存的不是键值对啊，是一个泛型啊，那它是怎么办到的呢？
它把你要存的值当做
HashMap
的 key，而 value 值是一个
final
Object
对象，只起一个占位作用。而
HashMap
本身就不允许重复键，正好被
HashSet
拿来即用。
如何保证不重复呢
HashMap
中不允许存在相同的 key 的，那怎么保证 key 的唯一性呢，判断的代码如下。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
首先通过 hash 算法算出的值必须相等，算出的结果是 int，所以可以用 == 符号判断。只是这个条件可不行，要知道哈希碰撞是什么意思，有可能两个不一样的 key 最后产生的 hash 值是相同的。
并且待插入的 key == 当前索引已存在的 key，或者 待插入的 key.equals(当前索引已存在的key)，注意
==
和 equals 是或的关系。== 符号意味着这是同一个对象， equals 用来确定两个对象内容相同。
如果 key 是基本数据类型，比如 int，那相同的值肯定是相等的，并且产生的 hashCode 也是一致的。
String
类型算是最常用的 key 类型了，我们都知道相同的字符串产生的 hashCode 也是一样的，并且字符串可以用 equals 判断相等。
但是如果用引用类型当做 key 呢，比如我定义了一个
MoonKey
作为 key 值类型
public class MoonKey {
private String keyTile;
public String getKeyTile() {
return keyTile;
}
public void setKeyTile(String keyTile) {
this.keyTile = keyTile;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MoonKey moonKey = (MoonKey) o;
return Objects.equals(keyTile, moonKey.keyTile);
}
}
然后用下面的代码进行两次添加，你说 size 的长度是 1 还是 2 呢？
Map<MoonKey, String> m = new HashMap<>();
MoonKey moonKey = new MoonKey();
moonKey.setKeyTile("1");
MoonKey moonKey1 = new MoonKey();
moonKey1.setKeyTile("1");
m.put(moonKey, "1");
m.put(moonKey1, "2");
System.out.println(hash(moonKey));
System.out.println(hash(moonKey1));
System.out.println(m.size());
答案是 2 ，为什么呢，因为
MoonKey
没有重写
hashCode
方法，导致 moonkey 和 moonKey1 的 hash 值不可能一样，当不重写
hashCode
方法时，默认继承自
Object
的 hashCode 方法，而每个
Object
对象的 hash 值都是独一无二的。
划重点，正确的做法应该是加上
hashCode
的重写。
@Override
public int hashCode() {
return Objects.hash(keyTile);
}
这也是为什么要求重写
equals
方法的同时，也必须重写
hashCode
方法的原因之一。 如果两个对象通过调用equals方法是相等的，那么这两个对象调用hashCode方法必须返回相同的整数。有了这个基础才能保证
HashMap
或者
HashSet
的 key 唯一。
非线程安全
由于
HashMap
不是线程安全的，自然，
HashSet
也不是线程安全啦。在多线程、高并发环境中慎用，如果要用的话怎么办呢，不像
HashMap
那样有多线程版本的
ConcurrentHashMap
，不存在 ``ConcurrentHashSet`这种数据结构，如果想用的话要用下面这种方式。
Set<String> set = Collections.synchronizedSet(new HashSet<String>());
或者使用
ConcurrentHashMap.KeySetView
也可以，但是，这其实就不是
HashSet
了，而是
ConcurrentHashMap
的一个实现了
Set
接口的静态内部类，多线程情况下使用起来完全没问题。
ConcurrentHashMap.KeySetView<String,Boolean> keySetView = ConcurrentHashMap.newKeySet();
keySetView.add("a");
keySetView.add("b");
keySetView.add("c");
keySetView.add("a");
keySetView.forEach(System.out::println);
LinkedHashSet
如果说
HashSet
是套壳儿
HashMap
，那么
LinkedHashSet
就是套壳儿
LinkedHashMap
。对比
HashSet
，它的一个特点就是保证数据有序，插入的时候什么顺序，遍历的时候就是什么顺序。
看一下它其中的无参构造函数。
public LinkedHashSet() {
super(16, .75f, true);
}
LinkedHashSet
继承自
HashSet
，所以
super(16, .75f, true);
是调用了
HashSet
三个参数的构造函数。
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
这次不是
new HashMap
了，而是 new 了一个
LinkedHashMap
，这就是它能保证有序性的关键。
LinkedHashMap
用双向链表的方式在
HashMap
的基础上额外保存了键值对的插入顺序。
HashMap
中定义了下面这三个方法，这三个方法是在插入和删除键值对的时候调用的方法，用来维护双向链表，在
LinkedHashMap
中有具体的实现。
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
LinkedHashMap
可以保证键值对顺序，所以，用来实现简单的 LRU 缓存。
所以，如果你有场景既要保证元素无重复，又要保证元素有序，可以使用
LinkedHashSet
最后
其实你掌握了
HashMap
就掌握了
HashSet
，它没有什么新东西，就是巧妙的利用了
HashMap
而已，新不新不要紧，好用才是最重要的。
壮士且慢，先给点个赞吧，总是被白嫖，身体吃不消！
我是风筝，公众号「古时的风筝」。一个兼具深度与广度的程序员鼓励师，一个本打算写诗却写起了代码的田园码农！你可选择现在就关注我，或者看看历史文章再关注也不迟。
人生没有回头路，珍惜当下。