Java 集合系列： HashSet詳解！！看這篇就夠了

這一章，我們對HashSet進行學習。

我們先對HashSet有個整體認識，然後再學習它的源碼，最後再通過實例來學會使用HashSet。

第1部分 HashSet介紹

HashSet 簡介

HashSet 是一個沒有重複元素的集合。

它是由HashMap實現的，不保證元素的順序，而且HashSet允許使用 null 元素。

HashSet是非同步的。如果多個線程同時訪問一個哈希 set，而其中至少一個線程修改了該 set，那麼它必須 保持外部同步。這通常是通過對自然封裝該 set 的對象執行同步操作來完成的。如果不存在這樣的對象，則應該使用 Collections.synchronizedSet 方法來“包裝” set。最好在創建時完成這一操作，以防止對該 set 進行意外的不同步訪問：

Set s = Collections.synchronizedSet(new HashSet(...));

HashSet通過iterator()返回的迭代器是fail-fast的。

 // 默認構造函數
public HashSet() 
// 帶集合的構造函數
public HashSet(Collection extends E> c) 
// 指定HashSet初始容量和加載因子的構造函數
public HashSet(int initialCapacity, float loadFactor) 
// 指定HashSet初始容量的構造函數
public HashSet(int initialCapacity) 
// 指定HashSet初始容量和加載因子的構造函數,dummy沒有任何作用
HashSet(int initialCapacity, float loadFactor, boolean dummy) 

HashSet的主要API

boolean add(E object)
void clear()
Object clone()
boolean contains(Object object)
boolean isEmpty()
Iterator iterator()
boolean remove(Object object)
int size()

第2部分 HashSet數據結構

HashSet的繼承關係如下：

java.lang.Object
 ↳ java.util.AbstractCollection
 ↳ java.util.AbstractSet 

 ↳ java.util.HashSet
public class HashSet
 extends AbstractSet
 implements Set, Cloneable, java.io.Serializable { }

HashSet與Map關係如下圖：

這裡寫圖片描述

從圖中可以看出：

(01) HashSet繼承於AbstractSet，並且實現了Set接口。

(02) HashSet的本質是一個"沒有重複元素"的集合，它是通過HashMap實現的。HashSet中含有一個"HashMap類型的成員變量"map，HashSet的操作函數，實際上都是通過map實現的。

第3部分 HashSet源碼解析(基於JDK1.6.0_45)

為了更瞭解HashSet的原理，下面對HashSet源碼代碼作出分析。

package java.util;
public class HashSet
 extends AbstractSet
 implements Set, Cloneable, java.io.Serializable
{
 static final long serialVersionUID = -5024744406713321676L;
 // HashSet是通過map(HashMap對象)保存內容的
 private transient HashMap map;
 // PRESENT是向map中插入key-value對應的value
 // 因為HashSet中只需要用到key，而HashMap是key-value鍵值對；
 // 所以，向map中添加鍵值對時，鍵值對的值固定是PRESENT
 private static final Object PRESENT = new Object();
 // 默認構造函數 

 public HashSet() {
 // 調用HashMap的默認構造函數，創建map
 map = new HashMap();
 }
 // 帶集合的構造函數
 public HashSet(Collection extends E> c) {
 // 創建map。
 // 為什麼要調用Math.max((int) (c.size()/.75f) + 1, 16)，從 (c.size()/.75f) + 1 和 16 中選擇一個比較大的樹呢？ 
 // 首先，說明(c.size()/.75f) + 1
 // 因為從HashMap的效率(時間成本和空間成本)考慮，HashMap的加載因子是0.75。
 // 當HashMap的“閾值”(閾值=HashMap總的大小*加載因子) < “HashMap實際大小”時，
 // 就需要將HashMap的容量翻倍。
 // 所以，(c.size()/.75f) + 1 計算出來的正好是總的空間大小。
 // 接下來，說明為什麼是 16 。
 // HashMap的總的大小，必須是2的指數倍。若創建HashMap時，指定的大小不是2的指數倍；
 // HashMap的構造函數中也會重新計算，找出比“指定大小”大的最小的2的指數倍的數。
 // 所以，這裡指定為16是從性能考慮。避免重複計算。
 map = new HashMap(Math.max((int) (c.size()/.75f) + 1, 16));
 // 將集合(c)中的全部元素添加到HashSet中
 addAll(c);
 }
 // 指定HashSet初始容量和加載因子的構造函數
 public HashSet(int initialCapacity, float loadFactor) { 

 map = new HashMap(initialCapacity, loadFactor);
 }
 // 指定HashSet初始容量的構造函數
 public HashSet(int initialCapacity) {
 map = new HashMap(initialCapacity);
 }
 HashSet(int initialCapacity, float loadFactor, boolean dummy) {
 map = new LinkedHashMap(initialCapacity, loadFactor);
 }
 // 返回HashSet的迭代器
 public Iterator iterator() {
 // 實際上返回的是HashMap的“key集合的迭代器”
 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);
 }
 // 將元素(e)添加到HashSet中
 public boolean add(E e) {
 return map.put(e, PRESENT)==null;
 }
 // 刪除HashSet中的元素(o)
 public boolean remove(Object o) {
 return map.remove(o)==PRESENT;
 }
 public void clear() {
 map.clear();
 }
 // 克隆一個HashSet，並返回Object對象
 public Object clone() {
 try {
 HashSet newSet = (HashSet) super.clone();
 newSet.map = (HashMap 
) map.clone();
 return newSet;
 } catch (CloneNotSupportedException e) {
 throw new InternalError();
 }
 }
 // java.io.Serializable的寫入函數
 // 將HashSet的“總的容量，加載因子，實際容量，所有的元素”都寫入到輸出流中
 private void writeObject(java.io.ObjectOutputStream s)
 throws java.io.IOException {
 // Write out any hidden serialization magic
 s.defaultWriteObject();
 // Write out HashMap capacity and load factor
 s.writeInt(map.capacity());
 s.writeFloat(map.loadFactor());
 // Write out size
 s.writeInt(map.size());
 // Write out all elements in the proper order.
 for (Iterator i=map.keySet().iterator(); i.hasNext(); )
 s.writeObject(i.next());
 }
 // java.io.Serializable的讀取函數
 // 將HashSet的“總的容量，加載因子，實際容量，所有的元素”依次讀出
 private void readObject(java.io.ObjectInputStream s)
 throws java.io.IOException, ClassNotFoundException {
 // Read in any hidden serialization magic
 s.defaultReadObject();
 // Read in HashMap capacity and load factor and create backing HashMap
 int capacity = s.readInt();
 float loadFactor = s.readFloat();
 map = (((HashSet)this) instanceof LinkedHashSet ?
 new LinkedHashMap(capacity, loadFactor) :
 new HashMap(capacity, loadFactor));
 // Read in size
 int size = s.readInt();
 // Read in all elements in the proper order.
 for (int i=0; i<size> E e = (E) s.readObject();
 map.put(e, PRESENT);
 }
 }
} 

/<size>

說明： HashSet的代碼實際上非常簡單，通過上面的註釋應該很能夠看懂。它是通過HashMap實現的，若對HashSet的理解有困難，建議先學習以下HashMap；學完HashMap之後，在學習HashSet就非常容易了。

第4部分 HashSet遍歷方式

4.1 通過Iterator遍歷HashSet

第一步：根據iterator()獲取HashSet的迭代器。

第二步：遍歷迭代器獲取各個元素。

// 假設set是HashSet對象
for(Iterator iterator = set.iterator();
 iterator.hasNext(); ) { 
 iterator.next();
} 
 

4.2 通過for-each遍歷HashSet

第一步：根據toArray()獲取HashSet的元素集合對應的數組。

第二步：遍歷數組，獲取各個元素。

// 假設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的遍歷測試程序如下：

import java.util.Random;
import java.util.Iterator;
import java.util.HashSet;
/*
 * @desc 介紹HashSet遍歷方法
 *
 * @author skywang
 */
public class HashSetIteratorTest {
 public static void main(String[] args) {
 // 新建HashSet
 HashSet set = new HashSet();
 // 添加元素 到HashSet中
 for (int i=0; i<5; i++)
 set.add(""+i);
 // 通過Iterator遍歷HashSet
 iteratorHashSet(set) ;
 // 通過for-each遍歷HashSet
 foreachHashSet(set);
 }
 /*
 * 通過Iterator遍歷HashSet。推薦方式 

 */
 private static void iteratorHashSet(HashSet set) {
 for(Iterator iterator = set.iterator();
 iterator.hasNext(); ) {
 System.out.printf("iterator : %s\n", iterator.next());
 }
 }
 /*
 * 通過for-each遍歷HashSet。不推薦！此方法需要先將Set轉換為數組
 */
 private static void foreachHashSet(HashSet set) {
 String[] arr = (String[])set.toArray(new String[0]);
 for (String str:arr)
 System.out.printf("for each : %s\n", str);
 }
}

運行結果：

iterator : 3
iterator : 2
iterator : 1
iterator : 0
iterator : 4
for each : 3
for each : 2
for each : 1
for each : 0
for each : 4

第5部分 HashSet示例

下面我們通過實例學習如何使用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的實際大小
 System.out.printf("size : %d\n", set.size());
 // 判斷HashSet是否包含某個值
 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轉換為數組
 String[] arr = (String[])set.toArray(new String[0]);
 for (String str:arr)
 System.out.printf("for each : %s\n", str);
 // 新建一個包含b、c、f的HashSet
 HashSet otherset = new HashSet();
 otherset.add("b");
 otherset.add("c");
 otherset.add("f");
 // 克隆一個removeset，內容和set一模一樣
 HashSet removeset = (HashSet)set.clone();
 // 刪除“removeset中，屬於otherSet的元素”
 removeset.removeAll(otherset);
 // 打印removeset
 System.out.printf("removeset : %s\n", removeset);
 // 克隆一個retainset，內容和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");
 }
}

運行結果：

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

你必須很努力，然後看起來才毫不費力！

關注我每天都有乾貨，看下期哦。

閱讀更多 程序猿小龍 的文章

關鍵字: 詳解 數據結構 集合