Générateur de code de hachage le plus rapide .NET

Question

J'implémente un GetHashCode personnalisé pour la classe System.Drawing.Point en C#. Ma méthode échoue actuellement l'exigence suivante:

var hashA = MyGetHashCode(new Point(1, 0)); 
var hashB = MyGetHashCode(new Point(0, 1)); 
var hashC = MyGetHashCode(new Point(0, 0)); 
var hashD = MyGetHashCode(new Point(1, 1)); 
Assert.AreNotEqual(hashA^hashB, hashC^hashD); 

Pour réussir ce test, je suis sûr que l'utilisation de nouvelles SHA256Managed() ComputeHash (de currentHash) fera.. Mais il y a un autre algorithme de hachage plus rapide? Je sais que SHA256 est une question de sécurité, et je n'en ai pas besoin.

Answer 1

Un hachage simple? Que diriez-vous quelque chose comme:

(17 * point.X) + (23 * point.Y); 

Ou pour l'entropie plus évidente:

int hash = -1047578147; 
hash = (hash * -1521134295) + point.X; 
hash = (hash * -1521134295) + point.Y; 

(numéros de code de type anonyme de C#)

Answer 2

Je sais que cela ne va pas répondre à votre question, mais Je dois mentionner pour d'autres lecteurs que vous modifiez le comportement par défaut d'une méthode intégrée de l'infrastructure. Selon la documentation:
http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx

L'implémentation par défaut de la méthode GetHashCode ne pas garantie des valeurs de retour uniques pour différents objets. En outre, le .NET Framework ne garantit pas l'implémentation par défaut de la méthode GetHashCode, et la valeur qu'elle rendement sera le même entre différentes versions du framework .NET . Par conséquent, l'implémentation par défaut de cette méthode doit être ne doit pas être utilisée comme un objet unique identifiant à des fins de hachage.

Answer 3

• Pourquoi faites-vous cela? Sûrement System.Drawing.Point a déjà une bonne fonction de hachage? Vous comprenez que le test ne représente pas une exigence stricte, n'est-ce pas? Les codes de hachage ne doivent pas nécessairement être uniques.

• Si vous voulez vraiment un très bon hachage des coordonnées en question, vous pouvez commencer à this page sur le hachage de plusieurs entiers.

Answer 4

Voici un article intéressant sur la vitesse de hachage:

A Hash Function for Hash Table Lookup

Answer 5

Une simple mise en œuvre de hachage Elf (il est en delphi, shoudl facile à traduire)

function ElfHash(id : string; tableSize : integer) : integer; 
var 
    i : integer; 
    h,x : longint; 
begin 
    h := 0; 
    // Obtener el valor numérico 
    for i := 1 to Length(id) do 
    begin 
    h := (h shl 4) + Ord(id[i]); 

    x := h and $F0000000; 
    if x <;>; 0 then 
     h = h xor (x shr 24) xor x; 
    end; 
    // Ajustar al tamaño de la tabla 
    result := h mod tableSize; 
end; 

Answer 6

Je ne Je ne sais pas quelle est votre application, mais vous cherchez peut-être un hachage Zobrist.

http://en.wikipedia.org/wiki/Zobrist_hashing

Il peut être mis à jour progressivement, ce qui le rend très rapide.

Answer 7

Si vous savez à l'avance que votre valeur de point est comprise entre 0 et N, vous pouvez utiliser hashcode = X+Y*N; Ceci est un hachage plutôt évident. Ce n'est pas aléatoire du tout, a une mauvaise répétition, et est généralement assez idiot. Cela équivaut à concaténer les bits de vos deux points, en supposant que N est une puissance de 2. Et qu'il y a une distribution uniforme parfaite et aucune collision.

J'ai utilisé cette stratégie avec un excellent effet dans le passé, mais admettons qu'elle a des limitations réelles (mais évidentes). Le plus grand étant ce qui arrive quand N est assez grand pour que N^2 ne corresponde pas à votre valeur de hachage (collisions douloureuses)