Hashage d'un array: problème avec l'algorithme du tutoriel [Résolu]

[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_]

Envoyé par Jimmy_

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!

[Jimmy_]

Effectivement, mais si la condition initial est de n'avoir aucune collision. Il n'y a pas vraiment le choix.

[tchize_]

on ne peux pas n'avoir "aucune" collision avec du hashage.

Si je prend des chaines de 10 caractère, soit 800 bits, je ne peux pas garantir de non-collision quand je la réduit à 32 bits (taille d'un int java), et le hashage cryptographique ne garantis pas ça non plus. Le hashage crypto te garanti seulement qu'il est presque impossible de construire délibérément une autre chaine de caractère avec le même hash.

[Jimmy_]

presque impossible de construire délibérément une autre chaine de caractère avec le même hash

C'est ce que j’essaie de faire comprendre. Il faut aussi ajouter que si c'est le cas le message ayant le même hash sera de toute manière tellement différent qu'il n'y a aucune chance en pratique qu'il fasse partie du domaine de valeur de ce message. Ne pas oublier que ces algorithmes possèdent un effet avalanche. Pour chaque bit différent en entrée, il y a 50% de chance que cela modifie chaque bit de la sortie.

Alors on peut toujours pinailler dans la nuance du presque impossible et zero collision. En pratique si tu haches quelques milliards de message avec SHA-256 tu as très largement plus de chance de gagner au loto que de trouver une collision.

[tchize_]

Sauf qu'on est pas dans un range 256bits, mais dans un range 32 bits. Les risque de collision sont exactement de 1/2^32 par paire. Le 60.000ème élément a donc en cochonne approximation 60.000 fois ce risque (entre 2^15 et 2^16 * 1/2^32), ce qui nous amène à une probabilité approximée cochon de 1/2^17. Soit une chance sur 130.000 d'avoir un cas de collision.

Sur 60.000 hash, on n'est donc plus dans le négligeable. Le hashcode de java n'a pas pour but d'être unique, donc encore une fois, aucune raison de plomber les performances en utilisant un hash cryptographique!

[lvr]

Bon j'ai fait mes comptes, et abandonné le hashage java. Beaucoup trop de doublons.
J'ai fait comme test en partant d'un tableau de nombres allant de 1 à 20 et j'en ai fait toutes les combinaisons de 1 à 3 nombres. Sur les 1561 combinaisons, j'ai quand même 25% de doubles. Si je monte jusque 100, je passe à 3% de doubles. Ca reste trop.

Maintenant je suis passé à un algorithme FLV en 64bits. L'algorithme est très rapide: on n'est pas dans le domaine du cryptographique. Je n'ai pas encore fait de test de charge, mais cela me semble plus rapide que la technique du hashage java. Résultat plus aucun doublons

Ici le code source dont je me suis servi pour ce hashage.