STL Map和静态数组的比较

Question

我需要存储有关内容的信息在一个查找表中，以便可以非常快速地访问。我可能需要递归引用查找表中的一些元素才能获取有关内容的完整信息。哪种数据结构更好：

1. 使用其中一个参数作为键，将所有条目唯一性并将其余信息作为值的Map。
2. 为每个唯一条目使用静态数组，并根据键（与MAP中使用的相同）在需要时访问它们。

我希望我的软件具有鲁棒性，因为如果发生任何故障，这对我的产品来说都是灾难性的。

- learningstack

Answer 1

这取决于你拥有的键的范围。

通常，当你说查找表时，你指的是一个可以直接索引的小型表格（O(1)）。举个简单的例子，对于一个替换密码, 你可以有一个char cipher[256]，只需使用字符的ASCII码来索引替换字符。如果键是复杂对象或者太多，你可能只能使用映射表。

你还可以考虑哈希表（参见unordered_map）。

回答：

如果键本身可以是任何32位数字，那么存储非常稀疏的40亿元素数组就没有意义。

但是，如果你的键本身在0..10000之间，那么你可以有一个包含指向对象的指针（或对象本身）的10000元素数组，其中只有2000-5000个元素包含非空指针（或有意义的数据）。访问将是O(1)。

如果你的键值对比较大，那么我建议使用 unordered_map。使用一个包含5000个元素的 map，平均访问时间为 O(log n)，大约需要12次访问。而哈希表则最多只需要一到两次访问。

我不熟悉完美哈希，无法提供关于它们的实现建议。如果你选择使用完美哈希，我会感激你提供一两个相关链接以便参考。

- Vlad

---

注意：使用完美哈希可能会使复杂对象可存储在静态数组中（使用哈希作为索引）。 - Matthieu M.

@Vlad 非常感谢。仅用于确认：我计划的软件将具有以下内容：键为整数（数字），值可以是复杂数据结构（最简单的是字符串），键的数量可以达到2000至5000。在这种情况下，您会建议我使用映射吗？ - learningstack

@Vlad 请告诉我任何支持的论据。Mathieu提出的一个也对我来说是一个很好的论据。 - learningstack

@learningstack 我已经编辑了我的回答并附上了答复。希望能对你有所帮助。 - Vlad

Answer 2

std::map中的查找时间应该为O=ln(n)，在最坏情况下，静态数组中的线性搜索为O=n。

即使std::map占用更多内存（在大多数情况下这不应该成为问题），我仍强烈建议使用它。

此外，您可以创建“映射的映射”或更深层次的结构：

typedef std::map<MyKeyType, std::map<MyKeyType, MyValueType> > MyDoubleMapType;

- Constantinius