c - 在 C 中匹配(几个)字符串的最有效方法？

Question

我们的系统需要接受来自终端的用户输入并匹配一些已知的关键字字符串(可能是 10 个)。

我们没有空间/计算机来做正则表达式等，代码需要小而快。

现在，最糟糕的做法是:

   // str is null-terminated, assume we know it's safe/sane here
   if(!strncmp(str,"hello",5)
   {
      do_hello();
   }
   else if(!strncmp(str,"world",5)
   {
      do_world();
   }
   else
   {
      meh(); // Wasn't a match
   }

因此，经过一些谷歌搜索和阅读后，我确信更好的方法是将各种匹配项的哈希值预先计算为一个 int，然后只使用一个 case 语句:

// Assume hash() stops at NULL
switch(hash(str))
{
   case HASH_OF_HELLO:
      do_hello();
      break;

   case HASH_OF_WORLD:
      do_world();
      break;

   default:
      meh();
      break;
}

我们可以在编译时计算*HASH_OF_match*。这似乎是一种从相对较小的集合中挑选字符串的更快/更优雅的方法。

那么 - 这看起来合理吗？/这样做有什么明显的问题吗？/有谁有更优雅的方法吗？

作为脚注，这是我今天下午看到的最漂亮的哈希算法；)，归功于 dan bernstein，它看起来很适合手头的工作。

unsigned int
get_hash(const char* s)
{
    unsigned int hash = 0;
    int c;

    while((c = *s++))
    {
        // hash = hash * 33 ^ c 
        hash = ((hash << 5) + hash) ^ c;
    }

    return hash;
}

Answer 1

散列的问题在于，用户输入的任意字符串可能生成与您的匹配项 相同的散列，您将执行错误的操作。对于小至 10 的搜索集，我会坚持使用 if-else 方法。或者使用字符串数组和函数指针数组(假设所有函数具有相同的签名)来选择要执行的函数。

char const *matches[10] = {"first", "second", ..., "tenth"};
void (*fn[10])(void) = {&do_first, &do_second, ..., &do_tenth};

for( i = 0; i < 10; ++i ) {
  if( strcmp( str, matches[i] ) == 0 ) {
    (*fn[i])();
  }
}