CODEWITHSUNDEEP
c++data-structures
rafa
rafa

Reputation: 47

Hash Function Clarification

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

Upvotes: 2

Views: 124

Answers (2)

smac89
smac89

Reputation: 43068

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 231 - 1 or 2147483647 while the negative can go down to -231 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;
}

Upvotes: 3

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

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.

Upvotes: 1

Related Questions