HashSet
可以直接看HashMap
1. 底層實現(xiàn)
HashSet的底層實現(xiàn)是HashMap
Set不能有重復的元素，HashMap不允許有重復的鍵
Set中有且只有1個元素的值為null
HashMap中，null可以作為鍵，這樣的鍵只有一個；可以有一個或多個鍵所對應的值為null。
在HashSet中：
- 元素都存到HashMap鍵值對的Key上面，
-
Value是有一個統(tǒng)一的值
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細節(jié)請移步深入理解HashMap）
- 如果不存在，則插入新值，同時這個插入的細節(jié)會依照HashMap插入細節(jié)
- 如果存在就不插入
刪除：
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
同HashMap刪除原理：底層實際調(diào)用HashMap的remove方法刪除指定Entry。
- 如果存在于此set中，則需要將其移除的對象，并返回true
如果不存在，返回false
【問題1】既然hashset基于hashmap實現(xiàn)，你說一下 hashset的add方法中，為什么要在map.put的val上放上一個object類型的靜態(tài)常量present？
首先要看hashmap的put 方法的返回值，map對象在調(diào)用put的時候傳入一個key和val，會對其key進行一個算法得到一個位置，會把put的數(shù)據(jù)放到其位置上，如果該位置上已經(jīng)存在當前key，會對其key映射的val給替換掉，并且返回之前的val，否則返回null。
好了，既然put的返回值原理搞清楚了，就要去看看 set 的add方法的實現(xiàn)，add方法是調(diào)用了put方法，并且把key放在了put的key上，val放了一個hashset類的靜態(tài)常量present， 如果put 返回的是null，不是present，就說明 put的key是不存在的，add也會返回true，如果put返回的是present就說明之前的key是存在的，并不是說沒有put上，所以add方法返回的false并不是存失敗的意思，而是map.put的key是已經(jīng)存在的，而且已經(jīng)把val給替換了。
【問題2】既然hashset基于hashmap實現(xiàn)，你說一下 hashset的remove方法中，為什么要在map.remove key 完了之后要和present進行一個等值比較呢？
首先要看hashmap的remove的返回原因，hashmap的remove方法刪除一個key的時候會把之前的val的返回出來，這點弄清楚。
就要明白為什么set在remove的時候要和present進行對比，如果map中remove的返回是present，說明key是存在的，返回true，這點要結(jié)合set的add進行一個聯(lián)想，如果返回的不是present，說明這個key在set對象里面的hashmap中是不存在的，所以返回的是false。
注意：
- 說白了，HashSet就是限制了功能的HashMap，所以了解HashMap的實現(xiàn)原理，這個HashSet自然就通
- 對于HashSet中保存的對象，主要要正確重寫equals方法和hashCode方法，以保證放入Set對象的唯一性
- 雖說是Set是對于重復的元素不放入，倒不如直接說是底層的Map直接把原值替代了（這個Set的put方法的返回值真有意思）
- HashSet沒有提供get()方法，原因是同HashMap一樣，Set內(nèi)部是無序的，只能通過迭代的方式獲得
