2

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

我需要决定是否应该将这些数据放在地图或哈希图中以获得最佳平均查找率。我倾向于使用 O(log n) 运行时说 map，因为当我对字符串的输入格式知之甚少时，我不相信我可以为字符串进行适当的有效散列。关于哪个会更好的任何想法？

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

我真正想要的是一个哈希映射实现，它将“桶”中的多个值按有序的manaer排序，因此它可以提供桶的（log N）搜索；但我不认为 Stardrd C++ 中存在它，也不值得从头开始编写。

pps。数据接近静态。我偶尔会不得不将它添加到列表中，这很罕见，我愿意接受缓慢的写入时间。我只关心查找时间。

4

4 回答 4

4

很难提出单一的建议。这取决于几个权衡（迭代类型、内存与查找）。在整个过程中，我假设您可以使用 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>具有相同的哈希函数。

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

于 2012-08-14T18:04:02.993 回答
3

除了 std::set、std::map、std::unordered_set 和 std::unordered_map - 我还会考虑研究Tries以查看它们是否更适合：

http://en.wikipedia.org/wiki/Trie

于 2012-08-14T18:07:59.110 回答
1

Cedar、HAT-Trie和JudyArray非常棒，你可以在这里找到基准。

基准测试结果

于 2015-02-27T05:46:49.397 回答
0

您可能想看看基准： http: //www.dotnetperls.com/sorteddictionary 它出现在实际应用程序中，尽管发生冲突 字典比 SortedDictionary 更好。

于 2012-08-14T18:16:26.967 回答