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




algorithm (15)

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

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?


Questo è buono:

/// <summary>
/// Helper class for generating hash codes suitable 
/// for use in hashing algorithms and data structures like a hash table. 
/// </summary>
public static class HashCodeHelper
{
    private static int GetHashCodeInternal(int key1, int key2)
    {
        unchecked
        {
           var num = 0x7e53a269;
           num = (-1521134295 * num) + key1;
           num += (num << 10);
           num ^= (num >> 6);

           num = ((-1521134295 * num) + key2);
           num += (num << 10);
           num ^= (num >> 6);

           return num;
        }
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="arr">An array of objects used for generating the 
    /// hash code.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode(params object[] arr)
    {
        int hash = 0;
        foreach (var item in arr)
            hash = GetHashCodeInternal(hash, item.GetHashCode());
        return hash;
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <param name="obj4">The fourth object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and
    /// data structures like a hash table.
    /// </returns>
    public static int GetHashCode<T1, T2, T3, T4>(T1 obj1, T2 obj2, T3 obj3,
        T4 obj4)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3, obj4));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2, T3>(T1 obj1, T2 obj2, T3 obj3)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2>(T1 obj1, T2 obj2)
    {
        return GetHashCodeInternal(obj1.GetHashCode(), obj2.GetHashCode());
    }
}

Ed ecco come usarlo:

private struct Key
{
    private Type _type;
    private string _field;

    public Type Type { get { return _type; } }
    public string Field { get { return _field; } }

    public Key(Type type, string field)
    {
        _type = type;
        _field = field;
    }

    public override int GetHashCode()
    {
        return HashCodeHelper.GetHashCode(_field, _type);
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Key))
            return false;
        var tf = (Key)obj;
        return tf._field.Equals(_field) && tf._type.Equals(_type);
    }
}

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();
}

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.


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

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.


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.)


Microsoft conduce per diversi modi di hashing ...

//for classes that contain a single int value
return this.value;

//for classes that contain multiple int value
return x ^ y;

//for classes that contain single number bigger than int    
return ((int)value ^ (int)(value >> 32)); 

//for classes that contain class instance fields which inherit from object
return obj1.GetHashCode();

//for classes that contain multiple class instance fields which inherit from object
return obj1.GetHashCode() ^ obj2.GetHashCode() ^ obj3.GetHashCode(); 

Posso indovinare che per molti big int puoi usare questo:

int a=((int)value1 ^ (int)(value1 >> 32));
int b=((int)value2 ^ (int)(value2 >> 32));
int c=((int)value3 ^ (int)(value3 >> 32));
return a ^ b ^ c;

E lo stesso per il multi-tipo: tutti convertiti per primi ad intusare GetHashCode()poi i valori int saranno xor'ed e il risultato è il tuo hash.

Per chi usa l'hash come ID (intendo un valore univoco), l'hash è naturalmente limitato a un numero di cifre, penso che fosse 5 byte per l'algoritmo di hash, almeno MD5.

È possibile convertire più valori in un valore hash e alcuni di essi sono uguali, quindi non utilizzarlo come identificativo. (forse un giorno userò il tuo componente)


Ecco il mio assistente di hashcode.
Il vantaggio è che utilizza argomenti di tipo generico e quindi non causerà il pugilato:

public static class HashHelper
{
    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
         unchecked
         {
             return 31 * arg1.GetHashCode() + arg2.GetHashCode();
         }
    }

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

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

    public static int GetHashCode<T>(T[] list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    public static int GetHashCode<T>(IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    /// <summary>
    /// Gets a hashcode for a collection for that the order of items 
    /// does not matter.
    /// So {1, 2, 3} and {3, 2, 1} will get same hash code.
    /// </summary>
    public static int GetHashCodeForOrderNoMatterCollection<T>(
        IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            int count = 0;
            foreach (var item in list)
            {
                hash += item.GetHashCode();
                count++;
            }
            return 31 * hash + count.GetHashCode();
        }
    }

    /// <summary>
    /// Alternative way to get a hashcode is to use a fluent 
    /// interface like this:<br />
    /// return 0.CombineHashCode(field1).CombineHashCode(field2).
    ///     CombineHashCode(field3);
    /// </summary>
    public static int CombineHashCode<T>(this int hashCode, T arg)
    {
        unchecked
        {
            return 31 * hashCode + arg.GetHashCode();   
        }
    }

Inoltre ha un metodo di estensione per fornire un'interfaccia fluente, quindi puoi usarlo in questo modo:

public override int GetHashCode()
{
    return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}

o in questo modo:

public override int GetHashCode()
{
    return 0.CombineHashCode(Manufacturer)
        .CombineHashCode(PartN)
        .CombineHashCode(Quantity);
}

Fino a poco tempo fa la mia risposta sarebbe stata molto vicina a quella di Jon Skeet qui. Tuttavia, di recente ho avviato un progetto che utilizzava le tabelle hash power-of-two, ovvero le tabelle hash dove la dimensione della tabella interna è 8, 16, 32, ecc. C'è una buona ragione per favorire le dimensioni dei numeri primi, ma lì sono alcuni vantaggi anche per la potenza di due dimensioni.

E praticamente succhiato. Quindi, dopo un po 'di sperimentazione e ricerca, ho iniziato a rifare i miei hash con il seguente:

public static int ReHash(int source)
{
  unchecked
  {
    ulong c = 0xDEADBEEFDEADBEEF + (ulong)source;
    ulong d = 0xE2ADBEEFDEADBEEF ^ c;
    ulong a = d += c = c << 15 | c >> -15;
    ulong b = a += d = d << 52 | d >> -52;
    c ^= b += a = a << 26 | a >> -26;
    d ^= c += b = b << 51 | b >> -51;
    a ^= d += c = c << 28 | c >> -28;
    b ^= a += d = d << 9 | d >> -9;
    c ^= b += a = a << 47 | a >> -47;
    d ^= c += b << 54 | b >> -54;
    a ^= d += c << 32 | c >> 32;
    a += d << 25 | d >> -25;
    return (int)(a >> 1);
  }
}

E poi il mio hash table power-of-two non ha succhiato più.

Questo mi ha però disturbato, perché quanto sopra non dovrebbe funzionare. O, più precisamente, non dovrebbe funzionare a meno che il GetHashCode() originale non fosse molto povero in un modo molto particolare.

Ri-mescolare un hashcode non può migliorare un ottimo codice hash, perché l'unico effetto possibile è che introduciamo un po 'più di collisioni.

Ri-mescolare un codice hash non può migliorare un terribile codice hash, perché l'unico effetto possibile è che cambiamo ad esempio un gran numero di collisioni sul valore 53 su un grande numero di valori 18.3487.291.

Ri-mescolare un codice hash può solo migliorare un codice hash che ha fatto almeno abbastanza bene nell'evitare le collisioni assolute in tutto il suo intervallo (2 32 valori possibili) ma malamente nell'evitare le collisioni quando modulo giù per l'uso effettivo in una tabella hash. Mentre il modulo più semplice di un tavolo power-of-two ha reso questo più evidente, ha anche avuto un effetto negativo con le tabelle dei numeri primi più comuni, che non era altrettanto ovvio (il lavoro extra in rilassa supererebbe il vantaggio , ma il beneficio sarebbe ancora lì).

Modifica: stavo anche usando l'indirizzamento aperto, che avrebbe anche aumentato la sensibilità alla collisione, forse più che il fatto che fosse un power-of-two.

E bene, è stato inquietante il modo in cui le implementazioni string.GetHashCode() in .NET (o studio here ) potrebbero essere migliorate in questo modo (nell'ordine dei test in esecuzione circa 20-30 volte più veloce a causa di un minor numero di collisioni) e più inquietante come molti miei codici hash potrebbero essere migliorati (molto più di questo).

Tutte le implementazioni GetHashCode () che avevo codificato in passato, e in effetti utilizzate come base per le risposte su questo sito, erano molto peggiori di quanto avrei potuto fare . Per gran parte del tempo è stato "abbastanza buono" per molti degli usi, ma volevo qualcosa di meglio.

Quindi ho messo da parte questo progetto (era comunque un progetto per animali domestici) e ho iniziato a studiare come produrre rapidamente un codice hash buono e ben distribuito in .NET.

Alla fine ho optato per il porting di SpookyHash su .NET. In effetti, il codice sopra riportato è una versione a percorso rapido dell'utilizzo di SpookyHash per produrre un output a 32 bit da un input a 32 bit.

Ora, SpookyHash non è un bel pezzo di codice da ricordare. Il mio punto di forza è ancora meno, perché l'ho sottolineato a mano molto per una migliore velocità *. Ma è a questo che serve il riutilizzo del codice.

Quindi ho messo da parte questo progetto, perché proprio come il progetto originale aveva prodotto la domanda su come produrre un codice hash migliore, così che il progetto ha prodotto la domanda su come produrre una memcpy .NET migliore.

Poi sono tornato e ho prodotto molti sovraccarichi per alimentare facilmente tutti i tipi nativi (eccetto i decimal †) in un codice hash.

È veloce, per cui Bob Jenkins merita la maggior parte del merito perché il suo codice originale da cui sono stato trasferito è ancora più veloce, specialmente su macchine a 64 bit che l'algoritmo è ottimizzato per ‡.

Il codice completo può essere visto su https://bitbucket.org/JonHanna/spookilysharp/src ma considera che il codice sopra è una versione semplificata di esso.

Tuttavia, poiché è già stato scritto, è possibile utilizzarlo più facilmente:

public override int GetHashCode()
{
  var hash = new SpookyHash();
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

Prende anche i valori di inizializzazione, quindi se hai bisogno di gestire input non attendibili e vuoi proteggerti dagli attacchi di Hash DoS puoi impostare un seme in base al tempo di attività o simile e rendere i risultati imprevedibili dagli aggressori:

private static long hashSeed0 = Environment.TickCount;
private static long hashSeed1 = DateTime.Now.Ticks;
public override int GetHashCode()
{
  //produce different hashes ever time this application is restarted
  //but remain consistent in each run, so attackers have a harder time
  //DoSing the hash tables.
  var hash = new SpookyHash(hashSeed0, hashSeed1);
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

* Una grande sorpresa in questo è che mano-inlining un metodo di rotazione che ha restituito (x << n) | (x >> -n) (x << n) | (x >> -n) cose migliorate. Sarei stato sicuro che il jitter lo avrebbe sottolineato per me, ma il profiling ha mostrato il contrario.

decimal non è nativo dal punto di vista .NET sebbene provenga dal C #. Il problema è che il proprio GetHashCode() considera la precisione come significativa mentre il suo stesso Equals() no. Entrambe sono scelte valide, ma non mescolate in questo modo. Nell'implementare la tua versione, devi scegliere di fare l'una o l'altra, ma non posso sapere quale vorresti.

‡ A titolo di confronto. Se usato su una stringa, SpookyHash su 64 bit è considerevolmente più veloce di string.GetHashCode() su 32 bit, che è leggermente più veloce di string.GetHashCode() su 64 bit, che è considerevolmente più veloce di SpookyHash su 32 bit, sebbene sia ancora veloce abbastanza per essere una scelta ragionevole.


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.


A partire da https://github.com/dotnet/coreclr/pull/14863 , c'è un nuovo modo per generare codici hash che è semplicissimo! Scrivi e basta

public override int GetHashCode()
    => HashCode.Combine(field1, field2, field3);

Questo genererà un codice hash di qualità senza che tu debba preoccuparti dei dettagli di implementazione.


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.


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.







.net algorithm hashcode gethashcode