Long的哈希值計算理念和哈希沖突的情況舉例

 一、背景

《阿裡巴巴 Java開發手冊》的作者孤盡大佬舉辦的第一期 DIY 班，由最初的幾百人，目前僅有60多人堅持到現在。

其一，Deeply Inspire Yourself           深度激發自己

其二，Do It Yourself           實踐出真知

其中第 20 期的題目是：自主選擇一個類，說明它hashCode方法的設計理念和代碼核心邏輯。

本人選取 Long這個類進行分析。

二、分析

2.1 自主選擇一個類，說明它hashCode方法的設計理念和代碼核心邏輯。

java.lang.Long#hashCode(long)

/**
* Returns a hash code for this {@code Long}. The result is
* the exclusive OR of the two halves of the primitive
* {@code long} value held by this {@code Long}
* object. That is, the hashcode is the value of the expression:
*
* <blockquote>
* {@code (int)(this.longValue()^(this.longValue()>>>32))}
* </blockquote>
*
* @return a hash code value for this object.
*/
@Override
public int hashCode() {
return Long.hashCode(value);
}      

設計理念：

long 64 位 int 34 位，而 hash值是 int 類型，是以需要将 64位轉化為小于等于32位。

讓高位和低位都能夠參與到 hash 運算中，讓結果離散。

核心邏輯：long 的 hash 值是通過将前半段和後半段異或得到的。

public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}      

2.2 如何構造hash沖突

由于 long 的hash 值是将 64 位運算得到32位，即講一個大範圍映射到小範圍，是以必然會有 hash沖突。

根據 Long 的 hash函數映射規則，可以看出最簡單的構造方式就是根據 hash 規則，将低位和高位互換或者 0 和1 互換，運算結果一緻。

// 【1】高低位互換

long value = Long.MAX_VALUE - 1024L;
System.out.println(Long.toBinaryString(value));
// 取高32位
long high32 = value >>> 32;
// 取高32
long low32 = value << 32;
// 高 32 和 低32 互換
long newValue = high32 | low32;
// 新的hash 值 和原值相同
System.out.println(newValue);
Assert.assertEquals(Long.hashCode(value), Long.hashCode(newValue));      

// 【2】0 和1 互換

// 0 和1 互換
newValue = (~high32) & (~low32);
System.out.println(newValue);
Assert.assertEquals(Long.hashCode(value), Long.hashCode(newValue));      

通過hash 值可以快速判斷兩個值是否不同，然後再通過 equals 函數判斷是否相同。

java.lang.Long#equals

public boolean equals(Object obj) {
  if (obj instanceof Long) {
    return value == ((Long)obj).longValue();
   }
  return false;
}      

而且重寫equals時要修改 hashcode函數確定 相等的兩個對象的hashcode 一定相同。

隻有這樣才能保證優先通過hashcode判斷有可能相（hash值相同）等的情況下再調用equals判斷是否相等。

hash函數的本質是将資料編碼成數字，而 java 中的 hashcode 傳回值是 int 類型，如果hash函數寫的不好或者某種那類型的數量大于整數，必然可能産生沖突（不同的對象相同的哈希值）。

通常讓每一位都參與到運算中等手段設計更優秀的hash函數，盡可能避免hash沖突。

沖突之後通常需要通過 再散列，拉鍊，公共溢出去等方式來解決。

同樣地，大家也可以選取其他類，如 String, Integer 等，去看他們的hash值的計算方式，研究如何構造hash沖突。

三、總結

很多人開發的時候很少去看源碼，導緻對很多知識點一知半解。

通過DIY班孤盡大佬的一些問題，讓我也養成了讀源碼得習慣。

希望大家也可以帶着問題去學習，平時開發時偶爾去源碼裡看一下。