Hash Function Clarification

Question

Went over this in class today:

const int tabsize = 100000; int hash(string s) { const int init = 21512712, mult = 96169, emergency = 876127; int v = init; for (int i=0; i<s.length(); i+=1) v = v * mult + s[i]; if (v < 0) v = -v; if (v < 0) v = emergency; return v % tabsize; }

Having some trouble figuring out what the last 2 if-statements are supposed to do.

Any ideas?

Thanks

Note that overflow of signed integers are undefined behavior in C++. — MikeCAT
– MikeCAT, Commented Oct 1, 2015 at 1:30
Yep, a compiler could optimize away the last if statement because it can only have an effect if undefined behavior happens on the line before. — David Grayson
– David Grayson, Commented Oct 1, 2015 at 2:18

smac89 · Accepted Answer · 2015-10-01 15:11:49Z

The first if statement takes care of overflow behavior of signed integers. Thus if the integer gets too big that it wraps and becomes negative, this if statement ensures that only the positive integer is returned.

The second if statement is used to take care of the rare case of where v is 2147483648.

Note that positive signed 32 bit integers only go up to 2³¹ - 1 or 2147483647 while the negative can go down to -2³¹ or -2147483648.

This number is negative and even negating it still gives a negative number. So that is what the emergency number is for

int main() { int t = -2147483648; std::cout << (-t) << std::endl; }

1201ProgramAlarm · Accepted Answer · 2015-10-01 01:36:00Z

They ensure the v is positive, because when you use the % operator on a negative number you can get a negative result which is not desirable for a hash value.

However, this does get into undefined behavior with the integer overflow so it might not work everywhere.

Collectives™ on Stack Overflow

Hash Function Clarification

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related