What is the best 32bit hash function for short strings (tag names)?

algorithm hash tags 32-bit
Andrey Shchekin picture Andrey Shchekin · Feb 28, 2010 · Viewed 50.3k times · Source

What is the best 32bit hash function for relatively short strings?

Strings are tag names that consist of English letters, numbers, spaces and some additional characters (#, $, ., ...). For example: Unit testing, C# 2.0.

I am looking for 'best' as in 'minimal collisions', performance is not important for my goals.

Answer

Nick Dandoulakis picture Nick Dandoulakis · Feb 28, 2010

I'm not sure if it's the best choice, but here is a hash function for strings:

The Practice of Programming (HASH TABLES, pg. 57)

/* hash: compute hash value of string */
unsigned int hash(char *str)
{
   unsigned int h;
   unsigned char *p;

   h = 0;
   for (p = (unsigned char*)str; *p != '\0'; p++)
      h = MULTIPLIER * h + *p;
   return h; // or, h % ARRAY_SIZE;
}

Empirically, the values 31 and 37 have proven to be good choices for the multiplier in a hash function for ASCII strings.

Related questions

hash function for string

I'm working on hash table in C language and I'm testing hash function for string. The first function I've tried is to add ascii code and use modulo (%100) but i've got poor results with the first test of data: 40 collisions …

Read More
What is a good Hash Function?

What is a good Hash function? 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. As a rule of …

Read More
Why does Java's hashCode() in String use 31 as a multiplier?

Per the Java documentation, the hash code for a String object is computed as: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, …

Read More