前言
今天來介紹下HashSet。前面，我們已經(jīng)系統(tǒng)的對List和Map進(jìn)行了學(xué)習(xí)针史。接下來，我們開始可以學(xué)習(xí)Set而芥。相信經(jīng)過Map的了解之后，學(xué)習(xí)Set會容易很多膀值。畢竟棍丐，Set的實(shí)現(xiàn)類都是基于Map來實(shí)現(xiàn)的(HashSet是通過HashMap實(shí)現(xiàn)的)误辑。
構(gòu)造圖如下:
藍(lán)色線條：繼承
綠色線條：接口實(shí)現(xiàn)
正文
對于HashSet而言，它是基于HashMap來實(shí)現(xiàn)的歌逢，底層采用HashMap來保存元素巾钉。所以如果對HashMap比較熟悉，那么HashSet是so easy!!
HashSet簡介
HashSet定義
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
HashSet 是一個(gè)沒有重復(fù)元素的集合秘案。
它是由HashMap實(shí)現(xiàn)的砰苍，不保證元素的順序，而且HashSet允許使用 null 元素阱高。
HashSet是非同步的赚导。如果多個(gè)線程同時(shí)訪問一個(gè)哈希 set，而其中至少一個(gè)線程修改了該 set讨惩，那么它必須 保持外部同步。這通常是通過對自然封裝該 set 的對象執(zhí)行同步操作來完成的寒屯。如果不存在這樣的對象荐捻，則應(yīng)該使用 Collections.synchronizedSet 方法來“包裝” set。最好在創(chuàng)建時(shí)完成這一操作寡夹，以防止對該 set 進(jìn)行意外的不同步訪問：
Set s = Collections.synchronizedSet(new HashSet(...));
HashSet通過iterator()返回的迭代器是fail-fast的处面。
HashSet屬性
// 底層使用HashMap來保存HashSet的元素
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
// 由于Set只使用到了HashMap的key，所以此處定義一個(gè)靜態(tài)的常量Object類菩掏，來充當(dāng)HashMap的value
private static final Object PRESENT = new Object();
看到這里就明白了魂角，和我們前面說的一樣，HashSet是用HashMap來保存數(shù)據(jù)智绸，而主要使用到的就是HashMap的key野揪。
看到private static final Object PRESENT = new Object();不知道你有沒有一點(diǎn)疑問呢。這里使用一個(gè)靜態(tài)的常量Object類來充當(dāng)HashMap的value瞧栗，既然這里map的value是沒有意義的斯稳，為什么不直接使用null值來充當(dāng)value呢？比如寫成這樣子private final Object PRESENT = null;我們都知道的是迹恐，Java首先將變量PRESENT分配在椪醵瑁空間，而將new出來的Object分配到堆空間殴边，這里的new Object()是占用堆內(nèi)存的（一個(gè)空的Object對象占用8byte）憎茂，而null值我們知道，是不會在堆空間分配內(nèi)存的锤岸。那么想一想這里為什么不使用null值竖幔。想到什么嗎，看一個(gè)異常類java.lang.NullPointerException是偷， 噢買尬赏枚，這絕對是Java程序員的一個(gè)噩夢亡驰，這是所有Java程序猿都會遇到的一個(gè)異常，你看到這個(gè)異常你以為很好解決饿幅，但是有些時(shí)候也不是那么容易解決凡辱，Java號稱沒有指針，但是處處碰到NullPointerException栗恩。所以啊透乾，為了從根源上避免NullPointerException的出現(xiàn)，浪費(fèi)8個(gè)byte又怎么樣磕秤，在下面的代碼中我再也不會寫這樣的代碼啦if (xxx == null) { ... } else {....}乳乌，好爽。
HashSet構(gòu)造函數(shù)
/**
* 使用HashMap的默認(rèn)容量大小16和默認(rèn)加載因子0.75初始化map市咆，構(gòu)造一個(gè)HashSet
*/
public HashSet() {
map = new HashMap<E,Object>();
}
/**
* 構(gòu)造一個(gè)指定Collection參數(shù)的HashSet汉操，這里不僅僅是Set，只要實(shí)現(xiàn)Collection接口的容器都可以
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<E,Object>(Math. max((int) (c.size()/.75f) + 1, 16));
// 使用Collection實(shí)現(xiàn)的Iterator迭代器蒙兰，將集合c的元素一個(gè)個(gè)加入HashSet中
addAll(c);
}
/**
* 使用指定的初始容量大小和加載因子初始化map磷瘤，構(gòu)造一個(gè)HashSet
*/
public HashSet( int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 使用指定的初始容量大小和默認(rèn)的加載因子0.75初始化map，構(gòu)造一個(gè)HashSet
*/
public HashSet( int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
/**
* 不對外公開的一個(gè)構(gòu)造方法（默認(rèn)default修飾）搜变，底層構(gòu)造的是LinkedHashMap采缚，dummy只是一個(gè)標(biāo)示參數(shù)，無具體意義
*/
HashSet( int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
從構(gòu)造方法可以很輕松的看出挠他，HashSet的底層是一個(gè)HashMap扳抽，理解了HashMap后，這里沒什么可說的殖侵。只有最后一個(gè)構(gòu)造方法有寫區(qū)別贸呢，這里構(gòu)造的是LinkedHashMap，該方法不對外公開拢军，實(shí)際上是提供給LinkedHashSet使用的贮尉，而第三個(gè)參數(shù)dummy是無意義的，只是為了區(qū)分其他構(gòu)造方法朴沿。
API方法摘要
HashSet源碼解析(基于JDK1.6.0_45)
增加和刪除
/**
* 利用HashMap的put方法實(shí)現(xiàn)add方法
*/
public boolean add(E e) {
return map .put(e, PRESENT)== null;
}
/**
* 利用HashMap的remove方法實(shí)現(xiàn)remove方法
*/
public boolean remove(Object o) {
return map .remove(o)==PRESENT;
}
/**
* 添加一個(gè)集合到HashSet中猜谚，該方法在AbstractCollection中
*/
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
// 取得集合c迭代器Iterator
Iterator<? extends E> e = c.iterator();
// 遍歷迭代器
while (e.hasNext()) {
// 將集合c的每個(gè)元素加入到HashSet中
if (add(e.next()))
modified = true;
}
return modified;
}
/**
* 刪除指定集合c中的所有元素，該方法在AbstractSet中
*/
public boolean removeAll(Collection<?> c) {
boolean modified = false;
// 判斷當(dāng)前HashSet元素個(gè)數(shù)和指定集合c的元素個(gè)數(shù)赌渣，目的是減少遍歷次數(shù)
if (size() > c.size()) {
// 如果當(dāng)前HashSet元素多魏铅，則遍歷集合c，將集合c中的元素一個(gè)個(gè)刪除
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
// 如果集合c元素多坚芜，則遍歷當(dāng)前HashSet览芳，將集合c中包含的元素一個(gè)個(gè)刪除
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
是否包含
/**
* 利用HashMap的containsKey方法實(shí)現(xiàn)contains方法
*/
public boolean contains(Object o) {
return map .containsKey(o);
}
/**
* 檢查是否包含指定集合中所有元素，該方法在AbstractCollection中
*/
public boolean containsAll(Collection<?> c) {
// 取得集合c的迭代器Iterator
Iterator<?> e = c.iterator();
// 遍歷迭代器鸿竖，只要集合c中有一個(gè)元素不屬于當(dāng)前HashSet沧竟，則返回false
while (e.hasNext())
if (!contains(e.next()))
return false;
return true;
}
****由于HashMap基于hash表實(shí)現(xiàn)铸敏，hash表實(shí)現(xiàn)的容器最重要的一點(diǎn)就是可以快速存取，那么HashSet對于contains方法悟泵，利用HashMap的containsKey方法杈笔，效率是非常之快的。在我看來糕非，這個(gè)方法也是HashSet最核心的賣點(diǎn)方法之一蒙具。****
容量檢查
/**
* Returns the number of elements in this set (its cardinality).
*
* @return the number of elements in this set (its cardinality)
*/
public int size() {
return map .size();
}
/**
* Returns <tt>true</tt> if this set contains no elements.
*
* @return <tt> true</tt> if this set contains no elements
*/
public boolean isEmpty() {
return map .isEmpty();
}
HashSet遍歷方式
通過Iterator遍歷HashSet
第一步：根據(jù)iterator()獲取HashSet的迭代器。
第二步：遍歷迭代器獲取各個(gè)元素朽肥。
// 假設(shè)set是HashSet對象
for(Iterator iterator = set.iterator();
iterator.hasNext(); ) {
iterator.next();
}
通過for-each遍歷HashSet
第一步：根據(jù)toArray()獲取HashSet的元素集合對應(yīng)的數(shù)組禁筏。
第二步：遍歷數(shù)組，獲取各個(gè)元素衡招。
// 假設(shè)set是HashSet對象篱昔，并且set中元素是String類型
String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr)
System.out.printf("for each : %s\n", str);
HashSet示例
下面我們通過實(shí)例學(xué)習(xí)如何使用HashSet
import java.util.Iterator;
import java.util.HashSet;
/*
* @desc HashSet常用API的使用。
*
* @author skywang
*/
public class HashSetTest {
public static void main(String[] args) {
// HashSet常用API
testHashSetAPIs() ;
}
/*
* HashSet除了iterator()和add()之外的其它常用API
*/
private static void testHashSetAPIs() {
// 新建HashSet
HashSet set = new HashSet();
// 將元素添加到Set中
set.add("a");
set.add("b");
set.add("c");
set.add("d");
set.add("e");
// 打印HashSet的實(shí)際大小
System.out.printf("size : %d\n", set.size());
// 判斷HashSet是否包含某個(gè)值
System.out.printf("HashSet contains a :%s\n", set.contains("a"));
System.out.printf("HashSet contains g :%s\n", set.contains("g"));
// 刪除HashSet中的“e”
set.remove("e");
// 將Set轉(zhuǎn)換為數(shù)組
String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr)
System.out.printf("for each : %s\n", str);
// 新建一個(gè)包含b始腾、c州刽、f的HashSet
HashSet otherset = new HashSet();
otherset.add("b");
otherset.add("c");
otherset.add("f");
// 克隆一個(gè)removeset，內(nèi)容和set一模一樣
HashSet removeset = (HashSet)set.clone();
// 刪除“removeset中窘茁，屬于otherSet的元素”
removeset.removeAll(otherset);
// 打印removeset
System.out.printf("removeset : %s\n", removeset);
// 克隆一個(gè)retainset怀伦，內(nèi)容和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");
}
}
運(yùn)行結(jié)果：
size : 5
HashSet contains a :true
HashSet contains g :false
for each : d
for each : b
for each : c
for each : a
removeset : [d, a]
retainset : [b, c]
iterator : d
iterator : b
iterator : c
iterator : a
set is empty
總結(jié)
HashSet和HashMap山林、Hashtable的區(qū)別
參考
該文為本人學(xué)習(xí)的筆記，方便以后自己跳槽前復(fù)習(xí)邢羔。參考網(wǎng)上各大帖子驼抹，取其精華整合自己的理解而成。集合框架源碼面試經(jīng)常會問拜鹤，所以解讀源碼十分必要,希望對你有用框冀。
java提高篇（二四）-----HashSet
Java 集合系列16之 HashSet詳細(xì)介紹(源碼解析)和使用示例
給jdk寫注釋系列之jdk1.6容器(6)-HashSet源碼解析&Map迭代器
整理的集合框架思維導(dǎo)圖
個(gè)人整理的Java集合框架思維導(dǎo)圖，動態(tài)維護(hù)敏簿。導(dǎo)出的圖片無法查看備注的一些信息明也，所以需要源文件的童鞋可以關(guān)注我個(gè)人主頁上的公眾號，回復(fù)Java集合框架即可獲取源文件惯裕。
一直覺得自己寫的不是技術(shù)温数，而是情懷，一篇篇文章是自己這一路走來的痕跡蜻势〕糯蹋靠專業(yè)技能的成功是最具可復(fù)制性的，希望我的這條路能讓你少走彎路握玛，希望我能幫你抹去知識的蒙塵够傍，希望我能幫你理清知識的脈絡(luò)甫菠，希望未來技術(shù)之巔上有你也有我。
