我只是好奇，最近我已經看到在Java中使用Hashmaps，並想知道Delphi的Sorted String列表是否完全相似。Sorted TStringList，排序是如何工作的？
TStringList對象是否生成一個散列用作每個項目的索引？那麼如何通過Find函數檢查字符串列表中的搜索字符串？
我經常使用Sorted TStringLists，我只想了解一些事情。
請假設我不知道哈希映射是如何工作的，因爲我不:)
感謝
我正在解釋這個問題，一般來說，作爲對列表和字典的概述的請求。
爲了讓我們打電話給我們的名單L和我們的字典D。
列表具有真正的隨機訪問。如果你知道它的索引，一個項目可以在恆定的時間查找。字典並非如此，他們通常使用基於散列的算法來實現高效的隨機訪問。
當您嘗試查找值時，排序列表可以執行二分搜索。找到一個值V，就是獲得索引的行爲I，例如L[I]=V。二進制搜索非常有效。如果列表沒有排序，那麼它必須執行線性搜索，效率要低得多。排序列表可以使用插入排序來維護列表的順序 - 添加新項目時，它會插入到正確的位置。
您可以將字典視爲<Key,Value>對的列表。您可以遍歷所有對，但更常見的是，您可以使用索引標記查找給定鍵的值：D[Key]。請注意，這與在列表中查找值的操作不同 - 它是在知道索引I時閱讀L[I]的類似物。
在舊版本的Delphi中，通常會將字典行爲與字符串列表。表演很糟糕。內容幾乎沒有靈活性。
隨着現代德爾福，有TDictionary，一個可以容納任何東西的泛型類。該實現使用散列，雖然我沒有親自測試過它的性能，但我知道它是值得尊敬的。
有最佳使用所有這些容器的常用算法：未排序列表，排序列表，字典。您只需要使用正確的問題即可解決問題。
我從來沒有經歷過TStringList表現爲'可怕'，但這可能是因爲我幾乎沒有把數以萬計的物品放在它裏面。很好的解釋，儘管它沒有提到任何地方的quicksort，實際上這是TStringList使用的排序。 – GolezTrol 2011-02-25 16:00:03
@Golez當列表被「排序」時，它使用插入排序。當你在未排序的列表上調用'Sort（）'時，它使用快速排序。當用作列表時，字符串列表的性能非常好，但當被強制爲像字典時，性能很差。 – 2011-02-25 16:03:40
你可以看看源代碼，因爲自帶的德爾福。按Ctrl-點擊代碼中的「排序」調用。
這是在非Unicode Delphi中的一個簡單的字母順序排序，以及稍後版本中稍微更復雜的Unicode排序。您可以提供您自己的自定義排序順序比較。不幸的是，我沒有Delphi的最新版本，因此無法確認，但我期望在引擎蓋下有適當的Unicode識別和區域識別字符串比較例程。 Unicode排序/字符串比較不是微不足道的，有點網絡搜索會指出一些缺陷。
提供自己的比較例程通常是在字符串或附加到它們的對象（Objects屬性）中分隔文本時完成的。在這些情況下，你經常會根據對象的屬性或字符串中第一個字段以外的內容進行排序。或者它可能就像想要在字符串上進行數字排序一樣簡單（所以「2」在「1」之後而不是在「19」之後）
謝謝，是的，我曾經想過看看源代碼，但是我認爲（不好），它會比遍歷比較的列表更復雜。 – CatalystNZ 2011-02-25 02:50:53
@CatalystNZ，如果你沒有設置Sorted爲true，它只會進行線性搜索。將Sorted設置爲true時，會執行快速的二進制搜索。 – 2011-02-25 03:19:46
默認TStringList.Sort使用QuickSort算法，不存在散列或任何涉及的內容。如果將字符串添加到已排序的列表中，則TStringList使用二進制搜索Find方法找到正確的位置，然後使用System.Move「打開」一個間隙來添加新項目。在長列表中，內存移動可能是最慢的部分，除非您使用慢速自定義比較方法。 – 2011-02-25 03:26:41
TStringList將字符串保存在數組中。
如果您對其他未排序的（Sorted property = false）字符串列表調用Sort，則會執行QuickSort對項目進行排序。
如果將Sorted設置爲true，則會發生同樣的情況。
如果您在未排序的字符串列表中調用Find（或IndexOf，它調用find）（Sorted property = false，即使您顯式調用Sort如果Sorted屬性不爲true，比較從開始到找到匹配的所有字符串。
如果調用查找排序的字符串列表（Sorted屬性=真）則執行二進制搜索（見http://en.wikipedia.org/wiki/Binary_search瞭解詳細信息）。
如果您添加一個字符串的排序字符串列表，執行二進制搜索，以確定正確的插入位置，陣列中的所有元素之後由一個移，新的字符串被插入。
由於此插入性能變得更糟，字符串列表越大。如果你想插入大量條目爲已排序字符串列表，它通常是更好地把分揀關閉，插入字符串，然後一組分類回真正的執行快速排序。
這種方法的缺點是，你將無法防止重複插入。
編輯：如果你想要一個哈希映射，使用TDictionary從單位泛型。收藏
+1中還有一個簡單的THashedStringList，用於'在大型列表中插入多個項目時排序「。人們往往會忘記這一點，並在插入數千個項目時抱怨字符串列表的性能。 – GolezTrol 2011-02-25 16:03:04
您可以通過設置Capacity屬性來分配足夠的空間，以獲得更快的速度。這將防止stringlist在新項目不適合時不得不重新分配整個數組。 Stringlist確實增加了大塊的容量，但如果知道項目的數量，最好自己設置容量。 – GolezTrol 2011-02-25 16:04:24
在添加時留下插入的問題實際上是每次插入時的內存副本。添加到列表的末尾基本上是免費的。在中間插入成本。其他種類的時間複雜性也是一樣的。 – 2011-02-25 20:14:34
還有一個THashedStringList，這可能是一個選項（特別是在舊的Delphi版本中）。
順便說一下，TStringList的Unicode排序例程很慢。如果您重寫TStringList.CompareStrings方法，那麼如果這些字符串只包含Ansi字符（如果您僅使用英語，它們將會），您可以使用定製的Ansi字符串比較。我使用我自己定製的TStringList類來完成此操作，它比TStringList類的排序列表快4倍，以便從列表讀寫字符串。
德爾福的字典類型（在Delphi的泛型啓用版本中）是與Delphi一起發佈的哈希映射最接近的。 THashedStringList使查找速度比在排序的字符串列表中更快。你可以在排序的字符串列表中使用二進制搜索來進行查找，所以它比蠻力搜索更快，但速度不如散列快。
散列的一般理論是它是無序的，但在查找和插入時非常快速。排序列表的插入速度相當快，直到列表的大小變大，儘管它不如字典插入效率高。
列表最大的好處是它是有序的，但是哈希查找字典不是。
使用的排序算法是QuickSort。 – 2011-02-25 03:18:19