我是風箏，公眾號「古時的風箏」，一個兼具深度與廣度的程式員鼓勵師，一個本打算寫詩卻寫起了代碼的田園碼農！
文章會收錄在 JavaNewBee 中，更有 Java 后端知識圖譜，從小白到大牛要走的路都在里面，
之前的7000 字說清楚 HashMap已經詳細介紹了 HashMap 的原理和實作，本次再來說說他的同胞兄弟 HashSet，這兩兄弟經常被拿出來一起說，面試的時候，也經常是兩者結合著考察，難道它們兩個的實作方式很類似嗎，不然為什么總是放在一起比較，
實際上并不是因為它倆相似，從根本上來說，它倆本來就是同一個東西，再說的清楚明白一點， HashSet 就是個套了殼兒的 HashMap，所謂君子善假于物，HashSet 就假了 HashMap，既然你 HashMap 都擺在那兒了，那我 HashSet 何必重復造輪子，借你一樣，何不美哉！
HashSet 是什么
下面是 HashSet的繼承關系圖，還是老樣子，我們看一個資料結構的時候先看它的繼承關系圖，與 HashSet并列的還有 TreeSet，另外 HashSet 還有個子型別 LinkedHashSet，這個我們后面再說，
套殼 HashMap
為啥這么說呢，在我第一次看 HashSet原始碼的時候，已經準備好了筆記本，拿好了圓珠筆，準備好好探究一下 HashSet的神奇所在，可當我按著Ctrl+滑鼠左鍵進入原始碼的建構式的時候，我以為我走錯了地方，這建構式有點簡單，甚至還有點神奇，new 了一個 HashMap并且賦給了 map 屬性，
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
再三確認沒看錯的情況下，我明白了，HashSet就是在HashMap的基礎上套了個殼兒，我們用的是個HashSet，實際上它的內部存盤邏輯都是 HashMap的那套邏輯，
除了上面的那個無參型別的構造方法，還有其他的有參構造方法，一看便知，其實就是 HashMap包裝了一層而已，
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
用法
HashSet應該算是眾多資料結構中最簡單的一個了，滿打滿算也就那么幾個方法，
public Iterator<E> iterator() {
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);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
很簡單對不對，就這么幾個方法，而且你看每個方法其實都是對應的操作 map，也就是內部的 HashMap，也就是說只要你懂了 HashMap自然也就懂了 HashSet，
保證不重復
Set介面要求不能有重復項，只要繼承了 Set就要遵守這個規定，我們大多數情況下使用 HashSet也是因為它有去重的功能，
那它是如何辦到的呢，這就要從它的 add方法說起了，
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashSet的 add方法其實就是呼叫了HashMap的put方法，但是我們都知道 put進去的是一個鍵值對，但是 HashSet存的不是鍵值對啊，是一個泛型啊，那它是怎么辦到的呢？
它把你要存的值當做 HashMap的 key，而 value 值是一個 final的Object物件，只起一個占位作用，而HashMap本身就不允許重復鍵，正好被HashSet拿來即用，
如何保證不重復呢
HashMap中不允許存在相同的 key 的，那怎么保證 key 的唯一性呢，判斷的代碼如下，
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
首先通過 hash 演算法算出的值必須相等，算出的結果是 int，所以可以用 == 符號判斷，只是這個條件可不行，要知道哈希碰撞是什么意思，有可能兩個不一樣的 key 最后產生的 hash 值是相同的，
并且待插入的 key == 當前索引已存在的 key，或者 待插入的 key.equals(當前索引已存在的key)，注意== 和 equals 是或的關系，== 符號意味著這是同一個物件， equals 用來確定兩個物件內容相同，
如果 key 是基本資料型別，比如 int，那相同的值肯定是相等的，并且產生的 hashCode 也是一致的，
String 型別算是最常用的 key 型別了，我們都知道相同的字串產生的 hashCode 也是一樣的，并且字串可以用 equals 判斷相等，
但是如果用參考型別當做 key 呢，比如我定義了一個 MoonKey 作為 key 值型別
public class MoonKey {
private String keyTile;
public String getKeyTile() {
return keyTile;
}
public void setKeyTile(String keyTile) {
this.keyTile = keyTile;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MoonKey moonKey = (MoonKey) o;
return Objects.equals(keyTile, moonKey.keyTile);
}
}
然后用下面的代碼進行兩次添加，你說 size 的長度是 1 還是 2 呢？
Map<MoonKey, String> m = new HashMap<>();
MoonKey moonKey = new MoonKey();
moonKey.setKeyTile("1");
MoonKey moonKey1 = new MoonKey();
moonKey1.setKeyTile("1");
m.put(moonKey, "1");
m.put(moonKey1, "2");
System.out.println(hash(moonKey));
System.out.println(hash(moonKey1));
System.out.println(m.size());
答案是 2 ，為什么呢，因為 MoonKey 沒有重寫 hashCode 方法，導致 moonkey 和 moonKey1 的 hash 值不可能一樣，當不重寫 hashCode 方法時，默認繼承自 Object的 hashCode 方法，而每個 Object物件的 hash 值都是獨一無二的，
劃重點，正確的做法應該是加上 hashCode的重寫，
@Override
public int hashCode() {
return Objects.hash(keyTile);
}
這也是為什么要求重寫 equals 方法的同時，也必須重寫 hashCode方法的原因之一， 如果兩個物件通過呼叫equals方法是相等的，那么這兩個物件呼叫hashCode方法必須回傳相同的整數，有了這個基礎才能保證 HashMap或者HashSet的 key 唯一，
非執行緒安全
由于HashMap不是執行緒安全的，自然，HashSet也不是執行緒安全啦，在多執行緒、高并發環境中慎用，如果要用的話怎么辦呢，不像 HashMap那樣有多執行緒版本的ConcurrentHashMap，不存在 ``ConcurrentHashSet`這種資料結構，如果想用的話要用下面這種方式，
Set<String> set = Collections.synchronizedSet(new HashSet<String>());
或者使用 ConcurrentHashMap.KeySetView也可以，但是，這其實就不是 HashSet了，而是 ConcurrentHashMap的一個實作了 Set介面的靜態內部類，多執行緒情況下使用起來完全沒問題，
ConcurrentHashMap.KeySetView<String,Boolean> keySetView = ConcurrentHashMap.newKeySet();
keySetView.add("a");
keySetView.add("b");
keySetView.add("c");
keySetView.add("a");
keySetView.forEach(System.out::println);
LinkedHashSet
如果說 HashSet是套殼兒HashMap，那么LinkedHashSet就是套殼兒LinkedHashMap，對比 HashSet，它的一個特點就是保證資料有序，插入的時候什么順序，遍歷的時候就是什么順序，
看一下它其中的無參建構式，
public LinkedHashSet() {
super(16, .75f, true);
}
LinkedHashSet繼承自 HashSet，所以 super(16, .75f, true);是呼叫了HashSet三個引數的建構式，
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
這次不是 new HashMap了，而是 new 了一個 LinkedHashMap，這就是它能保證有序性的關鍵，LinkedHashMap用雙向鏈表的方式在 HashMap的基礎上額外保存了鍵值對的插入順序，
HashMap中定義了下面這三個方法，這三個方法是在插入和洗掉鍵值對的時候呼叫的方法，用來維護雙向鏈表，在LinkedHashMap中有具體的實作，
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
由于LinkedHashMap可以保證鍵值對順序，所以，用來實作簡單的 LRU 快取，
所以，如果你有場景既要保證元素無重復，又要保證元素有序，可以使用 LinkedHashSet，
最后
其實你掌握了 HashMap就掌握了 HashSet，它沒有什么新東西，就是巧妙的利用了 HashMap而已，新不新不要緊，好用才是最重要的，
壯士且慢，先給點個贊吧，總是被白嫖，身體吃不消！
我是風箏，公眾號「古時的風箏」，一個兼具深度與廣度的程式員鼓勵師，一個本打算寫詩卻寫起了代碼的田園碼農！你可選擇現在就關注我，或者看看歷史文章再關注也不遲，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/153784.html
標籤：Java