以字符串快速查找的字符串/整数对的最佳存储空间？

Question

我需要维护字符串和整数之间的对应关系，然后查找字符串值并返回整数。什么是存储此信息的最佳结构，以满足以下要求：

• 速度和内存大小依次是重要的。

• 我不想重新发明轮子并编写我自己的分拣程序。对Sort（CompareFunction）的调用当然是好的。

条件：

• 的整数，但不保证连续的，也不是有一个“开始值”如0或1

• 数据对数可以从100变化到100000

• 数据全部读入开头，没有后续的添加/删除/修改

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

有这么多的选项（TStringList中（使用对象或名称/值对），TObjectList，TDictionary，...），我最好请教第一...

我读How can I search faster for name/value pairs in a Delphi TStringList?其中建议TDictionary字符串/字符串对，​​建议TStringlist对象的字符串/整数，但排序完成整数。

Answer 1

您在问题中包含的第二个链接不适用。这是一个关于排序而不是有效查找的问题。尽管你在你的问题中讨论了多次排序，但你没有排序的要求。您的需求仅仅是一个字典，也被称为关联数组。当然，您可以通过对数组进行排序并使用二进制搜索来实现查找，但排序不是必需的。你只需要一个高效的字典。

开箱即用，您问题的最有效和最方便的数据结构是TDictionary<string, Integer>。这具有O（1）的查找复杂性，因此适用于大型集合。对于较小的集合，查找复杂度为O（log n）的基于二进制搜索的查找可能具有竞争力，确实可以超出字典。

Cosmin Prund在SO上写了一个很好的answer，在这里他比较了字典查找与基于二进制搜索的查找的性能。我建议你有一个阅读。我会说，对于小容器来说，性能对你来说可能不是什么大问题。所以即使二分查找可能更快，但这可能并不重要，因为您的性能无论如何都很好。但是性能可能成为更大容器的问题，这就是字典总是更强大的地方。对于容量足够大的容器，二进制搜索的性能可能变得不可接受。我相信可以制作比Embarcadero更高效的词典实现，但我也会说Embarcadero的实现是完美的。它使用体面散列函数，并没有任何明显的弱点。

在内存复杂度方面，字典和排序数组之间的选择很少。为了内存的使用，不可能改进已排序的数组。

我建议你从TDictionary<string, Integer>开始，只有当你的表现要求没有得到满足时，才会超越。

Answer 2

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

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