Hey guys, I am having issues understanding how exactly to mod something to avoid overflow.

say i have this hash function:

``````int universalHash(const string &x,int B) {
long long sum;
long long power;
sum=0;
pow = 1;
for (int i=0;i<(signed)x.length();i++) {
//		cout << "sum= " << sum << endl;
//		cout << "pow= " << pow << endl;
sum = sum +  (x[i]-'a') * power;
power =  power*26;
}
return sum;
}``````

This is wrong because it will cause an overflow so I have to do this equation Mod B (where B is the table size (997) and the string I am passing in is the letters a through p in order.

I found that these are the rules for mod B arithmetic:

x + y Mod B = ((x Mod B) + (y Mod B)) Mod B
x * y Mod B = ((x Mod B) * (y Mod B)) Mod B

Here was my attempt that was not giving the correct answer (28).

``````int universalHash(const string &x,int B) {
long long sum;
long long pow;
sum=0;
pow = 1;
for (int i=0;i<(signed)x.length();i++) {
cout << "sum= " << sum << endl;
cout << "pow= " << pow << endl;
sum += (((x[i]-'a')%B) * (pow%B))%B;
pow = ((pow%B)*(26%B));
}
return sum;
}``````

If you want to obtain hash index in a table of size B, don't forget:
1. Make unsigned int calculations ( `x[i]-a` is signed value).
2. Result is sum % B.
3. As usually, no need to avoid integer overflow.
May be better don't invent a square wheel?
Are you familiar with http://www.partow.net/programming/hashfunctions/?