用于快速名称查找的容器

Question

我想存储字符串并为每个字符串分配一个唯一的 ID 号（索引就可以了）。 我只需要每个字符串的一份副本，并且需要快速查找。 我经常检查该字符串是否存在于表中，以至于我注意到性能受到影响。 为此使用的最佳容器是什么以及如何查找字符串是否存在？

Answer 1

我建议 tr1::unordered_map。 它是作为哈希图实现的，因此其查找的预期复杂度为 O(1)，最坏情况为 O(n)。 如果您的编译器不支持 tr1，还有一个 boost 实现。

#include <string>
#include <iostream>
#include <tr1/unordered_map>

using namespace std;

int main()
{
    tr1::unordered_map<string, int> table;

    table["One"] = 1;
    table["Two"] = 2;

    cout << "find(\"One\") == " << boolalpha << (table.find("One") != table.end()) << endl; 
    cout << "find(\"Three\") == " << boolalpha << (table.find("Three") != table.end()) << endl; 

    return 0;
}

Answer 2

试试这个：

_{（来源：adrinael.net）}

Answer 3

尝试 std::map。

Answer 4

首先您必须能够量化您的选择。 您还告诉我们，您感兴趣的主要使用模式是查找，而不是插入。

令 N 为您期望表中包含的字符串数量，并令 C 为表中存在的任何给定字符串的平均字符数。所述表（或在对照表检查的字符串中）。

1. 在基于哈希的方法的情况下，对于每次查找，您需要支付以下费用： p>

   • O(C) - 计算您要查找的字符串的哈希值
   • 介于 O(1 x C) 和 O(N x C) 之间，其中 1..N 是您期望的成本根据哈希键遍历存储桶，此处乘以 C 以根据查找键重新检查每个字符串中的字符
   • 总时间：O(2 x C) 和 O((N + 1) x C)

2. 如果是基于 std::map 的方法（使用红黑树），对于每次查找，您需要支付以下费用：

   • 总时间：在 O(1 x C) 和 O(log(N) x C) 之间 - 其中 O(log(N))< /code> 是最大树遍历成本，O(C) 是 std::map 的通用 less<> 的时间> 实现需要在树遍历期间重新检查您的查找键

   


在 N 值较大且缺乏保证少于 log(N) 冲突的哈希函数的情况下，或者如果您只是想安全起见，< strong>您最好使用基于树的 (std::map) 方法。 如果 N 很小，无论如何，请使用基于哈希的方法（同时仍然确保哈希冲突较低。）

不过，在做出任何决定之前，您还应该检查：

• http://meshula.net/wordpress/?p=183
• http://wyw.dcweb.cn/mstring.htm

Answer 5

要搜索的字符串是否静态可用？ 您可能想看看完美的哈希函数

Answer 6

听起来数组可以很好地工作，其中索引是数组的索引。 要检查它是否存在，只需确保索引位于数组范围内并且其条目不为 NULL。

编辑：如果您对列表进行排序，您始终可以使用应该具有快速查找功能的二分搜索。

编辑：此外，如果您想搜索字符串，也可以随时使用 std::map 。 这应该有一些不错的查找速度。

Answer 7

最简单的是使用 std::map。

它的工作原理如下：

#include <map>
using namespace std;

...

   map<string, int> myContainer;
   myContainer["foo"] = 5; // map string "foo" to id 5
   // Now check if "foo" has been added to the container:
   if (myContainer.find("foo") != myContainer.end())
   {
       // Yes!
       cout << "The ID of foo is " << myContainer["foo"];
   }
   // Let's get "foo" out of it
   myContainer.erase("foo")

Answer 8

Google 稀疏哈希 可能