Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

string hashing - djb2 Hash Function

I am using the djb2 algorithm to generate the hash key for a string which is as follows

hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

Now with every loop there is a multiplication with two big numbers, After some time with the 4th of 5th character of the string there is a overflow as the hash value becomes huge

What is the correct way to refactor so that the hash value does not overflow and the hashing also happens correctly

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Hash calculations often overflow. That's generally not a problem at all, so long as you have guarantees about what's going to happen when it does overflow. Don't forget that the point of a hash isn't to have a number which means something in terms of magniture etc - it's just a way of detecting equality. Why would overflow interfere with that?


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...