用于高效查找通用字符串的映射或哈希图？

Question

我需要能够存储和查找通用字符串。我对字符串的内容了解不多，2/3 以上是人类语言单词，其余的更接近 UUID 或数字/字母组合。我知道任何特定的分组都是不变的（即，如果它有一些人类单词，那么它将全部是人类单词，如果它有一些 UUID，那么所有内容都将是 UUID 等）。

我需要决定是否应该将此数据放入映射或哈希映射中以获得最佳平均查找率。我倾向于使用 O(log n) 运行时进行映射，因为当我对字符串的输入格式知之甚少时，我不相信我可以为字符串进行适当有效的哈希。有什么想法会更好吗？

编辑：我忘记了一个关键方面。我不知道字符串的长度，因此担心对于长字符串来说内存使用量可能会变得太大。如果我使用哈希方法，我会做一些事情，在 X 个字符之后，哈希不会在每个字符的基础上进行哈希，以避免内存消耗太大。

我真正想要的是一个哈希映射实现，它可以将“存储桶”中的多个值按有序方式排序，以便它可以提供存储桶的（log N）搜索；但我认为 stardrd C++ 中不存在这种情况，并且不值得从头开始编写。

pps。数据接近静态。我偶尔需要将其添加到列表中，这种情况很少见，而且我愿意接受缓慢的写入时间。我只关心查找时间。

Answer 1

很难提出单一的建议。这取决于几个权衡（迭代类型、内存与查找）。在整个过程中，我假设您可以使用 C++11 编译器（或等效的 Boost 或 TR1 库）。

如果插入/查找时间对您来说最重要，我肯定会使用std::unordered_set（请参阅参考资料）与std::hash<std::string>（请参阅参考资料）。插入和查找都是平均的（摊余常数）。O(1)如果

请注意，无序哈希容器不允许您按排序顺序进行迭代。所以如果你想要排序迭代，那么你可以使用有序容器std::set<std::string>，但你付出的代价是O(log N)查找/插入。

内存限制更难以分析。首先，有序容器std::set每个元素std::map大约需要3 个单词的开销来维护允许有序迭代的树结构。然而，无序散列容器具有一些闲置容量，因为散列容器在满负载因子上运行非常差。

#include <iostream>
#include <functional>
#include <string>
#include <unordered_set> // or <set> for ordered lookup

int main()
{
    // or std::set<std::string> for ordered lookup
    std::unordered_set<std::string> dictionary; 

    std::string str = "Meet the new boss...";
    dictionary.insert(str);
    auto it = dictionary.find(str);

    std::cout << *it << '\n';
}

在Ideone上输出。如果您还想Value与 一起存储std::string，那么您可以使用std::unordered_map<std::string, Value>, 或 以及std::map<std::string, Value>相同的哈希函数。

结论：最好根据上述权衡来衡量最适合您的应用程序的方法。