delphi TStringList 与 THashedStringList 与 TDictionary

受国际Delphi Praxis论坛中的Dictionaries、Hashing 和 Performance主题的提示，我做了一些时间来比较 Delphi 运行时库中可用于存储按字符串索引的数据的数据结构的性能：

一个排序的、区分大小写的TStringList（从 Delphi 6 开始可用）

一个排序的、区分大小写的THashedStringList（从 Delphi 6 开始可用）

一个TDictionary <字符串，整数>（购自一个Delphi 2009）

以防万一您不知道 THashedStringList：它是 System.IniFiles 中声明的 TStringList 后代。它用于加快对 TMemIniFile 的访问。（编辑：正如Uwe Raabe 指出的那样，这不再正确。从 Delphi 10.3 开始（可能更早，我还没有检查过）TMemIniFile 也使用 TDictionary<string,Integer>。）

该测试将 676 个字符串（'AA' .. 'ZZ'）添加到每个结构中，并执行 10000 次（这意味着在添加时要进行很多重复检查）。然后 - 再次 10000 次 - 它对这些字符串中的每一个进行查找。

当然，这只是一个简单的测试，既不是大量的条目，也不是长字符串。我只是想感受一下这些结构的性能。

下面是 TStringList 和 THashedStringList 的主要代码：

procedure Tf_HashedStringListTest.DoTiming(sl: TStringList);
const
  CYCLES = 10000;
var
  k: integer;
  i: integer;
  j: integer;
  sw: TStopwatch;
  s: string;
  Idx: Integer;
begin
  sl.Sorted := True;
  sl.CaseSensitive := True;
  sl.Duplicates := dupError;
  sw := TStopwatch.StartNew;
  sl.BeginUpdate;
  for k := 1 to CYCLES do begin
    for i := Ord('A') to Ord('Z') do begin
      for j := Ord('A') to Ord('Z') do begin
        s := chr(i) + chr(j);
        if not sl.Find(s, Idx) then
          sl.AddObject(s, Pointer(i * 100 + j));
      end;
    end;
  end;
  sl.EndUpdate;
  sw.Stop;
  m_Output.Lines.Add(sl.Count.ToString + ': Add: ' + sw.Elapsed.ToString);

  sw.Reset;
  sw.Start;
  for k := 1 to CYCLES do begin
    for i := Ord('A') to Ord('Z') do begin
      for j := Ord('A') to Ord('Z') do begin
        s := chr(i) + chr(j);
        sl.IndexOf(s);
      end;
    end;
  end;
  m_Output.Lines.Add(sl.Count.ToString + ': IndexOf: ' + sw.Elapsed.ToString);
end;

和 TDictionary 非常相似：

procedure Tf_HashedStringListTest.DoTiming(sl: TDictionary<string, integer>);
const
  CYCLES = 10000;
var
  k: integer;
  i: integer;
  j: integer;
  sw: TStopwatch;
  s: string;
  v: integer;
begin
  sw := TStopwatch.StartNew;
  for k := 1 to CYCLES do begin
    for i := Ord('A') to Ord('Z') do begin
      for j := Ord('A') to Ord('Z') do begin
        s := chr(i) + chr(j);
        if not sl.TryGetValue(s, v) then
          sl.Add(s, i * 100 + j);
      end;
    end;
  end;
  sw.Stop;
  m_Output.Lines.Add(sl.Count.ToString + ': Add: ' + sw.Elapsed.ToString);

  sw.Reset;
  sw.Start;
  for k := 1 to CYCLES do begin
    for i := Ord('A') to Ord('Z') do begin
      for j := Ord('A') to Ord('Z') do begin
        s := chr(i) + chr(j);
        sl.Items[s];
      end;
    end;
  end;
  m_Output.Lines.Add(sl.Count.ToString + ': IndexOf: ' + sw.Elapsed.ToString);
end;

结果并不令人意外：

TDictionary 大获全胜，其次是 THashedStringList，然后是 TStringList。两个字符串列表仅在 IndexOf 次数上有所不同，添加次数非常相似。

在我的计算机上，使用 AMD Phenom II XE 1090T 处理器并使用 Delphi 10.3 编译，我得到以下时间：

结构 添加时间 [秒] IndexOf [秒] 的时间

字符串列表 7.43 7.48

哈希字符串列表 7.45 4.40

TD词典 1.05 1.04

编辑：我刚刚发现将THashedStringlist的代码从使用Find更改为使用IndexOf将添加条目的时间减少到与IndexOf大致相同的时间。所以两者都是大约4秒。这让我怀疑THashedStringList 中是否存在错误，因为它没有覆盖AddObject。它只是从TStringList继承它，对于排序列表调用Find以查看字符串是否已经在列表中。与IndexOf相比，Find 方法不使用哈希，所以它和TStringList一样慢. 但也许这是故意的，因为所有条目的哈希计算得相当频繁。我的印象是THashedStringList没有很好地实现，没有人注意到，因为它已经足够好了。

EDIT2：由于它仅用于TMemIniFile以快速访问条目而无需对其进行排序，因此实现可能已经足够好了。我上面的测试没有检查 Add 的性能，因为它是TMemIniFile使用的未排序的THashedStringList。