本文將深入討論HashSet實(shí)現(xiàn)原理的源碼細(xì)節(jié)帆离。在分析源碼之前玩徊，首先我們需要對HashSet有一個基本的理解晰筛。
HashSet只存儲不同的值，set中是不會出現(xiàn)重復(fù)值的莹汤。
HashSet和HashMap一樣也需要實(shí)現(xiàn)hash算法來計算對象的hash值快鱼，但不同的是，HashMap中添加一個鍵值對的時候纲岭， (Key, Value)抹竹，hash函數(shù)計算的是Key的hash值。而HashSet則是計算value的hash值止潮。當(dāng)我們調(diào)用HashSet的add（E e）的方法 的時候窃判，我們會計算機(jī)元素e的hash值，如果這個值之前沒出現(xiàn)過沽翔，就說明這個元素在set中不存在兢孝，如果出現(xiàn)過，就說明仅偎。set中已經(jīng)存在了跨蟹，就添加失敗。
知道了上述的基本概念之后橘沥，我們就可以打開JDK源碼窗轩，來一探究竟了。
關(guān)于hashSet的實(shí)現(xiàn)原理座咆，最重要的一個點(diǎn)就是HashSet內(nèi)部是使用HashMap來存儲對象的痢艺。所以請讀者務(wù)必先對hashMap的實(shí)現(xiàn)原理有一個初步的認(rèn)識。參考筆者的文章HashMap實(shí)現(xiàn)原理分析（Java源碼剖析）
我們可以看到HashSet有多個構(gòu)造函數(shù)介陶，但每個構(gòu)造函數(shù)都是初始化了一個HashMap的對象
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
/**
* Constructs a new set containing the elements in the specified
* collection. The <tt>HashMap</tt> is created with default load factor
* (0.75) and an initial capacity sufficient to contain the elements in
* the specified collection.
*
* @param c the collection whose elements are to be placed into this set
* @throws NullPointerException if the specified collection is null
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* the specified initial capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* the specified initial capacity and default load factor (0.75).
*
* @param initialCapacity the initial capacity of the hash table
* @throws IllegalArgumentException if the initial capacity is less
* than zero
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
我們可以觀察到堤舒，默認(rèn)的構(gòu)造函數(shù)指定的初始化容量是16，負(fù)載因子是0.75.哺呜。也就是說創(chuàng)建了一個長度為16的數(shù)組舌缤，默認(rèn)的負(fù)載因子為0.75，當(dāng)達(dá)到容量時，map會自動擴(kuò)容国撵。
而這里的HashMap的是如下：
private transient HashMap<E,Object> map;
可以看到陵吸，HashSet中使用的HashMap，key為Set的元素類型介牙，value為Object壮虫。
add(E e)
我們來看add方法的實(shí)現(xiàn)
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element <tt>e</tt> to this set if
* this set contains no element <tt>e2</tt> such that
* <tt>(e==null ? e2==null : e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns <tt>false</tt>.
*
* @param e element to be added to this set
* @return <tt>true</tt> if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
PRESENT的定義
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
我們看到PRESENT是一個靜態(tài)的類對象，Object類型环础。所有HashSet的實(shí)例都共享這個對象囚似。
也就是說，我們在向set中添加一個e元素的時候喳整，實(shí)際上就是在像map添加一個（e, Object）的鍵值對谆构。我們添加的元素e變成了map中的key，而value則都是Obeject對象框都。又因?yàn)閙ap中key值是唯一的，而value是可以重復(fù)的呵晨。所以我們添加的e作為key的話魏保，就可以保證添加成功的話，e一定是唯一的摸屠。這就實(shí)現(xiàn)了set的唯一性谓罗。
remove(Object o)
我們接下來看remove的代碼
/**
* Removes the specified element from this set if it is present.
* More formally, removes an element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>,
* if this set contains such an element. Returns <tt>true</tt> if
* this set contained the element (or equivalently, if this set
* changed as a result of the call). (This set will not contain the
* element once the call returns.)
*
* @param o object to be removed from this set, if present
* @return <tt>true</tt> if the set contained the specified element
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
我們知道Hashmap中移除一個key的話，會返回這個key值鎖對應(yīng)的value季二，而我們這里的map檩咱，所有的key的value都是同一個對象PRESENT，所以我們這里只需要判斷map.remove(o)的返回值是不是PRESENT胯舷，就可以確定是否成功移除了
iterator()
我們知道hashSet沒有g(shù)et方法刻蚯，想要獲取HashSet的元素需要調(diào)用iterator()
為什么會這樣呢？
其實(shí)只要我們結(jié)合HashSet底層是由HashMap實(shí)現(xiàn)的就知道桑嘶，我們添加的元素值都被map當(dāng)成了key來存儲炊汹，顯然沒有從map中獲取單獨(dú)一個key的方法，但是我們可以獲取所有key逃顶，調(diào)用keySet方法即可讨便。
/**
* Returns an iterator over the elements in this set. The elements
* are returned in no particular order.
*
* @return an Iterator over the elements in this set
* @see ConcurrentModificationException
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
小結(jié)
HashSet由于內(nèi)部實(shí)現(xiàn)是完全基于HashMap的，所以原理較為簡單以政，代碼也不多霸褒，源碼加上注釋也就是300多行。
關(guān)于hashSet的實(shí)現(xiàn)原理盈蛮，我們需要掌握一下幾點(diǎn)
hashSet內(nèi)部用HashMap來存儲元素
HashSet利用本身的值來計算hash值废菱，因?yàn)橹当划?dāng)作hashmap的key，而hashmap是利用key來計算hash值的
因?yàn)閔ashset將value當(dāng)作key來存儲，所以根據(jù)map的key值唯一的原理昙啄，我們就可以實(shí)現(xiàn)set的無重復(fù)元素的功能
