c - 如何在 O(1) 的数组中查找字符串

Question

我正在为将来的面试而学习，我想知道一些事情。我有一个包含六个字符串的数组，我想知道是否有某种方法像哈希表一样在 O(1) 中找到其中之一。例如，假设我们预先有如下字符串。

char* massageOp[6] = {"SIL","TAG","SILA","TAGS","AVS", "AVST"};

现在用户给我一个字符串，任何字符串，我想知道我是否可以在我的数组中找到该字符串，或者不能，在 O(1) 中。有什么办法可以做到这一点，或者我需要遍历所有数组才能找到它？谢谢。

Answer 1

这取决于您如何定义 O(1)，就像 Oli 提到的那样。如果你想要一个 EXPECTED O(1) (回想一下哈希表可能有冲突并且很难估计最坏情况的复杂度)字符串数量的时间复杂度。使用一些好的字符串哈希算法来解决这个问题会很容易，例如我们可以使用ELFHash:

int ELFhash(char* key, long M) {
  unsigned long h = 0;
  while(*key) {
    h = (h << 4) + *key++;
    unsigned long g = h & 0xF0000000L;
    if (g) h ^= g >> 24;
    h &= ~g;
  }
  return h % M;
}

使用这个 ELFHash 函数，将您的字符串作为“键”，将一个大素数作为“M”，您可以获得一个整数值，它是您的字符串的哈希值。您还可以使用其他一些字符串哈希函数，您可以在此处找到一些讨论:Hashing Tutorial