Hash函數溢出

在我班上的數據結構，我們正在學習不同的散列函數，但是這一次我特別不明白，爲什麼在最後三行代碼的他們是否HashVal < 0，因爲自HashVal是提醒對於tableSize的劃分，它不應該小於零。請我只想了解這最後一部分。先謝謝你。Hash函數溢出

public static int hash(String key, int tableSize) 

{ 

int hashVal = 0; 

for(int i = 0; i < key.length(); i++) 

    hashVal = 37 * hashVal + key.charAt(i); 

hashVal %= tableSize; 

if(hashVal < 0) //overflow case 

    hashVal += tableSize; 

return hashVal;

}

來源

2016-03-06 jpro

hashVal是INT，而且可能溢出成爲負數。 – SCaffrey

hashVal是INT，並且它具有的最大尺寸。如果字符串的長度足夠長，hashVal因爲你已經通過37多次乘它，它溢出變得非常大。當溢出，它可能會成爲負數，所以你需要檢查的結果，如果hashVal爲負。

也有解決這個已知的方式。更改

for(int i = 0; i < key.length(); i++) 
    hashVal = 37 * hashVal + key.charAt(i); 
    hashVal %= tableSize;

到

for(int i = 0; i < key.length(); i++) { 
    hashVal = 37 * hashVal + key.charAt(i); 
    hashVal %= tableSize; 
}

來源

2016-03-06 01:16:14 SCaffrey

非常感謝您的回答！而用你改變for循環的方式不需要檢查溢出權嗎？ – jpro

使用long **和** for循環可能會有所幫助。我猜如果tableSize足夠大，模塊結果* 37可能仍會溢出。順便說一句，@Artem的回答描述了整數溢出的原因。 – SCaffrey

int類型的Java簽訂32-bit data type。因此，它能夠存儲的最大值是2^31-1這是在Integer類MAX_VALUE恆定。基於（左邊的符號位），一旦數字大於MAX_VALUE，它將基於該表示形式變爲負值。

來源

2016-03-06 01:21:59 Artem

非常感謝你！它真的幫了大忙！ – jpro

回答

相關問題