哈希值爲負值

非常多標題：我哈希了一堆名稱（10000-ish），有些輸出爲負值。（表格大小是20011）。哈希值爲負值

有問題的哈希函數是：

public static long hash2 (String key){ 
    int hashVal = 0; 
    for(int i = 0; i < key.length(); i++) 
     hashVal = (37 * hashVal) + key.charAt(i); 
    return hashVal % 20011; 
}

我周圍挖，我想我要做的是與「環繞」。但我不知道如何去做。

來源

2017-05-09 Alex M

如果您不確定它是否「環繞」，請使用「Math.toIntExact」。如果是這種情況，這應該會引發異常。另外，考慮到你的方法返回類型是'long'，爲什麼不聲明'hashVal'長？ –

當你定義'hash2（）'返回'long'時，爲什麼你要用'int'來表示'hashVal'？同樣使用「長」。 –

這是一個明確的案例Integer Overflow。正如你在字符串可能有10000字符的問題中提到的那樣，那麼hashValue肯定會溢出，因爲需要將值存儲在37^10000左右。即使這將在長度爲20的字符串中失敗。

在數論，

(A+B)%M = (A%M + B%M) % M; 
(A*B)%M = (A%M * B%M) % M;

您應該應用模運算裏面的for循環。但是，如果最後執行模操作或執行for循環，兩者將給出相同的答案如果溢出未發生。因此

因此做出改變，

public static long hash2 (String key){ 
    int hashVal = 0; 
    for(int i = 0; i < key.length(); i++) 
    { 
     hashVal = (37 * hashVal) + key.charAt(i); 
     hashVal%=20011; 
    } 
    return hashVal; 
}

來源

2017-05-09 12:24:38

hashVal是一個整數。這很可能是你的散列函數導致整數溢出。

您可以使用Math.abs()輕鬆解決此問題，以確保hashVal是一個正數。例如

hashVal = hashVal == Integer.MIN_VALUE ? 0 : Math.abs(hashVal); 
return hashVal % 20011;

國防部%是確保計算的最終索引是表的範圍內（即，如果它是> = 20011，它採用分割爲你說的其餘「環繞」）。

來源

2017-05-09 12:25:16

請注意'Math.abs（Integer.MIN_VALUE）'返回'Integer.MIN_VALUE'。 –

雖然我不確定它是如何影響分佈的，但可以修改爲'Math.abs（hashVal％20011）'。 –

@StefanWarminski更新以反映這種特殊情況。 –

哈希值爲負值

回答

相關問題