How would you go about designing a function for a

Question

The domain of interest is string matching. Assume I have a structure like this.

typedef struct
{
    char *name,
    int (*function)();

} StringArray

StringArray s[] = 
{
    {"George", func1},
    {"Paul",   func2},
    {"Ringo",  func3},
    {"John",   func4},
    {"",       NULL}   /* End of list */ 
}

There are a fixed number of strings in the array. They are hard coded as in the example. If the table changes, there would be a need to re-evaluate the quality of the hash function.

I want to apply a hash function to a string, and if the string matches one in the array, then call the function. A perfect hash function is needed for this. No collisions are allowed.The purpose of requiring hashing is to get O(1) performance on the lookup.

What ideas do you have on designing a function to do this?

Answer 1

See:

What is a good Hash Function?

Best hashing algorithm in terms of hash collisions and performance

What is a performant string hashing function that results in a 32 bit integer with low collision rates?

Choosing a multiplier for a (string) hash function

Very low cost hash function

What’s the best hashing algorithm to use on a stl string when using hash_map?

Answer 2

See the gperf home page.