日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
補(bǔ)補(bǔ)HashCode，畢竟菜乃原醉

大家好，我是沉默王二。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：空間域名、網(wǎng)絡(luò)空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、孟連網(wǎng)站維護(hù)、網(wǎng)站推廣。

假期結(jié)束了，需要快速切換到工作的狀態(tài)投入到新的一天當(dāng)中。放假的時(shí)候痛快地玩耍，上班的時(shí)候積極的工作，這應(yīng)該是我們大多數(shù)“現(xiàn)代人”該有的生活狀態(tài)。

我之所以費(fèi)盡心思鋪墊了前面這段話，就是想告訴大家，技術(shù)文雖遲但到，來(lái)吧，學(xué)起來(lái)~

今天我們來(lái)談?wù)?Java 中的 hashCode() 方法。眾所周知，Java 是一門(mén)面向?qū)ο蟮木幊陶Z(yǔ)言，所有的類都會(huì)默認(rèn)繼承自 Object 類，而 Object 的中文意思就是“對(duì)象”。

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

 
 
 
 
    
  
  
  
  
  1. @HotSpotIntrinsicCandidate
    2. 
  
  
  
  
  2. public native int hashCode();
    3.

意味著所有的類都會(huì)有一個(gè) hashCode() 方法，該方法會(huì)返回一個(gè) int 類型的值。由于 hashCode() 方法是一個(gè)本地方法(native 關(guān)鍵字修飾的方法，用 C/C++ 語(yǔ)言實(shí)現(xiàn)，由 Java 調(diào)用)，意味著 Object 類中并沒(méi)有給出具體的實(shí)現(xiàn)。

具體的實(shí)現(xiàn)可以參考 jdk/src/hotspot/share/runtime/synchronizer.cpp(源碼可以到 GitHub 上 OpenJDK 的倉(cāng)庫(kù)中下載)。get_next_hash() 方法會(huì)根據(jù) hashCode 的取值來(lái)決定采用哪一種哈希值的生成策略。

并且 hashCode() 方法被 @HotSpotIntrinsicCandidate 注解修飾，說(shuō)明它在 HotSpot 虛擬機(jī)中有一套高效的實(shí)現(xiàn)，基于 CPU 指令。

那大家有沒(méi)有想過(guò)這樣一個(gè)問(wèn)題：為什么 Object 類需要一個(gè) hashCode() 方法呢?

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

哈希表(Hash Table)，也叫散列表，是一種可以通過(guò)關(guān)鍵碼值(key-value)直接訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，它最大的特點(diǎn)就是可以快速實(shí)現(xiàn)查找、插入和刪除。其中用到的算法叫做哈希，就是把任意長(zhǎng)度的輸入，變換成固定長(zhǎng)度的輸出，該輸出就是哈希值。像 MD5、SHA1 都用的是哈希算法。

像 Java 中的 HashSet、Hashtable(注意是小寫(xiě)的 t)、HashMap 都是基于哈希表的具體實(shí)現(xiàn)。其中的 HashMap 就是最典型的代表，不僅面試官經(jīng)常問(wèn)，工作中的使用頻率也非常的高。

大家想一下，如果沒(méi)有哈希表，但又需要這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)，它里面存放的數(shù)據(jù)是不允許重復(fù)的，該怎么辦呢?

要不使用 equals() 方法進(jìn)行逐個(gè)比較?這種方案當(dāng)然是可行的。但如果數(shù)據(jù)量特別特別大，采用 equals() 方法進(jìn)行逐個(gè)對(duì)比的效率肯定很低很低，最好的解決方案就是哈希表。

拿 HashMap 來(lái)說(shuō)吧。當(dāng)我們要在它里面添加對(duì)象時(shí)，先調(diào)用這個(gè)對(duì)象的 hashCode() 方法，得到對(duì)應(yīng)的哈希值，然后將哈希值和對(duì)象一起放到 HashMap 中。當(dāng)我們要再添加一個(gè)新的對(duì)象時(shí)：

  • 獲取對(duì)象的哈希值;
  • 和之前已經(jīng)存在的哈希值進(jìn)行比較，如果不相等，直接存進(jìn)去;
  • 如果有相等的，再調(diào)用 equals() 方法進(jìn)行對(duì)象之間的比較，如果相等，不存了;
  • 如果不等，說(shuō)明哈希沖突了，增加一個(gè)鏈表，存放新的對(duì)象;
  • 如果鏈表的長(zhǎng)度大于 8，轉(zhuǎn)為紅黑樹(shù)來(lái)處理。

就這么一套下來(lái)，調(diào)用 equals() 方法的頻率就大大降低了。也就是說(shuō)，只要哈希算法足夠的高效，把發(fā)生哈希沖突的頻率降到最低，哈希表的效率就特別的高。

來(lái)看一下 HashMap 的哈希算法：

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

先調(diào)用對(duì)象的 hashCode() 方法，然后對(duì)該值進(jìn)行右移運(yùn)算，然后再進(jìn)行異或運(yùn)算。

通常來(lái)說(shuō)，String 會(huì)用來(lái)作為 HashMap 的鍵進(jìn)行哈希運(yùn)算，因此我們?cè)賮?lái)看一下 String 的 hashCode() 方法：

 
 
 
 
    
  
  
  
  
  1. public int hashCode() {
    2. 
  
  
  
  
  2.     int h = hash;
    3. 
  
  
  
  
  3.     if (h == 0 && value.length > 0) {
    4. 
  
  
  
  
  4.         hash = h = isLatin1() ? StringLatin1.hashCode(value)
    5. 
  
  
  
  
  5.                 : StringUTF16.hashCode(value);
    6. 
  
  
  
  
  6.     }
    7. 
  
  
  
  
  7.     return h;
    8. 
  
  
  
  
  8. }
    9. 
  
  
  
  
  9. public static int hashCode(byte[] value) {
    10. 
  
  
  
  
  10.     int h = 0;
    11. 
  
  
  
  
  11.     int length = value.length >> 1;
    12. 
  
  
  
  
  12.     for (int i = 0; i < length; i++) {
    13. 
  
  
  
  
  13.         h = 31 * h + getChar(value, i);
    14. 
  
  
  
  
  14.     }
    15. 
  
  
  
  
  15.     return h;
    16. 
  
  
  
  
  16. }
    17.

可想而知，經(jīng)過(guò)這么一系列復(fù)雜的運(yùn)算，再加上 JDK 作者這種大師級(jí)別的設(shè)計(jì)，哈希沖突的概率我相信已經(jīng)降到了最低。

當(dāng)然了，從理論上來(lái)說(shuō)，對(duì)于兩個(gè)不同對(duì)象，它們通過(guò) hashCode() 方法計(jì)算后的值可能相同。因此，不能使用 hashCode() 方法來(lái)判斷兩個(gè)對(duì)象是否相等，必須得通過(guò) equals() 方法。

也就是說(shuō)：

  • 如果兩個(gè)對(duì)象調(diào)用 equals() 方法得到的結(jié)果為 true，調(diào)用 hashCode() 方法得到的結(jié)果必定相等;
  • 如果兩個(gè)對(duì)象調(diào)用 hashCode() 方法得到的結(jié)果不相等，調(diào)用 equals() 方法得到的結(jié)果必定為 false;

反之：

  • 如果兩個(gè)對(duì)象調(diào)用 equals() 方法得到的結(jié)果為 false，調(diào)用 hashCode() 方法得到的結(jié)果不一定不相等;
  • 如果兩個(gè)對(duì)象調(diào)用 hashCode() 方法得到的結(jié)果相等，調(diào)用 equals() 方法得到的結(jié)果不一定為 true;

來(lái)看下面這段代碼。

 
 
 
 
    
  
  
  
  
  1. public class Test {
    2. 
  
  
  
  
  2.     public static void main(String[] args) {
    3. 
  
  
  
  
  3.         Student s1 = new Student(18, "張三");
    4. 
  
  
  
  
  4.         Map scores = new HashMap<>();
    5. 
  
  
  
  
  5.         scores.put(s1, 98);
    6. 
  
  
  
  
  6.         System.out.println(scores.get(new Student(18, "張三")));
    7. 
  
  
  
  
  7.     }
    8. 
  
  
  
  
  8. }
    9. 
  
  
  
  
  9.  class Student {
    10. 
  
  
  
  
  10.     private int age;
    11. 
  
  
  
  
  11.     private String name;
    12. 
  
  
  
  
  12. 
  
  
  
  
  13.      public Student(int age, String name) {
    14. 
  
  
  
  
  14.          this.age = age;
    15. 
  
  
  
  
  15.          this.name = name;
    16. 
  
  
  
  
  16.      }
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.      @Override
    19. 
  
  
  
  
  19.      public boolean equals(Object o) {
    20. 
  
  
  
  
  20.          Student student = (Student) o;
    21. 
  
  
  
  
  21.          return age == student.age &&
    22. 
  
  
  
  
  22.                  Objects.equals(name, student.name);
    23. 
  
  
  
  
  23.      }
    24. 
  
  
  
  
  24.  }
    25.

我們重寫(xiě)了 Student 類的 equals() 方法，如果兩個(gè)學(xué)生的年紀(jì)和姓名相同，我們就認(rèn)為是同一個(gè)學(xué)生，雖然很離譜，但我們就是這么草率。

在 main() 方法中，18 歲的張三考試得了 98 分，很不錯(cuò)的成績(jī)，我們把張三和成績(jī)放到了 HashMap 中，然后準(zhǔn)備輸出張三的成績(jī)：

 
 
 
 
    
  
  
  
  
  1. null
    2.

很不巧，結(jié)果為 null，而不是預(yù)期當(dāng)中的 98。這是為什么呢?

原因就在于重寫(xiě) equals() 方法的時(shí)候沒(méi)有重寫(xiě) hashCode() 方法。默認(rèn)情況下，hashCode() 方法是一個(gè)本地方法，會(huì)返回對(duì)象的存儲(chǔ)地址，顯然 put() 中的 s1 和 get() 中的 new Student(18, "張三") 是兩個(gè)對(duì)象，它們的存儲(chǔ)地址肯定是不同的。

HashMap 的 get() 方法會(huì)調(diào)用 hash(key.hashCode()) 計(jì)算對(duì)象的哈希值，雖然兩個(gè)不同的 hashCode() 結(jié)果經(jīng)過(guò) hash() 方法計(jì)算后有可能得到相同的結(jié)果，但這種概率微乎其微，所以就導(dǎo)致 scores.get(new Student(18, "張三")) 無(wú)法得到預(yù)期的值 18。

怎么解決這個(gè)問(wèn)題呢?很簡(jiǎn)單，重寫(xiě) hashCode() 方法。

 
 
 
 
    
  
  
  
  
  1. @Override
    2. 
  
  
  
  
  2. public int hashCode() {
    3. 
  
  
  
  
  3.     return Objects.hash(age, name);
    4. 
  
  
  
  
  4. }
    5.

Objects 類的 hash() 方法可以針對(duì)不同數(shù)量的參數(shù)生成新的 hashCode() 值。

 
 
 
 
    
  
  
  
  
  1. public static int hashCode(Object a[]) {
    2. 
  
  
  
  
  2.  if (a == null)
    3. 
  
  
  
  
  3.      return 0;
    4. 
  
  
  
  
  4. 
  
  
  
  
  5.  int result = 1;
    6. 
  
  
  
  
  6. 
  
  
  
  
  7.  for (Object element : a)
    8. 
  
  
  
  
  8.      result = 31 * result + (element == null ? 0 : element.hashCode());
    9. 
  
  
  
  
  9. 
  
  
  
  
  10.  return result;
    11. 
  
  
  
  
  11. }
    12.

代碼似乎很簡(jiǎn)單，歸納出的數(shù)學(xué)公式如下所示(n 為字符串長(zhǎng)度)。

注意：31 是個(gè)奇質(zhì)數(shù)，不大不小，一般質(zhì)數(shù)都非常適合哈希計(jì)算，偶數(shù)相當(dāng)于移位運(yùn)算，容易溢出，造成數(shù)據(jù)信息丟失。

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

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

設(shè)計(jì) hashCode() 時(shí)最重要的因素就是：無(wú)論何時(shí)，對(duì)同一個(gè)對(duì)象調(diào)用 hashCode() 都應(yīng)該生成同樣的值。如果在將一個(gè)對(duì)象用 put() 方法添加進(jìn) HashMap 時(shí)產(chǎn)生一個(gè) hashCode() 值，而用 get() 方法取出時(shí)卻產(chǎn)生了另外一個(gè) hashCode() 值，那么就無(wú)法重新取得該對(duì)象了。所以，如果你的 hashCode() 方法依賴于對(duì)象中易變的數(shù)據(jù)，用戶就要當(dāng)心了，因?yàn)榇藬?shù)據(jù)發(fā)生變化時(shí)，hashCode() 就會(huì)生成一個(gè)不同的哈希值，相當(dāng)于產(chǎn)生了一個(gè)不同的鍵。

也就是說(shuō)，如果在重寫(xiě) hashCode() 和 equals() 方法時(shí)，對(duì)象中某個(gè)字段容易發(fā)生改變，那么最好舍棄這些字段，以免產(chǎn)生不可預(yù)期的結(jié)果。

好。有了上面這些內(nèi)容作為基礎(chǔ)后，我們回頭再來(lái)看看本地方法 hashCode() 的 C++ 源碼。

 
 
 
 
    
  
  
  
  
  1. static inline intptr_t get_next_hash(Thread* current, oop obj) {
    2. 
  
  
  
  
  2.   intptr_t value = 0;
    3. 
  
  
  
  
  3.   if (hashCode == 0) {
    4. 
  
  
  
  
  4.     // This form uses global Park-Miller RNG.
    5. 
  
  
  
  
  5.     // On MP system we'll have lots of RW access to a global, so the
    6. 
  
  
  
  
  6.     // mechanism induces lots of coherency traffic.
    7. 
  
  
  
  
  7.     value = os::random();
    8. 
  
  
  
  
  8.   } else if (hashCode == 1) {
    9. 
  
  
  
  
  9.     // This variation has the property of being stable (idempotent)
    10. 
  
  
  
  
  10.     // between STW operations.  This can be useful in some of the 1-0
    11. 
  
  
  
  
  11.     // synchronization schemes.
    12. 
  
  
  
  
  12.     intptr_t addr_bits = cast_from_oop(obj) >> 3;
    13. 
  
  
  
  
  13.     value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
    14. 
  
  
  
  
  14.   } else if (hashCode == 2) {
    15. 
  
  
  
  
  15.     value = 1;            // for sensitivity testing
    16. 
  
  
  
  
  16.   } else if (hashCode == 3) {
    17. 
  
  
  
  
  17.     value = ++GVars.hc_sequence;
    18. 
  
  
  
  
  18.   } else if (hashCode == 4) {
    19. 
  
  
  
  
  19.     value = cast_from_oop(obj);
    20. 
  
  
  
  
  20.   } else {
    21. 
  
  
  
  
  21.     // Marsaglia's xor-shift scheme with thread-specific state
    22. 
  
  
  
  
  22.     // This is probably the best overall implementation -- we'll
    23. 
  
  
  
  
  23.     // likely make this the default in future releases.
    24. 
  
  
  
  
  24.     unsigned t = current->_hashStateX;
    25. 
  
  
  
  
  25.     t ^= (t << 11);
    26. 
  
  
  
  
  26.     current->_hashStateX = current->_hashStateY;
    27. 
  
  
  
  
  27.     current->_hashStateY = current->_hashStateZ;
    28. 
  
  
  
  
  28.     current->_hashStateZ = current->_hashStateW;
    29. 
  
  
  
  
  29.     unsigned v = current->_hashStateW;
    30. 
  
  
  
  
  30.     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    31. 
  
  
  
  
  31.     current->_hashStateW = v;
    32. 
  
  
  
  
  32.     value = v;
    33. 
  
  
  
  
  33.   }
    34. 
  
  
  
  
  34. 
  
  
  
  
  35.   value &= markWord::hash_mask;
    36. 
  
  
  
  
  36.   if (value == 0) value = 0xBAD;
    37. 
  
  
  
  
  37.   assert(value != markWord::no_hash, "invariant");
    38. 
  
  
  
  
  38.   return value;
    39. 
  
  
  
  
  39. }
    40.

如果沒(méi)有 C++ 基礎(chǔ)的話，不用細(xì)致去看每一行代碼，我們只通過(guò)表面去了解一下 get_next_hash() 這個(gè)方法就行。其中的 hashCode 變量是 JVM 啟動(dòng)時(shí)的一個(gè)全局參數(shù)，可以通過(guò)它來(lái)切換哈希值的生成策略。

  • hashCode==0，調(diào)用操作系統(tǒng) OS 的 random() 方法返回隨機(jī)數(shù)。
  • hashCode == 1，在 STW(stop-the-world)操作中，這種策略通常用于同步方案中。利用對(duì)象地址進(jìn)行計(jì)算，使用不經(jīng)常更新的隨機(jī)數(shù)(GVars.stw_random)參與其中。
  • hashCode == 2，使用返回 1，用于某些情況下的測(cè)試。
  • hashCode == 3，從 0 開(kāi)始計(jì)算哈希值，不是線程安全的，多個(gè)線程可能會(huì)得到相同的哈希值。
  • hashCode == 4，與創(chuàng)建對(duì)象的內(nèi)存位置有關(guān)，原樣輸出。
  • hashCode == 5，默認(rèn)值，支持多線程，使用了 Marsaglia 的 xor-shift 算法產(chǎn)生偽隨機(jī)數(shù)。所謂的 xor-shift 算法，簡(jiǎn)單來(lái)說(shuō)，看起來(lái)就是一個(gè)移位寄存器，每次移入的位由寄存器中若干位取異或生成。所謂的偽隨機(jī)數(shù)，不是完全隨機(jī)的，但是真隨機(jī)生成比較困難，所以只要能通過(guò)一定的隨機(jī)數(shù)統(tǒng)計(jì)檢測(cè)，就可以當(dāng)作真隨機(jī)數(shù)來(lái)使用。

至于更深層次的挖掘，涉及到數(shù)學(xué)知識(shí)和物理知識(shí)，就不展開(kāi)了。畢竟菜是原罪。

參考資料：

https://zhuanlan.zhihu.com/p/121555725 https://www.cnblogs.com/dolphin0520/p/3681042.html


文章題目：補(bǔ)補(bǔ)HashCode，畢竟菜乃原醉
當(dāng)前URL：http://www.5511xx.com/article/dpssdci.html