Question Quel est le meilleur algorithme pour un System.Object.GetHashCode surchargé?


En .NET System.Object.GetHashCode La méthode est utilisée dans beaucoup d'endroits, dans les bibliothèques de classes de base .NET. Surtout lorsque vous recherchez rapidement des articles dans une collection ou pour déterminer l'égalité. Existe-t-il un algorithme / une bonne pratique standard sur la façon de mettre en GetHashCode remplacer pour mes classes personnalisées afin que je ne dégrade pas les performances?


1216
2017-11-04 20:53


origine


Réponses:


Je vais généralement avec quelque chose comme la mise en œuvre donnée dans Josh Bloch fabuleux  Java efficace. C'est rapide et crée un assez bon hasch qui est peu susceptible de causer des collisions. Choisissez deux nombres premiers différents, par ex. 17 et 23, et faire:

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 à multiplier par plutôt. 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ù les nombres non premiers sont souvent utilisés. Dans le non-tout à fait-FNV Par exemple, par la suite, j'ai utilisé des nombres qui fonctionnent apparemment bien - mais la valeur initiale n'est pas un nombre premier. (La constante de multiplication est Premier cependant. Je ne sais pas à quel point c'est important.)

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

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

D'ailleurs, l'algorithme précédent est celui actuellement utilisé par le compilateur C # pour les types anonymes.

Cette page donne pas mal d'options. Je pense que, dans la plupart des cas, ce qui précède est «assez bon» et il est incroyablement facile de s'en souvenir et de bien faire les choses. le FNV alternative est similaire simple, mais utilise des constantes différentes et XOR au lieu de ADD comme une opération de combinaison. Ça a l'air quelque chose comme le code ci-dessous, mais l'algorithme FNV normal fonctionne sur des octets individuels, donc cela nécessiterait une modification pour effectuer une itération par octet, plutôt que par une valeur de hachage de 32 bits. FNV est également conçu pour des longueurs de données variables, alors que nous l'utilisons ici toujours pour le même nombre de valeurs de champs. Les commentaires sur cette réponse suggèrent que le code ici ne fonctionne pas aussi bien (dans 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 que, dans l'idéal, vous devriez éviter que votre état sensible à l'égalité (et donc au code hachage) ne change après l'avoir ajouté à une collection qui dépend du code de hachage.

Selon le Documentation:

Vous pouvez remplacer GetHashCode pour les types de référence immuables. En général, pour les types de référence modifiables, vous devez remplacer GetHashCode uniquement 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 lorsque l'objet est contenu dans une collection qui repose sur son code de hachage.

1357
2017-11-04 20:56



Microsoft fournit déjà un bon générateur générique HashCode: Copiez simplement vos valeurs de propriété / champ à 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 ou de ressources supplémentaires. Il utilise simplement l'algorithme déjà implémenté dans le framework pour les types anonymes.


302
2018-01-07 21:38



Voici mon assistant hashcode.
Son avantage est qu'il utilise des arguments de type génériques et ne provoquera 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();   
        }
    }

En outre, il a une 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
2018-04-04 18:26



J'ai une classe Hashing 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;
}

Ensuite, vous pouvez simplement l'utiliser comme:

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

Je n'ai pas évalué sa performance, donc tout commentaire est le bienvenu.


57
2018-02-23 11:46



Voici ma classe d'aide en utilisant La mise en œuvre 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 voulez éviter d'écrire une méthode d'extension pour System.Int32:

public struct HashCode
{
    private readonly int _value;

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

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

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

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

    public override int GetHashCode() => _value;
}

Il est toujours 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 causé la boxe donc je suis passé au comparateur par défaut.

  • Voir cette réponse en ce qui concerne les performances du comparateur par défaut.
  • Voir cette question pour une discussion sur les codes de hachage des valeurs nulles.

Modifier (mai 2018):

EqualityComparer<T>.Default getter est maintenant un JIT intrinsèque - le tirer une requête est mentionné par Stephen Toub dans ce blog.


49
2017-09-04 12:32



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

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

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


26
2018-02-23 11:55



Jusqu'à récemment, ma réponse aurait été très proche de celle de Jon Skeet. Cependant, j'ai récemment démarré un projet qui utilisait des tables de hachage power-of-two, c'est-à-dire des tables de hachage dont la taille est de 8, 16, 32, etc. Il y a de bonnes raisons de privilégier les tailles de nombres premiers. Certains avantages sont également liés à la puissance de deux tailles.

Et ça a été plutôt nul. Donc, après un peu d'expérimentation et de recherche, j'ai commencé à refaire mes hachages avec ce qui suit:

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 power-of-two ne m'a plus rien sucé.

Cela m'a dérangé 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-mélanger un code de hachage ne peut pas améliorer un grand code de hachage, car le seul effet possible est que nous introduisons quelques collisions de plus.

Re-mélanger un code de hachage ne peut pas améliorer un code de hachage terrible, parce que le seul effet possible est nous changeons par ex. un grand nombre de collisions sur la valeur 53 à un grand nombre de valeur 18,3487,291.

Le remixage d'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 dans toute son étendue (232 valeurs possibles) mais mal à éviter les collisions lorsque modulo'd vers le bas pour une utilisation réelle dans une table de hachage. Tandis que le modulo plus simple d'une table de deux puissances le rendait plus apparent, il avait aussi un effet négatif sur les tables de nombres premiers les plus courantes, ce qui n'était pas aussi évident (le travail supplémentaire de rehaussement l'emportait sur le bénéfice , mais le bénéfice serait toujours là).

Edit: J'utilisais aussi l'adressage ouvert, ce qui aurait également augmenté la sensibilité à la collision, peut-être plus que le fait qu'il s'agissait d'un power-of-two.

Et bien, il était troublant combien le string.GetHashCode() implémentations dans .NET (ou étudier ici) pourrait être amélioré de cette façon (de l'ordre de 20 à 30 fois plus rapide en raison de moins de collisions) et plus dérangeant à quel point 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 qui étaient en fait utilisées comme base de réponses sur ce site, étaient bien pires que je ne l'aurais fait.. La plupart du temps, c'était «assez bon» pour la plupart des utilisations, mais je voulais quelque chose de mieux.

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

En fin de compte, je me suis installé sur le portage SpookyHash à .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 souvenir de morceau de code. Mon portage est encore moins important parce que j'en ai mis beaucoup en main pour une meilleure vitesse *. Mais c'est ce à quoi sert la réutilisation du code.

Alors je mets cette projet d'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 memoire .NET.

Puis je suis revenu, et a produit beaucoup de surcharges pour nourrir 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 car son code d'origine est 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érez que le code ci-dessus est une version simplifiée de celui-ci.

Cependant, puisqu'il est 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 départ, donc si vous avez besoin de traiter des entrées non fiables et que vous voulez protéger contre les attaques Hash DoS, vous pouvez définir une graine basée sur uptime 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 dans ceci est que main-inlining une méthode de rotation qui a retourné (x << n) | (x >> -n) choses améliorées. J'aurais été sûr que la gigue aurait souligné cela pour moi, mais le profilage a montré le contraire.

decimal n'est pas natif de la perspective .NET bien qu'il provienne du C #. Le problème avec cela est que son propre GetHashCode() traite la précision comme significative tandis que sa propre Equals() ne fait pas. Les deux sont des choix valables, mais pas mélangés comme ça. En implémentant votre propre version, vous devez choisir de faire l'un ou l'autre, mais je ne peux pas savoir lequel vous voulez.

‡ A 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, mais toujours assez rapide pour être un choix raisonnable.


18
2018-01-14 14:15