具有快速查找字符串的字符串/整数对的最佳存储方式是什么？

Question

我需要维护字符串和整数之间的对应关系，然后查找字符串值并返回整数。哪种最佳结构可以满足以下要求：

• 速度和内存大小很重要，按顺序排列。

• 我不想重新发明轮子并编写自己的排序程序。当然，调用Sort（CompareFunction）就可以了。

条件：

• 整数不能保证是连续的，也没有像0或1这样的“起始值”

• 数据对的数量可以从100到100000个不等

• 所有数据都在开始时读入，没有后续添加/删除/修改

• FWIW，字符串是Outlook（MAPI？）用于标识条目的十六进制条目ID。示例：00000000FE42AA0A18C71A10E8850B651C24000003000000040000000000000018000000000000001E7FDF4152B0E944BA66DFBF2C6A6416E4F52000487F22

有很多选项可供选择（TStringList（带对象或名称/值对），TObjectList，TDictionary等），我最好先寻求建议...

我已阅读如何在Delphi TStringList中更快地搜索名称/值对？，建议使用TDictionary进行字符串/字符串对，以及在Delphi 2007中排序多维数组，建议使用TStringlist对象进行字符串/整数对，但其中排序是在整数上完成的。

- Jan Doggen

---

我会建议使用类似于 type TNamedInt = record Name: String; Value: Integer; end; 的记录，然后再创建一个该类型的数组 type TNamedInts = Array of TNamedInt，最后通过各种方法（例如 Lookup(Name: String): Integer;）来查找和操作它。 - Jerry Dodge

@JerryDodge 如果你没有为“Lookup”提供实现，那么说这样的话很容易。而且，你选择用来使“Lookup”高效的算法可能会影响底层数据结构。字典是一个非常好的例子。 - David Heffernan

@David 确实，这就是我把它作为评论以“我会说”的形式留下，而不是回答的原因，好像在说“这就是答案”。 - Jerry Dodge

留下它（提醒我在喝咖啡之前不要打字） - Jerry Dodge

Answer 1

你在问题中提到的第二个链接与此无关，那是一个有关排序而非高效查找的问题。虽然你在问题中多次讨论了排序，但你并没有要求进行排序。你所需的仅是一个字典，也称为关联数组。当然，你可以通过对数组进行排序并使用二分查找来实现它，但排序不是必须的。你只需要一个高效的字典。

从开箱即用的角度来看，最有效和便捷的数据结构是 TDictionary<string, Integer>。它具有O(1)的查找复杂度，因此适用于大型集合。对于较小的集合，基于二分查找的查找具有 O(log n) 的查找复杂度，并且可以与字典竞争并确实可以超过字典。 Cosmin Prund 在 SO 上写了一个优秀的 回答，其中他比较了字典查找和基于二分查找的查找的性能。我建议你去阅读一下。我认为对于小容器来说，性能可能不是很重要。因此，即使二分查找可能更快，它可能并不重要，因为你的性能两种方式都很好。但对于更大的容器来说，性能可能成为问题，而字典在这方面始终更强。对于足够大的容器，二分查找的性能可能变得无法接受。

我相信可以产生比Embarcadero更高效的字典实现方法，但我也会说Embarcadero的实现非常可靠。它使用了一个不错的哈希函数，没有任何明显的缺点。

在内存复杂度方面，字典和排序数组之间几乎没有什么区别。不能在内存使用上改进排序数组。

我建议你先从 TDictionary<string, Integer> 开始，只有在未满足性能要求时才考虑其他选项。

- David Heffernan

Answer 2

看起来你要查找长而均匀分布的字符串。对于这种问题，最快的数据结构之一是Trie。

但是你的数据集大小相当小，而现成的 Delphi 解决方案，如 THashedStringList 或 TDictionary（更方便），将提供相当高的速度。

- MBo