前两天复习数据结构，刚看完散列这一章，于是就想研究一下HashSet和HashMap的源码是怎么实现的。但是大概看了下HashMap，底层貌似用到了红黑树的数据结构，而HashSet比较简单，是基于HashMap实现的，所以这篇文章主要还是分析HashSet。
先来看看他的属性和方法：
image
是不是特别少？事实上除了底下的几个实现的接口以及注释，核心的代码实现可能一共也就几十行。
再来看看他实现的接口和继承的父类：
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
HashSet的核心功能都由Set接口和AbstractSet给定义好了。
属性
我们先来看下HashSet的属性：
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
第一个是序列化ID，第二个就是用来存储元素的一个HashMap。由于使用HashMap的时候只用到了Key，因此定义了一个PRESENT常量来当Value。
构造方法
HashSet一共有五个构造方法，都非常简单。
- 无参构造
public HashSet() {
map = new HashMap<>();
}
直接创建一个空的集合
- 通过其他容器进行构造
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
只要实现了Collection接口的容器，都可以直接构造成集合的形式，这就包括了List一类。
注意看在构造HashMap的时候，传了一个整数值(Math.max((int) (c.size()/.75f) + 1, 16))进去，这个整数值实际上就是确定集合的初始容量。c.size表示容器大小，“.75f”表示平衡因子为0.75（不知道平衡因子的可以到网上再复习一下散列），c.size()/0.75就是一个散列（这里就是这个map）的理想存储大小。如果散列的理想存储大小不足16，那在初始化的时候就为map分16个单位的存储空间，即该集合初始容量为16。
- 通过传入平衡因子和初始容量进行构造
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
这个很明显，基本和上面的概念类似。
4.只传入初始容量进行构造
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
- 采用另外一种map进行构造
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
这个基本不怎么使用
成员函数
跟集合相关操作的核心操作实际上只有8个，我看了下，这8个函数加一起的代码量可能都不超过三十行，举个例子：
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
这是蕴含判断操作和添加操作，实际上所有的操作都交由其成员变量map完成了，所以很简单，我就不一一介绍了，我想介绍的是为什么通过这几行简单的代码就能完全实现集合的特性呢？
事实上我们知道离散数学中定义的集合有三个特性：
- 确定性。给定任意一个元素，可以知道该元素是否存在于这个集合中。
- 互异性。集合中的任意元素都是唯一的，不存在两个相同的元素。
- 无序性。集合中的元素是没有顺序的。
无序性就不说了，因为在HashSet中根本就没有提供任何随机访问的API或数组。说下前两个特性。我们知道HashMap是以键值对的形式存储的，而保证键值对存储有效性的关键点就在于key和value是一一映射的，所以可以保证HashSet中存储的对象是唯一的，同时由于HashMap自身携带了contains方法，所以确定性也就实现了。
其他
HashSet是 非同步的 。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：
Set s = Collections.synchronizedSet(new HashSet(...));
网友评论