Hash function to give fewer collisions

A 32-bit int has a range of over 4 billion. (If your ints are 64-bit, the range is much bigger.) But your code simply adds up the values of each character in the string and it will never get anywhere near the upper range. All your hash codes will be smaller numbers, crowding the lower end of possible values, and increasing the chance of collisions.

That's why a good algorithm will be more complicated than this.

Here's one article that turned up in a quick Google search.

"foo bar" and "bar foo" hash to the same value right? Implement it in such a way that the ascii value and its position in the string are used to compute the hash, I naively imagine this will reduce collision significantly.

int hash(char* s) { int hash = 0; int pos = 0; while(*s) { pos++; hash += (*s * pos); s++; } return hash; } 

Try this and see if it helps. I dont have much theoretical knowledge behind this answer.

EDIT* as mentioned below, you would probably want hash to be an unsigned int. I tested this out on codechef.com, here is the source and results:

#include <stdio.h> unsigned int hash(char* s); unsigned int hash2(char* s); int main(void) { unsigned int temp1 = hash("foo bar"); unsigned int temp2 = hash("bar foo"); printf("temp1 is %d and temp2 is %d\n",temp1, temp2); temp1 = hash2("foo bar"); temp2 = hash2("bar foo"); printf("temp1 is %d and temp2 is %d\n",temp1, temp2); return 0; } unsigned int hash(char* s) { unsigned int hash = 0; while(*s) { hash = hash + *s; s++; } return hash; } unsigned int hash2(char* s) { unsigned int hash = 0; int pos = 0; while(*s) { pos++; hash += (*s * pos); s++; } return hash; } 

With output:

temp1 is 665 and temp2 is 665

temp1 is 2655 and temp2 is 2715

Yes, your "hash" function will have collisions for strings which consist of the same letters, for example "rail safety" and "fairy tales". This is because you are only using the addition which is commutative.

You can use something like this which involves a prime as factor.

unsigned long int hashBetter(const char* s) { unsigned long int hash = 1234567890ul; while(*s) { hash = (*s + hash) * 4294967291ul; s++; } return hash; } 

Or you involve a CRC which spreads broadly the input data over the valid range of possible hash values:

unsigned long int hashGood(const char* s) { unsigned long int hash = 1234567890ul; while(*s) { hash = crc(hash, *s); s++; } return hash; }