Delphi Dictionary and ordering data

Question

My code is:

procedure TfrmSettings.btnFillDictClick(Sender: TObject);
var
  Dict: TDictionary<string, string>;
  Item: TPair<string, string>;
begin
  Dict := TDictionary<string, string>.Create();

  Dict.Add('Key1', 'Text1');
  Dict.Add('Key2', 'Text2');
  Dict.Add('Key3', 'Text3');
  Dict.Add('Key4', 'Text4');

  for Item in Dict do
  begin
    ShowMessage(Item.Key + ' ' + Item.Value);
  end;    
end;

Why almost every time I'm getting a different value in Showmessage?
Why values are not stored in the order in which they were added?

I'm a noob in Delphi and do not know how Dictionary is working. And I didn't find any information about this in Google. Could you please explain me why it is so?
Is there any way to use Dictionary without using TList<> for sort data?

Thanks

Answer 1

Dictionary does not maintain order of elements because the way it is internally organized as look up table and it is ordered by the hash of the key. They are optimized for speed and not to preserve ordering.

If you need to maintain order of elements you need pair list instead of dictionary. Delphi does not provide that out of the box. You can use following code to implement simple pair list and customize it for your needs.

type
  TPairs<TKey, TValue> = class(TList < TPair < TKey, TValue >> )
  protected
    fKeyComparer: IComparer<TKey>;
    fValueComparer: IComparer<TValue>;
    function GetValue(Key: TKey): TValue;
    procedure SetValue(Key: TKey; const Value: TValue);
    function ComparePair(const Left, Right: TPair<TKey, TValue>): Integer;
  public
    constructor Create; overload;
    procedure Add(const aKey: TKey; const aValue: TValue); overload;
    function IndexOfKey(const aKey: TKey): Integer;
    function ContainsKey(const aKey: TKey): Boolean; inline;
    property Values[Key: TKey]: TValue read GetValue write SetValue;
  end;

constructor TPairs<TKey, TValue>.Create;
begin
  if fKeyComparer = nil then fKeyComparer := TComparer<TKey>.Default;
  if fValueComparer = nil then fValueComparer := TComparer<TValue>.Default;
  inherited Create(TDelegatedComparer <TPair<TKey, TValue>>.Create(ComparePair));
end;

function TPairs<TKey, TValue>.ComparePair(const Left, Right: TPair<TKey, TValue>): Integer;
begin
  Result := fKeyComparer.Compare(Left.Key, Right.Key);
  if Result = 0 then Result := fValueComparer.Compare(Left.Value, Right.Value);
end;

function TPairs<TKey, TValue>.IndexOfKey(const aKey: TKey): Integer;
var
  i: Integer;
begin
  Result := -1;
  for i := 0 to Count - 1 do
    if fKeyComparer.Compare(Items[i].Key, aKey) = 0 then
      begin
        Result := i;
        break;
      end;
end;

function TPairs<TKey, TValue>.ContainsKey(const aKey: TKey): Boolean;
begin
  Result := IndexOfKey(aKey) >= 0;
end;

function TPairs<TKey, TValue>.GetValue(Key: TKey): TValue;
var
  i: Integer;
begin
  i := IndexOfKey(Key);
  if i >= 0 then Result := Items[i].Value
  else Result := default (TValue);
end;

procedure TPairs<TKey, TValue>.SetValue(Key: TKey; const Value: TValue);
var
  i: Integer;
  Pair: TPair<TKey, TValue>;
begin
  i := IndexOfKey(Key);
  if i >= 0 then FItems[i].Value := Value
  else
    begin
      Pair.Create(Key, Value);
      inherited Add(Pair);
    end;
end;

procedure TPairs<TKey, TValue>.Add(const aKey: TKey; const aValue: TValue);
begin
  SetValue(aKey, aValue);
end;

And then you can use it the same way you would use dictionary, but order of elements will be maintained.

var
  Pairs: TPairs<string, string>;
  Item: TPair<string, string>;
begin
  Pairs := TPairs<string, string>.Create();

  Pairs.Add('Key1', 'Text1');
  Pairs.Add('Key2', 'Text2');
  Pairs.Add('Key3', 'Text3');
  Pairs.Add('Key4', 'Text4');
  Pairs.Add('Key5', 'Text5');

  for Item in Pairs do
    begin
      Memo1.Lines.Add(Item.Key + ' ' + Item.Value);
    end;
end;

---

SetValue update for newer Delphi versions where FItems is not available in TList<T> descendant classes.

procedure TPairs<TKey, TValue>.SetValue(Key: TKey; const Value: TValue);
var
  i: Integer;
  Pair: TPair<TKey, TValue>;
begin
  i := IndexOfKey(Key);
  if i >= 0 then
    begin
      Pair := Items[i];
      Pair.Value := Value;
      Items[i] := Pair;
    end
  else
    begin
      Pair.Create(Key, Value);
      inherited Add(Pair);
    end;
end;