Hashset源碼分析
- 2020 年 3 月 12 日
- 筆記
1. 概述
Hashset 實現 set 介面，底層基於 Hashmap 實現, 但與 Hashmap 不同的實 Hashmap 存儲鍵值對，Hashset 僅存儲對象。
HashSet 使用成員對象來計算 hashcode 值。
2. 原理
在《Head fist java》一書中有描述:
當你把對象加入 HashSet 時，HashSet 會先計算對象的 hashcode 值來判斷對象加入的位置，同時也會與其他加入的對象的 hashcode 值作比較，如果沒有相符的 hashcode，HashSet 會假設對象沒有重複出現。但是如果發現有相同 hashcode 值的對象，這時會調用 equals()方法來檢查 hashcode 相等的對象是否真的相同。如果兩者相同，則覆蓋舊元素。
這裡看到很多文章說: 如果 equals()方法相等，HashSet 就不會讓加入操作成功。根據 hashmap 的 put()方法源碼可知，實際上是覆蓋操作，雖然覆蓋對象的 key 和 value 都完全一致。
hashCode()與 equals()的相關規定：
- 如果兩個對象相等，則 hashcode 一定也是相同的
- 兩個對象相等,對兩個 equals 方法返回 true
- 兩個對象有相同的 hashcode 值，它們也不一定是相等的
- 綜上，equals 方法被覆蓋過，則 hashCode 方法也必須被覆蓋
- hashCode()的默認行為是對堆上的對象產生獨特值。如果沒有重寫 hashCode()，則該 class 的兩個對象無論如何都不會相等（即使這兩個對象指向相同的數據）。
==與 equals 的區別
- ==是判斷兩個變數或實例是不是指向同一個記憶體空間 equals 是判斷兩個變數或實例所指向的記憶體空間的值是不是相同
- ==是指對記憶體地址進行比較 equals()是對字元串的內容進行比較
- ==指引用是否相同 equals()指的是值是否相同
3. 源碼分析
首先查看下源碼結構，發現該類源碼相對比較簡單
3.1 構造方法
/** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has * default initial capacity (16) and load factor (0.75). */ // 內部存儲在hashmap中 public HashSet() { map = new HashMap<>(); }3.2 添加元素 add()
private static final Object PRESENT = new Object(); public boolean add(E e) { return map.put(e, PRESENT)==null; }可以看到添加的對象直接作為 Hashmap 的 key, 而 value 是 final 修飾的空對象。
根據之前對 Java 面試必問之 Hashmap 底層實現原理(JDK1.8) 中 put() 方法的解讀可以知道:
在 Hashmap 中首先根據 hashCode 尋找數組 bucket，當 hash 衝突時，需要比較 key 是否相等，相等則覆蓋，否則通過拉鏈法進行處理。在 Hashset 中存儲的對象作為 key，所以存儲對象需要重寫 hashCode() 和 equals() 方法。
4. 使用案例分析
4.1 存儲字元串案例
再來看一組示例
public class Demo2 { public static void main(String[] args) { HashSet<Object> hashSet = new HashSet<>(); hashSet.add("a"); hashSet.add("b"); hashSet.add("c"); hashSet.add("a"); System.out.println(hashSet); } }結果
[a, b, c]分析
查看字元串源碼.字元串重寫了 hashCode()和 equals 方法, 所以結果符合預期
public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } public boolean equals(Object anObject) { if (this == anObject) { return true; } if (anObject instanceof String) { String anotherString = (String)anObject; int n = value.length; if (n == anotherString.value.length) { char v1[] = value; char v2[] = anotherString.value; int i = 0; while (n-- != 0) { if (v1[i] != v2[i]) return false; i++; } return true; } } return false; } }4.2 存儲對象錯誤案例
首先我們創建一個 user 對象
@Getter@Setter @AllArgsConstructor @ToString public class User { private String username; }根據 set 集合的屬性，set 中的元素是不重複的，現在測試下
public class Demo { public static void main(String[] args) { HashSet<Object> hashSet = new HashSet<>(); hashSet.add(new User("a")); hashSet.add(new User("b")); hashSet.add(new User("c")); hashSet.add(new User("a")); System.out.println(hashSet); } }結果輸出
[User(username=a), User(username=c), User(username=b), User(username=a)]怎麼會有重複的呢? 和預期結果不符呀。其實根據上邊的源碼我們已經知道原因了，列印 hash 值確認下
[901506536, 1513712028, 747464370, 1018547642]java 中對象默認繼承頂級父類 Object。在 Object 類中源碼如下:
public native int hashCode(); // 比較記憶體地址 public boolean equals(Object obj) { return (this == obj); }4.3 存儲對象正確示範
重寫 equals()和 hashCode()方法。(這裡偷了個懶，感興趣的大家可以自己重寫下這 2 個方法)
@Getter@Setter @AllArgsConstructor @ToString @EqualsAndHashCode public class User extends Object{ private String username; }再次輸出發現結果唯一了
[User(username=a), User(username=b), User(username=c)]5. 總結
其實 HashSet 的一些東西都是用 HashMap 來實現的，如果 HashMap 的源碼已經閱讀過的話基本上沒有什麼問題。這可能是我寫的最輕鬆的一篇文章。
