Quel est le meilleur algorithme pour un substituée Système.Objet.GetHashCode?

La méthode

dans .NET System.Object.GetHashCode est utilisée dans de nombreux endroits, à travers les bibliothèques de la classe de base .NET. Surtout quand trouver des articles dans une collection rapide ou de déterminer l'égalité. Y a-t-il un algorithme standard/ une pratique exemplaire sur la façon d'implémenter le GetHashCode override pour mes classes personnalisées afin que je ne dégrade pas les performances?

1246
demandé sur iYoung 2008-11-04 23:53:19
la source

17 ответов

je vais habituellement avec quelque chose comme la mise en œuvre donnée dans fabuleuse 1519100920" Java efficace de Josh Bloch . Il est rapide et crée un assez bon hachage qui est peu susceptible de causer 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 noté dans les commentaires, vous pouvez trouver qu'il est préférable de choisir un grand prime pour multiplier par à la place. Apparemment 486187739 c'est bien... et bien que la plupart des les exemples que j'ai vu avec de petits nombres ont tendance à utiliser des nombres premiers, il y a au moins des algorithmes similaires où des nombres non premiers sont souvent utilisés. Dans l'exemple pas tout à fait FNV plus tard, par exemple, j'ai utilisé des nombres qui apparemment fonctionnent bien-mais la valeur initiale n'est pas un premier. (La constante de multiplication est prime though. Je ne sais pas trop combien c'est important.)

c'est mieux que la pratique courante de XOR hashcodes pour deux raisons principales. Supposons que nous ayons un type avec deux champs int :

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 donne quelques options. Je pense que pour la plupart des cas, ce qui précède est "assez bon" et il est incroyablement facile de s'en souvenir et d'obtenir le droit. L'alternative FNV est tout aussi simple, mais utilise différentes constantes et XOR au lieu de ADD comme une opération de combinaison. Il ressemble à quelque chose comme comme le code ci-dessous, mais L'algorithme normal FNV fonctionne sur des octets individuels, de sorte que cela nécessiterait une modification pour effectuer une itération par octet, au lieu de par valeur de hachage 32 bits. FNV est également conçu pour des longueurs de données variables, alors que la façon dont nous l'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 le cas de l'échantillon 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 qu'idéalement vous devriez empêcher votre état sensible à l'égalité (et donc sensible au hashcode) de changer après l'ajout à une collection qui dépend du code de hachage.

selon la documentation :

vous pouvez outrepasser GetHashCode pour les types de référence immuables. En général, pour les types de référence mutables, vous devriez outrepasser GetHashCode seulement si:

  • vous pouvez calculer le code de hachage à partir des champs qui ne sont pas modifiables; ou
  • vous pouvez Vous assurer que le code de hachage d'un objet mutable ne change pas alors que l'objet est contenu dans une collection qui s'appuie sur son code de hachage.
1382
répondu Jon Skeet 2018-03-16 10:20:13
la source

Type Anonyme

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

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

Cela fonctionne pour n'importe quel nombre de propriétés. Il n'utilise pas la boxe. Il utilise l'algorithme déjà mis en œuvre dans le cadre des types anonymes.

ValueTuple - mise à Jour pour C# 7

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

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

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

308
répondu Rick Love 2018-08-16 17:13:51
la source

Voici mon helper hashcode.

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

aussi il a la méthode d'extension pour fournir une interface fluide, de sorte que vous pouvez l'utiliser comme ceci:

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

ou comme ceci:

public override int GetHashCode()
{
    return 0.CombineHashCode(Manufacturer)
        .CombineHashCode(PartN)
        .CombineHashCode(Quantity);
}
94
répondu nightcoder 2011-03-25 18:29:38
la source

j'ai une classe de hachage dans la bibliothèque Helper que je l'utilise à cette fin.

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

alors, vous pouvez simplement l'utiliser comme:

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

Je n'ai pas évalué son rendement, donc toute rétroaction est la bienvenue.

57
répondu Wahid Shalaly 2016-06-22 15:00:19
la source

voici ma classe helper en utilisant Jon Skete's implementation .

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

Utilisation:

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

si vous voulez éviter d'écrire une méthode d'extension pour le système.Int32:

public struct HashCode
{
    private readonly int _value;

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

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

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

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

    public override int GetHashCode() => _value;
}

il est encore générique, il évite toujours toute allocation de tas et il 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);
}

mise à jour après le commentaire de Martin:

obj != null cause boxe donc je suis passé au compareur par défaut.

Édition (Mai 2018):

EqualityComparer<T>.Default getter est maintenant un JIT intrinsic - le pull request est mentionné par Stephen Toub dans ce billet de blog .

50
répondu Şafak Gür 2018-05-06 17:18:58
la source

dans la plupart des cas où Equals() compare plusieurs champs il n'a pas vraiment d'importance si votre GetHash() hache sur un champ ou sur plusieurs. Vous avez juste à vous assurer que le calcul du hash est vraiment bon marché ( aucune allocation , s'il vous plaît) et rapide ( aucun calcul lourd et certainement pas de connexions de base de données) et fournit une bonne distribution.

le levage lourd doit faire partie de la méthode Equal (); le hachage doit être opération très bon marché pour activer calling Equals() sur le moins d'articles possible.

Et un dernier conseil: Ne comptez pas sur GetHashCode() étant stable sur plusieurs application s'exécute . Beaucoup de types.Net ne garantissent pas que leurs codes de hachage restent les mêmes après un redémarrage, donc vous ne devriez utiliser la valeur de GetHashCode() que pour les structures de données en mémoire.

26
répondu Bert Huijben 2009-02-23 14:55:44
la source

jusqu'à récemment, ma réponse aurait été très proche de celle de Jon Skeet. Cependant, j'ai récemment commencé un projet qui a utilisé la puissance-de-deux tables de hachage, qui est des tables de hachage où la taille de la table interne est 8, 16, 32, etc. Il y a une bonne raison de préférer les nombres premiers, mais il y a aussi des avantages à pouvoir de deux tailles.

et c'était nul. Donc après un peu d'expérimentation et de recherche j'ai commencé à re-Hasher mes coups de fouet avec le

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 hash power-of-two n'était plus nulle.

cela me dérangeait cependant, parce que ce qui précède ne devrait pas fonctionner. Ou plus précisément, il ne devrait pas fonctionner à moins que l'original GetHashCode() était pauvre d'une manière très particulière.

re-mixer un hashcode ne peut pas améliorer un grand hashcode, car le seul effet possible est d'introduire quelques collisions supplémentaires.

Re-mixer un code de hachage ne peut pas améliorer un code de hachage terrible, parce que le seul effet possible est de changer par exemple un grand nombre de collisions sur la valeur 53 à un grand nombre de valeur 18.3487.291.

Re-mélange d'un code de hachage ne peut qu'améliorer un code de hachage qui a fait au moins assez bien en évitant absolue collisions dans son aire de répartition (2 32 valeurs possibles), mais mal à éviter les collisions lors de l'modulo serais en bas pour une table de hachage. Alors que le le modulo plus simple d'une table de pouvoir-de-deux a rendu cela plus apparent, il avait aussi un effet négatif avec les tables plus communes de nombre premier, qui n'était tout simplement pas aussi évident (le travail supplémentaire dans le ressasser l'emporterait sur le bénéfice, mais le bénéfice serait toujours là).

Edit: j'utilisais aussi l'adressage ouvert, ce qui aurait aussi augmenté la sensibilité à la collision, peut-être plus que le fait que c'était le pouvoir-de-deux.

Et bien, c'était troublant combien les implémentations string.GetHashCode() dans .NET (ou l'étude ici ) pourraient être améliorées de cette façon (sur l'ordre d'essais courant environ 20-30 fois plus vite en raison de moins de collisions) et plus troublant combien mes propres codes de hachage pourraient être améliorés (beaucoup 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 beaucoup pire que . La plupart du temps, c'était assez "bon" pour beaucoup d'utilisations, mais je voulais quelque chose de mieux.

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

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

maintenant, SpookyHash n'est pas un petit morceau de code facile à mémoriser. Mon port est d'autant plus faible que j'en ai livré beaucoup pour une meilleure vitesse*. Mais c'est à ça que sert la réutilisation de code.

puis j'ai mis que projet à un côté, parce que tout comme le projet original avait produit la question de savoir comment produire un meilleur code de hachage, de sorte que le projet a produit la question de savoir comment produire un meilleur. net memcpy.

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

c'est rapide, pour lequel Bob Jenkins mérite la plus grande partie du mérite parce que son code d'origine I porté à partir est encore plus rapide, surtout sur les machines 64 bits dont l'algorithme est optimisé pour‡.

le code complet peut être vu à https://bitbucket.org/JonHanna/spookilysharp/src mais considérer que le code ci-dessus est une version simplifiée de celui-ci.

cependant, puisqu'il est maintenant déjà écrit, on peut s'en servir 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 aussi des valeurs de graine, donc si vous avez besoin de traiter l'entrée non fiable et que vous voulez protéger contre les attaques DoS de hachage vous pouvez définir une graine basée sur le temps de disponibilité ou similaire, et rendre les résultats imprévisibles par 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 en ceci est que la méthode de rotation manuelle qui retourne (x << n) | (x >> -n) améliore les choses. J'aurais été sûr que la gigue aurait inline que pour moi, mais profilage a montré le contraire.

decimal n'est pas natif du point de vue de .NET bien qu'il soit du C#. Le problème est que sa propre GetHashCode() considère la précision comme importante alors que sa propre Equals() ne le fait pas. Les deux sont des choix valables, mais pas mixte comme ça. Dans la mise en œuvre de votre propre version, vous devez choisir de faire l'un ou l'autre, mais je ne peux pas savoir ce que vous voulez.

‡à titre de comparaison. S'il est utilisé sur une corde, 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, mais encore assez rapide pour être un choix raisonnable.

19
répondu Jon Hanna 2018-04-05 00:11:03
la source

celle-ci est 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);
    }
}
12
répondu Magnus 2011-12-02 18:20:42
la source

Voici mon approche simpliste. J'utilise le modèle de constructeur classique pour cela. Il est tapesafe (pas de boxe/unboxing) et aussi compatbile 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);
        }
    }
}
8
répondu bitbonk 2013-04-15 10:18:32
la source

Voici une autre implémentation courante de l'algorithme affiché 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(); }
    }
}

Utilisation:

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 que HashValue n'est pas appelé avec une classe en raison de la contrainte de type générique. Mais il n'y a pas de support de compilateur pour HashObject puisque l'ajout d'un argument Générique ajoute aussi une opération de boxe.

8
répondu Scott Wegner 2017-05-23 13:31:37
la source

à partir de https://github.com/dotnet/coreclr/pull/14863 , il y a une nouvelle façon de générer des codes de hachage qui est super simple! Il suffit d'écrire

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 la mise en œuvre.

6
répondu James Ko 2017-11-23 18:06:05
la source

ReSharper les utilisateurs peuvent générer GetHashCode, égaux, et d'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;
    }
}
4
répondu Charles Burns 2018-04-05 17:19:15
la source

la plupart de mon travail est fait avec la connectivité de base de données qui signifie que toutes mes classes ont 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 hashcode.

// Unique ID from database
private int _id;

...    
{
  return _id.GetHashCode();
}
3
répondu Mark G 2008-11-05 08:03:24
la source

assez similaire à la solution de nightcoder sauf qu'il est plus facile d'élever des nombres premiers si vous le voulez.

PS: c'est l'un de ces moments où vous vomissez un peu dans votre bouche, sachant que cela pourrait être refactorisé dans une méthode avec 9 par défaut mais ce serait plus lent, donc vous fermez juste 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;
        }
    }
}
3
répondu Dbl 2014-10-21 21:49:34
la source

j'ai rencontré un problème avec les flotteurs et les décimales en utilisant l'implémentation choisie comme réponse ci-dessus.

ce test échoue (flotte; le hash est le même bien que 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 cet essai est réussi (avec des essais 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));

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

    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;
                }
        }
    }
1
répondu HokieMike 2014-09-28 20:44:25
la source

si nous n'avons pas plus de 8 propriétés (avec un peu de chance), voici une autre alternative.

ValueTuple est une structure et semble avoir une application solide GetHashCode .

cela signifie que nous pourrions simplement faire ceci:

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

regardons l'implémentation actuelle de .NET Core pour ValueTuple 's GetHashCode .

c'est 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 c'est 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éplacement circulaire) h1 par 5 positions.
  • Ajouter le résultat et h1 ensemble.
  • XOR le résultat avec h2.
  • commencer par effectuer l'opération ci-dessus sur { static random seed, h1 }.
  • pour chaque en outre, effectuer l'opération sur le résultat précédent et l'article 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, s'en remettre à ValueTuple pour notre propre GetHashCode peut ne pas être aussi rapide que nous le souhaiterions et l'attendons. ce commentaire dans une discussion connexe montre que le fait d'appeler directement HashHelpers.Combine est plus performant. Sur d'un autre côté, celui-ci est interne, donc nous devrions copier le code, sacrifiant une grande partie de ce que nous avions gagné ici. Aussi, nous serions responsables de se rappeler d'abord Combine avec la graine aléatoire. Je ne sais pas quelles seront les conséquences si nous sautons cette étape.

1
répondu Timo 2018-05-15 15:00:46
la source

Microsoft tête depuis plusieurs façon de hachage...

//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 grands 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 int en utilisant GetHashCode() alors les valeurs int seront xor'ED et le résultat sera votre hachage.

pour ceux qui utilisent le hash comme ID (je veux dire une valeur unique), le hash est naturellement limité à un nombre de chiffres, je pense qu'il était de 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 sont identiques, donc ne l'utilisez pas comme un identifiant. (peut-être un jour je vais utiliser votre composant)

0
répondu deadManN 2018-04-06 14:48:24
la source

Autres questions sur algorithm .net hashcode gethashcode