深入 Java 原始碼來剖析 hashCode，從此菜不再是原罪-有解無憂

看完記得一鍵三連哦，微信搜索【沉默王二】關注這個沉默但有點東西的小丑，

假期結束了，需要快速切換到作業的狀態投入到新的一天當中，放假的時候痛快地玩耍，上班的時候積極的作業，這應該是我們大多數“現代人”該有的生活狀態，

我之所以費盡心思鋪墊了前面這段話，就是想告訴大家，技術文雖遲但到，來吧，學起來~

今天我們來談談 Java 中的 hashCode() 方法，眾所周知，Java 是一門面向物件的編程語言，所有的類都會默認繼承自 Object 類，而 Object 的中文意思就是“物件”，

Object 類中就包含了 hashCode() 方法：

@HotSpotIntrinsicCandidate
public native int hashCode();

意味著所有的類都會有一個 hashCode() 方法，該方法會回傳一個 int 型別的值，由于 hashCode() 方法是一個本地方法（native 關鍵字修飾的方法，用 C/C++ 語言實作，由 Java 呼叫），意味著 Object 類中并沒有給出具體的實作，

具體的實作可以參考 jdk/src/hotspot/share/runtime/synchronizer.cpp（原始碼可以到 GitHub 上 OpenJDK 的倉庫中下載），get_next_hash() 方法會根據 hashCode 的取值來決定采用哪一種哈希值的生成策略，

并且 hashCode() 方法被 @HotSpotIntrinsicCandidate 注解修飾，說明它在 HotSpot 虛擬機中有一套高效的實作，基于 CPU 指令，

那大家有沒有想過這樣一個問題：為什么 Object 類需要一個 hashCode() 方法呢？

在 Java 中，hashCode() 方法的主要作用就是為了配合哈希表使用的，

哈希表（Hash Table），也叫散串列，是一種可以通過關鍵碼值（key-value）直接訪問的資料結構，它最大的特點就是可以快速實作查找、插入和洗掉，其中用到的演算法叫做哈希，就是把任意長度的輸入，變換成固定長度的輸出，該輸出就是哈希值，像 MD5、SHA1 都用的是哈希演算法，

像 Java 中的 HashSet、Hashtable（注意是小寫的 t）、HashMap 都是基于哈希表的具體實作，其中的 HashMap 就是最典型的代表，不僅面試官經常問，作業中的使用頻率也非常的高，

大家想一下，如果沒有哈希表，但又需要這樣一個資料結構，它里面存放的資料是不允許重復的，該怎么辦呢？

要不使用 equals() 方法進行逐個比較？這種方案當然是可行的，但如果資料量特別特別大，采用 equals() 方法進行逐個對比的效率肯定很低很低，最好的解決方案就是哈希表，

拿 HashMap 來說吧，當我們要在它里面添加物件時，先呼叫這個物件的 hashCode() 方法，得到對應的哈希值，然后將哈希值和物件一起放到 HashMap 中，當我們要再添加一個新的物件時：

獲取物件的哈希值；
和之前已經存在的哈希值進行比較，如果不相等，直接存進去；
如果有相等的，再呼叫 equals() 方法進行物件之間的比較，如果相等，不存了；
如果不等，說明哈希沖突了，增加一個鏈表，存放新的物件；
如果鏈表的長度大于 8，轉為紅黑樹來處理，

就這么一套下來，呼叫 equals() 方法的頻率就大大降低了，也就是說，只要哈希演算法足夠的高效，把發生哈希沖突的頻率降到最低，哈希表的效率就特別的高，

來看一下 HashMap 的哈希演算法：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

先呼叫物件的 hashCode() 方法，然后對該值進行右移運算，然后再進行異或運算，

通常來說，String 會用來作為 HashMap 的鍵進行哈希運算，因此我們再來看一下 String 的 hashCode() 方法：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                : StringUTF16.hashCode(value);
    }
    return h;
}
public static int hashCode(byte[] value) {
    int h = 0;
    int length = value.length >> 1;
    for (int i = 0; i < length; i++) {
        h = 31 * h + getChar(value, i);
    }
    return h;
}

可想而知，經過這么一系列復雜的運算，再加上 JDK 作者這種大師級別的設計，哈希沖突的概率我相信已經降到了最低，

當然了，從理論上來說，對于兩個不同物件，它們通過 hashCode() 方法計算后的值可能相同，因此，不能使用 hashCode() 方法來判斷兩個物件是否相等，必須得通過 equals() 方法，

也就是說：

如果兩個物件呼叫 equals() 方法得到的結果為 true，呼叫 hashCode() 方法得到的結果必定相等；
如果兩個物件呼叫 hashCode() 方法得到的結果不相等，呼叫 equals() 方法得到的結果必定為 false；

反之：

如果兩個物件呼叫 equals() 方法得到的結果為 false，呼叫 hashCode() 方法得到的結果不一定不相等；
如果兩個物件呼叫 hashCode() 方法得到的結果相等，呼叫 equals() 方法得到的結果不一定為 true；

來看下面這段代碼，

public class Test {
    public static void main(String[] args) {
        Student s1 = new Student(18, "張三");
        Map<Student, Integer> scores = new HashMap<>();
        scores.put(s1, 98);
        System.out.println(scores.get(new Student(18, "張三")));
    }
}
 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() 方法，默認情況下，hashCode() 方法是一個本地方法，會回傳物件的存盤地址，顯然 put() 中的 s1 和 get() 中的 new Student(18, "張三") 是兩個物件，它們的存盤地址肯定是不同的，

HashMap 的 get() 方法會呼叫 hash(key.hashCode()) 計算物件的哈希值，雖然兩個不同的 hashCode() 結果經過 hash() 方法計算后有可能得到相同的結果，但這種概率微乎其微，所以就導致 scores.get(new Student(18, "張三")) 無法得到預期的值 18，

怎么解決這個問題呢？很簡單，重寫 hashCode() 方法，

 @Override
 public int hashCode() {
     return Objects.hash(age, name);
 }

Objects 類的 hash() 方法可以針對不同數量的引數生成新的 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;
}

代碼似乎很簡單，歸納出的數學公式如下所示（n 為字串長度），

注意：31 是個奇質數，不大不小，一般質數都非常適合哈希計算，偶數相當于移位運算，容易溢位，造成資料資訊丟失，

這就意味著年紀和姓名相同的情況下，會得到相同的哈希值，scores.get(new Student(18, "張三")) 就會回傳 98 的預期值了，

《Java 編程思想》這本圣經中有一段話，對 hashCode() 方法進行了一段描述，

設計 hashCode() 時最重要的因素就是：無論何時，對同一個物件呼叫 hashCode() 都應該生成同樣的值，如果在將一個物件用 put() 方法添加進 HashMap 時產生一個 hashCode() 值，而用 get() 方法取出時卻產生了另外一個 hashCode() 值，那么就無法重新取得該物件了，所以，如果你的 hashCode() 方法依賴于物件中易變的資料，用戶就要當心了，因為此資料發生變化時，hashCode() 就會生成一個不同的哈希值，相當于產生了一個不同的鍵，

也就是說，如果在重寫 hashCode() 和 equals() 方法時，物件中某個欄位容易發生改變，那么最好舍棄這些欄位，以免產生不可預期的結果，

好，有了上面這些內容作為基礎后，我們回頭再來看看本地方法 hashCode() 的 C++ 原始碼，

static inline intptr_t get_next_hash(Thread* current, oop obj) {
  intptr_t value = 0;
  if (hashCode == 0) {
    // This form uses global Park-Miller RNG.
    // On MP system we'll have lots of RW access to a global, so the
    // mechanism induces lots of coherency traffic.
    value = os::random();
  } else if (hashCode == 1) {
    // This variation has the property of being stable (idempotent)
    // between STW operations.  This can be useful in some of the 1-0
    // synchronization schemes.
    intptr_t addr_bits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
  } else if (hashCode == 2) {
    value = 1;            // for sensitivity testing
  } else if (hashCode == 3) {
    value = ++GVars.hc_sequence;
  } else if (hashCode == 4) {
    value = cast_from_oop<intptr_t>(obj);
  } else {
    // Marsaglia's xor-shift scheme with thread-specific state
    // This is probably the best overall implementation -- we'll
    // likely make this the default in future releases.
    unsigned t = current->_hashStateX;
    t ^= (t << 11);
    current->_hashStateX = current->_hashStateY;
    current->_hashStateY = current->_hashStateZ;
    current->_hashStateZ = current->_hashStateW;
    unsigned v = current->_hashStateW;
    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    current->_hashStateW = v;
    value = v;
  }

  value &= markWord::hash_mask;
  if (value == 0) value = 0xBAD;
  assert(value != markWord::no_hash, "invariant");
  return value;
}

如果沒有 C++ 基礎的話，不用細致去看每一行代碼，我們只通過表面去了解一下 get_next_hash() 這個方法就行，其中的 hashCode 變數是 JVM 啟動時的一個全域引數，可以通過它來切換哈希值的生成策略，

hashCode==0，呼叫作業系統 OS 的 random() 方法回傳亂數，
hashCode == 1，在 STW（stop-the-world）操作中，這種策略通常用于同步方案中，利用物件地址進行計算，使用不經常更新的亂數（GVars.stw_random）參與其中，
hashCode == 2，使用回傳 1，用于某些情況下的測驗，
hashCode == 3，從 0 開始計算哈希值，不是執行緒安全的，多個執行緒可能會得到相同的哈希值，
hashCode == 4，與創建物件的記憶體位置有關，原樣輸出，
hashCode == 5，默認值，支持多執行緒，使用了 Marsaglia 的 xor-shift 演算法產生偽亂數，所謂的 xor-shift 演算法，簡單來說，看起來就是一個移位暫存器，每次移入的位由暫存器中若干位取異或生成，所謂的偽亂數，不是完全隨機的，但是真隨機生成比較困難，所以只要能通過一定的亂數統計檢測，就可以當作真亂數來使用，

至于更深層次的挖掘，涉及到數學知識和物理知識，就不展開了，畢竟菜是原罪，

我最近花了近一周的時間整理了一份純 Java 版的刷題筆記，一共 300 道題解！

圖文并茂，截圖如下，不只是干巴巴的題解代碼，很多題都給出了多種解題思路，真的會提高大家刷題的幸福指數~

刷完 300 道 LeetCode 題后，我膨脹到要飄起來了！純正 Java 版

我是沉默王二，希望大家都能把編程學好，可以微信搜一搜「 沉默王二 」關注我，回復【面試】有我為大家精心準備的一份面試資料~如果內容有幫助的話，歡迎一鍵三連！

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/273770.html

標籤：其他

上一篇：【C語言從青銅到王者】第零篇·與C語言來個約會

下一篇：藍橋杯刷題之分享方法---前綴差分