在c++11中将100万个字符串映射到in

Question

我有一百万个ASCII字符串，没有重复，每个字符串最多有7个字节长。我需要将每个字符串映射到一个正整数。这些国家中最大的不应超过一百万。虽然初始化可能很慢，但查找应该是快速的:给定一个字符串，返回相应的int (或-1，如果找不到)。如何在C++11中实现这一点？

一种解决方案:将字符串累加到std::unordered_map<string,int>中；然后遍历映射，从递增计数器分配ints。然后查一查，只有unordered_map::find("foo")->second。但它闻起来像其他容器，速度更快，开销更小(内置索引，而不是手工编码)。也许unordered_set和指针算法？？

范围限制似乎使一个完美的哈希变得困难。

(int的范围受到限制，因为它索引到传递给灯的特征向量中。该软件不使用稀疏存储，因此具有数万亿(大部分为零)元素的向量使其内存耗尽。因此，这种字符串到int预处理实现了稀疏的数据结构。)

Answer 1

你所描述的看起来像完美散列。

有一些实现完美哈希的C++库，例如用于C、C++和Lua的微型完美哈希库。

Answer 2

将字符串转换为int64_t，将它们存储在unordered_set中，并使用迭代器作为唯一索引。实际上，您将实现O(1)查找，加上计算迭代器偏移量的O(N)。您还可以保证最大索引不会超过数组的大小。

  unordered_set<int> s;
  s.insert(10);
  s.insert(2000000);
  s.insert(5000000);

  int index = std::distance(s.find(10), s.end());
  cout << index << endl;
  index = std::distance(s.find(2000000), s.end());
  cout << index << endl;
  index = std::distance(s.find(5000000), s.end());
  cout << index << endl;

产出：

1
2
3

现在您有了唯一的映射，使用unordered_map来实现您的目标，并放弃unordered_set

  unordered_set<int> s;
  unordered_map<int,int> m;
  s.insert(10);
  s.insert(2000000);
  s.insert(5000000);

  int index = std::distance(s.find(10), s.end());
  m[10] = index;
  cout << index << endl;
  index = std::distance(s.find(2000000), s.end());
  m[2000000] = index;
  cout << index << endl;
  index = std::distance(s.find(5000000), s.end());
  m[5000000] = index;
  cout << index << endl;

  s.clear();
  cout << m[10] << " " << m[2000000] << " " << m[5000000] <<  endl;

查找将是O(1)。

Answer 3

如果你有上百万个字符串，每个都有7个字节长，那么这是使用基排序的完美前提；所以首先你把所有10^6个字符串都存储在大数组中(只有7MB/6.7MiB，非常容易管理)，然后使用基排序算法-时间复杂度O(wn)，w= 7，n= 10^6，可以在原地实现。实现的细节对于保持线性复杂度的低常数很重要，但是基排序很容易实现。

作为对基排序的替代，您可以简单地将字符串视为uint64_t并使用std::sort (它实现了优化的内部排序，尽管时间复杂度较高，但它可以为您的约束执行良好的基)。

一旦对数组进行了排序，就可以迭代它，并将数组索引以字符串作为键放入普通的std::unordered_map中。最后，您在基本上线性的时间内创建了完美的散列，并以平均O(1)的反向查找结束。

编辑将字符串放入unordered_map，您可能需要实现自己的散列算法，我建议使用djb2，它具有良好的统计特性，并且易于实现。