Discussion :

[nzo70]

Bonjour,

je souhaite actuellement développer ma propre fonction de hachage. Après des recherches sur internet pour en comprendre le fonctionnement, je me suis aperçu que chaque caractère pouvait etre affecté à un int et que cela donnais une valeur différente pour chaque caractère

Par conséquent, je me demande si une fonction de hachage ne pourrait pas simplement être écrite comme ci-dessous

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
int fonctionHash(String s){
 
    int h = 0;
 
    for(int i = 0; i<s.length();i++){
 
         h += s.charAt(i);
 
    }
 
    return h;
 
}

Sur les quelques tests que j'ai effectué cela me donne bien une valeur différente pour chaque String que j'ai testée mais j'ai l'impression que la fonction est trop simple...

Pourriez vous donc me dire si cela est une fonction de hachage correcte ou non? Si non je voudrais également savoir pourquoi elle n'est pas correcte?

Par ailleurs j'ai trouvé sur le net une fonction faite a peu près de la même manière sauf dans la boucle (voir ci-dessous) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
 
int fonctionHash(String s){
 
    int B = 256; (en reference a une puissance de 2?)
    int N = 311; (en reference à un nombre premier?);
    int h = 0;
 
    for(int i = 0; i<s.length();i++){
 
         h = (h*B + s.charAt(i)) % N;
 
    }
 
    return h;
 
}

Pourquoi dans cet exemple les developpeurs n'ont ils pas simplement pris la valeur de s.charAt(i) comme je l'ai fait?


merci

[CyberChouan]

Pourquoi dans cet exemple les developpeurs n'ont ils pas simplement pris la valeur de s.charAt(i) comme je l'ai fait?

Parce que le but d'une fonction de hachage est d'assurer au maximum que deux chaînes différentes donnent des hachages différents.

Dans ton cas, le hachage est mauvais : il ne tient pas compte de l'ordre dans lequel sont tes lettres. Ainsi, tous les anagrammes auront la même valeur hachée.

L'algorithme que tu as trouvé est meilleurs : la valeur "h" étant réutilisée dans le calcul, les anagrammes auront plus facilement des hachages différents.

Vérifie toi-même

[Jidefix]

Souviens-toi des deux règles de base des fonctions de hash:
Si y = hash(x);

- Il est très difficile* de trouver un z différent de x tel que hash(z) = y
- Il est très difficile* de retrouver x en se basant uniquement sur y.

On part bien sûr du principe que tout le monde connaît l'algorithme.

Si ton algorithme ne respecte pas ces deux règles, il ne s'agit pas d'un bon algorithme de hash.
Ici, ton premier algo ne respecte pas la première règle.

Le deuxieme algo ne respecte pas la seconde règle car si on hashe une seule lettre, le résultat est exactement la valeur ASCII de cette lettre

*très difficile, en crypto, signifie "trop long". Le minimum syndical étant que l'algorithme de force brute (c'est à dire qui consiste à tester toutes les possibilités) doit s'effectuer en plus de 2^80 opérations (enfin ça c'était il y a deux ans je ne sais pas si ça a changé)