delphi - 为 TEqualityComparer.Construct 编写哈希函数的规范方法是什么？

Question

考虑以下记录:

TMyRecord = record
  b: Boolean;
  // 3 bytes of padding in here with default record alignment settings
  i: Integer;
end;

我希望实现IEqualityComparer<TMyRecord> 。为此，我想调用 TEqualityComparer<TMyRecord>.Construct 。这需要提供 TEqualityComparison<TMyRecord>这对我来说没有任何问题。

但是，Construct还需要 THasher<TMyRecord>我想知道实现这一点的规范方法。该函数需要具有以下形式:

function MyRecordHasher(const Value: TMyRecord): Integer;
begin
  Result := ???
end;

我预计我需要调用 BobJenkinsHash记录值的两个字段，然后如何将它们组合起来。这是正确的方法吗？我应该如何将它们结合起来？

我不使用TEqualityComparison<TMyRecord>.Default的原因是它使用 CompareMem由于记录的填充，因此将不正确。

Answer 1

Effective Java (by Joshua Bloch)关于覆盖 hashCode 的部分可能会有用。它展示了如何组合对象(或记录)的各个部分来有效地构造 hashCode。

A good hash function tends to produce unequal hash codes for unequal objects. This is exactly what is meant by the third provision of the hashCode contract. Ideally, a hash function should distribute any reasonable collection of unequal instances uniformly across all possible hash values. Achieving this ideal can be extremely difficult. Luckily it is not too difficult to achieve a fair approximation. Here is a simple recipe:

1. Store some constant nonzero value, say 17, in an int variable called result.

2. For each significant field f in your object (each field taken into account by the equals method, that is), do the following:

   a. Compute an int hash code c for the field: ..... details omitted ....

   b. Combine the hash code c computed in step a into result as follows: result = 37*result + c;

3. Return result.

4. When you are done writing the hashCode method, ask yourself whether equal instances have equal hash codes. If not, figure out why and fix the problem.

这可以翻译成 Delphi 代码如下:

{$IFOPT Q+}
  {$DEFINE OverflowChecksEnabled}
  {$Q-}
{$ENDIF}
function CombinedHash(const Values: array of Integer): Integer;
var
  Value: Integer;
begin
  Result := 17;
  for Value in Values do begin
    Result := Result*37 + Value;
  end;
end;
{$IFDEF OverflowChecksEnabled}
  {$Q+}
{$ENDIF}

这样就可以实现MyRecordHasher:

function MyRecordHasher(const Value: TMyRecord): Integer;
begin
  Result := CombinedHash([IfThen(Value.b, 0, 1), Value.i]);
end;