(almost) Non-colliding simple hashing function for use in a switch

Question

Hi, I am writing an advanced calculator in C. As you can guess, it currently has many functions, and I use a switch to do the proper operation for every function name. It goes something like this:

switch(hash_of(function_name_currently_being_parsed))
{
  case HASH_COS:
    // do something
    break;

  case HASH_SIN:
    // do something else
    break;

  // etc.
}

Up to now, I used this simple function I found somewhere on the internet to do the hashing:

#define NHASH 29989
#define MULT 31

unsigned int simple_hash(char *p)
{
  unsigned int h = 0;
  for(; *p; p++)
    h = MULT * h + tolower(*p);
  return h % NHASH;
}

It used to do the job just fine and is very fast. However, now that the calculator is expanding more and more, and also users can define their own functions and variables, collisions become quite noticeable -- for example cond and dotp both hash to 612.

Could somebody recommend a fast and simple, and as non-colliding as possible hashing function to replace the one I'm using right now? Also, the table of the functions is NOT entirely hard-coded, the hashing function would also be used to hash the names of user-defined functions, for which a different way of checking a match is used, but the hashing function I use is the same.

Thanks in advance.

Answer 1

If your looking for hash functions, have a look at both Paul Hseih' Page and Bob Jenkins' Page(this one is gold) on hashing, though personally I generally use Murmur2 for hashing(with some different seeds), with the right seed, you won't get many(if any collisions) using a 32bit output, or even less(basically none, unless your purposely subverting the hash) using a 64bit version(I haven't tested 16bits though).

As for your problem, it might be easier if you used some form of binary search tree to lookup functions, seeing as there are user defined functions(a trie might even work)

Answer 2

You could use trees for lookup. They have no collisions.