(几乎)不发生碰撞的简单哈希函数，用于交换机中的使用

Question

我正在用C语言编写一个高级计算器。正如您所猜测的那样，它目前有许多功能，并且我使用switch语句为每个函数名称执行适当的操作。大致如下：

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都散列到612。

有人能推荐一个快速、简单且尽可能避免碰撞的哈希函数来替换我现在正在使用的那个吗？此外，函数表并不是完全硬编码的，哈希函数也将用于哈希用户定义函数的名称，对于这种情况，使用了不同的匹配检查方式，但我使用的哈希函数是相同的。

提前致谢。

- houbysoft

---

可能是如何设计完美哈希函数的函数？的重复问题。 - kennytm

那个链接中的帖子对于哈希函数来哈希一个固定表格很感兴趣，但在我的情况下，用户可以添加新的函数，所以表格并不完全静态（对于这些情况，使用了不同的机制，switch语句用于硬编码的函数）。编辑过的帖子以澄清这一点。 - houbysoft

不存在不会产生碰撞的哈希函数，也许你指的是映射函数。 - codymanix

短函数名称，如sin和cos，与使用哈希表查找相比，将更快地使用strcmp。这是因为在公式中每次出现函数名称时都必须生成哈希值。 - codymanix

用户定义函数名称的长度限制是多少？（如果没有限制，则除非哈希函数的结果也具有无限长度，否则无法拥有此类函数）。 - caf

@caf：它（任意地）设置为64个字符，但实际上通常较短，比如说最多16个字符。 - houbysoft

Answer 1

如果你正在寻找哈希函数，可以查看Paul Hseih' Page和Bob Jenkins' Page(这个非常好)关于哈希的页面，然而我个人通常使用Murmur2进行哈希(使用不同的种子)，正确选择种子后，使用32位输出就不会有太多碰撞(或者根本没有碰撞)，使用64位版本则更少(除非你故意破坏哈希)(虽然我没有测试过16位)。

至于你的问题，如果你想查找函数，使用一些形式的二叉搜索树可能会更容易，因为有用户定义的函数(甚至可能使用字典树)。

- Necrolis

Answer 2

你可以使用树进行查找。它们没有碰撞。

- codymanix