HashSet
可以直接看HashMap
1. 底层实现
HashSet的底层实现是HashMap
Set不能有重复的元素，HashMap不允许有重复的键
Set中有且只有1个元素的值为null
HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。
在HashSet中：
- 元素都存到HashMap键值对的Key上面，
-
Value是有一个统一的值
private static final Object PRESENT = new Object();- 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
2. 源码分析
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map; // 底层使用HashMap来保存HashSet中所有元素。
private static final Object PRESENT = new Object();// 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
//实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
public HashSet() {
map = new 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(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
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();
}
......
}
3. HashSet的插入与删除
插入：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
当有新值加入时，底层的HashMap会判断Key值是否存在（HashMap细节请移步深入理解HashMap）
- 如果不存在，则插入新值，同时这个插入的细节会依照HashMap插入细节
- 如果存在就不插入
删除：
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
同HashMap删除原理：底层实际调用HashMap的remove方法删除指定Entry。
- 如果存在于此set中，则需要将其移除的对象，并返回true
如果不存在，返回false
【问题1】既然hashset基于hashmap实现，你说一下 hashset的add方法中，为什么要在map.put的val上放上一个object类型的静态常量present？
首先要看hashmap的put 方法的返回值，map对象在调用put的时候传入一个key和val，会对其key进行一个算法得到一个位置，会把put的数据放到其位置上，如果该位置上已经存在当前key，会对其key映射的val给替换掉，并且返回之前的val，否则返回null。
好了，既然put的返回值原理搞清楚了，就要去看看 set 的add方法的实现，add方法是调用了put方法，并且把key放在了put的key上，val放了一个hashset类的静态常量present， 如果put 返回的是null，不是present，就说明 put的key是不存在的，add也会返回true，如果put返回的是present就说明之前的key是存在的，并不是说没有put上，所以add方法返回的false并不是存失败的意思，而是map.put的key是已经存在的，而且已经把val给替换了。
【问题2】既然hashset基于hashmap实现，你说一下 hashset的remove方法中，为什么要在map.remove key 完了之后要和present进行一个等值比较呢？
首先要看hashmap的remove的返回原因，hashmap的remove方法删除一个key的时候会把之前的val的返回出来，这点弄清楚。
就要明白为什么set在remove的时候要和present进行对比，如果map中remove的返回是present，说明key是存在的，返回true，这点要结合set的add进行一个联想，如果返回的不是present，说明这个key在set对象里面的hashmap中是不存在的，所以返回的是false。
注意：
- 说白了，HashSet就是限制了功能的HashMap，所以了解HashMap的实现原理，这个HashSet自然就通
- 对于HashSet中保存的对象，主要要正确重写equals方法和hashCode方法，以保证放入Set对象的唯一性
- 虽说是Set是对于重复的元素不放入，倒不如直接说是底层的Map直接把原值替代了（这个Set的put方法的返回值真有意思）
- HashSet没有提供get()方法，原因是同HashMap一样，Set内部是无序的，只能通过迭代的方式获得
