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

Question

我需要保持字符串和整数之间的对应关系,然后查找字符串值并返回整数.存储符合以下要求的信息的最佳结构是什么:

• 按顺序,速度和内存大小很重要.

• 我不想重新发明轮子并编写自己的排序程序.调用Sort(CompareFunction)当然没问题.

条件:

• 整数不保证是连续的,也没有像0或1那样的"起始值"

• 数据对的数量可以在100到100000之间变化

• 所有数据都在开头读入,没有后续的添加/删除/修改

• FWIW字符串是Outlook(MAPI？)用于标识条目的十六进制条目ID.示例:00000000FE42AA0A18C71A10E8850B651C24000003000000040000000000000018000000000000001E7FDF4152B0E944BA66DFBF2C6A6416E4F52000487F22

有很多选项(TStringList(带有对象或名称/值对),TObjectList,TDictionary,......)我最好先征求意见......

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

Answer 1

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

开箱即用,为您的问题提供最有效,最方便的数据结构TDictionary<string, Integer>.这具有O(1)的查找复杂性,因此适用于大型集合.对于较小的集合,具有查找复杂度O(log n)的基于二进制搜索的查找可以是竞争性的并且实际上可以胜过字典.

Cosmin Prund在SO上写了一个很好的答案,他将字典查找的性能与基于二进制搜索的查找进行了比较.我建议你读一读.我会说,对于小型容器,性能对您来说可能不是一个大问题.因此,尽管二进制搜索可能更快,但它可能并不重要,因为无论哪种方式,您的表现都很好.但是性能可能成为更大容器的问题,而字典总是更强大.对于足够大的容器,二进制搜索的性能可能变得不可接受.

我确信有可能比Embarcadero生成更高效的字典实现,但我也说Embarcadero实现完全可靠.它使用了一个不错的哈希函数,并没有任何明显的弱点.

就内存复杂性而言,在字典和排序数组之间几乎没有选择.对于内存使用,不可能改进排序数组.

TDictionary<string, Integer>如果不满足您的性能要求,我建议您首先考虑并超越它.