112 votes

Combinaisons rapides et simples de codes de hachage

Peut-on recommander des moyens rapides et simples pour combiner les codes de hachage de deux objets ? Je ne m'inquiète pas trop des collisions puisque j'ai une table de hachage qui s'en chargera efficacement, je veux juste quelque chose qui génère un code le plus rapidement possible.

En lisant SO et le web, il semble qu'il y ait quelques candidats principaux :

  1. XORing
  2. XORing avec la multiplication par les nombres premiers
  3. Opérations numériques simples telles que la multiplication/division (avec contrôle de dépassement ou enveloppement)
  4. Construction d'une chaîne de caractères et utilisation de la méthode Hash Code des classes de chaînes de caractères

Que recommanderait-on et pourquoi ?

162voto

Jon Skeet Points 692016

Personnellement, j'éviterais XOR - cela signifie que deux valeurs égales donneront 0 - donc hash(1, 1) == hash(2, 2) == hash(3, 3) etc. De même, hash(5, 0) == hash(0, 5) etc ce qui peut arriver occasionnellement. I avoir Il a été délibérément utilisé pour le hachage d'ensembles - si vous voulez hacher une séquence d'éléments et que vous avez l'intention de le faire, vous pouvez l'utiliser pour le hachage d'ensembles. ne La commande n'a pas d'importance, c'est une bonne chose.

J'utilise habituellement :

unchecked
{
    int hash = 17;
    hash = hash * 31 + firstField.GetHashCode();
    hash = hash * 31 + secondField.GetHashCode();
    return hash;
}

C'est la forme que Josh Bloch propose dans Effective Java. La dernière fois que j'ai répondu à une question similaire, j'ai réussi à trouver un article où cette forme était discutée en détail - IIRC, personne ne sait vraiment pourquoi elle fonctionne bien, mais c'est le cas. Elle est également facile à retenir, facile à mettre en œuvre et facile à étendre à n'importe quel nombre de champs.

106voto

c45207 Points 1825

Si vous utilisez .NET Core 2.1 ou plus récent, ou .NET Framework 4.6.1 ou plus tard, envisagez d'utiliser l'option System.HashCode pour faciliter la production de codes de hachage composites. Elle a deux modes de fonctionnement : Ajouter et Combiner.

Un exemple utilisant Combine qui est généralement plus simple et fonctionne pour un maximum de huit articles :

public override int GetHashCode()
{
    return HashCode.Combine(object1, object2);
}

Exemple d'utilisation Add :

public override int GetHashCode()
{
    var hash = new HashCode();
    hash.Add(this.object1);
    hash.Add(this.object2);
    return hash.ToHashCode();
}

Pour :

  • Fait partie de .NET lui-même, à partir de .NET Core 2.1/.NET Standard 2.1 (cependant, voir l'escroquerie ci-dessous).
    • Pour le .NET Framework 4.6.1 et les versions ultérieures, l'option Microsoft.Bcl.HashCode Le paquet NuGet peut être utilisé pour porter ce type de produit.
  • Il semble que les caractéristiques de performance et de mélange soient bonnes, d'après le travail effectué auparavant par l'auteur et les évaluateurs. fusionner avec le repo corefx
  • Traite automatiquement les nullités
  • Les surcharges qui prennent IEqualityComparer instances

Cons :

68voto

Special Sauce Points 1341

Bien que le modèle décrit dans la réponse de Jon Skeet fonctionne bien en général en tant que famille de fonctions de hachage, le choix des constantes est important et la graine de 17 et le facteur de 31 comme indiqué dans la réponse, ne fonctionnent pas bien du tout pour les cas d'utilisation courants. Dans la plupart des cas d'utilisation, les valeurs hachées sont beaucoup plus proches de zéro que des valeurs de int.MaxValue et le nombre d'éléments soumis à un hachage commun est inférieur ou égal à quelques dizaines.

Pour le hachage d'un tuple entier {x, y} donde -1000 <= x <= 1000 y -1000 <= y <= 1000 Il a un taux de collision abyssal de près de 98,5 %. A titre d'exemple, {1, 0} -> {0, 31} , {1, 1} -> {0, 32} , etc. Si nous étendons la couverture pour inclure également les n-tuples où 3 <= n <= 25 En revanche, il est moins mauvais avec un taux de collision d'environ 38%. Mais nous pouvons faire beaucoup mieux.

public static int CustomHash(int seed, int factor, params int[] vals)
{
    int hash = seed;
    foreach (int i in vals)
    {
        hash = (hash * factor) + i;
    }
    return hash;
}

J'ai écrit une boucle de recherche par échantillonnage de Monte Carlo qui a testé la méthode ci-dessus avec diverses valeurs pour la graine et le facteur sur divers n-tuples aléatoires d'entiers aléatoires. i . Les plages autorisées sont les suivantes 2 <= n <= 25 (où n était aléatoire mais biaisée vers le bas de la fourchette) et les -1000 <= i <= 1000 . Au moins 12 millions de tests de collision uniques ont été effectués pour chaque paire de semences et de facteurs.

Après environ 7 heures de fonctionnement, la meilleure paire trouvée (où la graine et le facteur étaient tous deux limités à 4 chiffres ou moins) était : seed = 1009 , factor = 9176 avec un taux de collision de 0,1131%. Dans les zones à 5 et 6 chiffres, il existe des options encore meilleures. Mais par souci de concision, j'ai sélectionné la meilleure option à 4 chiffres, qui fonctionne très bien dans tous les cas courants. int y char scénarios de hachage. Il semble également fonctionner correctement avec des nombres entiers beaucoup plus importants.

Il convient de noter que le fait d'être "premier" ne semble pas être une condition préalable générale pour obtenir de bons résultats en tant que semence et/ou facteur, bien que cela soit probablement utile. 1009 mentionné ci-dessus est en fait premier, mais 9176 ne l'est pas. J'ai explicitement testé des variantes de ce principe en modifiant factor à divers nombres premiers proches de 9176 (tout en laissant seed = 1009 ) et elles sont toutes moins performantes que la solution ci-dessus.

Enfin, j'ai également effectué une comparaison avec la famille générique de fonctions de recommandation de ReSharper, à savoir hash = (hash * factor) ^ i; et l'original CustomHash() comme indiqué ci-dessus, le surpasse largement. Le style XOR de ReSharper semble avoir des taux de collision de l'ordre de 20 à 30 % pour les hypothèses de cas d'utilisation courants et ne devrait pas être utilisé à mon avis.

26voto

Yepeekai Points 131

Utiliser la logique de combinaison dans le tuple. L'exemple utilise des tuples c#7.

(field1, field2).GetHashCode();

21voto

Stipo Points 2776

Je présume que l'équipe du .NET Framework a fait un travail décent en testant ses System.String.GetHashCode() Je l'utiliserais donc :

// System.String.GetHashCode(): http://referencesource.microsoft.com/#mscorlib/system/string.cs,0a17bbac4851d0d4
// System.Web.Util.StringUtil.GetStringHashCode(System.String): http://referencesource.microsoft.com/#System.Web/Util/StringUtil.cs,c97063570b4e791a
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash1 = (5381 << 16) + 5381;
    int hash2 = hash1;

    int i = 0;
    foreach (var hashCode in hashCodes)
    {
        if (i % 2 == 0)
            hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ hashCode;
        else
            hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ hashCode;

        ++i;
    }

    return hash1 + (hash2 * 1566083941);
}

Une autre application est celle de System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32) y System.Array.CombineHashCodes(System.Int32, System.Int32) des méthodes. Celle-ci est plus simple, mais n'offre probablement pas une aussi bonne distribution que la méthode ci-dessus :

// System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#System.Web/Util/HashCodeCombiner.cs,21fb74ad8bb43f6b
// System.Array.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#mscorlib/system/array.cs,87d117c8cc772cca
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash = 5381;

    foreach (var hashCode in hashCodes)
        hash = ((hash << 5) + hash) ^ hashCode;

    return hash;
}

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X