在 JDK1.8 中，HashMap 是由 數(shù)組+鏈表+紅黑樹(shù)構(gòu)成，相對(duì)于早期版本的 JDK HashMap 實(shí)現(xiàn)，新增了紅黑樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)量較大且哈希碰撞較多時(shí)，能夠極大的增加檢索的效率。了解 HashMap 的具體實(shí)現(xiàn)后，我們?cè)賮?lái)介紹由 HashMap 作為底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的一種數(shù)據(jù)結(jié)構(gòu)——HashSet。（如果不了解 HashMap 的實(shí)現(xiàn)原理，建議先看看 HashMap，不然直接看 HashSet 是很難看懂的）。

1、HashSet 定義

HashSet 是一個(gè)由 HashMap 實(shí)現(xiàn)的集合。元素?zé)o序且不能重復(fù)。

public class HashSet< E >
     extends AbstractSet< E >
     implements Set< E >, Cloneable, java.io.Serializable

和前面介紹的大多數(shù)集合一樣，HashSet 也實(shí)現(xiàn)了 Cloneable 接口和 Serializable 接口，分別用來(lái)支持克隆以及支持序列化。還實(shí)現(xiàn)了 Set 接口，該接口定義了 Set 集合類(lèi)型的一套規(guī)范。

2、字段屬性

//HashSet集合中的內(nèi)容是通過(guò) HashMap 數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)的
 private transient HashMap< E,Object > map;
 //向HashSet中添加數(shù)據(jù)，數(shù)據(jù)在上面的 map 結(jié)構(gòu)是作為 key 存在的，而value統(tǒng)一都是 PRESENT
 private static final Object PRESENT = new Object();

第一個(gè)定義一個(gè) HashMap，作為實(shí)現(xiàn) HashSet 的數(shù)據(jù)結(jié)構(gòu)；第二個(gè) PRESENT 對(duì)象，因?yàn)榍懊嬷v過(guò) HashMap 是作為鍵值對(duì) key-value 進(jìn)行存儲(chǔ)的，而 HashSet 不是鍵值對(duì)，那么選擇 HashMap 作為實(shí)現(xiàn)，其原理就是存儲(chǔ)在 HashSet 中的數(shù)據(jù) 作為 Map 的 key，而 Map 的value 統(tǒng)一為 PRESENT（下面介紹具體實(shí)現(xiàn)時(shí)會(huì)了解）。

3、構(gòu)造函數(shù)

①、無(wú)參構(gòu)造

public HashSet() {
         map = new HashMap<  >();
     }

直接 new 一個(gè) HashMap 對(duì)象出來(lái)，采用無(wú)參的 HashMap 構(gòu)造函數(shù)，具有默認(rèn)初始容量（16）和加載因子（0.75）。

②、指定初始容量

public HashSet(int initialCapacity) {
         map = new HashMap<  >(initialCapacity);
     }

③、指定初始容量和加載因子

public HashSet(int initialCapacity, float loadFactor) {
         map = new HashMap<  >(initialCapacity, loadFactor);
     }

④、構(gòu)造包含指定集合中的元素

public HashSet(Collection< ? extends E > c) {
         map = new HashMap<  >(Math.max((int) (c.size()/.75f) + 1, 16));
         addAll(c);
     }

集合容量很好理解，這里我介紹一下什么是加載因子。在 HashMap 中，能夠存儲(chǔ)元素的數(shù)量就是：總的容量*加載因子 ，新增一個(gè)元素時(shí)，如果HashMap集合中的元素大于前面公式計(jì)算的結(jié)果了，那么就必須要進(jìn)行擴(kuò)容操作，從時(shí)間和空間考慮，加載因子一般都選默認(rèn)的0.75。

4、添加元素

public boolean add(E e) {
         return map.put(e, PRESENT)==null;
     }

通過(guò) map.put() 方法來(lái)添加元素，在上一篇博客介紹該方法時(shí)，說(shuō)明了該方法如果新插入的key不存在，則返回null，如果新插入的key存在，則返回原key對(duì)應(yīng)的value值（注意新插入的value會(huì)覆蓋原value值）。

也就是說(shuō) HashSet 的 add(E e) 方法，會(huì)將 e 作為 key，PRESENT 作為 value 插入到 map 集合中，如果 e 不存在，則插入成功返回 true;如果存在，則返回false。

5、刪除元素

public boolean remove(Object o) {
         return map.remove(o)==PRESENT;
     }

調(diào)用 HashMap 的remove(Object o) 方法，該方法會(huì)首先查找 map 集合中是否存在 o ，如果存在則刪除，并返回該值，如果不存在則返回 null。

也就是說(shuō) HashSet 的 remove(Object o) 方法，刪除成功返回 true，刪除的元素不存在會(huì)返回 false。

6、查找元素

public boolean contains(Object o) {
         return map.containsKey(o);
     }

調(diào)用 HashMap 的 containsKey(Object o) 方法，找到了返回 true，找不到返回 false。

7、遍歷元素

HashSet< Integer > set = new HashSet<  >();
set.add(1);
set.add(2);
//增強(qiáng)for循環(huán)
for(Integer i : set){
    System.out.println(i);
}
//普通for循環(huán)
Iterator< Integer > iterator = set.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
}

8、小結(jié)

好了，這就是JDK中java.util.HashSet 類(lèi)的介紹。