.net - Qual è il miglior algoritmo per un System.Object.GetHashCode sottoposto a override?




algorithm (12)

Nel metodo .NET System.Object.GetHashCode viene utilizzato in molti posti, in tutte le librerie di classi di base .NET. Soprattutto quando si trovano oggetti in una collezione veloce o per determinare l'uguaglianza. Esiste un algoritmo standard / best practice su come implementare l'override GetHashCode per le mie classi personalizzate in modo da non degradare le prestazioni?


Tipo anonimo

Microsoft fornisce già un buon generatore generico di HashCode: copia i tuoi valori di proprietà / campo su un tipo anonimo e cancellalo:

new { PropA, PropB, PropC, PropD }.GetHashCode();

Questo funzionerà per qualsiasi numero di proprietà. Non usa il pugilato. Usa solo l'algoritmo già implementato nel framework per i tipi anonimi.

ValueTuple - Aggiornamento per C # 7

Come cita @cactuaroid nei commenti, è possibile utilizzare una tupla di valori. Ciò consente di risparmiare alcune sequenze di tasti e, più importante, viene eseguito esclusivamente nello stack (senza elementi inutili):

(PropA, PropB, PropC, PropD).GetHashCode();

(Nota: la tecnica originale che utilizza i tipi anonimi sembra creare un oggetto sull'heap, ovvero garbage, dato che i tipi anonimi sono implementati come classi, anche se questo potrebbe essere ottimizzato dal compilatore. Sarebbe interessante confrontare queste opzioni, ma il l'opzione tuple dovrebbe essere superiore.)


Di solito vado con qualcosa di simile all'implementazione data nel favoloso Efficace Java di Josh Bloch. È veloce e crea un hash piuttosto buono, che è improbabile che causi collisioni. Scegli due numeri primi diversi, ad esempio 17 e 23, e fai:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

Come notato nei commenti, è possibile che sia preferibile selezionare un grande numero di moltiplicatori. Apparentemente 486187739 è buono ... e sebbene molti esempi che ho visto con numeri piccoli tendano a usare i numeri primi, ci sono almeno algoritmi simili in cui vengono spesso usati numeri non primi. Nell'esempio del non- FNV più tardi, ad esempio, ho usato numeri che apparentemente funzionano bene, ma il valore iniziale non è un numero primo. (La costante di moltiplicazione è primaria però. Non so quanto sia importante.)

Questo è migliore della pratica comune di XOR per l'hashcode per due motivi principali. Supponiamo di avere un tipo con due campi int :

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

A proposito, l'algoritmo precedente è quello attualmente utilizzato dal compilatore C # per i tipi anonimi.

Questa pagina offre alcune opzioni. Penso che per la maggior parte dei casi quanto sopra sia "abbastanza buono" ed è incredibilmente facile da ricordare e correggere. L'alternativa FNV è allo stesso modo semplice, ma utilizza costanti diverse e XOR invece di ADD come operazione di combinazione. Sembra qualcosa di simile al codice sottostante, ma l'algoritmo FNV normale opera su singoli byte, quindi ciò richiederebbe la modifica per eseguire un'iterazione per byte, invece che per un valore hash a 32 bit. FNV è progettato anche per lunghezze variabili di dati, mentre il modo in cui lo usiamo qui è sempre per lo stesso numero di valori di campo. I commenti su questa risposta suggeriscono che il codice qui non funziona altrettanto bene (nel caso campione testato) come l'approccio di aggiunta sopra.

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = (hash * 16777619) ^ field1.GetHashCode();
        hash = (hash * 16777619) ^ field2.GetHashCode();
        hash = (hash * 16777619) ^ field3.GetHashCode();
        return hash;
    }
}

Si noti che una cosa da tenere presente è che idealmente si dovrebbe evitare che lo stato sensibile all'uguaglianza (e quindi sensibile al codice hash) cambi dopo averlo aggiunto a una raccolta che dipende dal codice hash.

Come da documentation :

È possibile eseguire l'override di GetHashCode per tipi di riferimento immutabili. In generale, per i tipi di riferimento modificabili, è necessario eseguire l'override di GetHashCode solo se:

  • Puoi calcolare il codice hash da campi che non sono mutabili; o
  • Puoi assicurarti che il codice hash di un oggetto mutabile non cambi mentre l'oggetto è contenuto in una collezione che si basa sul suo codice hash.

Ecco la mia lezione di aiuto con l'implementazione di Jon Skeet .

public static class HashCode
{
    public const int Start = 17;

    public static int Hash<T>(this int hash, T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked((hash * 31) + h);
    }
}

Uso:

public override int GetHashCode()
{
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)
        .Hash(_field3);
}

Se si desidera evitare di scrivere un metodo di estensione per System.Int32:

public struct HashCode
{
    private readonly int _value;

    public HashCode(int value) => _value = value;

    public static HashCode Start { get; } = new HashCode(17);

    public static implicit operator int(HashCode hash) => hash._value;

    public HashCode Hash<T>(T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked(new HashCode((_value * 31) + h));
    }

    public override int GetHashCode() => _value;
}

È ancora generico, evita comunque qualsiasi allocazione di heap e viene utilizzato esattamente allo stesso modo:

public override int GetHashCode()
{
    // This time `HashCode.Start` is not an `Int32`, it's a `HashCode` instance.
    // And the result is implicitly converted to `Int32`.
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)     
        .Hash(_field3);
}

Aggiornamento dopo il commento di Martin:

obj != null causato la boxe quindi sono passato al confronto predefinito.

  • Vedi questa risposta per quanto riguarda le prestazioni del comparatore predefinito.
  • Vedi questa domanda per una discussione sui codici hash dei valori nulli.

Modifica (maggio 2018):

EqualityComparer<T>.Default getter EqualityComparer<T>.Default è ora un JIT intrinseco - la richiesta di pull è menzionata da Stephen Toub in questo post del blog .


Ecco un'altra implementazione fluente dell'algoritmo pubblicato sopra da Jon Skeet , ma che non include allocazioni o operazioni di boxe:

public static class Hash
{
    public const int Base = 17;

    public static int HashObject(this int hash, object obj)
    {
        unchecked { return hash * 23 + (obj == null ? 0 : obj.GetHashCode()); }
    }

    public static int HashValue<T>(this int hash, T value)
        where T : struct
    {
        unchecked { return hash * 23 + value.GetHashCode(); }
    }
}

Uso:

public class MyType<T>
{
    public string Name { get; set; }

    public string Description { get; set; }

    public int Value { get; set; }

    public IEnumerable<T> Children { get; set; }

    public override int GetHashCode()
    {
        return Hash.Base
            .HashObject(this.Name)
            .HashObject(this.Description)
            .HashValue(this.Value)
            .HashObject(this.Children);
    }
}

Il compilatore assicurerà che HashValuenon venga chiamato con una classe a causa del vincolo di tipo generico. Ma non c'è un supporto per il compilatore HashObjectpoiché l'aggiunta di un argomento generico aggiunge anche un'operazione di boxe.


Ho una classe di hash nella libreria di Helper che la uso a questo scopo.

/// <summary> 
/// This is a simple hashing function from Robert Sedgwicks Hashing in C book.
/// Also, some simple optimizations to the algorithm in order to speed up
/// its hashing process have been added. from: www.partow.net
/// </summary>
/// <param name="input">array of objects, parameters combination that you need
/// to get a unique hash code for them</param>
/// <returns>Hash code</returns>
public static int RSHash(params object[] input)
{
    const int b = 378551;
    int a = 63689;
    int hash = 0;

    // If it overflows then just wrap around
    unchecked
    {
        for (int i = 0; i < input.Length; i++)
        {
            if (input[i] != null)
            {
                hash = hash * a + input[i].GetHashCode();
                a = a * b;
            }
        }
    }

    return hash;
}

Quindi, semplicemente puoi usarlo come:

public override int GetHashCode()
{
    return Hashing.RSHash(_field1, _field2, _field3);
}

Non ho valutato le sue prestazioni, quindi qualsiasi feedback è ben accetto.


Nella maggior parte dei casi, dove Equals () confronta più campi, non importa se i tuoi hash GetHash () su un campo o su molti. Devi solo assicurarti che il calcolo dell'hash sia davvero economico ( nessuna allocazione , per favore) e veloce ( niente calcoli pesanti e certamente nessuna connessione al database) e fornisce una buona distribuzione.

Il sollevamento pesante dovrebbe essere parte del metodo Equals (); l'hash dovrebbe essere un'operazione molto economica per abilitare la chiamata a Equals () sul minor numero possibile di elementi.

E un ultimo consiglio: non fare affidamento sul fatto che GetHashCode () sia stabile su più esecuzioni di applicazioni . Molti tipi .Net non garantiscono che i loro codici hash rimangano uguali dopo un riavvio, quindi è necessario utilizzare il valore di GetHashCode () solo nelle strutture di dati di memoria.


ReSharper utenti ReSharper possono generare GetHashCode, Equals e altri con ReSharper -> Edit -> Generate Code -> Equality Members.

// ReSharper's GetHashCode looks like this
public override int GetHashCode() {
    unchecked {
        int hashCode = Id;
        hashCode = (hashCode * 397) ^ IntMember;
        hashCode = (hashCode * 397) ^ OtherIntMember;
        hashCode = (hashCode * 397) ^ (RefMember != null ? RefMember.GetHashCode() : 0);
        // ...
        return hashCode;
    }
}

Ho riscontrato un problema con float e decimali utilizzando l'implementazione selezionata come risposta sopra.

Questo test fallisce (float, l'hash è lo stesso anche se ho cambiato 2 valori per essere negativo):

        var obj1 = new { A = 100m, B = 100m, C = 100m, D = 100m};
        var obj2 = new { A = 100m, B = 100m, C = -100m, D = -100m};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

Ma questo test passa (con ints):

        var obj1 = new { A = 100m, B = 100m, C = 100, D = 100};
        var obj2 = new { A = 100m, B = 100m, C = -100, D = -100};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

Ho cambiato la mia implementazione per non utilizzare GetHashCode per i tipi primitivi e sembra funzionare meglio

    private static int InternalComputeHash(params object[] obj)
    {
        unchecked
        {
            var result = (int)SEED_VALUE_PRIME;
            for (uint i = 0; i < obj.Length; i++)
            {
                var currval = result;
                var nextval = DetermineNextValue(obj[i]);
                result = (result * MULTIPLIER_VALUE_PRIME) + nextval;

            }
            return result;
        }
    }



    private static int DetermineNextValue(object value)
    {
        unchecked
        {

                int hashCode;
                if (value is short
                    || value is int
                    || value is byte
                    || value is sbyte
                    || value is uint
                    || value is ushort
                    || value is ulong
                    || value is long
                    || value is float
                    || value is double
                    || value is decimal)
                {
                    return Convert.ToInt32(value);
                }
                else
                {
                    return value != null ? value.GetHashCode() : 0;
                }
        }
    }

Praticamente simile alla soluzione di nightcoder, tranne che è più facile sollevare numeri primi se lo si desidera.

PS: Questa è una di quelle volte in cui ti vomiti un po 'in bocca, sapendo che questo potrebbe essere rifattorizzato in un unico metodo con 9 di default ma sarebbe più lento, quindi chiudi gli occhi e prova a dimenticartene.

/// <summary>
/// Try not to look at the source code. It works. Just rely on it.
/// </summary>
public static class HashHelper
{
    private const int PrimeOne = 17;
    private const int PrimeTwo = 23;

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9, T10 arg10)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();
            hash = hash * PrimeTwo + arg9.GetHashCode();
            hash = hash * PrimeTwo + arg10.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();
            hash = hash * PrimeTwo + arg9.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, T4 arg4)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();

            return hash;
        }
    }
}

Se non abbiamo più di 8 proprietà (si spera), ecco un'altra alternativa.

ValueTupleè una struttura e sembra avere GetHashCodeun'implementazione solida .

Ciò significa che potremmo semplicemente fare questo:

// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();

Diamo uno sguardo al corrente implementazione di .NET Core for ValueTuple's GetHashCode.

Questo è da ValueTuple:

    internal static int CombineHashCodes(int h1, int h2)
    {
        return HashHelpers.Combine(HashHelpers.Combine(HashHelpers.RandomSeed, h1), h2);
    }

    internal static int CombineHashCodes(int h1, int h2, int h3)
    {
        return HashHelpers.Combine(CombineHashCodes(h1, h2), h3);
    }

E questo è da HashHelper:

    public static readonly int RandomSeed = Guid.NewGuid().GetHashCode();

    public static int Combine(int h1, int h2)
    {
        unchecked
        {
            // RyuJIT optimizes this to use the ROL instruction
            // Related GitHub pull request: dotnet/coreclr#1830
            uint rol5 = ((uint)h1 << 5) | ((uint)h1 >> 27);
            return ((int)rol5 + h1) ^ h2;
        }
    }

In inglese:

  • Ruota a sinistra (spostamento circolare) h1 di 5 posizioni.
  • Aggiungi il risultato e h1 insieme.
  • XOR il risultato con h2.
  • Inizia eseguendo l'operazione sopra su {seed random statico, h1}.
  • Per ogni ulteriore elemento, eseguire l'operazione sul risultato precedente e sull'elemento successivo (ad es. H2).

Sarebbe bello sapere di più sulle proprietà di questo algoritmo di codice hash ROL-5.

Purtroppo, il rinvio per ValueTupleconto nostro GetHashCodepotrebbe non essere veloce come vorremmo e aspettarci. Questo commento in una discussione correlata illustra che la chiamata diretta HashHelpers.Combineè più performante. Il rovescio della medaglia, quello è interno, quindi dovremmo copiare il codice, sacrificando gran parte di ciò che avevamo guadagnato qui. Inoltre, saremo responsabili di ricordare prima Combinecon il seme casuale. Non so quali sono le conseguenze se saltiamo quel passaggio.


Ecco il mio approccio semplicistico. Sto usando il classico modello di builder per questo. È tipicamente sicuro (nessun boxing / unboxing) e anche compatibile con .NET 2.0 (senza metodi di estensione, ecc.).

È usato così:

public override int GetHashCode()
{
    HashBuilder b = new HashBuilder();
    b.AddItems(this.member1, this.member2, this.member3);
    return b.Result;
} 

Ed ecco la classe del costruttore acutal:

internal class HashBuilder
{
    private const int Prime1 = 17;
    private const int Prime2 = 23;
    private int result = Prime1;

    public HashBuilder()
    {
    }

    public HashBuilder(int startHash)
    {
        this.result = startHash;
    }

    public int Result
    {
        get
        {
            return this.result;
        }
    }

    public void AddItem<T>(T item)
    {
        unchecked
        {
            this.result = this.result * Prime2 + item.GetHashCode();
        }
    }

    public void AddItems<T1, T2>(T1 item1, T2 item2)
    {
        this.AddItem(item1);
        this.AddItem(item2);
    }

    public void AddItems<T1, T2, T3>(T1 item1, T2 item2, T3 item3)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
    }

    public void AddItems<T1, T2, T3, T4>(T1 item1, T2 item2, T3 item3, 
        T4 item4)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
    }

    public void AddItems<T1, T2, T3, T4, T5>(T1 item1, T2 item2, T3 item3, 
        T4 item4, T5 item5)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
        this.AddItem(item5);
    }        

    public void AddItems<T>(params T[] items)
    {
        foreach (T item in items)
        {
            this.AddItem(item);
        }
    }
}

La maggior parte del mio lavoro è fatto con la connettività del database, il che significa che tutte le mie classi hanno un identificatore univoco dal database. Uso sempre l'ID dal database per generare l'hashcode.

// Unique ID from database
private int _id;

...    
{
  return _id.GetHashCode();
}




gethashcode