What is the canonical way to write a hasher function for TEqualityComparer.Construct?

delphi, delphi-xe2, hash

Solution

The Effective Java (by Joshua Bloch) section about overriding hashCode could be useful. It shows how the individual parts of the object (or record) can be combined to efficiently construct a 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:

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

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;`

Return `result`.

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.

This can be translated into Delphi code as follows:

{$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}

This then allows the implementation of `MyRecordHasher`:

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

Problem

Consider the following record: ``` TMyRecord = record b: Boolean; // 3 bytes of padding in here with default record alignment settings i: Integer; end; ``` I wish to implement `IEqualityComparer<TMyRecord>`. In order to do so I want to call `TEqualityComparer<TMyRecord>.Construct`. This needs to be supplied with a `TEqualityComparison<TMyRecord>` which presents no problems to me. However, `Construct` also requires a `THasher<TMyRecord>` and I would like to know the canonical method for implementing that. The function needs to have the following form: ``` function MyRecordHasher(const Value: TMyRecord): Integer; begin Result := ??? end; ``` I expect that I need to call `BobJenkinsHash` on both fields of the record value and then combine them some how. Is this the right approach, and how should I combine them? The reason I don't use `TEqualityComparison<TMyRecord>.Default` is that it uses `CompareMem` and so will be incorrect due to the record's padding.

Original source