Hash Function Determination

Question

How can we find the most efficient hash function(least possible chances of collision) for the set of strings.

Suppose we are given with some strings.. And the length of the strings is also not defined. Ajay Vijay Rakhi ....

we know the count of no. of strings available, so we can design a hash table of size(count available). what could be the perfect hash function that we could design for such problem??

Multiplying each character ascii value by 31(prime no.) in increment fashion leads to the a hash value greater than the value of MAX_INT, and then modulus would not work properly... So please give some efficient hash function build up solution....

I have few set of strings,, lets say count = 10.... I need to implement a hash function such that all those 10 strings fit in uniquely in the hash table.... Any perfect hash function O(1) available, for this kind of problem?? hash table size will be 10, for this case...

Only C Programming...

Please explain the logic at website.... http://burtleburtle.net/bob/c/perfect.c This looks very complicated but perfect to me..!! what is the algorithm used here... Reading the code straight away, is very difficult!!

Thanks....

Answer 1

you might want to have a look at gperf, you could kinda do this on the fly if you didn't do it too often and your data set a small. if the strings are know ahead of time, then this is the method

Answer 2

Check some of these out, they apparantly have good distributions

http://www.partow.net/programming/hashfunctions/#HashingMethodologies

Answer 3

You might want to look into perfect hashing.

Answer 4

Hash tables are meant to be able to handle dynamic input. If you can guarantee only a particular set of inputs, and you want to guarantee a particular slot for each input, why hash at all?

Just make an array indexed for each known available input.