What is a good hash function?

Question

I saw a lot of hash function and applications in my data structures courses in college, but I mostly got that it's pretty hard to make a good hash function. I get that is a somewhat good function to avoid collisions and a fast one, but how can I make a better one? Is there better hash functions for string keys against numeric keys?

Answer 1

A hash function is specific to an object type. Unfortunately, this means that there is no general "good hash function", because a hash function is impossible to make without first knowing what type you're hashing for. For example, a hash function for an int will likely be totally different than a hash function for a string.

You are correct in saying that a good hash function can be quickly calculated and produce a unique hash value (most of the time) for each unique object value. In general, it is easier to come up with a good hash function for numeric objects than other types of objects, such as strings.

Here are two examples of good(ish) hash functions (written in C++): one for an int and one for a string.

int hash_int(int i, int size)

{

return i%size;

}

A very simple hash function for a string would be to sum up the underlying integer value of each character in the string and then mod the sum by a size

int hash_string(string s, int size)

{

int sum = 0;

for(int i = 0; i < s.size(); ++i) {

sum += static_cast<int>(s[i]);

}

return sum%size;

}

As a disclaimer, there are much better hash functions for strings than what I have here.