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/?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.