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

Question

Dans .NET System.Object.GetHashCode méthode est l'utilisation dans beaucoup d'endroits tout au long de l' .NET bibliothèques de classes de base. En particulier lors de la recherche d'éléments dans une collection rapide ou pour déterminer l'égalité. Est-il un algorithme standard/ meilleures pratiques sur la façon de mettre en œuvre l' GetHashCode remplacement pour mes classes personnalisées, donc je ne pas dégrader les performances?

Answer 1

J'ai l'habitude d'aller avec quelque chose comme la mise en œuvre compte tenu de Josh Bloch est fabuleux Efficace Java. C'est rapide et crée une assez bonne de hachage qui est peu susceptible de provoquer des collisions. Choisir deux nombres premiers, par exemple, 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;
    }
}

(EDIT: Comme indiqué dans les commentaires, vous pouvez trouver qu'il est préférable de choisir un grand premier à multiplier par la place. Apparemment 486187739 est bon...)

C'est mieux que la pratique courante de l' XORing hashcodes pour deux raisons principales. Supposons que nous avons un type avec deux int champs:

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

Par la manière, plus l'algorithme est celui qui est actuellement utilisé par le compilateur C# pour les types anonymes.

EDIT: Cette page donne quelques options. Je pense que pour la plupart des cas ci-dessus est "assez bon" et il est incroyablement facile à mémoriser et à obtenir le droit. La FNV alternative est aussi simple, mais utilise différentes constantes et XOR au lieu de l'AJOUTER comme une combinaison de l'opération. Il ressemble à quelque chose comme le code ci-dessous, mais la normale FNV algorithme opère sur les différents octets, de sorte que cela nécessiterait la modification à effectuer une itération par octets, au lieu de par 32-bit valeur de hachage. FNV est également conçu pour la longueur variable des données, 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 ne fonctionne pas (dans le cas de l'échantillon testé) que l'ajout de l'approche 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;
    }
}

EDIT: Notez qu'une chose à prendre en compte est que, idéalement, vous devez prévenir votre égalité sensible (et donc hashcode sensible) de l'état de changer après l'ajouter à une collection qui repose sur le code de hachage.

Selon la documentation:

Vous pouvez remplacer GetHashCode pour immuable types de référence. En général, pour mutable types de référence, vous devez remplacer GetHashCode si et seulement si:

• Vous pouvez calculer le code de hachage de champs qui ne sont pas mutables; 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.

Answer 2

Microsoft dispose déjà d'un bon générique HashCode générateur: il suffit de copier votre propriété/domaine de valeurs d'un type anonyme et de hachage:

new { A = PropA, B = PropB, C = PropC, D = PropD }.GetHashCode();

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

Answer 3

Voici mon hashcode helper.
C'est l'avantage est qu'elle utilise un type générique arguments et ne sera donc pas en cause la 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 aussi une extension de la méthode de 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);
}

Answer 4

J'ai un Hachage de la classe dans la bibliothèque d'aide 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;

    // I have added the unchecked keyword to make sure 
    // not get an overflow exception.
    // It can be enhanced later by catching the OverflowException.

    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 l'utiliser comme:

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

Je n'ai pas d'évaluer sa performance, donc tout commentaires sont les bienvenus.

Answer 5

Voici ma classe helper qui utilise la mise en œuvre de Jon Skeet posté.

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

    public static int Hash<T>(this int hash, T obj)
    {
        var h = obj != null ? obj.GetHashCode() : 0;
        return unchecked((hash * 31) + h);
    }
}

Utilisation:

public override int GetHashCode()
{
    return HashCode.Start
        .Hash(field1)
        .Hash(field2)
        .Hash(field3);
}

Edit (1er avril 2014)

J'ai décidé que je n'aimais pas l'idée d'écrire une méthode d'extension pour le type Int32 j'ai donc écrit une structure pour envelopper la valeur de hachage calculée.

public struct HashCode
{
    private readonly int hashCode;

    public HashCode(int hashCode)
    {
        this.hashCode = hashCode;
    }

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

    public static implicit operator int(HashCode hashCode)
    {
        return hashCode.GetHashCode();
    }

    public HashCode Hash<T>(T obj)
    {
        var h = obj != null ? obj.GetHashCode() : 0;
        unchecked { h += this.hashCode * 31; }
        return new HashCode(h);
    }

    public override int GetHashCode()
    {
        return this.hashCode;
    }
}

C'est encore le générique, il encore évite 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);
}