Discussion :

[lvr]

Bonjour,
J'ai une array de int à hasher et j'utilise l'algorithme du tutoriel mais j'ai très vite des hash dupliquées.

Je prends comme SEED 3 et comme MULTIPLIER 5

Si mon array vaut {145} le hash vaut 3*5+145=160
Si mon array vaut {14,15} le hash vaut (3*5+14)*5+15=160
Si mon array vaut {7,50} le hash vaut (3*5+7)*5+50=160
...

Qu'est-ce qu'il y aurait comme amélioration à apporter ou autre algorithme pour hasher ces tableaux ?

[Deaf]

Bonjour,

je te conseillerais de mieux choisir ton multiplieur, c'est lui qui a le rôle le plus central (à première vue).

5 est un peut trop 'banal'. Dans le tuto, c'est 17 et dans la JRE c'est 31 (Arrays.hashCode).

Bien entendu, si ton appli manipule essentiellement des multiples de 31, utilise plutôt 37.
Je pense que si tu tapes dans les nombres premiers, tu auras de meilleurs résultats de manière générale.

Note:
Si tu faisais une méthode de hash de tableaux pour un besoin et non pour l'expérience, tu peux très bien te rabattre sur la méthode Arrays.hashCode).

[Jimmy_]

Bonjour,

Le tutoriel est un exemple, si tu veux une fonction de hashage qui minimise les collisions tourne toi vers les fonctions de hashage cryptographique comme MD5 ou SHA.
Tu es certains que dans un même groupe de valeur aucune n'aura le même hash. Ils sont conçus pour ça.

[lvr]

J'ai fait un rapide savant calcul pour m'apercevoir qu'avec 3 et 5 j'étais très limité dans le range de int que je pouvais utiliser (très exactement le int max vaut 67 ) donc j'ai revu le Seed et le Multiplier pour pouvoir un max plus élevé et qu'une array de 20 int < ce max donne un hash qui soit toujours un long (je détermine le max tel que hash({1,2})>=hash({max+1}))

Conclusion: Seed=89, Multiplier=7

Je n'ai pas poussé ma réflexion plus loin. Si je constate d'autres anomalies, j'irai du côté des algorithme de cryptage. Je crains juste le temps que cela mettrais pour crypter +-65000 array.

[Jimmy_]

Attention on dit chiffrement et pas cryptage, MD5 et SHA sont des algorithmes de hashage, ce qui n'est pas du tout la même chose que du chiffrement.

On dit que ce sont des algorithmes de hashage cryptographique car ils possèdent plusieurs propriétés :
- Il est très difficile de retrouver le texte à partir du hash.
- Il est très difficile de générer la même signature que celle d'un texte déjà connu.
- Il est très difficile avec 2 messages aléatoires d'obtenir le même hash.

Et non ils sont très rapides, des implémentations comme BouncyCastle sont très utilisé un peu partout.

[tchize_]

Et non ils sont très rapides, des implémentations comme BouncyCastle sont très utilisé un peu partout.

Heu non.
Ils ont beau être assez rapide, il y a un monde de performance entre faire un hash cryptographique de 65.000 données et faire 65.000 hash séparés!