固定长度字符串查找的数据结构

Question

我有一堆字符串作为键.就像是...

AAAA ABBA ACEA ALFG
...
...
ZURF [AAA _JFS aKDJ

它们都是任意4个字符的独特组合,并且长度都相同.有成千上万的这些.我想执行查找并检索与每个字符串关联的值.

我目前将它实现为哈希表,但主要关注的是冲突(我已经在Wiki上实现了所有策略).

我正在考虑将其实现为前缀树.鉴于参数虽然(唯一,固定长度),我想知道是否有一个现成的数据结构,我想不到最适合这个......

编辑:此外,所有可能的组合都由数据文件填充一次.然后,查找以线速发生.

Answer 1

由于您提前知道所有字符串,因此可以使用gperf生成完美的哈希函数,该函数没有冲突.例如,使用四个输入字符串AAAA ABBA ACEA ALFG,它生成以下哈希函数(使用命令行gperf -L ANSI-C input.txt):

static unsigned int
hash (register const char *str, register unsigned int len)
{
  static unsigned char asso_values[] =
    {
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12,  7,  2,  5, 12, 12,
      12, 12, 12, 12, 12, 12,  0, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12
    };
  return len + asso_values[(unsigned char)str[1]];
}

const char *
in_word_set (register const char *str, register unsigned int len)
{
  static const char * wordlist[] =
    {
      "", "", "", "",
      "ALFG",
      "",
      "ABBA",
      "", "",
      "ACEA",
      "",
      "AAAA"
    };

  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)
    {
      register int key = hash (str, len);

      if (key <= MAX_HASH_VALUE && key >= 0)
        {
          register const char *s = wordlist[key];

          if (*str == *s && !strcmp (str + 1, s + 1))
            return s;
        }
    }
  return 0;
}

这需要单个表查找,长度比较和字符串比较.如果您确定您正在散列的单词是您的源词之一,那么您可以跳过字符串比较.

将输入大小从4扩展到10000随机生成的字符串会将散列函数增加到只有4个表查找以及长度比较和字符串比较.但是,由于字符串比较必须将每个源字符串存储在其中,因此这将出现在编译对象文件中的一个非常大的表中(1.4 MB).如果您不需要进行字符串比较,则可以省略该表.