string - 检查字符串是否在静态编译时集中的最快方法是什么？

Question

我知道哈希码通常是检查动态集的最快方法，但我想知道检查动态字符串是否在编译时已知的只读字符串集中的最快方法是什么。 (我的意思主要是 {length: usize; chars: &[u8]} 字符串，而不是 ropes 或 cons 字符串。)

目前，我通常会做这样的事情，但它似乎不是最理想的:

// What I mean
let keywords = Set::new(["do", "if", "in", "for", "new", "try"]);
fun is_keyword(s: &str) { keywords.contains(s) }

// What I write
function is_keyword(s: &str) {
    match s.length() {
        2 -> s == "do" || s == "if" || s == "in",
        3 -> s == "for" || s == "new" || s == "try",
        // etc.
        _ -> false
    }
}

对于 C 风格字符串集，是否有比从第二个变体派生的东西更快的东西？或者它是我能合理得到的最快速度吗？

这是与语言无关的——我不在乎答案使用什么语言。我只是因为熟悉才使用 Rust。

Answer 1

对于静态集，您可以使用完美散列。这本质上是一个哈希表，但哈希函数保证集合中的每个字符串都哈希到表中的唯一索引。

要测试动态字符串，您只需使用完美哈希函数将其哈希到一个索引，然后查看该索引处的唯一字符串是否与测试字符串匹配。

谷歌搜索会为您找到许多不同的方法来进行完美散列。这里描述了我的最爱之一:http://cmph.sourceforge.net/papers/chm92.pdf

它通常用于编译器中的关键字匹配，或者在支持它的语言中对字符串实现 switch/case。