面試官：HashSet如何保證元素不重復？

作者：磊哥 2021-12-21 07:07:43

HashSet 實現了 Set 接口，由哈希表(實際是 HashMap)提供支持。HashSet 不保證集合的迭代順序，但允許插入 null 值。也就是說 HashSet 不能保證元素插入順序和迭代順序相同。

HashSet 實現了 Set 接口，由哈希表(實際是 HashMap)提供支持。HashSet 不保證集合的迭代順序，但允許插入 null 值。也就是說 HashSet 不能保證元素插入順序和迭代順序相同。HashSet 具備去重的特性，也就是說它可以將集合中的重復元素自動過濾掉，保存存儲在 HashSet 中的元素都是唯一的。

1.HashSet 基本用法

HashSet 基本操作方法有：add(添加)、remove(刪除)、contains(判斷某個元素是否存在)和 size(集合數量)。這些方法的性能都是固定操作時間，如果哈希函數是將元素分散在桶中的正確位置。HashSet 基本使用如下：

// 創建 HashSet 集合 
HashSet<String> strSet = new HashSet<>(); 
// 給 HashSet 添加數據 
strSet.add("Java"); 
strSet.add("MySQL"); 
strSet.add("Redis"); 
// 循環打印 HashSet 中的所有元素 
strSet.forEach(s -> System.out.println(s));

2.HashSet 無序性

HashSet 不能保證插入元素的順序和循環輸出元素的順序一定相同，也就是說 HashSet 其實是無序的集合，具體代碼示例如下：

HashSet<String> mapSet = new HashSet<>(); 
mapSet.add("深圳"); 
mapSet.add("北京"); 
mapSet.add("西安"); 
// 循環打印 HashSet 中的所有元素 
mapSet.forEach(m -> System.out.println(m));

以上程序的執行結果如下：

從上述代碼和執行結果可以看出，HashSet 插入的順序是：深圳 -> 北京 -> 西安，而循環打印的順序卻是：西安 -> 深圳 -> 北京，所以 HashSet 是無序的，不能保證插入和迭代的順序一致。

PS：如果要保證插入順序和迭代順序一致，可使用 LinkedHashSet 來替換 HashSet。

3.HashSet 錯誤用法

有人說 HashSet 只能保證基礎數據類型不重復，卻不能保證自定義對象不重復?這樣說對嗎?我們通過以下示例來說明此問題。

3.1 HashSet 與基本數據類型

使用 HashSet 存儲基本數據類型，實現代碼如下：

HashSet<Long> longSet = new HashSet<>(); 
longSet.add(666l); 
longSet.add(777l); 
longSet.add(999l); 
longSet.add(666l); 
// 循環打印 HashSet 中的所有元素 
longSet.forEach(l -> System.out.println(l));

以上程序的執行結果如下：

從上述結果可以看出，使用 HashSet 可以保證基礎數據類型不重復。

3.2 HashSet 與自定義對象類型

接下來，將自定義對象存儲到 HashSet 中，實現代碼如下：

public class HashSetExample { 
    public static void main(String[] args) { 
        HashSet<Person> personSet = new HashSet<>(); 
        personSet.add(new Person("曹操", "123")); 
        personSet.add(new Person("孫權", "123")); 
        personSet.add(new Person("曹操", "123")); 
        // 循環打印 HashSet 中的所有元素 
        personSet.forEach(p -> System.out.println(p)); 
    } 
} 
@Getter 
@Setter 
@ToString 
class Person { 
    private String name; 
    private String password; 
 
    public Person(String name, String password) { 
        this.name = name; 
        this.password = password; 
    } 
}

以上程序的執行結果如下：

從上述結果可以看出，自定義對象類型確實沒有被去重，那也就是說 HashSet 不能實現自定義對象類型的去重咯?其實并不是，HashSet 去重功能是依賴元素的 hashCode 和 equals 方法判斷的，通過這兩個方法返回的都是 true 那就是相同對象，否則就是不同對象。而前面的 Long 類型元素之所以能實現去重，正是因為 Long 類型中已經重寫了 hashCode 和 equals 方法，具體實現源碼如下：

@Override 
public int hashCode() { 
    return Long.hashCode(value); 
} 
public boolean equals(Object obj) { 
    if (obj instanceof Long) { 
        return value == ((Long)obj).longValue(); 
    } 
    return false; 
} 
//省略其他源碼......

更多關于 hashCode 和 equals 的內容，詳見：https://mp.weixin.qq.com/s/40zaEJEkQYM3Awk2EwIrWA

那么，想讓 HashSet 支持自定義對象去重，只需要在自定義對象中重寫 hashCode 和 equals 方法即可，具體實現代碼如下：

@Setter 
@Getter 
@ToString 
class Person { 
    private String name; 
    private String password; 
    public Person(String name, String password) { 
        this.name = name; 
        this.password = password; 
    } 
    @Override 
    public boolean equals(Object o) { 
        if (this == o) return true; // 引用相等返回 true 
        // 如果等于 null，或者對象類型不同返回 false 
        if (o == null || getClass() != o.getClass()) return false; 
        // 強轉為自定義 Person 類型 
        Person persion = (Person) o; 
        // 如果 name 和 password 都相等，就返回 true 
        return Objects.equals(name, persion.name) && 
                Objects.equals(password, persion.password); 
    } 
    @Override 
    public int hashCode() { 
        // 對比 name 和 password 是否相等 
        return Objects.hash(name, password); 
    } 
}

重新運行以上代碼，執行結果如下圖所示：圖片從上述結果可以看出，之前的重復項“曹操”已經被去重了。

4.HashSet 如何保證元素不重復?

我們只要了解了 HashSet 執行添加元素的流程，就能知道為什么 HashSet 能保證元素不重復了?HashSet 添加元素的執行流程是：當把對象加入 HashSet 時，HashSet 會先計算對象的 hashcode 值來判斷對象加入的位置，同時也會與其他加入的對象的 hashcode 值作比較，如果沒有相符的 hashcode，HashSet 會假設對象沒有重復出現，會將對象插入到相應的位置中。但是如果發現有相同 hashcode 值的對象，這時會調用對象的 equals() 方法來檢查對象是否真的相同，如果相同，則 HashSet 就不會讓重復的對象加入到 HashSet 中，這樣就保證了元素的不重復。

為了更清楚的了解 HashSet 的添加流程，我們可以嘗試閱讀 HashSet 的具體實現源碼，HashSet 添加方法的實現源碼如下(以下源碼基于 JDK 8)：

// hashmap 中 put() 返回 null 時，表示操作成功 
public boolean add(E e) { 
    return map.put(e, PRESENT)==null; 
}

從上述源碼可以看出 HashSet 中的 add 方法，實際調用的是 HashMap 中的 put，那么我們繼續看 HashMap 中的 put 實現：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
                boolean evict) { 
     Node<K, V>[] tab; 
     Node<K, V> p; 
     int n, i; 
     //如果哈希表為空，調用 resize() 創建一個哈希表，并用變量 n 記錄哈希表長度 
     if ((tab = table) == null || (n = tab.length) == 0) 
         n = (tab = resize()).length; 
     /** 
      * 如果指定參數 hash 在表中沒有對應的桶，即為沒有碰撞 
      * Hash函數，(n - 1) & hash 計算 key 將被放置的槽位 
      * (n - 1) & hash 本質上是 hash % n 位運算更快 
      */ 
     if ((p = tab[i = (n - 1) & hash]) == null) 
         // 直接將鍵值對插入到 map 中即可 
         tab[i] = newNode(hash, key, value, null); 
     else {// 桶中已經存在元素 
         Node<K, V> e; 
         K k; 
         // 比較桶中第一個元素(數組中的結點)的 hash 值相等，key 相等 
         if (p.hash == hash && 
                 ((k = p.key) == key || (key != null && key.equals(k)))) 
             // 將第一個元素賦值給 e，用 e 來記錄 
             e = p; 
             // 當前桶中無該鍵值對，且桶是紅黑樹結構，按照紅黑樹結構插入 
         else if (p instanceof TreeNode) 
             e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); 
             // 當前桶中無該鍵值對，且桶是鏈表結構，按照鏈表結構插入到尾部 
         else { 
             for (int binCount = 0; ; ++binCount) { 
                 // 遍歷到鏈表尾部 
                 if ((e = p.next) == null) { 
                     p.next = newNode(hash, key, value, null); 
                     // 檢查鏈表長度是否達到閾值，達到將該槽位節點組織形式轉為紅黑樹 
                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
                         treeifyBin(tab, hash); 
                     break; 
                 } 
                 // 鏈表節點的<key, value>與 put 操作<key, value> 
                 // 相同時，不做重復操作，跳出循環 
                 if (e.hash == hash && 
                         ((k = e.key) == key || (key != null && key.equals(k)))) 
                     break; 
                 p = e; 
             } 
         } 
         // 找到或新建一個 key 和 hashCode 與插入元素相等的鍵值對，進行 put 操作 
         if (e != null) { // existing mapping for key 
             // 記錄 e 的 value 
             V oldValue = e.value; 
             /** 
              * onlyIfAbsent 為 false 或舊值為 null 時，允許替換舊值 
              * 否則無需替換 
              */ 
             if (!onlyIfAbsent || oldValue == null) 
                 e.value = value; 
             // 訪問后回調 
             afterNodeAccess(e); 
             // 返回舊值 
             return oldValue; 
         } 
     } 
     // 更新結構化修改信息 
     ++modCount; 
     // 鍵值對數目超過閾值時，進行 rehash 
     if (++size > threshold) 
         resize(); 
     // 插入后回調 
     afterNodeInsertion(evict); 
     return null; 
 }

從上述源碼可以看出，當將一個鍵值對放入 HashMap 時，首先根據 key 的 hashCode() 返回值決定該 Entry 的存儲位置。如果有兩個 key 的 hash 值相同，則會判斷這兩個元素 key 的 equals() 是否相同，如果相同就返回 true，說明是重復鍵值對，那么 HashSet 中 add() 方法的返回值會是 false，表示 HashSet 添加元素失敗。因此，如果向 HashSet 中添加一個已經存在的元素，新添加的集合元素不會覆蓋已有元素，從而保證了元素的不重復。如果不是重復元素，put 方法最終會返回 null，傳遞到 HashSet 的 add 方法就是添加成功。

總結

HashSet 底層是由 HashMap 實現的，它可以實現重復元素的去重功能，如果存儲的是自定義對象必須重寫 hashCode 和 equals 方法。HashSet 保證元素不重復是利用 HashMap 的 put 方法實現的，在存儲之前先根據 key 的 hashCode 和 equals 判斷是否已存在，如果存在就不在重復插入了，這樣就保證了元素的不重復。

責任編輯：武曉燕來源： Java面試真題解析

HashSet 元素數量