在Java中，重寫hashCode()方法時常常會使用31作為乘數，這是因為31具有一些獨特的數學性質，使其成為一個優秀的選擇。以下是幾個原因：

1. 奇質數的特性

31是一個奇數和質數，這意味著它能有效地減少哈希沖突的概率。使用質數作為乘數可以幫助分散哈希值，從而提高哈希表的性能。

2. 位運算效率

在計算機中，乘以31可以通過位運算來優化：

• x * 31可以用 (x << 5) - x 來替代，其中<<表示左移操作。這種方式比直接乘法更加高效，因為位移操作通常比乘法快得多。

3. 良好的分布性

經過實踐證明，31可以提供良好的哈希值分布，適用于字符串等對象的哈希計算。它能夠有效地將不同的輸入映射到不同的哈希值上，減少了碰撞的可能性。

示例代碼

下面是一個簡單的示例，展示如何在hashCode()方法中使用31：

@Override
public int hashCode() {
    int result = 17; // 一個非零的初始值
    result = 31 * result + (field1 != null ? field1.hashCode() : 0);
    result = 31 * result + (field2 != null ? field2.hashCode() : 0);
    return result;
}

在這個例子中，field1和field2的哈希值被乘以31并累加到結果中，從而生成一個組合的哈希值。

總結

使用31作為乘數在hashCode()重寫中是為了提高哈希函數的性能和分布性。它結合了數學上的優雅與計算上的高效，是Java開發者的常見做法。

質數提高哈希分散性

在哈希函數中，使用質數（如 31、37、53 等）進行乘法運算是一個常見的實踐，這樣做可以提高哈希值的分散性，減少哈希沖突。下面是對這一現象的詳細解釋：

1. 哈希沖突的概念

哈希沖突發生在不同的輸入數據被映射到同一個哈希值時。這種情況會導致哈希表性能下降，因為在查找、插入或刪除操作時需要處理這些沖突。

2. 為什么使用質數？

a. 數學性質

• 質數的特性：質數是只能被 1 和它自身整除的自然數。這個特性使得它們在數學上具有良好的分布性。
• 避免重復模式：使用質數可以有效地打破輸入數據之間的規律性和重復模式，從而增加哈希值的隨機性。例如，如果我們總是用偶數來計算哈希值，可能會導致某些輸入數據產生相似的哈希結果，而質數的使用可以防止這種情況。

b. 增強混合效果

• 乘法的影響：當我們將當前哈希值與質數相乘并加上新的元素的哈希值時，質數有助于在生成的新哈希值中引入更多的信息。這樣可以有效地“混合”之前的哈希值和新添加的值。

• 例如：

  result = prime * result + newValueHash;
  

  在這個公式中，result 是之前計算得到的哈希值，newValueHash 是新加入元素的哈希值。通過乘以質數 prime，我們確保了即使 newValueHash 的值相似，它們也不會簡單地疊加在一起，從而減少沖突的概率。

3. 位運算優化

• 計算效率：在 Java 中，選擇 31 作為質數的一個原因是，它可以通過位移運算進行優化。具體來說，乘以 31 可以通過以下方式實現：

  result = (result << 5) - result; // 相當于 result * 31
  

  這里的 << 5 表示左移 5 位，相當于乘以 32，然后再減去原值 result，達到乘以 31 的效果。這樣的操作比直接乘法更高效。

4. 實際應用中的效果

通過使用質數來計算哈希值，可以顯著提高哈希函數的分散性，使得不同的輸入能夠產生更加均勻的哈希分布。這對于實現高效的哈希表（如 HashMap、HashSet）至關重要，因為它能減少沖突、提高查找速度，并優化內存使用。

總結

• 使用質數（如 31）在哈希函數中可以提高哈希值的分散性，減少哈希沖突。
• 質數的數學特性和乘法帶來的混合效果有助于生成更隨機的哈希值。
• 通過位運算優化乘法運算，可以提高計算效率。

因此，在設計哈希函數時，使用質數是一種有效的策略，以確保哈希表結構的性能和效率。