Quel est le meilleur algorithme pour remplacer GetHashCode?

1449

Dans .NET, la GetHashCodeméthode est utilisée à de nombreux endroits dans les bibliothèques de classes de base .NET. L'implémenter correctement est particulièrement important pour trouver rapidement des éléments dans une collection ou pour déterminer l'égalité.

Existe-t-il un algorithme standard ou une meilleure pratique sur la façon d'implémenter GetHashCodepour mes classes personnalisées afin de ne pas dégrader les performances?

bitbonk
la source
38
Après avoir lu cette question et l'article ci-dessous, je pourrais implémenter le remplacement de GetHashCode. J'espère que ce serait utile pour les autres. Lignes directrices et règles pour GetHashCode écrites par Eric Lippert
rene
4
"ou pour déterminer l'égalité": non! Deux objets avec le même hashcode ne sont pas nécessairement égaux.
Thomas Levesque
1
@ThomasLevesque Vous avez raison, deux objets avec le même code de hachage ne sont pas nécessairement égaux. Mais GetHashCode()est toujours utilisé dans de très nombreuses implémentations de Equals(). C'est ce que je voulais dire avec cette déclaration. GetHashCode()inside Equals()est souvent utilisé comme raccourci pour déterminer l' inégalité , car si deux objets ont un code de hachage différent, ils doivent être des objets qui ne sont pas égaux et le reste du contrôle d'égalité n'a pas à être exécuté.
bitbonk
3
@bitbonk Habituellement, les deux GetHashCode()et Equals()doivent regarder tous les champs des deux objets (Equals doit le faire si les codes de hachage sont égaux ou non vérifiés). Pour cette raison, un appel vers l' GetHashCode()intérieur Equals()est souvent redondant et pourrait réduire les performances. Equals()peut également être en mesure de court-circuiter, ce qui le rend beaucoup plus rapide - cependant dans certains cas, les codes de hachage peuvent être mis en cache, ce qui rend la GetHashCode()vérification plus rapide et donc utile. Voir cette question pour plus.
NotEnoughData
MISE À JOUR JAN 2020: le blog d'Eric Lippert situé à: docs.microsoft.com/en-us/archive/blogs/ericlippert/…
Rick Davin

Réponses:

1604

J'utilise généralement quelque chose comme l'implémentation donnée dans le fabuleux Java efficace de Josh Bloch . Il est rapide et crée un très bon hachage qui est peu susceptible de provoquer des collisions. Choisissez deux nombres premiers différents, par exemple 17 et 23, et faites:

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

Comme indiqué dans les commentaires, vous trouverez peut-être préférable de choisir un grand nombre premier à multiplier par. Apparemment, 486187739 est bon ... et bien que la plupart des exemples que j'ai vus avec de petits nombres aient tendance à utiliser des nombres premiers, il existe au moins des algorithmes similaires où des nombres non premiers sont souvent utilisés. Dans l' exemple FNV pas tout à fait plus tard, par exemple, j'ai utilisé des nombres qui semblent bien fonctionner - mais la valeur initiale n'est pas un nombre premier. (La constante de multiplication est cependant primordiale. Je ne sais pas à quel point c'est important.)

C'est mieux que la pratique courante d' XORingérer des codes de hachage pour deux raisons principales. Supposons que nous ayons un type avec deux intchamps:

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

Soit dit en passant, l'algorithme précédent est celui actuellement utilisé par le compilateur C # pour les types anonymes.

Cette page propose plusieurs options. Je pense que dans la plupart des cas, ce qui précède est "assez bon" et c'est incroyablement facile à retenir et à bien faire. L' alternative FNV est tout aussi simple, mais utilise des constantes différentes et XORnon ADDcomme une opération de combinaison. Il ressemble quelque chose comme le code ci - dessous, mais l'algorithme de FNV normale fonctionne sur des octets individuels, donc cela nécessiterait la modification d'effectuer une itération par octet, au lieu de par la valeur de hachage 32 bits. FNV est également conçu pour des longueurs de données variables, alors que la façon dont nous les utilisons ici est toujours pour le même nombre de valeurs de champ. Les commentaires sur cette réponse suggèrent que le code ici ne fonctionne pas aussi bien (dans l'exemple de cas testé) que l'approche d'addition ci-dessus.

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

Notez qu'une chose à savoir est que, idéalement, vous devriez empêcher votre état sensible à l'égalité (et donc sensible au code de hachage) de changer après l'avoir ajouté à une collection qui dépend du code de hachage.

Selon la documentation :

Vous pouvez remplacer GetHashCode pour les types de référence immuables. En général, pour les types de référence mutables, vous ne devez remplacer GetHashCode que si:

  • Vous pouvez calculer le code de hachage à partir de champs qui ne sont pas modifiables; ou
  • Vous pouvez vous assurer que le code de hachage d'un objet modifiable ne change pas pendant que l'objet est contenu dans une collection qui s'appuie sur son code de hachage.
Jon Skeet
la source
8
L'algorithme décrit dans le livre que vous mentionnez est en fait un peu plus détaillé, il décrit en particulier ce qu'il faut faire pour différents types de données des champs. Par exemple: pour les champs de type long, utilisez (int) (champ ^ f >>> 32) au lieu d'appeler simplement GetHashcode. Est-ce que long.GetHashCodes est implémenté de cette façon?
bitbonk
13
Oui, Int64.GetHashCode fait exactement cela. En Java, cela nécessiterait bien sûr de la boxe. Cela me rappelle - il est temps d'ajouter un lien vers le livre ...
Jon Skeet
77
23 n'est pas un bon choix, car (à partir de .net 3.5 SP1) Dictionary<TKey,TValue>suppose une bonne distribution modulo certains nombres premiers. Et 23 est l'un d'entre eux. Donc, si vous avez un dictionnaire avec Capacity 23, seule la dernière contribution à GetHashCodeinfluence le code de hachage composé. Je préfère donc utiliser 29 au lieu de 23.
CodesInChaos
23
@CodeInChaos: Seule la dernière contribution influe sur le bucket - il pourrait donc, au pire, devoir parcourir les 23 entrées du dictionnaire. Il va toujours vérifier le code de hachage réel de chaque entrée, ce qui sera bon marché. Si vous avez un dictionnaire aussi petit, il est peu probable qu'il importe beaucoup.
Jon Skeet
20
@Vajda: J'utilise habituellement 0 comme code de hachage efficace null- ce qui n'est pas la même chose que d'ignorer le champ.
Jon Skeet
431

Type anonyme

Microsoft fournit déjà un bon générateur générique HashCode: copiez simplement vos valeurs de propriété / champ dans un type anonyme et hachez-le:

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

Cela fonctionnera pour n'importe quel nombre de propriétés. Il n'utilise pas de boxe. Il utilise simplement l'algorithme déjà implémenté dans le cadre pour les types anonymes.

ValueTuple - Mise à jour pour C # 7

Comme @cactuaroid le mentionne dans les commentaires, un tuple de valeur peut être utilisé. Cela permet d'économiser quelques frappes et, plus important encore, de s'exécuter uniquement sur la pile (pas de déchets):

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

(Remarque: la technique d'origine utilisant des types anonymes semble créer un objet sur le tas, c'est-à-dire des ordures, car les types anonymes sont implémentés en tant que classes, bien que cela puisse être optimisé par le compilateur. Il serait intéressant de comparer ces options, mais le l'option tuple doit être supérieure.)

Rick Love
la source
85
Oui, l' GetHashCodeimplémentation anonyme est très efficace (BTW c'est la même que celle de la réponse de Jon Skeet), mais le seul problème avec cette solution est que vous générez une nouvelle instance à chaque GetHashCodeappel. Cela peut être un peu
trop lourd
5
@digEmAll Bon point, je n'ai pas pensé à la surcharge de création d'un nouvel objet. La réponse de Jon Skeet est la plus efficace et n'utilisera pas la boxe. (@Kumba Pour résoudre les problèmes non vérifiés dans VB, utilisez simplement un Int64 (long) et tronquez-le après les calculs.)
Rick Love
42
pourrait simplement dire new { PropA, PropB, PropC, PropD }.GetHashCode()trop
sehe
17
VB.NET doit utiliser la clé dans la création de type anonyme: New With {Key PropA}.GetHashCode()sinon GetHashCode ne renverra pas le même code de hachage pour différents objets avec les mêmes propriétés «d'identification».
David Osborne
4
@Keith dans ce cas, j'envisagerais d'enregistrer l'IEnumerable en tant que valeur de liste quelque part au lieu de l'énumérer chaque fois que le code de hachage est calculé. Cacluler ToList à chaque fois dans GetHashCode peut nuire aux performances dans de nombreuses situations.
Rick Love du
105

Voici mon assistant de hachage.
Son avantage est qu'il utilise des arguments de type générique et ne causera donc pas de boxe:

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

Il a également une méthode d'extension pour fournir une interface fluide, vous pouvez donc l'utiliser comme ceci:

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

ou comme ça:

public override int GetHashCode()
{
    return 0.CombineHashCode(Manufacturer)
        .CombineHashCode(PartN)
        .CombineHashCode(Quantity);
}
codeur de nuit
la source
5
Pas besoin de T[]séparément car il est déjàIEnumerable<T>
nawfal
5
Vous pouvez refactoriser ces méthodes et restreindre la logique de base à une seule fonction
nawfal
12
Par ailleurs, 31 est un décalage et une soustraction sur le CPU, ce qui est extrêmement rapide.
Chui Tey
4
@nightcoder vous pouvez utiliser des paramètres .
ANeves
6
@ChuiTey C'est quelque chose que tous les Primes Mersenne ont en commun.
Pharap
63

J'ai une classe de hachage dans la bibliothèque d'aide que je l'utilise à cet effet.

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

Ensuite, vous pouvez simplement l'utiliser comme:

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

Je n'ai pas évalué ses performances, tout commentaire est donc le bienvenu.

Wahid Shalaly
la source
26
Eh bien, cela entraînera la boxe, si les champs sont des types de valeur.
Nightcoder
5
"peut être amélioré plus tard en interceptant l'OverflowException" Le but de la uncheckedméthode est d'éviter les exceptions de débordement souhaitées GetHashCode. Ce n'est donc pas incorrect si la valeur déborde intet que cela ne fait pas de mal du tout.
Tim Schmelter
1
Un problème avec cet algorithme est que tout tableau plein de valeurs nulles retournera toujours 0, quelle que soit sa longueur
Nathan Adams
2
Cette méthode d'assistance alloue également un nouvel objet []
James Newton-King
1
Comme le mentionne @NathanAdams, le fait d' nullêtre entièrement ignoré pourrait vous donner des résultats inattendus. Au lieu de les ignorer, vous devez simplement utiliser une valeur constante au lieu de input[i].GetHashCode()quand input[i]est nul.
David Schwartz
58

Voici ma classe d'aide utilisant l'implémentation de 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);
    }
}

Usage:

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

Si vous souhaitez éviter d'écrire une méthode d'extension pour System.Int32:

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

Il évite toujours toute allocation de tas et est utilisé exactement de la même manière:

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

Edit (mai 2018): EqualityComparer<T>.Defaultgetter est maintenant un intrinsèque JIT - la demande de pull est mentionnée par Stephen Toub dans ce billet de blog .

Şafak Gür
la source
1
Je changerais la ligne avec l'opérateur tertiaire pour être:var h = Equals(obj, default(T)) ? 0 : obj.GetHashCode();
Bill Barry
Je crois que l'opérateur ternaire avec obj != nullcompilera une boxinstruction qui allouera de la mémoire si Test un type de valeur. À la place, vous pouvez utiliser obj.Equals(null)ce qui se compilera en un appel virtuel de la Equalsméthode.
Martin Liversage du
Parce que this.hashCode != h. Il ne retournerait pas la même valeur.
Şafak Gür
Désolé, réussissez à supprimer mon commentaire au lieu de le modifier. Est-il plus avantageux de créer une nouvelle structure puis de changer le hashCode en non-lecture seule et de faire: "unchecked {this.hashCode ^ = h * 397;} return this;" par exemple?
Erik Karlsson
L'immuabilité a ses avantages ( pourquoi les structures mutables sont-elles mauvaises? ). En ce qui concerne les performances, ce que je fais est assez bon marché car il n'alloue aucun espace dans le tas.
Şafak Gür
30

.NET Standard 2.1 et supérieur

Si vous utilisez .NET Standard 2.1 ou supérieur, vous pouvez utiliser la structure System.HashCode . Il existe deux méthodes pour l'utiliser:

HashCode.Combine

La Combineméthode peut être utilisée pour créer un code de hachage, donné jusqu'à huit objets.

public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);

HashCode.Add

La Addméthode vous aide à gérer les collections:

public override int GetHashCode()
{
    var hashCode = new HashCode();
    hashCode.Add(this.object1);
    foreach (var item in this.collection)
    {
        hashCode.Add(item);
    }
    return hashCode.ToHashCode();
}

GetHashCode Made Easy

Vous pouvez lire le billet de blog complet « GetHashCode Made Easy » pour plus de détails et de commentaires.

Exemple d'utilisation

public class SuperHero
{
    public int Age { get; set; }
    public string Name { get; set; }
    public List<string> Powers { get; set; }

    public override int GetHashCode() =>
        HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers);
}

la mise en oeuvre

public struct HashCode : IEquatable<HashCode>
{
    private const int EmptyCollectionPrimeNumber = 19;
    private readonly int value;

    private HashCode(int value) => this.value = value;

    public static implicit operator int(HashCode hashCode) => hashCode.value;

    public static bool operator ==(HashCode left, HashCode right) => left.Equals(right);

    public static bool operator !=(HashCode left, HashCode right) => !(left == right);

    public static HashCode Of<T>(T item) => new HashCode(GetHashCode(item));

    public static HashCode OfEach<T>(IEnumerable<T> items) =>
        items == null ? new HashCode(0) : new HashCode(GetHashCode(items, 0));

    public HashCode And<T>(T item) => 
        new HashCode(CombineHashCodes(this.value, GetHashCode(item)));

    public HashCode AndEach<T>(IEnumerable<T> items)
    {
        if (items == null)
        {
            return new HashCode(this.value);
        }

        return new HashCode(GetHashCode(items, this.value));
    }

    public bool Equals(HashCode other) => this.value.Equals(other.value);

    public override bool Equals(object obj)
    {
        if (obj is HashCode)
        {
            return this.Equals((HashCode)obj);
        }

        return false;
    }

    public override int GetHashCode() => this.value.GetHashCode();

    private static int CombineHashCodes(int h1, int h2)
    {
        unchecked
        {
            // Code copied from System.Tuple a good way to combine hashes.
            return ((h1 << 5) + h1) ^ h2;
        }
    }

    private static int GetHashCode<T>(T item) => item?.GetHashCode() ?? 0;

    private static int GetHashCode<T>(IEnumerable<T> items, int startHashCode)
    {
        var temp = startHashCode;

        var enumerator = items.GetEnumerator();
        if (enumerator.MoveNext())
        {
            temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));

            while (enumerator.MoveNext())
            {
                temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
            }
        }
        else
        {
            temp = CombineHashCodes(temp, EmptyCollectionPrimeNumber);
        }

        return temp;
    }
}

Qu'est-ce qui fait un bon algorithme?

La vitesse

L'algorithme qui calcule un code de hachage doit être rapide. Un algorithme simple va généralement être plus rapide.

Déterministe

L'algorithme de hachage doit être déterministe, c'est-à-dire que pour la même entrée, il doit toujours produire la même sortie.

Réduisez les collisions

L'algorithme qui calcule un code de hachage doit conserver les collisions de hachage à un minimum. Une collision de hachage est une situation qui se produit lorsque deux appels à GetHashCodedeux objets différents produisent des codes de hachage identiques. Notez que les collisions sont autorisées (certains pensent à tort qu'elles ne le sont pas) mais elles doivent être réduites au minimum.

Une bonne fonction de hachage doit mapper les entrées attendues aussi uniformément que possible sur sa plage de sortie. Il devrait avoir une uniformité.

Prevent's DoS

Dans .NET Core, chaque fois que vous redémarrez une application, vous obtenez différents codes de hachage. Il s'agit d'une fonction de sécurité pour empêcher les attaques par déni de service (DoS). Pour .NET Framework , vous devez activer cette fonctionnalité en ajoutant le fichier App.config suivant:

<?xml version ="1.0"?>  
<configuration>  
   <runtime>  
      <UseRandomizedStringHashAlgorithm enabled="1" />  
   </runtime>  
</configuration>

En raison de cette fonctionnalité, les codes de hachage ne doivent jamais être utilisés en dehors du domaine d'application dans lequel ils ont été créés, ils ne doivent jamais être utilisés comme champs clés dans une collection et ils ne doivent jamais être persistants.

En savoir plus à ce sujet ici .

Cryptographiquement sécurisé?

Il n'est pas nécessaire que l'algorithme soit une fonction de hachage cryptographique . Cela signifie qu'il ne doit pas satisfaire aux conditions suivantes:

  • Il est impossible de générer un message qui donne une valeur de hachage donnée
  • Il est impossible de trouver deux messages différents avec la même valeur de hachage
  • Une petite modification apportée à un message devrait modifier la valeur de hachage de manière si importante que la nouvelle valeur de hachage n'apparaît pas corrélée avec l'ancienne valeur de hachage (effet d'avalanche).
Muhammad Rehan Saeed
la source
29

Dans la plupart des cas où Equals () compare plusieurs champs, peu importe que votre GetHash () hache sur un champ ou sur plusieurs. Vous devez juste vous assurer que le calcul du hachage est vraiment bon marché ( pas d'allocations , s'il vous plaît) et rapide ( pas de calculs lourds et certainement pas de connexions à la base de données) et fournit une bonne distribution.

Le levage de charges lourdes doit faire partie de la méthode Equals (); le hachage devrait être une opération très bon marché pour permettre d'appeler Equals () sur le moins d'éléments possible.

Et une dernière astuce: ne vous fiez pas à la stabilité de GetHashCode () sur plusieurs exécutions d'applications . De nombreux types .Net ne garantissent pas que leurs codes de hachage restent identiques après un redémarrage, vous ne devez donc utiliser que la valeur de GetHashCode () pour les structures de données en mémoire.

Bert Huijben
la source
10
"Dans la plupart des cas où Equals () compare plusieurs champs, peu importe si votre GetHash () hache sur un champ ou sur plusieurs." C'est un conseil dangereux, car pour les objets qui ne diffèrent que dans les champs non hachés, vous obtiendrez des collisions de hachage. Si cela se produit fréquemment, les performances des collections basées sur le hachage (HashMap, HashSet etc.) se dégraderont (jusqu'à O (n) dans le pire des cas).
sleske
10
Cela s'est réellement produit en Java: dans les premières versions du JDK String.hashCode () ne considérait que le début de la chaîne; cela conduit à des problèmes de performances si vous avez utilisé des chaînes comme clés dans HashMaps qui ne différaient qu'à la fin (ce qui est courant par exemple pour les URL). L'algorithme a donc été modifié (en JDK 1.2 ou 1.3 je crois).
sleske
3
Si ce champ "fournit une bonne distribution" (dernière partie de ma réponse), alors un champ suffit. S'il ne fournit pas une bonne distribution , alors (et juste à ce moment-là) vous avez besoin d'un autre calcul. (Par exemple , utiliser juste un autre champ qui ne fournit une bonne répartition, ou utiliser plusieurs champs)
Bert Huijben
Je ne pense pas qu'il y ait un problème à GetHashCodeeffectuer des allocations de mémoire, à condition qu'il ne le fasse que la première fois qu'il est utilisé (avec des invocations ultérieures renvoyant simplement un résultat mis en cache). L'important n'est pas de se donner beaucoup de mal pour éviter les collisions, mais plutôt d'éviter les collisions "systémiques". Si un type a deux intchamps oldXet newXqui diffèrent fréquemment d'un, une valeur de hachage oldX^newXaffecterait 90% de ces enregistrements à des valeurs de hachage de 1, 2, 4 ou 8. L'utilisation de oldX+newX[l'arithmétique non vérifiée] pourrait générer plus de collisions ...
supercat
1
... que ne le ferait une fonction plus sophistiquée, mais une collection de 1000000 de choses qui ont 500000 valeurs de hachage différentes conviendra très bien si chaque valeur de hachage a deux choses associées, et très mal si une valeur de hachage a 500001 choses et les autres en ont une chacune.
supercat
23

Jusqu'à récemment, ma réponse aurait été très proche de celle de Jon Skeet ici. Cependant, j'ai récemment lancé un projet qui utilisait des tables de hachage avec puissance de deux, c'est-à-dire des tables de hachage où la taille de la table interne est de 8, 16, 32, etc. Il y a une bonne raison de privilégier les tailles de nombre premier, mais sont également des avantages pour les tailles à deux.

Et c'est à peu près nul. Donc, après un peu d'expérimentation et de recherche, j'ai commencé à retailler mes hachages avec les éléments suivants:

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

Et puis ma table de hachage de puissance de deux n'a plus sucé.

Cela m'a toutefois dérangé, car ce qui précède ne devrait pas fonctionner. Ou plus précisément, cela ne devrait fonctionner que si l'original GetHashCode()était médiocre d'une manière très particulière.

Re-mélanger un hashcode ne peut pas améliorer un excellent hashcode, car le seul effet possible est que nous introduisons quelques collisions supplémentaires.

Re-mélanger un code de hachage ne peut pas améliorer un terrible code de hachage, car le seul effet possible est que nous changeons par exemple un grand nombre de collisions sur la valeur 53 en un grand nombre de valeur 18 348 27991.

Re-mélanger un code de hachage ne peut qu'améliorer un code de hachage qui a au moins assez bien réussi à éviter les collisions absolues sur toute sa plage (2 32 valeurs possibles) mais mal à éviter les collisions lorsqu'il est modulé pour une utilisation réelle dans une table de hachage. Bien que le module plus simple d'une table de puissance de deux ait rendu cela plus évident, il avait également un effet négatif avec les tables de nombres premiers les plus courantes, ce n'était tout simplement pas aussi évident (le travail supplémentaire de ressassement l'emporterait sur l'avantage , mais l'avantage serait toujours là).

Edit: J'utilisais également l'adressage ouvert, ce qui aurait également augmenté la sensibilité à la collision, peut-être plus que le fait qu'il s'agissait d'une puissance de deux.

Et bien, cela perturbait la façon dont les string.GetHashCode()implémentations dans .NET (ou étudiez ici ) pouvaient être améliorées de cette façon (dans l'ordre des tests qui s'exécutaient environ 20 à 30 fois plus rapidement en raison de moins de collisions) et plus inquiétant combien mes propres codes de hachage pourrait être amélioré (bien plus que cela).

Toutes les implémentations de GetHashCode () que j'avais codées dans le passé, et en fait utilisées comme base de réponses sur ce site, étaient bien pires que je n'en avais traversé . La plupart du temps, c'était "assez bien" pour la plupart des utilisations, mais je voulais quelque chose de mieux.

J'ai donc mis ce projet de côté (c'était un projet familier de toute façon) et j'ai commencé à chercher comment produire rapidement un bon code de hachage bien distribué dans .NET.

À la fin, j'ai décidé de porter SpookyHash sur .NET. En effet, le code ci-dessus est une version rapide de l'utilisation de SpookyHash pour produire une sortie 32 bits à partir d'une entrée 32 bits.

Maintenant, SpookyHash n'est pas un bon morceau de code rapide à retenir. Mon port est encore moins parce que j'en ai aligné beaucoup pour une meilleure vitesse *. Mais c'est à cela que sert la réutilisation du code.

Ensuite, j'ai mis ce projet de côté, car tout comme le projet d'origine avait posé la question de savoir comment produire un meilleur code de hachage, ce projet a posé la question de savoir comment produire une meilleure mémoire .NET.

Puis je suis revenu et j'ai produit beaucoup de surcharges pour alimenter facilement à peu près tous les types natifs (sauf decimal†) dans un code de hachage.

C'est rapide, pour lequel Bob Jenkins mérite le plus de crédit parce que son code d'origine à partir duquel je l'ai porté est encore plus rapide, en particulier sur les machines 64 bits pour lesquelles l'algorithme est optimisé ‡.

Le code complet peut être consulté sur https://bitbucket.org/JonHanna/spookilysharp/src mais considérez que le code ci-dessus en est une version simplifiée.

Cependant, comme il est déjà écrit, on peut l'utiliser plus facilement:

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

Il prend également des valeurs de graine, donc si vous avez besoin de traiter des entrées non fiables et que vous souhaitez vous protéger contre les attaques Hash DoS, vous pouvez définir une graine basée sur la disponibilité ou similaire, et rendre les résultats imprévisibles pour les attaquants:

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

* Une grande surprise est que cette méthode de rotation en ligne à la main a permis d' (x << n) | (x >> -n)améliorer les choses. J'aurais été sûr que la gigue aurait souligné cela pour moi, mais le profilage a montré le contraire.

decimaln'est pas natif du point de vue .NET bien qu'il provienne du C #. Le problème avec cela est que son propre GetHashCode()considère la précision comme significative tandis que le sien Equals()ne le fait pas. Les deux sont des choix valables, mais pas mélangés comme ça. Lors de l'implémentation de votre propre version, vous devez choisir de faire l'une ou l'autre, mais je ne sais pas laquelle vous souhaitez.

‡ À titre de comparaison. S'il est utilisé sur une chaîne, le SpookyHash sur 64 bits est considérablement plus rapide que string.GetHashCode()sur 32 bits, ce qui est légèrement plus rapide que string.GetHashCode()sur 64 bits, ce qui est considérablement plus rapide que SpookyHash sur 32 bits, bien que suffisamment rapide pour être un choix raisonnable.

Jon Hanna
la source
Lorsque je combine plusieurs valeurs de hachage en une seule, j'ai tendance à utiliser des longvaleurs pour les résultats intermédiaires, puis à fusionner le résultat final jusqu'à un int. Cela vous semble-t-il une bonne idée? Ma préoccupation est que l'on utilise par exemple hash = (hash * 31) + nextField, alors les paires de valeurs correspondantes n'affecteront que les 27 bits supérieurs du hachage. Laisser le calcul s'étendre à un longet emballer des choses minimiserait ce danger.
supercat
@supercat cela dépend de la distribution de votre munging final. La bibliothèque SpookilySharp garantirait que la distribution était bonne, idéalement (car elle n'aura pas besoin de création d'objet) en passant un pointeur vers un type blittable, ou en passant l'un des énumérables qu'elle gère directement, mais si vous n'avez pas déjà blittable données ou une énumération appropriée, puis appeler .Update()avec les valeurs multiples selon la réponse ci-dessus fera l'affaire.
Jon Hanna
@JonHanna seriez-vous prêt à être plus précis avec le comportement problématique que vous avez rencontré? J'essaie d'implémenter une bibliothèque qui rend l'implémentation d'objets de valeur triviale ( ValueUtils ) et j'adorerais un ensemble de tests démontrant une mauvaise miscibilité du hachage dans la puissance de deux tables de hachage.
Eamon Nerbonne
@EamonNerbonne Je n'ai rien de plus précis que "le temps global a été plus lent de cette façon". Comme je l'ai ajouté dans un montage, le fait que j'utilisais l'adressage ouvert peut avoir été plus important que le facteur de puissance de deux. Je prévois de faire quelques cas de test sur un projet particulier où je comparerai quelques approches différentes, donc j'aurai peut-être une meilleure réponse pour vous après cela, bien que ce ne soit pas une priorité élevée (un projet personnel sans besoin urgent) , donc j'y arriverai quand j'y arriverai ...)
Jon Hanna
@ JonHanna: oui, je sais comment se déroule le calendrier personnel du projet - bonne chance! En tout cas, je vois que je n'ai pas bien formulé ce dernier commentaire: je voulais demander l'apport problématique, et pas nécessairement les détails des problèmes qui en ont résulté. Je serais ravi de l'utiliser comme un ensemble de tests (ou d'inspiration pour un ensemble de tests). Dans tous les cas - bonne chance avec votre projet animal :-).
Eamon Nerbonne
13

C'est une bonne:

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

Et voici comment l'utiliser:

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);
    }
}
Magnus
la source
1
Comment les clés sont-elles déterminées? GetHashCode () ne prend aucun paramètre, il doit donc appeler celui-ci avec deux clés qui doivent être déterminées d'une manière ou d'une autre. Désolé, sans autre explication, cela ne semble intelligent, mais pas si bon.
Michael Stum
Et pourquoi avez-vous besoin des surcharges génériques? Le type n'est pas important (et n'est pas utilisé dans votre code) car tous les objets ont une GetHashCode()méthode, vous pouvez donc toujours utiliser la méthode avec le paramsparamètre tableau. Ou est-ce que je manque quelque chose ici?
gehho
4
Lorsque vous utilisez un objet au lieu de génériques, vous obtenez des allocations de boxe et de mémoire, ce que vous ne voulez pas dans GetHashCode. Les génériques sont donc la voie à suivre.
CodesInChaos
1
Les étapes shift / xor de fin ( h += (h << 10); h ^= (h >> 6); h += (h << 3); h ^= (h >> 11); h += (h << 15);ont un codemell: elles ne dépendent d'aucune entrée et me semblent terriblement redondantes.
Voir le
1
@Magnus oui, je vais supprimer mon commentaire d'origine. Juste une petite note que cela peut ne pas être aussi rapide que d'autres solutions ici, mais comme vous le dites ne devrait pas avoir d'importance. La distribution est excellente, meilleure que la plupart des solutions ici, alors +1 de ma part! :)
nawfal
11

Depuis https://github.com/dotnet/coreclr/pull/14863 , il existe une nouvelle façon de générer des codes de hachage qui est super simple! Ecrivez

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

Cela générera un code de hachage de qualité sans que vous ayez à vous soucier des détails de mise en œuvre.

James Ko
la source
Cela ressemble à un ajout intéressant ... de quelle manière savoir quelle version de .NET Core sera livrée?
Dan J
1
@DanJ Quelle heureuse coïncidence, les HashCodechangements pour corefx ont été fusionnés quelques heures avant votre commentaire :) Le type devrait être livré dans .NET Core 2.1.
James Ko
C'est génial - et tout à fait le délai d'exécution. A voté. :)
Dan J
@DanJ Encore mieux: il devrait être disponible dès maintenant sur les versions nocturnes de CoreFX hébergées sur le flux dotnet-core MyGet.
James Ko
Douce - qui ne me permet pas au travail, puisque nous ne sommes pas tout à fait que des saignements de pointe, mais bon à savoir. À votre santé!
Dan J
9

Voici une autre implémentation fluide de l'algorithme publié ci-dessus par Jon Skeet , mais qui ne comprend aucune allocation ou opération de 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(); }
    }
}

Usage:

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

Le compilateur s'assurera qu'il HashValuen'est pas appelé avec une classe en raison de la contrainte de type générique. Mais il n'y a pas de prise en charge du compilateur HashObjectcar l'ajout d'un argument générique ajoute également une opération de boxe.

Scott Wegner
la source
8

Voici mon approche simpliste. J'utilise le modèle de générateur classique pour cela. Il est de type sécurisé (pas de boxe / unboxing) et également compatible avec .NET 2.0 (pas de méthodes d'extension, etc.).

Il est utilisé comme ceci:

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

Et voici la classe de constructeur 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);
        }
    }
}
bitbonk
la source
vous pouvez éviter la création d'objet dans la fonction gethashcode comme dans la réponse de Mangus. Appelez simplement les fonctions de hachage statiques (qui se soucie du hachage de démarrage). En outre, vous pouvez utiliser la AddItems<T>(params T[] items)méthode plus souvent dans la classe d'assistance (que d'appeler à AddItem(T)chaque fois).
nawfal
Et quel avantage trouvez-vous à en faire this.result * Prime2 * item.GetHashCode()souvent this.result * Prime2 + item.GetHashCode()?
nawfal
Je ne peux pas utiliser AddItems<T>(params T[] items)plus souvent parce que typeof(T1) != typeof(T2)etc.
bitbonk
oh oui j'ai raté ça.
nawfal
5

Les utilisateurs de ReSharper peuvent générer GetHashCode, Equals et autres avec 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;
    }
}
Charles Burns
la source
4

Si nous n'avons pas plus de 8 propriétés (espérons-le), voici une autre alternative.

ValueTupleest une structure et semble avoir une GetHashCodeimplémentation solide .

Cela signifie que nous pourrions simplement faire ceci:

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

Jetons un coup d' oeil à la mise en œuvre actuelle de .NET de base pour ValueTuple« s GetHashCode.

Cela vient de 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);
    }

Et cela vient de 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;
        }
    }

En anglais:

  • Rotation à gauche (décalage circulaire) h1 de 5 positions.
  • Additionnez le résultat et h1 ensemble.
  • XOR le résultat avec h2.
  • Commencez par exécuter l'opération ci-dessus sur {graine aléatoire statique, h1}.
  • Pour chaque autre élément, effectuez l'opération sur le résultat précédent et l'élément suivant (par exemple h2).

Ce serait bien d'en savoir plus sur les propriétés de cet algorithme de code de hachage ROL-5.

Malheureusement, le report de la ValueTuplenôtre GetHashCodene sera peut-être pas aussi rapide que nous le souhaiterions. Ce commentaire dans une discussion connexe illustre que l'appel direct HashHelpers.Combineest plus performant. D'un autre côté, celui-ci est interne, il nous faudrait donc copier le code, sacrifiant une grande partie de ce que nous avions gagné ici. De plus, nous serions responsables de nous rappeler d'abord Combineavec la graine aléatoire. Je ne sais pas quelles sont les conséquences si nous sautons cette étape.

Timo
la source
En supposant que h1 >> 270 l'ignore, h1 << 5est égal à h1 * 32donc c'est la même chose que h1 * 33 ^ h2. Selon cette page , il s'appelle "Bernstein modifié".
cactuaroïde
3

La plupart de mon travail se fait avec la connectivité à la base de données, ce qui signifie que mes classes ont toutes un identifiant unique de la base de données. J'utilise toujours l'ID de la base de données pour générer le code de hachage.

// Unique ID from database
private int _id;

...    
{
  return _id.GetHashCode();
}
Mark G
la source
Cela signifie que si vous avez des objets Personne et Compte et qu'ils ont tous les deux et ID = 1, ils auront le même code de hachage. Et ce n'est pas ok.
pero
15
En fait, le commentaire ci-dessus est incorrect. Il y aura toujours la possibilité de collisions de code de hachage (un code de hachage localise uniquement le compartiment, pas l'objet individuel). Une telle implémentation - pour un code de hachage contenant des objets mixtes - entraînerait donc de nombreuses collisions, ce qui n'est pas souhaitable, mais ce serait tout à fait correct si vous n'aviez jamais que des objets d'un seul type dans vos tables de hachage. De plus, il ne se distribue pas uniformément, mais l'implémentation de base sur system.object ne le fait pas non plus, donc je ne m'en inquiéterais pas trop ...
piers7
2
Le code de hachage peut simplement être l'id, car l'id est un entier. Il n'est pas nécessaire d'appeler GetHashCode sur un entier (c'est une fonction d'identité)
Darrel Lee
2
@DarrelLee mais tomo son _id pourrait être un Guid. C'est une bonne pratique de codage à faire _id.GetHashCodecar l'intention est claire.
nawfal
2
@ 1224 selon les modèles d'utilisation, cela peut être horrible pour la raison que vous donnez, mais cela peut aussi être génial; si vous avez une séquence de tels nombres sans trous, alors vous avez un hachage parfait, meilleur que n'importe quel algorithme peut produire. Si vous savez que c'est le cas, vous pouvez même compter dessus et ignorer le contrôle d'égalité.
Jon Hanna
3

Assez similaire à la solution de Nightcoder, sauf qu'il est plus facile d'augmenter les nombres premiers si vous le souhaitez.

PS: C'est l'un de ces moments où vous vomissez un peu dans votre bouche, sachant que cela pourrait être refactorisé en une seule méthode avec 9 valeurs par défaut, mais ce serait plus lent, alors fermez les yeux et essayez de l'oublier.

/// <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;
        }
    }
}
Dbl
la source
2
Ne gère pas les null.
JJS
1

J'ai rencontré un problème avec les flottants et les décimales en utilisant l'implémentation sélectionnée comme réponse ci-dessus.

Ce test échoue (flotte; le hachage est le même même si j'ai changé 2 valeurs pour être négatif):

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

Mais ce test réussit (avec des pouces):

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

J'ai changé mon implémentation pour ne pas utiliser GetHashCode pour les types primitifs et cela semble mieux fonctionner

    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;
                }
        }
    }
HokieMike
la source
1
Dans le cas où vous l' intention contraire uncheckedn'affecte pas Convert.ToInt32: uint, long, float, doubleet decimalpeuvent tous déborder ici.
Mark Hurd
1

Microsoft mène plusieurs hachages ...

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

Je peux deviner que pour plusieurs gros int, vous pouvez utiliser ceci:

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;

Et même pour multi-type: tous convertis d'abord en intutilisant GetHashCode() ensuite les valeurs int seront xor'ed et le résultat est votre hachage.

Pour ceux qui utilisent le hachage comme ID (je veux dire une valeur unique), le hachage est naturellement limité à un certain nombre de chiffres, je pense que c'était 5 octets pour l'algorithme de hachage, au moins MD5.

Vous pouvez transformer plusieurs valeurs en une valeur hachée et certaines d'entre elles doivent être identiques, alors ne l'utilisez pas comme identifiant. (peut-être qu'un jour je vais utiliser votre composant)

deadManN
la source
7
Xorer des entiers pour créer un code de hachage est un contre-modèle bien connu qui a tendance à entraîner un nombre particulièrement élevé de collisions avec des valeurs réelles.
Jon Hanna
Chacun ici utilise un entier, et il n'y a jamais eu de garantie pour que le hachage soit le même, il a juste essayé d'être aussi varié qu'il y a peu de collisions.
deadManN
Oui, mais vos deuxième et cinquième n'essaient pas d'éviter les collisions.
Jon Hanna
1
Oui, cet antipattern est assez courant.
Jon Hanna
2
Il y a un équilibre à atteindre. Utilisez un très bon code de hachage comme Spookyhash et vous obtiendrez beaucoup, beaucoup mieux l'évitement des collisions, mais il aura beaucoup plus de temps de calcul que n'importe lequel d'entre eux (mais quand il s'agit de hacher de très grandes quantités de données, Spookyhash est extrêmement rapide). Un simple décalage sur l'une des valeurs avant xoring n'est qu'un surcoût marginal pour une bonne réduction des collisions. Multiplication du nombre premier augmentant à la fois le temps et la qualité. Ce qui est mieux entre shift ou mult est donc discutable. Bien que très souvent, il y a beaucoup de collisions sur des données réelles et qu'il vaut mieux éviter
Jon Hanna
1

Il s'agit d'une classe d'assistance statique qui implémente l'implémentation de Josh Bloch; et fournit des surcharges explicites pour "empêcher" la boxe, et également pour implémenter le hachage spécifiquement pour les primitives longues.

Vous pouvez passer une comparaison de chaînes qui correspond à votre implémentation égale.

Comme la sortie Hash est toujours un entier, vous pouvez simplement enchaîner les appels Hash.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using System.Runtime.CompilerServices;


namespace Sc.Util.System
{
    /// <summary>
    /// Static methods that allow easy implementation of hashCode. Example usage:
    /// <code>
    /// public override int GetHashCode()
    ///     => HashCodeHelper.Seed
    ///         .Hash(primitiveField)
    ///         .Hsh(objectField)
    ///         .Hash(iEnumerableField);
    /// </code>
    /// </summary>
    public static class HashCodeHelper
    {
        /// <summary>
        /// An initial value for a hashCode, to which is added contributions from fields.
        /// Using a non-zero value decreases collisions of hashCode values.
        /// </summary>
        public const int Seed = 23;

        private const int oddPrimeNumber = 37;


        /// <summary>
        /// Rotates the seed against a prime number.
        /// </summary>
        /// <param name="aSeed">The hash's first term.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int rotateFirstTerm(int aSeed)
        {
            unchecked {
                return HashCodeHelper.oddPrimeNumber * aSeed;
            }
        }


        /// <summary>
        /// Contributes a boolean to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aBoolean">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, bool aBoolean)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + (aBoolean
                                ? 1
                                : 0);
            }
        }

        /// <summary>
        /// Contributes a char to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aChar">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, char aChar)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + aChar;
            }
        }

        /// <summary>
        /// Contributes an int to the developing HashCode seed.
        /// Note that byte and short are handled by this method, through implicit conversion.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aInt">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, int aInt)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + aInt;
            }
        }

        /// <summary>
        /// Contributes a long to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aLong">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, long aLong)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + (int)(aLong ^ (aLong >> 32));
            }
        }

        /// <summary>
        /// Contributes a float to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aFloat">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, float aFloat)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + Convert.ToInt32(aFloat);
            }
        }

        /// <summary>
        /// Contributes a double to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aDouble">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, double aDouble)
            => aSeed.Hash(Convert.ToInt64(aDouble));

        /// <summary>
        /// Contributes a string to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aString">The value to contribute.</param>
        /// <param name="stringComparison">Optional comparison that creates the hash.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(
                this int aSeed,
                string aString,
                StringComparison stringComparison = StringComparison.Ordinal)
        {
            if (aString == null)
                return aSeed.Hash(0);
            switch (stringComparison) {
                case StringComparison.CurrentCulture :
                    return StringComparer.CurrentCulture.GetHashCode(aString);
                case StringComparison.CurrentCultureIgnoreCase :
                    return StringComparer.CurrentCultureIgnoreCase.GetHashCode(aString);
                case StringComparison.InvariantCulture :
                    return StringComparer.InvariantCulture.GetHashCode(aString);
                case StringComparison.InvariantCultureIgnoreCase :
                    return StringComparer.InvariantCultureIgnoreCase.GetHashCode(aString);
                case StringComparison.OrdinalIgnoreCase :
                    return StringComparer.OrdinalIgnoreCase.GetHashCode(aString);
                default :
                    return StringComparer.Ordinal.GetHashCode(aString);
            }
        }

        /// <summary>
        /// Contributes a possibly-null array to the developing HashCode seed.
        /// Each element may be a primitive, a reference, or a possibly-null array.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aArray">CAN be null.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, IEnumerable aArray)
        {
            if (aArray == null)
                return aSeed.Hash(0);
            int countPlusOne = 1; // So it differs from null
            foreach (object item in aArray) {
                ++countPlusOne;
                if (item is IEnumerable arrayItem) {
                    if (!object.ReferenceEquals(aArray, arrayItem))
                        aSeed = aSeed.Hash(arrayItem); // recursive call!
                } else
                    aSeed = aSeed.Hash(item);
            }
            return aSeed.Hash(countPlusOne);
        }

        /// <summary>
        /// Contributes a possibly-null array to the developing HashCode seed.
        /// You must provide the hash function for each element.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aArray">CAN be null.</param>
        /// <param name="hashElement">Required: yields the hash for each element
        /// in <paramref name="aArray"/>.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash<T>(this int aSeed, IEnumerable<T> aArray, Func<T, int> hashElement)
        {
            if (aArray == null)
                return aSeed.Hash(0);
            int countPlusOne = 1; // So it differs from null
            foreach (T item in aArray) {
                ++countPlusOne;
                aSeed = aSeed.Hash(hashElement(item));
            }
            return aSeed.Hash(countPlusOne);
        }

        /// <summary>
        /// Contributes a possibly-null object to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aObject">CAN be null.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, object aObject)
        {
            switch (aObject) {
                case null :
                    return aSeed.Hash(0);
                case bool b :
                    return aSeed.Hash(b);
                case char c :
                    return aSeed.Hash(c);
                case int i :
                    return aSeed.Hash(i);
                case long l :
                    return aSeed.Hash(l);
                case float f :
                    return aSeed.Hash(f);
                case double d :
                    return aSeed.Hash(d);
                case string s :
                    return aSeed.Hash(s);
                case IEnumerable iEnumerable :
                    return aSeed.Hash(iEnumerable);
            }
            return aSeed.Hash(aObject.GetHashCode());
        }


        /// <summary>
        /// This utility method uses reflection to iterate all specified properties that are readable
        /// on the given object, excluding any property names given in the params arguments, and
        /// generates a hashcode.
        /// </summary>
        /// <param name="aSeed">The developing hash code, or the seed: if you have no seed, use
        /// the <see cref="Seed"/>.</param>
        /// <param name="aObject">CAN be null.</param>
        /// <param name="propertySelector"><see cref="BindingFlags"/> to select the properties to hash.</param>
        /// <param name="ignorePropertyNames">Optional.</param>
        /// <returns>A hash from the properties contributed to <c>aSeed</c>.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashAllProperties(
                this int aSeed,
                object aObject,
                BindingFlags propertySelector
                        = BindingFlags.Instance
                        | BindingFlags.Public
                        | BindingFlags.GetProperty,
                params string[] ignorePropertyNames)
        {
            if (aObject == null)
                return aSeed.Hash(0);
            if ((ignorePropertyNames != null)
                    && (ignorePropertyNames.Length != 0)) {
                foreach (PropertyInfo propertyInfo in aObject.GetType()
                        .GetProperties(propertySelector)) {
                    if (!propertyInfo.CanRead
                            || (Array.IndexOf(ignorePropertyNames, propertyInfo.Name) >= 0))
                        continue;
                    aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
                }
            } else {
                foreach (PropertyInfo propertyInfo in aObject.GetType()
                        .GetProperties(propertySelector)) {
                    if (propertyInfo.CanRead)
                        aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
                }
            }
            return aSeed;
        }


        /// <summary>
        /// NOTICE: this method is provided to contribute a <see cref="KeyValuePair{TKey,TValue}"/> to
        /// the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
        /// this method has a different name since it will not be automatically invoked by
        /// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
        /// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
        /// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
        /// the generated hash code will not be consistent. This method itself ALSO will not invoke
        /// this method on the Key or Value here if that itself is a KeyValuePair.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="keyValuePair">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashKeyAndValue<TKey, TValue>(this int aSeed, KeyValuePair<TKey, TValue> keyValuePair)
            => aSeed.Hash(keyValuePair.Key)
                    .Hash(keyValuePair.Value);

        /// <summary>
        /// NOTICE: this method is provided to contribute a collection of <see cref="KeyValuePair{TKey,TValue}"/>
        /// to the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
        /// this method has a different name since it will not be automatically invoked by
        /// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
        /// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
        /// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
        /// the generated hash code will not be consistent. This method itself ALSO will not invoke
        /// this method on a Key or Value here if that itself is a KeyValuePair or an Enumerable of
        /// KeyValuePair.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="keyValuePairs">The values to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashKeysAndValues<TKey, TValue>(
                this int aSeed,
                IEnumerable<KeyValuePair<TKey, TValue>> keyValuePairs)
        {
            if (keyValuePairs == null)
                return aSeed.Hash(null);
            foreach (KeyValuePair<TKey, TValue> keyValuePair in keyValuePairs) {
                aSeed = aSeed.HashKeyAndValue(keyValuePair);
            }
            return aSeed;
        }
    }
}
Steven Coco
la source
Yipes: j'ai trouvé un bug! La HashKeysAndValuesméthode a été corrigée: elle invoque HashKeyAndValue.
Steven Coco
0

Si vous souhaitez effectuer un polyfill à HashCodepartir denetstandard2.1

public static class HashCode
{
    public static int Combine(params object[] instances)
    {
        int hash = 17;

        foreach (var i in instances)
        {
            hash = unchecked((hash * 31) + (i?.GetHashCode() ?? 0));
        }

        return hash;
    }
}

Remarque: s'il est utilisé avec struct, il allouera de la mémoire en raison de la boxe

Ivan Sanz-Carasa
la source