多項式哈希碼導致負數？

Question

對於某些情況下的大j函數，下面的哈希函數返回負值。

int hashing::hash(string a) 
{ 
    int i = 0; 
    int hvalue = 0; 
    int h =0 ; 
    while(a[i]!=NULL) 
    { 
     hvalue = hvalue + (int(a[i]))*pow(31,i); 
     i++; 
    } 
    h = hvalue%j; 
    return h; 
} 

這怎麼可能？我該如何糾正它？

在上面的代碼中，j是一個使用文件大小計算的質數。在字符串形式爲「s」的某些特定情況下出現負值。

我在做什麼錯？我該如何解決它？

Answer 1

請記住，int有一個有限的範圍，並且（通常）是一個有符號的值。這意味着如果您超過int的最大可能值，它將環繞並可能變爲負值。

有幾種方法可以解決這個問題。首先，您可以切換到使用unsigned int s來保存散列碼，散列碼永遠不會爲負數，並且在環繞時會表現得很好。另外，如果你仍然想使用int S，你可以屏蔽掉符號位做這個（在號碼前，使值負位）：

return (hvalue & INT_MAX) % j; 

（在這裏，INT_MAX定義在<climits>）。這將確保您的價值是積極的，儘管您從哈希代碼中失去了一點，這可能會導致大量數據集導致更多集羣。在mod之前做&的原因是你想在mod之前確保這個值是肯定的，否則你會溢出桶的數量。

編輯：你也有一個嚴重的錯誤在你的邏輯。這個循環是不正確的：

while(a[i]!=NULL) { 
    ... 
} 

C++ - 風格的字符串不是空終止，所以這不能保證阻止，一旦你閱讀過字符串的結尾。嘗試改變這個閱讀

for (int i = 0; i < a.length(); i++) { 
    /* ... process a[i] ... */ 
} 

希望這會有所幫助！