Combinaisons rapides et simples de codes de hachage

Question

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 ?

Answer 1

Il s'agit d'un reconditionnement de Sauce spéciale La solution brillamment étudiée par l'auteur.
Il utilise des tuples de valeurs ( ITuple ).
Cela permet de définir des valeurs par défaut pour les paramètres seed y factor .

public static int CombineHashes(this ITuple tupled, int seed=1009, int factor=9176)
{
    var hash = seed;

    for (var i = 0; i < tupled.Length; i++)
    {
        unchecked
        {
            hash = hash * factor + tupled[i].GetHashCode();
        }
    }

    return hash;
}

Uso:

var hash1 = ("Foo", "Bar", 42).CombineHashes();    
var hash2 = ("Jon", "Skeet", "Constants").CombineHashes(seed=17, factor=31);

Answer 2

Si vous recherchez la rapidité et que vous n'avez pas trop de collisions, XOR est le plus rapide. Pour éviter un regroupement autour de zéro, vous pourriez faire quelque chose comme ceci :

finalHash = hash1 ^ hash2;
return finalHash != 0 ? finalHash : hash1;

Bien sûr, un peu de prototypage devrait vous donner une idée des performances et du regroupement.

Answer 3

Si vos hachages d'entrée sont de la même taille, répartis de façon homogène et sans lien entre eux, un XOR devrait convenir. De plus, il est rapide.

La situation que je suggère est celle où vous voulez faire

H = hash(A) ^ hash(B); // A and B are different types, so there's no way A == B.

Bien entendu, si l'on peut s'attendre à ce que A et B aboutissent à la même valeur avec une probabilité raisonnable (non négligeable), il ne faut pas utiliser XOR de cette manière.

Answer 4

En supposant que vous disposiez d'une fonction toString() appropriée (où vos différents champs doivent apparaître), je renverrais simplement son code de hachage :

this.toString().hashCode();

Ce n'est pas très rapide, mais cela devrait permettre d'éviter les collisions.

Answer 5

Je recommanderais d'utiliser les fonctions de hachage intégrées dans System.Security.Cryptography plutôt que de créer vos propres fonctions.