delphi TDictionary 与 TStringList 评测对比

在国际Delphi Praxis论坛上以“字典，哈希和性能”为主题，我做了一些时间比较Delphi运行时库中可用于存储按字符串索引的数据的数据结构的性能：

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

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

一个TDictionary  (从 Delphi 2009开始可用)

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

该测试向每个结构添加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);
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进行编译，我得到以下时间：

编辑：我刚刚发现，改变了代号为THashedStringlist使用查找使用的IndexOf减少的时间将条目添加到大约在同一时间为的IndexOf。因此，两者都是大约4秒。这使我想知道THashedStringList中是否存在错误，因为它没有覆盖AddObject。它只是从TStringList继承而来，对于已排序的列表，TStringList会调用Find来查看字符串是否已在列表中。与IndexOf相比，Find方法不使用哈希，因此它的速度与TStringList中的速度一样慢。但这也许是有目的的，因为对于所有条目而言，哈希的计算都相当频繁。我得到的印象是THashedStringList的实现不是很好，并且没有人注意到它，因为它已经足够好了。

EDIT2：由于仅在TMemIniFile中使用它来快速访问条目，而无需对其进行排序，因此实现可能就足够了。我的测试上面不检查添加的表现为无序THashedStringList这就是TMemIniFile使用。