我在为将来的面试做准备,我想知道一些事情。
我有一个六根弦的数组,我想知道是否有办法
在O(1)中像哈希表一样找到其中一个。
例如,假设我们事先有以下字符串。

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

现在用户给了我一个字符串,任何字符串,我想知道是否可以在数组中找到该字符串,或者在O(1)中没有。有没有办法,或者我需要通过所有的数组来找到它?
谢谢。

最佳答案

这取决于您如何定义O(1),正如Oli所提到的。如果你想要一个期望的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函数,字符串为“key”,大素数为“M”,可以得到一个整数值,它是字符串的哈希值。您还可以使用其他一些字符串哈希函数,您可以在这里找到一些讨论:Hashing Tutorial

08-26 13:23
查看更多