Pourquoi les codes de hachage générés par cette fonction ne sont-ils pas uniques?
https://stackoverflow.com/questions/63897
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je teste la fonction VB ci-dessous obtenue par une recherche Google. Je prévois de l'utiliser pour générer des codes de hachage pour une comparaison rapide de chaînes. Cependant, il arrive parfois que deux chaînes différentes aient le même code de hachage. Par exemple, ces chaînes
"Taille du segment 122Gen 1 (w3wp de mémoire CLR .NET): mccsmtpteweb025.20833333333333E-02"
"Taille du segment de mémoire 122Gen 2 (w3wp de mémoire CLR .NET): mccsmtpteweb015.20833333333333E-02"
ont le même code de hachage de 237117279.
S'il vous plaît dites-moi: - Quel est le problème avec la fonction? - Comment puis-je résoudre ce problème?
Merci
martin
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, src As Any, ByVal bytes As Long)
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor codes(i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
La solution
Je parie qu'il y a plus que des "occasions". lorsque deux chaînes génèrent le même hachage en utilisant votre fonction. En fait, cela arrive probablement plus souvent que vous ne le pensez.
Quelques choses à réaliser:
Premièrement, il y aura des collisions de hachage. Ça arrive. Même avec de très grands espaces comme MD5 (128 bits), deux chaînes peuvent toujours générer le même hachage résultant. Vous devez gérer ces collisions en créant des compartiments.
Deuxièmement, un entier long n'est pas vraiment un grand espace de hachage. Vous allez avoir plus de collisions que si vous utilisiez plus de bits.
Troisièmement, il existe des bibliothèques disponibles dans Visual Basic (comme l’espace de noms System.Security.Cryptography .NET) qui feront un bien meilleur travail de hachage que la plupart des simples mortels.
Autres conseils
Les deux chaînes ont les mêmes caractères. (Notez le '2' et le '1' qui sont retournés)
C'est pourquoi la valeur de hachage est la même.
Assurez-vous que la fonction de hachage prend en compte l'ordre des caractères.
Les fonctions de hachage ne garantissent pas l'unicité des valeurs de hachage. Si la plage de valeurs d'entrée (juger vos exemples de chaînes) est supérieure à la plage de valeurs de sortie (par exemple un entier de 32 bits), l'unicité est physiquement impossible.
Si le plus gros problème est qu’il ne tienne pas compte de la position des octets, vous pouvez le réparer comme ceci:
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor (codes(i) + i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
La seule différence est qu’il ajoute la position des caractères à sa valeur en octets avant le XOR.
Aucune fonction de hachage ne peut garantir l'unicité. Il existe environ 4 milliards d’entiers sur 32 bits. Ainsi, même la meilleure fonction de hachage générera des doublons lorsqu’elle sera présentée avec environ 4 milliards et 1 chaînes (et la plupart du temps probablement avant).
Passer aux hachages 64 bits ou même aux hachages 128 bits n'est pas vraiment la solution, même si cela réduit la probabilité de collision.
Si vous voulez une meilleure fonction de hachage, vous pouvez regarder les hachages cryptographiques, mais il serait préférable de reconsidérer votre algorithme et de décider si vous pouvez gérer les collisions d'une autre manière.
Espace de nom System.Security.Cryptography contient plusieurs classes pouvant effectuer un hachage pour vous (tel que MD5 ) qui les hachera probablement mieux que vous ne le feriez vous-même et demandera beaucoup moins d'effort.
Vous n'avez pas toujours à réinventer la roue.
Simple XOR est un mauvais hash: vous trouverez beaucoup de chaînes qui entrent en collision. Le hachage ne dépend pas de l'ordre des lettres dans la chaîne, d'une part.
Essayez d’utiliser le hash FNV http://isthe.com/chongo/tech/comp / fnv /
C’est très simple à mettre en œuvre. Il décale le code de hachage après chaque XOR, ainsi les mêmes lettres dans un ordre différent produiront un hachage différent.
Les fonctions de hachage ne sont pas censées renvoyer des valeurs distinctes pour des chaînes distinctes. Cependant, une bonne fonction de hachage doit renvoyer des valeurs différentes pour des chaînes qui se ressemblent. Les fonctions de hachage permettent de rechercher de nombreuses raisons, notamment la recherche dans une grande collection. Si la fonction de hachage est bonne et si elle renvoie des valeurs comprises dans l'intervalle [0, N-1], une grande collection de M objets sera divisée en N collections, chacune contenant environ M / N éléments. De cette façon, vous devez rechercher uniquement dans un tableau d'éléments M / N au lieu de chercher dans un tableau d'éléments M.
Toutefois, si vous ne disposez que de 2 chaînes, il <<>> n'est pas plus rapide de calculer la valeur de hachage pour celles-ci! Il est préférable de simplement comparer les deux chaînes.
Une fonction de hachage interressante pourrait être:
unsigned int hash(const char* name) {
unsigned mul=1;
unsigned val=0;
while(name[0]!=0) {
val+=mul*((unsigned)name[0]);
mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards
name++;
}
return val;
}
J'ai corrigé la coloration syntaxique pour lui.
En outre, pour ceux qui ne sont pas sûrs de l'environnement ou qui suggèrent un hachage plus sécurisé: c'est un VB classique (pre.Net), car .Net aurait besoin de parenthèses pour l'appel de CopyMemory.
IIRC, il n'y a pas de hachage sécurisé intégré à Classic VB. Il n’ya pas grand chose sur le Web non plus, alors c’est peut-être son meilleur pari.
Je ne vois pas très bien l'environnement dans lequel vous travaillez. S'agit-il d'un code .Net? Si vous voulez vraiment de bons codes de hachage, je vous recommanderais d’examiner les hachages cryptographiques (algorithmes éprouvés) au lieu d’essayer d’écrire les vôtres.
Btw, pourriez-vous éditer votre message et coller le code dans un exemple de code (voir barre d’outils)? Cela faciliterait la lecture.
"Ne faites pas ça."
Écrire votre propre fonction de hachage est une grave erreur, car votre langage a certainement déjà une implémentation de SHA-1, qui est une excellente fonction de hachage. Si vous avez seulement besoin de 32 bits (au lieu des 160 fournis par SHA-1), utilisez simplement les 32 derniers bits de SHA-1.
Ce hachage particulier fonctionne avec XOR tous les caractères d’une chaîne. Malheureusement, XOR est associatif:
(a XOR b) XOR c = a XOR (b XOR c)
Ainsi, toutes les chaînes avec les mêmes caractères d’entrée donneront le même code de hachage. Les deux chaînes fournies sont les mêmes, à l'exception de l'emplacement de deux caractères, elles doivent donc avoir le même hashcode.
Vous devrez peut-être trouver un meilleur algorithme, MD5 serait un bon choix.
L’opération XOR est commutative; c'est-à-dire que, lorsque XORing tous les caractères d'une chaîne, l'ordre des caractères importe peu. Toutes les anagrammes d’une chaîne produiront le même hachage XOR.
Dans votre exemple, votre deuxième chaîne peut être générée à partir de la première en permutant l'option "1". après " ... Gen " avec le premier " 2 " suivant.
Il n’ya rien de mal avec votre fonction. Toutes les fonctions de hachage utiles génèrent parfois des collisions et votre programme doit être prêt à les résoudre.
Une collision se produit lorsqu'une entrée est hachée à une valeur déjà identifiée avec une entrée antérieure. Si un algorithme de hachage ne peut pas générer de collision, les valeurs de hachage doivent être aussi grandes que les valeurs d'entrée. Un tel algorithme de hachage serait d'une utilité limitée par rapport au simple stockage des valeurs d'entrée.
-Al.
Il y a une implémentation visuelle de base du hachage MD5 ici
