本篇结构：
- 前言
- 数据结构
- 重要参数
- 常用方法
- 源码分析
- 疑问解答
- 分析总结
一、前言
HashSet也是常用的数据结构，是一个没有重复元素的集合，也不能保证元素的顺序，可以有null值，但最多只能有一个。
HashSet的实现是基于HashMap的，在了解过HashMap的源码（java容器源码分析--HashMap（JDK1.8））后，再看HashSet的源码，会简单很多，所以本文也会简短很多。
二、数据结构
HashSet是基于HashMap来实现的，底层采用HashMap来保存元素。所以参考HashMap的数据结构即可。
三、重要参数
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
一个map属性，是底层使用该map来保存HashSet的元素；
一个静态的Object常量PRESENT，因为HashMap存的是Key-Value对，所以这里分配了一个静态空对象用作所有Key的Value。
四、常用方法
public class HashSetTest {
public static void main(String[] args) {
// HashSet常用API
testHashSetAPIs() ;
}
private static void testHashSetAPIs() {
// new
HashSet set = new HashSet();
// add
set.add("a");
set.add("b");
set.add("c");
set.add("d");
set.add("e");
// size
System.out.printf("size : %d\n", set.size());
// contains
System.out.printf("HashSet contains a :%s\n", set.contains("a"));
System.out.printf("HashSet contains g :%s\n", set.contains("g"));
// remove
set.remove("e");
// toArray
String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr)
System.out.printf("for each : %s\n", str);
// 新建一个包含b、c、f的HashSet
HashSet otherset = new HashSet();
otherset.add("b");
otherset.add("c");
otherset.add("f");
// 克隆一个removeset，内容和set一模一样
HashSet removeset = (HashSet)set.clone();
// 删除“removeset中，属于otherSet的元素”
removeset.removeAll(otherset);
// 打印removeset
System.out.printf("removeset : %s\n", removeset);
// 克隆一个retainset，内容和set一模一样
HashSet retainset = (HashSet)set.clone();
// 保留“retainset中，属于otherSet的元素”
retainset.retainAll(otherset);
// 打印retainset
System.out.printf("retainset : %s\n", retainset);
// 遍历HashSet
for(Iterator iterator = set.iterator();
iterator.hasNext(); )
System.out.printf("iterator : %s\n", iterator.next());
// 清空HashSet
set.clear();
// 输出HashSet是否为空
System.out.printf("%s\n", set.isEmpty()?"set is empty":"set is not empty");
}
}
运行结果：
size : 5
HashSet contains a :true
HashSet contains g :false
for each : a
for each : b
for each : c
for each : d
removeset : [a, d]
retainset : [b, c]
iterator : a
iterator : b
iterator : c
iterator : d
set is empty
比较懒，这段代码是直接拷贝过来的(http://www.cnblogs.com/skywang12345/p/3311252.html)。
主要是了解HashSet的常用方法。
五、源码分析
5.1、构造方法
一共有5个构造方法：
// 无参构造，默认初始化一个HashMap，HashMap的默认容量大小16和默认加载因子0.75
public HashSet() {
map = new HashMap<>();
}
// 构造一个指定Collection参数的HashSet，底层HashMap的容量为Math.max((int) (c.size()/.75f) + 1, 16)
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
// 构造指定初始容量大小和加载因子的底层HashMap
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
// 构造指定初始容量大小和默认的加载因子0.75的底层HashMap
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
// 不对外公开的一个构造方法（默认default修饰），底层构造的是LinkedHashMap，dummy只是一个标示参数，无具体意义
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
可以看到 new HashSet 其实就是 new HashMap， 所以可以预见，对 HashSet 的各种操作，其实对底层 HashMap 的操作。
5.2、添加操作
add(E e)
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
addAll(Collection<? extends E> c)
addAll(Collection<? extends E> c)是在其父类AbstractCollection中定义的。
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
// 遍历加入
for (E e : c)
if (add(e))
modified = true;
return modified;
}
5.3、删除操作
remove(Object o)
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
removeAll(Collection<?> c)
removeAll(Collection<?> c)是父类AbstractSet中定义的。
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
// 如果删除的集合容量小于HashSet的容量
if (size() > c.size()) {
// 遍历集合一个个删除
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
// 否则遍历HashSet，如果包含就删除
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
5.4、包含操作
contains(Object o)
public boolean contains(Object o) {
return map.containsKey(o);
}
containsAll(Collection<?> c)
// 一个个遍历判断，只要有一个不包含，就返回false
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
5.5、其他操作
size()
public int size() {
return map.size();
}
isEmpty()
public boolean isEmpty() {
return map.isEmpty();
}
iterator()
public Iterator<E> iterator() {
return map.keySet().iterator();
}
六、疑问解答
为什么要用HahSet?
假如我们现在想要在一大堆数据中查找X数据。LinkedList是基于链表的形式，查找需要逐级遍历，效率低。ArrayList如果不知道X的位置序号，还是一样要全部遍历一次直到查到结果，效率一样低。HashSet则根据散列值计算数组下标，速度很快。
七、分析总结
HashSet的源码更多的是对HashMap的封装，简单总结一下：
HashSet是基于HashMap实现的，不能有重复的元素；
HashSet可以插入null，但只能有一个；
HashSet不是线程安全的；
HashSet，HashMap都是hash表，而hash实现的容器最重要的一点就是可以快速存取。
