Créer un code de hachage de deux nombres

Question

J'essaie de créer une fonction de hachage rapide pour une classe de nombres complexes. (a + b) en C#.

J'ai vu à plusieurs reprises le a.GetHashcode()^b.GetHashCode() méthode. Mais cela donnera le même code de hachage pour (a,b) y (b,a) .

Existe-t-il un algorithme standard pour faire cela et des fonctions dans le cadre .Net pour aider ?

Answer 1

Ma façon habituelle de créer un code de hachage pour un ensemble arbitraire d'éléments hachables :

int hash = 23;
hash = hash * 31 + item1Hash;
hash = hash * 31 + item2Hash;
hash = hash * 31 + item3Hash;
hash = hash * 31 + item4Hash;
hash = hash * 31 + item5Hash;
// etc

Dans votre cas item1Hash pourrait juste être a y item2Hash pourrait juste être b .

Les valeurs de 23 et 31 sont relativement peu importantes, du moment qu'il s'agit de nombres premiers (ou au moins copieurs).

Bien sûr, il y aura toujours des collisions, mais vous ne rencontrerez pas les problèmes désagréables habituels :

hash(a, a) == hash(b, b)
hash(a, b) == hash(b, a)

Si vous en savez plus sur ce que sont les valeurs réelles de a y b vous pouvez probablement faire mieux, mais il s'agit d'une bonne implémentation initiale, facile à mémoriser et à mettre en œuvre. Notez que s'il y a une chance que vous construisiez l'assemblage avec "check for arithmetic overflow/underflow" coché, vous devriez mettre tout cela dans un bloc non coché. (Le débordement est parfait pour cet algorithme).

Answer 2

Voici une approche possible qui tient compte de l'ordre. (La deuxième méthode est définie comme une méthode d'extension).

public int GetHashCode()
{
    return a.GetHashcode() ^ b.GetHashcode().RotateLeft(16);
}

public static uint RotateLeft(this uint value, int count)
{
    return (value << count) | (value >> (32 - count))
}

Il serait certainement intéressant de voir comment le Complex de .NET 4.0 le fait.

Answer 3

Voici une méthode standard :

hashcode = 23
hashcode = (hashcode * 37) + v1
hashcode = (hashcode * 37) + v2

23 et 37 sont premiers, mais vous pouvez aussi utiliser d'autres nombres.

Answer 4

Qu'en est-il de ceci :

(a.GetHashcode() + b).GetHashcode()

Cela vous donne un code différent pour (a,b) et (b,a) et ce n'est pas vraiment très original.

Answer 5

@JonSkeet donne un algorithme juste et polyvalent pour calculer un code de hachage à partir de n codes de hachage, mais il suppose que vous savez déjà quels membres d'un objet doivent être hachés, que vous savez quoi faire des membres nuls, et il omet une implémentation pour n éléments arbitraires. Nous développons donc sa réponse :

1. Seuls les propriétés et champs publics et immuables doivent contribuer au code de hachage d'un objet. Ils doivent être publics (ou isomorphiques au public) car nous devons pouvoir compter sur deux objets ayant la même surface visible pour avoir le même code de hachage (ce qui suggère une relation entre l'égalité des objets et l'égalité des codes de hachage), et ils doivent être immuables car le code de hachage d'un objet ne doit jamais changer au cours de sa vie (car alors vous pourriez vous retrouver avec un objet dans le mauvais emplacement d'une table de hachage !)
2. les membres nuls doivent être hachés comme une constante, telle que 0
3. L'algorithme de @JonSkeet est un exemple de manuel pour l'application de la fonction d'ordre supérieur de programmation fonctionnelle généralement appelée fold ( Aggregate en C# LINQ), où 23 est notre semence et <hash accumulator> * 31 + <current item hash> est notre fonction de pliage :

En fa#

let computeHashCode items =
    items
    |> Seq.map (fun item -> if item = null then 0 else item.GetHashCode())
    |> Seq.fold (fun hash itemHash -> hash * 31 + itemHash) 23

En C#

Func<IEnumerable<Object>, int> computeHashCode = items =>
    items
    .Select(item => item == null ? 0 : item.GetHashCode())
    .Aggregate(23, (hash, itemHash) => hash * 31 + itemHash);