¿Cuál es la forma canónica de escribir una función hasher para TEqualityComparer.Construct?

Question

Considérese el siguiente registro:

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

deseo de implementar IEqualityComparer<TMyRecord>. Para hacerlo, quiero llamar al TEqualityComparer<TMyRecord>.Construct. Esto necesita ser provisto con un TEqualityComparison<TMyRecord> que no me presenta ningún problema.

Sin embargo, Construct también requiere un THasher<TMyRecord> y me gustaría conocer el método canónico para implementarlo. La función debe tener la siguiente forma:

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

espero que necesito llamar BobJenkinsHash en ambos campos del valor de registro y luego combinar de alguna forma. ¿Es este el enfoque correcto, y cómo debería combinarlos?

La razón por la que no uso TEqualityComparison<TMyRecord>.Default es que usa CompareMem y, por lo tanto, será incorrecta debido al relleno del registro.

Answer 1

La sección Effective Java (by Joshua Bloch) sobre la anulación de hashCode podría ser útil. Muestra cómo las partes individuales del objeto (o registro) se pueden combinar para construir de manera eficiente un código hash.

Una buena función hash tiende a producir códigos hash desiguales para objetos desiguales . Esto es exactamente lo que significa la tercera disposición del contrato hashCode . Idealmente, una función hash debería distribuir cualquier colección razonable de instancias desiguales uniformemente en todos los posibles valores hash. Lograr este ideal puede ser extremadamente difícil. Afortunadamente, no es demasiado difícil lograr una aproximación justa. Aquí es una receta sencilla:

1. tienda algún valor distinto de cero constante, digamos 17, en una variable llamada intresult.

2. Para cada campo significativo f en su objeto (cada campo tenidos en cuenta por el método equals, que es), haga lo siguiente:

   a. Calcular un código hash de intc para el campo: ..... detalles omitidos ....

   b. Combinar el código hash c calculado en el paso a en resultado de la siguiente manera: result = 37*result + c;

3. Volver result.

4. Cuando haya terminado de escribir el método hashCode, pregúntese si instancias iguales tienen los mismos códigos hash. Si no, averigüe por qué y solucione el problema.

Esto se puede traducir en código de Delphi de la siguiente manera:

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

Esto permite entonces la aplicación de MyRecordHasher:

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