时间戳

首页 > 解决方案 > 如何使用自定义平等比较器创建字典？

delphi - 如何使用自定义平等比较器创建字典？

问题描述

要创建一个TObjectDictionary<ansiString, boolean>具有自定义平等比较我必须做的：

TObjectDictionary<ansiString, boolean>.create(
  TDelegatedEqualityComparer<ansiString>.Create(
   function(const Left, Right: ansiString): Boolean
   begin
     Result := ALSameText(Left, Right);
   end,
   function(const Value: ansiString): Integer
   begin
     // !! here i want the default GetHashCode !! I don't want to write it myself 
   end))

所以我需要为函数Equals和GetHashCode提供一个实现。但我只想为Equals函数提供一个实现。可能吗？

标签： delphi

解决方案

但我只想为 Equals 函数提供一个实现。可能吗？

不，您需要同时提供EqualityComparison和Hasher功能的实现。

为了正确地做到这一点，您需要了解这些函数在字典实现中的用途。

平等比较

字典是存储键值对的集合，其中键必须是唯一的。密钥的唯一性最终由EqualityComparison功能决定。根据该函数的实现，字典将存储和更新与特定键关联的值。

例如，带有字符串键的字典可能要求不同的键必须完全匹配，包括大小写。对于这样的实现，“abc”和“ABC”将是两个不同的键，您可以存储与每个键关联的不同值。这是带有字符串键的 Delphi 字典的默认实现。

abc -> true
ABC -> false

存储上面的键值对将导致字典有两对。设置 'ABC' 键值后，您仍然可以检索未更改的 'abc' 值，这将是真的。

但是，带有字符串键的字典也可以以不区分大小写的方式实现，其中“abc”和“ABC”将是相同的键。这是您在示例中的一种实现。

abc -> true
ABC -> false

在不区分大小写的字典中存储上述键值对将导致字典仅包含单个对。存储 ABC 键值后，原始 abc 值将丢失，读取存储在 abc 或 ABC 键中的值将返回 false。

理论上，您可以在不需要Hasher功能的地方实现字典。

哈希器

如果Hasher不需要该功能，它的目的是什么？

哈希函数是快速从字典中检索值的原因。它根据键哈希值划分存储在桶中的键值对。因此，与其遍历所有键直到找到特定键，不如仅在特定桶中搜索键，并且在该桶中相等比较将用于最终确定两个键是否匹配。

因此，Hasher函数需要在程序运行期间为每个唯一键生成相同的哈希值。不同的键可以有相同的哈希值——冲突是可以接受的。字典的性能最终取决于哈希函数的性能和冲突次数（但是，选择不同主题的最佳哈希函数）

如果您需要不区分大小写的字符串字典，则默认散列函数将不起作用，因为键中的不同大小写可能导致不同的散列值。

procedure Test;
var
  d: TDictionary<string, boolean>;
  b: Boolean;
begin
  d := TDictionary<string, boolean>.Create(
  TDelegatedEqualityComparer<string>.Create(
   function(const Left, Right: string): Boolean
   begin
     Result := SameText(Left, Right);
   end,
   function(const Value: string): Integer
   begin
     Result := THashBobJenkins.GetHashValue(PChar(Value)^, Length(Value) * SizeOf(Char));
   end));

  d.AddOrSetValue('abc', true);
  d.AddOrSetValue('ABC', false);

  b := d.Items['abc'];
  Writeln(b); // TRUE 

  b := d.Items['ABC'];
  Writeln(b); // FALSE
end;

运行上面的代码会输出

TRUE 
FALSE

这不是我们想要的。我们希望 ABC 键的设置值覆盖存储在 abc 键中的值。

那么如何解决呢？什么是正确的哈希函数。

由于哈希函数必须满足的唯一条件是相等的键必须具有相同的哈希值，因此最简单（最愚蠢的）实现将只是为所有键返回相同的固定整数值——所有键将属于同一个桶。

用以下示例替换前面示例中的哈希函数将产生正确的结果

   function(const Value: string): Integer
   begin
     Result := 0;
   end));

但是，这种愚蠢的哈希函数会对字典性能产生负面影响。对于不区分大小写的键，会产生相同哈希值的稍微更好的哈希函数返回字符串长度而不是固定值。

   function(const Value: string): Integer
   begin
     Result := Length(Value);
   end));

这只是适用于不区分大小写要求的可能散列函数之一。找到更好的最终取决于什么是典型的键值 - 例如，如果字典中的所有键都具有相同的长度，那么基于长度的哈希函数将执行（实际上，更糟）与固定值之一一样糟糕。

推荐阅读