如何使用自定义相等比较器创建词典?

qnakjoqk  于 2022-09-21  发布在  其他
关注(0)|答案(3)|浏览(202)

要创建具有自定义相等比较的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))

因此,我需要给出函数EqualsGetHashCode的实现。但我只想给出equals函数的实现。有可能吗?

gg0vcinb

gg0vcinb1#

但我只想给出一个equals函数的实现。有可能吗?

不是的。您需要同时实现EqualityComparisonHasher函数。

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

平等对比

字典是存储键值对的集合,其中键必须是唯一的。密钥的唯一性最终由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>.Construct(
   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键中的值。

那么,如何解决这个问题呢?什么才是正确的hasher功能。

由于散列器函数必须满足的唯一条件是相等的键必须具有相同的散列值,所以最简单(最愚蠢)的实现将只是为所有键返回相同的固定整数值--所有键将属于相同的桶。

将上例中的hasher函数替换为下面的hasher函数将产生正确的结果

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

然而,这种愚蠢的hasher功能将对词典性能产生负面影响。对不区分大小写的键产生相同散列值的散列器函数返回字符串长度,而不是固定值。

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

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

eeq64g8w

eeq64g8w2#

TDictionaryTObjectDictionary需要散列密钥。如果你想使用TDelegatedEqualityComparer,那么你必须为它提供一个生成散列的函数,这就是它的工作方式。

但是,如果您不想从头开始编写您自己的散列代码,您可以利用RTL对AnsiString的本机散列,例如:

function(const Value: AnsiString): Integer
begin
  Result := TEqualityComparer<AnsiString>.Default.GetHashCode(Value);
end

它最终将委托给名为GetHashCode_LString()的内部函数,该函数将AnsiString数据传递给可从System.Generics.Defaults单元公开访问的BobJenkinsHash()函数,因此您可以直接调用该函数,例如:

function(const Value: AnsiString): Integer
begin
  Result := BobJenkinsHash(PAnsiChar(Value)^, Length(Value) * SizeOf(AnsiChar), 0);
end

或者,正如函数的documentation在XE8+中所说:

警告:BobJenkinsHash已弃用。请使用Hash.THashBobJenkins.GetHashValue()

uses
  System.Hash; 

function(const Value: AnsiString): Integer
begin
  Result := THashBobJenkins.GetHashValue(PAnsiChar(Value)^, Length(Value) * SizeOf(AnsiChar)); 
end
x4shl7ld

x4shl7ld3#

但我只想给出一个equals函数的实现。有可能吗?

不是的。您必须提供散列函数。这是一本词典所需要的。

相关问题