delphi - 已排序的TStringList，排序是如何工作的？

Question

我只是很好奇，因为最近我看到了 Java 中 Hashmap 的使用，想知道 Delphi 的排序字符串列表是否相似。

TStringList 对象是否生成一个哈希来用作每个项目的索引？如何通过“查找”功能根据字符串列表检查搜索字符串？

我经常使用 Sorted TStringLists，我只是想更多地了解发生了什么。

请假设我不知道 HashMap 是如何工作的，因为我不知道:)

谢谢

Answer 1

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

• 几乎所有人都知道，列表是一个由连续整数索引的容器。
• HashMap 、字典或关联数组是一个容器，其索引可以是任何类型。字典通常是用字符串索引的。

为了便于讨论，我们将列表命名为 L和我们的词典 D .

列表具有真正的随机访问。如果您知道某个项目的索引，则可以在恒定时间内查找该项目。字典的情况并非如此，它们通常采用基于哈希的算法来实现高效的随机访问。

当您尝试查找值时，排序列表可以执行二分搜索。查找值 V 是获取索引 I 的行为，使得 L[I]=V 。二分查找非常有效。如果列表未排序，则必须执行线性搜索，效率要低得多。排序列表可以使用插入排序来维护列表的顺序 - 当添加新项目时，它会被插入到正确的位置。

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

在旧版本的 Delphi 中，从字符串列表中诱导字典行为是很常见的。表现很糟糕。内容缺乏灵 active 。

对于现代 Delphi，有 TDictionary ，一个可以容纳任何东西的通用类。该实现使用了哈希，虽然我没有亲自测试过它的性能，但我认为它是值得尊敬的。

有一些常用的算法可以最佳地使用所有这些容器:未排序的列表、排序的列表、字典。您只需使用正确的方法来解决当前的问题即可。