比较字符串集合与字符串的最快方法是什么？

Question

我有一组字符串，我需要找到其中是否有一个特定的字符串。我只需要做一次(下一次字符串是不同的)。

我正在考虑用桶排序来排序字符串，然后进行二进制搜索。

时间复杂度: O(n+k)+O(log )

有没有更快/更好的解决方案？

对于set，我指的是更多的字符串，而不是std::set。

Answer 1

在回答中总结上面的评论。如果您正在加载要动态比较的字符串，并且不需要它们按照特定的顺序进行比较，那么std::unordered_set是目前最快的。

unordered_set是一个哈希集，它将通过哈希函数打孔字符串，并在恒定时间O(1)中查找它是否已经在该集合中。

如果您需要保留元素的顺序，那么保留向量并通过它进行线性搜索有什么更快的速度，或者是否仍然值得构建哈希集。

代码：

std::unordered_set<std::string> theSet;

// Insert a few elements.
theSet.insert("Mango");
theSet.insert("Grapes");
theSet.insert("Bananas");

if ( theSet.find("Hobgoblins") == theSet.end() ) {
    cout << "Could not find any hobgoblins in the set." << endl;
} 

if ( theSet.find("Bananas") != theSet.end() ) {
    cout << "But we did find bananas!!! YAY!" << endl;
}

供比较：

如果使用std::vector，则需要O(n)时间构建向量，然后O(n)时间查找元素。

如果使用std::unordered_set，仍然需要O(n)时间来构建向量，但之后您可以在恒定时间O(1)中找到一个元素。