c - (几乎)用于开关的非冲突简单哈希函数

Question

我正在用 C 写一个高级计算器。正如你所猜到的，它目前有很多函数，我使用一个开关来对每个函数名进行适当的操作。它是这样的:

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

  case HASH_SIN:
    // do something else
    break;

  // etc.
}

到目前为止，我使用在互联网上某处找到的这个简单函数来进行散列:

#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;
}

它过去做得很好，而且速度非常快。然而，现在计算器越来越大，用户也可以定义自己的函数和变量，冲突变得非常明显——例如 cond 和 dotp 都是 hash到 612。

有人可以推荐一个快速和简单，并且尽可能不冲突的散列函数来替换我现在正在使用的散列函数吗？ 此外，函数表并非完全硬编码，散列函数也可用于散列用户定义函数的名称，为此使用不同的检查匹配的方法，但散列函数我用的是一样的。

提前致谢。

Answer 1

如果您正在寻找哈希函数，请同时查看 Paul Hseih' Page和 Bob Jenkins' Page (这个是黄金)哈希，虽然我个人通常使用 Murmur2对于散列(使用一些不同的种子)，使用正确的种子，使用 32 位输出你不会得到很多(如果有任何冲突)，甚至更少(基本上没有，除非你故意破坏散列)使用 64 位版本(我虽然还没有测试 16 位)。

至于你的问题，如果你使用某种形式的二叉搜索树来查找函数可能会更容易，因为有用户定义的函数(trie 甚至可以工作)