###hash 的定義
Hash,一般翻譯做“散列”,也有直接音譯為“哈希”的,就是把任意長度的輸入(又叫做預映射, pre-image),通過雜湊演算法,變換成固定長度的輸出,該輸出就是散列值。這種轉換是一種壓縮映射,也就是,散列值的空間通常遠小于輸入的空間,不同的輸入可能會散列成相同的輸出,是以不可能從散列值來唯一的确定輸入值。簡單的說就是一種将任意長度的消息壓縮到某一固定長度的消息摘要的函數。
Java 中 hash 值的含義
- hash 值主要是用來在散列存儲結構中确定對象的存儲位址的,提高對象的查詢效率,如HashMap、HashTable等;
- 如果兩個對象相同,那麼這兩個對象的 hash 值一定相等;
- 如果要重寫對象的 equals 方法,那麼盡量重寫對象的 hashCode 方法;
- 兩個對象的 hash 值相等,并不一定表示兩個對象相同。
String中的 hashCode
在了解了 hash 值的含義後,在進行 hash 計算的時候,我們希望盡量減小生産重複 hash 值的機率,使得資料更離散一些,如果重複 hash 值太多,散列存儲結構中同一 hash 值映射的對象也會很多,導緻降低查詢效率。而且 equals() 計算的準确性也會降低。
接下來分析 String 類的 hashCode() 方法,代碼如下:
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;
}
在介紹 hashCode() 之前,我們先了解一下該方法中使用到的屬性。
value:是一個 private final 修飾的 char 數組,String 類是通過該數組來存在字元串的。
private final char value[];
hash:是一個 private 修飾的 int 變量,用來存放 String 對象的 hashCode。
private int hash;
接下來分析 hashCode() 的實作邏輯如下:
###判定條件分析
如果 hash 值不等于 0,且 value.length 大于 0,則進行 hash 值計算;這裡包含兩個條件:
第一個判定條件:
h == 0
為什麼
h == 0
時進行 hashCode()計算呢?h 是一個 int 類型的值,預設值為 0,是以 0 可以表示可能未執行過 hash 計算,但不能表示一定未執行過 hash 計算,原因是我們現在還不确定 hash 計算後是否會産生 0 值;
執行 hash 計算後,會不會産生值為 0 的 hash呢?根據 hash 的計算邏輯,當
val[0] = 0
時,根據公式
h = 31 * h + val[i];
進行計算, h 的值等于 0。
val[0] = 0
怎麼解釋呢?檢視 ASCII 表發現, null 的 ASCII 值為 0 。顯然 val[0]中永遠不可能存放 null,是以 hash 計算後不會産生 0 值,
h == 0
可以作為是否進行過 hash 計算的判定條件。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIn5GcusmUyI0V2Z2Lc12bj5ic1dWbp5Savw1LcpDc0RHaiojIsJye.png)
另一個判定條件:
value.length > 0
也就是說,如果字元串的長度為 0 ,不進行 hash 計算。
###計算公式分析
接下來我們來分析 hash 計算公式:
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
我們模拟一下 hash 的計算步驟:
String name = "liu";
value = {'l', 'i', 'u'};
hash = 0;
value.length = 3;
//執行邏輯:
val = value;
val[0] = "l";
val[1] = "i";
val[2] = "u";
h = 31 * 0 + l = l;
h = 31 * (31 * 0 + l) + i = 31 * l + i;
h = 31 * (31 * (31 * 0 + l) + i) + u = 31 * 31 * l + 31 * i + u;
推導出的數學公式如下:
val[0]*31^(n-1) + val[1]*31^(n-2) + ... + val[n-1]
為什麼是 31 呢,為什麼不是 32 呢?因為 31 是一個素數。什麼是素數,為什麼選擇素數?
素數又稱質數:指在一個大于1的自然數中,除了1和此整數自身外,沒法被其他自然數整除的數。
根據素數的特性,與素數相乘得到的結果比其他方式更容易産生唯一性,也就是說産生 hash 值重複的機率比較小。
素數有很多,為什麼是 31 呢?
31 的二進制為: 11111,占用 5 個二進制位,在進行乘法運算時,可以轉換為
(x << 5) - x
。
這裡需要考慮乘法的因素,在 Java 中如果相乘的數字太大會導緻記憶體溢出問題,進而導緻資料丢失。
大數相乘會造成記憶體溢出,17 也是素數,那為什麼不是 17 呢?
我也蒙圈了。
關于 31 大緻總結一下:
- 31 是一個素數,與素數相乘得到的結果比其他方式更容易産生唯一性。
- Java 中如果相乘的數字太大會導緻記憶體溢出問題,進而導緻資料丢失。
基于以上兩方面的考慮這個因子的值。
###參考資料
- Why does Java’s hashCode() in String use 31 as a multiplier
- 為什麼在定義hashcode時要使用31這個數呢?
- 關于hashcode 裡面 使用31 系數的問題