排序TStringList,排序如何工作？

Question

我只是好奇,因为我最近看到在Java中使用Hashmaps,并想知道Delphi的Sorted String列表是否相似.

TStringList对象是否生成Hash以用作每个项的索引？如何通过Find函数根据字符串列表检查搜索字符串？

我经常使用Sorted TStringLists,我只想了解更多内容.

请假设我不知道哈希映射是如何工作的,因为我没有:)

谢谢

Answer 1

我通常将这个问题解释为对列表和词典概述的请求.

为了论证,让我们称呼我们的列表L和字典D.

列表具有真正的随机访问权限.如果您知道其索引,则可以在固定时间内查找项目.字典不是这种情况,它们通常采用基于散列的算法来实现有效的随机访问.

当您尝试查找值时,排序列表可以执行二进制搜索.找到一个值V,就是获得索引I的行为L[I]=V.二进制搜索非常有效.如果列表未排序,那么它必须执行线性搜索,效率低得多.排序列表可以使用插入排序来维护列表的顺序 - 添加新项目时,它将插入到正确的位置.

您可以将字典视为对列表<Key,Value>.您可以迭代所有对,但更常见的是使用索引表示法来查找给定键的值:D[Key].请注意,这与在列表中查找值的操作不同 - L[I]当您知道索引I时,它就是读取的类似物.

在旧版本的Delphi中,通常会从字符串列表中哄骗字典行为.表现很糟糕.内容的灵活性很小.

对于现代的Delphi,有TDictionary一个可以容纳任何东西的泛型类.该实现使用哈希,虽然我没有亲自测试其性能,但我理解它是值得尊敬的.

有一些常用的算法可以最佳地使用所有这些容器:未排序列表,排序列表,字典.你只需要使用正确的问题来解决问题.

@Golez当列表为`Sorted`时,它使用插入排序.当你在未排序的列表上调用`Sort()`时,它使用quicksort.当用作列表时,字符串列表的性能非常好,但是当强制行为像字典时,性能很差. (2认同)