用于定长字符串查找的数据结构

Question

我有一堆字符串作为钥匙。就像..。

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

它们都是任意4个字符的唯一组合，并且长度都相同。有成百上千的这样的东西。我想执行一个查找并检索与每个字符串相关联的值。

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

我正在考虑将其实现为一个前缀树。考虑到参数(唯一，固定长度)，我想知道是否有一种开箱即用的数据结构，我想不出最适合这个……

编辑:此外，所有可能的组合都由数据文件填充一次。之后，查找会以线速进行。

Answer 1

因为您事先知道所有的字符串，所以可以使用gperf生成一个没有冲突的perfect hash function。例如，对于四个输入字符串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.4MB)中会产生一个非常大的表。如果不需要进行字符串比较，则可以省略该表。

Answer 2

即使存在冲突，哈希表的性能也会优于其他任何表，您可以对其进行调优以减少冲突。

Answer 3

首先，将每个字符串转换为一个整数。如果您的字母表包含64个符号(例如)，则可以使用4*6=24位整数作为密钥。

现在，如果超过一半的可能键正在使用中(如您所说，有数十万个)，也许最简单的解决方案可以做到:只需构建一个数组，通过索引(从字符串推导出的整数)来访问它。

如果可能，使用单个内存分配来实现这一点。它甚至可以节省内存(由于100,000的小分配而浪费的内存)。