Good Hash Function for Strings

java hash hashtable hashcode
Leif Andersen picture Leif Andersen · Apr 12, 2010 · Viewed 374.3k times · Source

I'm trying to think up a good hash function for strings. And I was thinking it might be a good idea to sum up the unicode values for the first five characters in the string (assuming it has five, otherwise stop where it ends). Would that be a good idea, or is it a bad one?

I am doing this in Java, but I wouldn't imagine that would make much of a difference.

Answer

jonathanasdf picture jonathanasdf · Apr 12, 2010

Usually hashes wouldn't do sums, otherwise stop and pots will have the same hash.

and you wouldn't limit it to the first n characters because otherwise house and houses would have the same hash.

Generally hashs take values and multiply it by a prime number (makes it more likely to generate unique hashes) So you could do something like:

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}

Related questions

What hashing function does Java use to implement Hashtable class?

From the book CLRS ("Introduction to Algorithms"), there are several hashing functions, such as mod, multiply, etc. What hashing function does Java use to map the keys to slots? I have seen there is a question here Hashing function used …

Read More
Hashtable, HashMap, HashSet , hash table concept in Java collection framework

I am learning Java Collection Framework and got moderated understanding. Now, when I am going a bit further I got some doubts in: HashMap, HashSet, Hashtable. The Javadoc for HashMap says: Hash table based implementation of the Map interface. This …

Read More
Why does HashMap require that the initial capacity be a power of two?

I was going through Java's HashMap source code when I saw the following //The default initial capacity - MUST be a power of two. static final int DEFAULT_INITIAL_CAPACITY = 16; My question is why does this requirement exists in the …

Read More