教妹學 Java ：為什么重寫 Equals 時必須重寫 HashCode 方法
“二哥，我在讀《Effective Java》 的時候，第 11 條規約說重寫 equals 的時候必須要重寫 hashCode 方法，這是為什么呀?”三妹單刀直入地問。
“三妹啊，這個問題問得非常好，因為它也是面試中經常考的一個知識點。今天哥就帶你來梳理一下。”我說。
Java 是一門面向對象的編程語言，所有的類都會默認繼承自 Object 類，而 Object 的中文意思就是“對象”。
Object 類中有這么兩個方法：
- public native int hashCode();
- public boolean equals(Object obj) {
- return (this == obj);
- }
1)hashCode 方法
這是一個本地方法，用來返回對象的哈希值(一個整數)。在 Java 程序執行期間，對同一個對象多次調用該方法必須返回相同的哈希值。
2)equals 方法
對于任何非空引用 x 和 y，當且僅當 x 和 y 引用的是同一個對象時，equals 方法才返回 true。
“二哥，看起來兩個方法之間沒有任何關聯啊?”三妹質疑道。
“單從這兩段解釋上來看，的確是這樣的。”我解釋道，“但兩個方法的 doc 文檔中還有這樣兩條信息。”
第一，如果兩個對象調用 equals 方法返回的結果為 true，那么兩個對象調用 hashCode 方法返回的結果也必然相同——來自 hashCode 方法的 doc 文檔。
第二，每當重寫 equals 方法時，hashCode 方法也需要重寫，以便維護上一條規約。
“哦，這樣講的話，兩個方法確實關聯上了，但究竟是為什么呢?”三妹拋出了終極一問。
“hashCode 方法的作用是用來獲取哈希值，而該哈希值的作用是用來確定對象在哈希表中的索引位置。”我說。
哈希表的典型代表就是 HashMap，它存儲的是鍵值對，能根據鍵快速地檢索出對應的值。
- public V get(Object key) {
- HashMap.Node<K,V> e;
- return (e = getNode(hash(key), key)) == null ? null : e.value;
- }
這是 HashMap 的 get 方法，通過鍵來獲取值的方法。它會調用 getNode 方法：
- final HashMap.Node<K,V> getNode(int hash, Object key) {
- HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
- if ((tab = table) != null && (n = tab.length) > 0 &&
- (first = tab[(n - 1) & hash]) != null) {
- if (first.hash == hash && // always check first node
- ((k = first.key) == key || (key != null && key.equals(k))))
- return first;
- if ((e = first.next) != null) {
- if (first instanceof HashMap.TreeNode)
- return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
- do {
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- } while ((e = e.next) != null);
- }
- }
- return null;
- }
通常情況(沒有發生哈希沖突)下，first = tab[(n - 1) & hash] 就是鍵對應的值。按照時間復雜度來說的話，可表示為 O(1)。
如果發生哈希沖突，也就是 if ((e = first.next) != null) {} 子句中，可以看到如果節點不是紅黑樹的時候，會通過 do-while 循環語句判斷鍵是否 equals 返回對應值的。按照時間復雜度來說的話，可表示為 O(n)。
HashMap 是通過拉鏈法來解決哈希沖突的，也就是如果發生哈希沖突，同一個鍵的坑位會放好多個值，超過 8 個值后改為紅黑樹，為了提高查詢的效率。
顯然，從時間復雜度上來看的話 O(n) 比 O(1) 的性能要差，這也正是哈希表的價值所在。
“O(n) 和 O(1) 是什么呀?”三妹有些不解。
“這是時間復雜度的一種表示方法，隨后二哥專門給你講一下。簡單說一下 n 和 1 的意思，很顯然，n 和 1 都代表的是代碼執行的次數，假如數據規模為 n，n 就代表需要執行 n 次，1 就代表只需要執行一次。”我解釋道。
“三妹，你想一下，如果沒有哈希表，但又需要這樣一個數據結構，它里面存放的數據是不允許重復的，該怎么辦呢?”我問。
“要不使用 equals 方法進行逐個比較?”三妹有些不太確定。
“這種方法當然是可行的，就像 if ((e = first.next) != null) {} 子句中那樣，但如果數據量特別特別大，性能就會很差，最好的解決方案還是 HashMap。”
HashMap 本質上是通過數組實現的，當我們要從 HashMap 中獲取某個值時，實際上是要獲取數組中某個位置的元素，而位置是通過鍵來確定的。
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
這是 HashMap 的 put 方法，會將鍵值對放入到數組當中。它會調用 putVal 方法：
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
- // 拉鏈
- }
- return null;
- }
通常情況下，p = tab[i = (n - 1) & hash]) 就是鍵對應的值。而數組的索引 (n - 1) & hash 正是基于 hashCode 方法計算得到的。
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- }
“那二哥，你好像還是沒有說為什么重寫 equals 方法的時候要重寫 hashCode 方法呀?”三妹忍不住了。
“來看下面這段代碼。”我說。
- public class Test {
- public static void main(String[] args) {
- Student s1 = new Student(18, "張三");
- Map<Student, Integer> scores = new HashMap<>();
- scores.put(s1, 98);
- Student s2 = new Student(18, "張三");
- System.out.println(scores.get(s2));
- }
- }
- class Student {
- private int age;
- private String name;
- public Student(int age, String name) {
- this.age = age;
- this.name = name;
- }
- @Override
- public boolean equals(Object o) {
- Student student = (Student) o;
- return age == student.age &&
- Objects.equals(name, student.name);
- }
- }
我們重寫了 Student 類的 equals 方法，如果兩個學生的年紀和姓名相同，我們就認為是同一個學生，雖然很離譜，但我們就是這么草率。
在 main 方法中，18 歲的張三考試得了 98 分，很不錯的成績，我們把張三和他的成績放到 HashMap 中，然后準備取出：
- null
“二哥，怎么輸出了 null，而不是預期當中的 98 呢?”三妹感到很不可思議。
“原因就在于重寫 equals 方法的時候沒有重寫 hashCode 方法。”我回答道，“equals 方法雖然認定名字和年紀相同就是同一個學生，但它們本質上是兩個對象，hashCode 并不相同。”
“那怎么重寫 hashCode 方法呢?”三妹問。
“可以直接調用 Objects 類的 hash 方法。”我回答。
- @Override
- public int hashCode() {
- return Objects.hash(age, name);
- }
Objects 類的 hash 方法可以針對不同數量的參數生成新的哈希值，hash 方法調用的是 Arrays 類的 hashCode 方法，該方法源碼如下：
- public static int hashCode(Object a[]) {
- if (a == null)
- return 0;
- int result = 1;
- for (Object element : a)
- result = 31 * result + (element == null ? 0 : element.hashCode());
- return result;
- }
第一次循環：
- result = 31*1 + Integer(18).hashCode();
第二次循環：
- result = (31*1 + Integer(18).hashCode()) * 31 + String("張三").hashCode();
針對姓名年紀不同的對象，這樣計算后的哈希值很難很難很難重復的;針對姓名年紀相同的對象，哈希值保持一致。
再次執行 main 方法，結果如下所示：
- 98
因為此時 s1 和 s2 對象的哈希值都為 776408。
“每當重寫 equals 方法時，hashCode 方法也需要重寫，原因就是為了保證：如果兩個對象調用 equals 方法返回的結果為 true，那么兩個對象調用 hashCode 方法返回的結果也必然相同。”我點題了。
“OK，get 了。”三妹開心地點了點頭，看得出來，今天學到了不少。
本文轉載自微信公眾號「沉默王二」，可以通過以下二維碼關注。轉載本文請聯系沉默王二公眾號。
