3

我只是好奇，因为最近我看到了 Java 中 Hashmaps 的使用，并且想知道 Delphi 的 Sorted String 列表是否完全相似。

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

我经常使用 Sorted TStringLists，我只是想进一步了解发生了什么。

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

谢谢

4

6 回答 6

5

我很笼统地将这个问题解释为对列表和字典的概述的请求。

  • 几乎每个人都知道，列表是一个由连续整数索引的容器。
  • 哈希映射、字典或关联数组是其索引可以是任何类型的容器。很常见的是，字典是用字符串索引的。

为了争论起见，让我们调用我们的列表L和字典D。

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

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

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

在旧版本的 Delphi 中，从字符串列表中哄骗字典行为是很常见的。表演很糟糕。内容几乎没有灵活性。

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

有一些常用的算法可以优化使用所有这些容器：未排序列表、排序列表、字典。您只需要使用正确的方法来解决手头的问题。

于 2011-02-25T07:39:36.060 回答
4

TStringList 将字符串保存在一个数组中。

如果您在其他未排序（已排序属性 = false）的字符串列表上调用 Sort，则执行 QuickSort 以对项目进行排序。

如果将 Sorted 设置为 true，也会发生同样的情况。

如果您在未排序的字符串列表上调用 Find（或调用 find 的 IndexOf）（Sorted 属性 = false，即使您显式调用了 Sort，如果 Sorted 属性不为 true，则该列表也被视为未排序）然后执行线性搜索，比较所有从开始直到找到匹配的字符串。

如果您在已排序的字符串列表（Sorted property = true）上调用 Find，则执行二进制搜索（有关详细信息，请参阅http://en.wikipedia.org/wiki/Binary_search）。

如果将字符串添加到已排序的字符串列表中，则会执行二进制搜索以确定正确的插入位置，数组中的所有后续元素都会移动 1 并插入新字符串。

由于这种插入性能变得更差，字符串列表越大。如果要将大量条目插入已排序的字符串列表，通常最好关闭排序，插入字符串，然后将 Sorted 设置回 true 以执行快速排序。

这种方法的缺点是您将无法防止插入重复项。

编辑：如果你想要一个哈希映射，请使用单元 Generics.Collections 中的 TDictionary

于 2011-02-25T03:18:13.983 回答
1

你可以看看源代码，因为它是 Delphi 自带的。Ctrl-单击代码中的“排序”调用。

它在非 Unicode Delphi 中是一种简单的字母排序，在后来的版本中是一种稍微复杂的 Unicode。您可以为自定义排序顺序提供自己的比较。不幸的是，我没有最新版本的 Delphi，因此无法确认，但我希望在后台有适当的 Unicode 感知和区域设置感知字符串比较例程。Unicode 排序/字符串比较不是微不足道的，一点点网络搜索就会指出一些陷阱。

当您在字符串或附加到它们的对象（Objects 属性）中分隔文本时，通常会提供您自己的比较例程。在这些情况下，您通常会按对象的属性或字符串中第一个字段以外的其他内容进行排序。或者它可能就像想要对字符串进行数字排序一样简单（所以“2”出现在“1”之后而不是“19”之后）

于 2011-02-25T02:28:46.667 回答
1

还有一个THashedStringList，它可能是一个选项（尤其是在较旧的 Delphi 版本中）。

于 2011-02-25T08:22:33.747 回答
0

顺便说一句，TStringList 的 Unicode 排序例程非常慢。如果您覆盖 TStringList.CompareStrings 方法，那么如果字符串仅包含 Ansi 字符（如果您专门使用英语，它们会），您可以使用自定义的 Ansi 字符串比较。我使用自己定制的 TStringList 类来执行此操作，它比 TStringList 类快 4 倍，用于从列表读取和写入字符串的排序列表。

于 2011-02-25T13:53:59.787 回答
0

Delphi 的字典类型（在支持泛型的 Delphi 版本中）最接近于 Delphi 附带的 hashmap。THashedStringList 使查找比在排序的字符串列表中更快。您可以在已排序的字符串列表中使用二进制搜索进行查找，因此它比蛮力搜索快，但不如哈希快。

散列的一般理论是它是无序的，但在查找和插入时非常快。排序列表在插入时相当快，直到列表的大小变大，尽管它不如插入字典效率高。

列表的最大好处是它是有序的，但哈希查找字典不是。

于 2011-02-27T02:10:07.333 回答