hash - 已知键集的最快字符串键查找

Question

考虑一个具有以下签名的查找函数，它需要为给定的字符串键返回一个整数:

int GetValue(string key) { ... }

进一步考虑在编写函数的源代码时预先知道编号为 N 的键值映射，例如:

// N=3
{ "foo", 1 },
{ "bar", 42 },
{ "bazz", 314159 }

因此，上述输入函数的有效(但不完美!)实现将是:

int GetValue(string key)
{
    switch (key)
    {
         case "foo": return 1;
         case "bar": return 42;
         case "bazz": return 314159;
    }

    // Doesn't matter what we do here, control will never come to this point
    throw new Exception();
}

还预先知道在运行时为每个给定键调用该函数的确切次数 (C>=1)。例如:

C["foo"] = 1;
C["bar"] = 1;
C["bazz"] = 2;

但是，此类调用的顺序未知。例如。以上可以描述运行时的以下调用序列:

GetValue("foo");
GetValue("bazz");
GetValue("bar");
GetValue("bazz");

或任何其他序列，前提是调用计数匹配。

还有一个限制 M，以任何最方便的单位指定，它定义了任何查找表和其他可以被 GetValue 使用的辅助结构的内存上限。 (结构是预先初始化的；该初始化不计入函数的复杂性)。例如，M=100 个字符，或 M=256 sizeof(object reference)。

问题是， GetValue的正文怎么写？使其尽可能快 - 换句话说，所有 GetValue 的总时间对于给定的 N、C 和 M？

该算法可能需要 M 的合理最小值，例如M >= char.MaxValue .它还可能要求 M 与某个合理的边界对齐——例如，它可能只是 2 的幂。它还可能要求 M 必须是某种类型的 N 的函数(例如，它可能允许有效的 M=N，或 M=2N，...；或有效的 M=N，或 M=N^2， ...; 等等)。

该算法可以用任何合适的语言或其他形式表达。对于生成代码的运行时性能约束，假设 GetValue 的生成代码将使用 C#、VB 或 Java(实际上，任何语言都可以，只要将字符串视为不可变的字符数组——即 O(1) 长度和 O(1) 索引，并且没有提前为它们计算其他数据)。此外，为了稍微简化一下，假设所有键的 C=1 的答案都被认为是有效的，尽管那些涵盖更一般情况的答案是首选。

关于可能的方法的一些思考

对上述问题的第一个显而易见的答案是使用完美的散列，但寻找一个的通用方法似乎并不完美。例如，对于上面的示例数据，可以使用 Pearson 散列轻松生成最小完美散列的表，但随后必须对每次调用 GetValue 时对输入键进行散列处理。 , 并且 Pearson 散列必须扫描整个输入字符串。但是所有示例键实际上在它们的第三个字符上有所不同，因此只能将其用作散列的输入而不是整个字符串。此外，如果要求 M 至少为 char.MaxValue ，那么第三个字符本身就变成了一个完美的散列。

对于一组不同的键，这可能不再正确，但在给出准确答案之前，仍然可以减少考虑的字符数量。此外，在某些情况下，最小的完美散列需要检查整个字符串，可以将查找减少到一个子集，或者通过使散列非最小来使其更快(例如，不太复杂的散列函数？) (即 M > N) - 为了速度有效地牺牲了空间。

也可能是传统的散列开始并不是一个好主意，并且更容易构建 GetValue 的主体。作为一系列条件，排列成第一个检查“最易变”的字符(在大多数键中变化的字符)，并根据需要进一步嵌套检查以确定正确答案。请注意，此处的“方差”可能受每个键将要查找的次数 (C) 的影响。此外，分支的最佳结构应该是什么并不总是显而易见的 - 例如，“最可变”字符可能只允许您区分 100 个键中的 10 个，但对于剩余的 90 个，则需要额外检查没有必要区分它们，平均而言(考虑到 C)，每个键的检查次数比不以“最可变”字符开头的不同解决方案要多。目标是确定完美的检查顺序。

Answer 1

您可以使用 Boyer搜索，但我认为Trie将是一种更有效的方法。您可以修改 Trie 以折叠单词，因为您使关键字的命中计数为零，从而减少了您必须在获得的行中进行的更远的搜索次数。您将获得的最大好处是您正在对索引进行数组查找，这比比较快得多。