Qual è il modo migliore per attuare questo GetHashCode composito()

Question

Ho una classe semplice:

public class TileName { 
    int Zoom, X, Y; 

    public override bool Equals (object obj) 
    { 
     var o = obj as TileName; 
     return (o != null) && (o.Zoom == Zoom) && (o.X == X) && (o.Y == Y); 
    } 

    public override int GetHashCode() 
    { 
     return (Zoom + X + Y).GetHashCode(); 
    } 
} 

ero curioso di sapere se avrei avuto una migliore distribuzione dei codici hash se invece ho fatto qualcosa di simile:

public override int GetHashCode() 
    { 
     return Zoom.GetHashCode() + X.GetHashCode() + Y.GetHashCode(); 
    } 

Questa classe verrà utilizzata come chiave del dizionario, quindi voglio essere sicuro che ci sia una distribuzione decente.

Answer 1

Come descritto da Jon Skeet in this SO answer, è consigliabile selezionare alcuni numeri primi e moltiplicarli con i singoli codici hash, quindi sommare tutto.

public int GetHashCode() 
{ 
    unchecked 
    { 
     int hash = 17; 
     // Maybe nullity checks, if these are objects not primitives! 
     hash = hash * 23 + Zoom.GetHashCode(); 
     hash = hash * 23 + X.GetHashCode(); 
     hash = hash * 23 + Y.GetHashCode(); 
     return hash; 
    } 
} 

I problemi con xor hash sono:

• se X è pari a Y allora il vostro hash sarà solo dello zoom, perché poi X^Y = X^X = 0 tiene
• xor è un operatore simmetrica, produrrà gli stessi identici hash per gli oggetti [Zoom = 3, X = 5, Y = 7], [Zoom = 3, X = 7, Y = 5], [Zoom = 7, X = 5, Y = 3] ecc.

Questi fatti rendono il metodo xor più probabile che causi collisioni.

Oltre a Jons, considerare l'utilizzo di un contesto unchecked per ignorare esplicitamente gli overflow. Perché come il MSDN dice:

Se né checked né unchecked è utilizzato, un'espressione costante utilizza l'overflow predefinita il controllo in fase di compilazione tempo, che viene controllata. Altrimenti, se l'espressione non è costante, il controllo di overflow di runtime dipende da altri fattori quali le opzioni del compilatore e la configurazione dell'ambiente.

Quindi, mentre di solito gli overflow saranno deselezionati, potrebbe essere che non riesca in qualche modo in qualche ambiente o sia stato costruito con un'opzione del compilatore. Ma in questo caso si desidera esplicitamente non controllare questi overflow.

Aggiornamento:

A proposito: someInt.GetHashCode() rendimenti someInt. In questo modo, è ovviamente la distribuzione più veloce possibile e perfetta senza una singola collisione. In quale altro modo si potrebbe mappare un int a un hash-int? :) Quindi quello che volevo dire: Il suo primo approccio:

return (Zoom + X + Y).GetHashCode(); 

e la tua seconda:

return Zoom.GetHashCode() + X.GetHashCode() + Y.GetHashCode(); 

sono esattamente gli stessi. Non è nemmeno necessario chiamare GetHashCode ed è molto probabile che entrambi abbiano collisioni. Forse anche peggio del metodo xor, se molto probabilmente hai valori interi piccoli per tutti e tre i valori.

Aggiornamento 2:

Come ho scritto nel commento a ChaosPandions inviare: Se v'è solo quei tre valori int, e X, Y e Zoom sono relativamente piccoli numeri (più piccoli di 1000 o 10000) questo uno può essere anche un buon generatore di hash:

public int GetHashCode() 
{ 
    return (X << 16)^(Y << 8)^Zoom; 
} 

Si distribuisce solo i bit del valore hash (esempio in big-endian per migliorare la leggibilità):

00000000 00000000 00000011 00110001 X = 817 
00000000 00000000 00011011 11111010 Y = 7162 
00000000 00000000 00000010 10010110 Zoom = 662 

00000011 00110001 00000000 00000000 X << 16 
00000000 00011011 11111010 00000000 Y << 8 
00000000 00000000 00000010 10010110 Zoom 

00000011 00101010 11111000 10010110 (X << 16)^(Y << 8)^Zoom 

Answer 2

public override int GetHashCode() 
{ 
    return (Zoom.ToString() + "-" + X.ToString() + "-" + Y.ToString()).GetHashCode(); 
} 

Answer 3

Ho trovato davvero efficace.

public override int GetHashCode() 
{ 
    return Zoom.GetHashCode()^X.GetHashCode()^Y.GetHashCode(); 
} 

Answer 4

Nessuna delle implementazioni nella domanda è l'ideale. Ad esempio, torneranno esattamente lo stesso hash per { Zoom=1, X=2, Y=3 }, { Zoom=2, X=3, Y=1 }, { Zoom=3, X=1, Y=2 } ecc ecc

io di solito uso qualcosa di simile:

public override int GetHashCode() 
{ 
    // 269 and 47 are primes 
    int hash = 269; 
    hash = (hash * 47) + Zoom.GetHashCode(); 
    hash = (hash * 47) + X.GetHashCode(); 
    hash = (hash * 47) + Y.GetHashCode(); 
    return hash; 
} 

(Dalla memoria, penso che il compilatore C# utilizza qualcosa di simile quando genera i metodi GetHashCode per i tipi anonimi.)