HashSet源码初探
附图：
timg.jpg
前言：
在日常项目中，一般我们需要一个元素唯一的集合多用HashSet实现， HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。但是他可以保证元素的唯一性。
其实对于HashSet，他的源码很简单，其本质就是对hashMap做了一个封装，基本上都是直接调用底层HashMap的相关方法来完成。另外他最大的特点就是Ele唯一，那么他是怎么实现的呢？我们知道，HashMap中key值是不能“重复”的（这个是否重复是通过hashcode和equals比较出来的，这是一个值得探讨的问题），HashSet正是借鉴了HashMap的key的这样一个特性，以此产生了这样一个不能包含重复数据的集合。
一 ：结构
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, Serializable {
二 ：为啥要用HahSet
假如我们现在想要在一大堆数据中查找X数据。LinkedList的数据结构就不说了，查找效率低的可怕。ArrayList哪，如果我们不知道X的位置序号，还是一样要全部遍历一次直到查到结果，效率一样可怕。HashSet天生就是为了提高查找效率的。
另外，散列码是由对象导出的一个整数值。在Object中有一个hashCode方法来得到散列码。基本上，每一个对象都有一个默认的散列码，其值就是对象的内存地址。
三：特性
（1）：是一个没有重复元素的集合
（2）：底层是由hashMap支持
（3）：它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变
（4）：允许使用 null 元素
（5）：非线程安全
四：重要知识点
（1）：重要属性
（2）：构造
（3）：重要方法
（4）：迭代方式
（5）：元素唯一性的保证机制
（6）：线程安全问题
（7）：与TreeSet以及其他集合比较
四：源码解析
4.1：重要属性
//序列号
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的源码中有一个重要属性map，这个map就是承载数据的容器，它实现了接口Serializable又以transient修饰map属性，其实质是用了另一种序列化方式，PRESENT是用来填充map的value的默认对象，而真正的值是在map的Key中存储，这也是HashSet为什么能保证元素的唯一性。
4.2：构造
/**
* 默认的无参构造器，构造一个空的HashSet。
*
* 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
*/
public HashSet() {
map = new HashMap<>();
}
/**
* 构造一个包含指定collection中的元素的新set。
* 实际底层使用默认的加载因子0.75和足以包含指定
* collection中所有元素的初始容量来创建一个HashMap。
* 其中的元素将存放在此set中的collection。
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size() / .75f) + 1, 16));
addAll(c);
}
/**
* 以指定的initialCapacity构造一个空的HashSet。
*
* 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
* @param initialCapacity 初始容量。
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
4.3添加元素
/**
* 可以看出，它调用的是map的添加方法，而把元素存储到了key中，value则是用PRESENT填充
*/
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
//map添加方法的实现
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
4.4删除元素
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
4.5 迭代器
/**
* 迭代器
* 由于其不保证元素的存入去除顺序，固没有get(int index)获取方法，
*
* 他的迭代器获取是取出map的key集合的迭代器（key才是真正的元素）
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
五：线程安全问题
通过看HashSet的源码我们发现其底层都是调用map的方法来实现的，而且都非同步方法，所以其非线程安全。
如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的
测试代码：
/**
* ClassName: TestHashSet
* @author lvfang
* @Desc: TODO
* @date 2017-9-22
*/
public class TestHashSet implements Runnable {
public Set<Integer> set = null;
public TestHashSet(Set<Integer> set){
this.set = set;
}
@Override
public void run() {
for (int i = 0; i < 50; i++) set.add(i);
System.out.println(set.size());
}
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
//单个线程操作（始终保持只有50个元素）
new Thread(new TestHashSet(set)).start();
//多个线程操作
//分别启动5个线程，每个线程都忘set中添加0-50的元素，我们知道set是保持元素唯一的，所以最终应该只有50个元素
for(int i=0;i<5;i++){
new Thread(new TestHashSet(set)).start();
}
}
}
解决方案 1 ：在操作时方法加同步
解决方案 2 ：Set s = Collections.synchronizedSet(new HashSet(...));
六：总结
（1）：HashSet：底层数据结构是哈希表,线程是非同步的，无须的
（2）：TreeSet：可以对Set集合中的元素进行排序(自然排序，由小到大) 底层的数据结构是二叉树，线程不同步
（3）：LinkedHashSet(链表结构和has结构相结合)
