HASH CODING
haccounsoft
Messages postés
18
Date d'inscription
jeudi 17 avril 2003
Statut
Membre
Dernière intervention
30 décembre 2003
-
9 avril 2005 à 19:51
verdy_p Messages postés 202 Date d'inscription vendredi 27 janvier 2006 Statut Membre Dernière intervention 29 janvier 2019 - 16 oct. 2009 à 21:59
verdy_p Messages postés 202 Date d'inscription vendredi 27 janvier 2006 Statut Membre Dernière intervention 29 janvier 2019 - 16 oct. 2009 à 21:59
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/9563-hash-coding
https://codes-sources.commentcamarche.net/source/9563-hash-coding
16 oct. 2009 à 21:59
En pratique, cela concerne surtout les tables de hachage de petite taille comportant de nombreuses collisions: les collisions seront nettement plus nombreuses dans les petits nombres si la taille de table n'est pas une puissance de 2, dès qu'on utilisera le modulo. C'est pour des raisons purement statistiques et c'est même totut à fait prédictible. La solution serait d'utiliser directement une fonction de hachage fournissant un entier dans l'intervalle demandé (la taille de table) sans avoir à appliquer un modulo final.
C'est bien pour ça que les tables de hachage standards de Java demandent à recalculer toutes les clés de hachage, quand leur taille est modifiée. Par exemple s'il y a trop d'éléments dans la table de hachage par rapport à sa taille, et si son taux de remplissage dépasse les 150%, la taille de la table est augmentée à 150%, et toutes les clés de hachage des éléments sont recalculées, pour répartir à nouveau tous ses éléments dans la table et réduire le taux moyen de collision.
Si on utilise en revanche une table de hachage trop grande par rapport au nombre d'éléments, il n'y aura pas de collision (ou très peu), mais ces éléments seront distrobués un peu partout dans la table avec plein d'emplacements vides, ce qui réduit la localité en terme d'accès aux données, donc les performances. Une bonne table de hachage doit pouvoir être dimensionnée si possible dès le début en prévoyant le nombre d'éléments qu'elle va avoir, ou le nombre le plus courant de ses éléments si ce nombre n'est pas connu au départ et dépend des données qu'il y aura à l'exécution.
Java redimensionnera automatiquement ses tables de hachage (celles de la série "Collection" ou celles de sa bibliothèque de base comme les tables de symboles, et les tables de chaines atomisées utilisées par le chargeur de classes compilées) en fonction de leur taux de remplissage (qui détermine le taux moyen de collisions) de façon exponentielle (avec un facteur de 1,5 dans les implémentations les plus courantes), afin de réduire le nombre d'opérations de redimensionnement (qui sont d'autant plus longues qu'il y aura à recalculer toutes les clés pour les ajuster à la nouvelle taille.
Noter que la méthode standard Object.hash() ne peut retourner que des clés limitées à 32 bits (mais les objets qui y sont stockés retournent la même valeur, indépendantmment des tables de hachage où les objets PEUVENT être référencés). Cela veut dire qu'on ne peut que retourner des clés 32-bits le plus uniformément distribues possible sur ces 32 bits.
Il n'y a malheureusement pas de méthode "Object.hash(int taille)" pour retourner une meilleure clé, et les tables de hachage des Collection's de Java se contentent d'ajuster la clé 32-bit retournée, par un simple modulo sur leur propre taille qu'elles ne communiquent pas aux objets pour lesquels elles demandent une clé 32-bit uniquement: elles sont donc facilement déséquilibrées si un objet ne retourne pas une clé 32-bits à peu près bien distribuée dans leur implémentation de la méthode "Object.hash()".
De plus, il manque aux Object's standards la possibilité de retourner des clés plus longues que 32-bits (dans le cas de leur utilisation dans de larges collections stockées de façon externe et indexées par une clé de hachage suffisante, puisque les Collection's standards ne peuvent non plus référencer plus de 2^31-1 éléments... Il faudrait d'abord étendre les Collection's avec une classe LongCollection, dont les index seraient sur 64-bits, et demandant aux objets qui doivent y être stockés d'implémenter une nouvelle interface avec la méthode:
public long longhash(long taille);
4 oct. 2009 à 03:28
Cordialement, Bacterius !
PS : si une fonction de hachage cryptographique intéresse quelqu'un, allez voir ma fonction "LEA" sur delphifr ...
18 juin 2007 à 21:48
Personnellement, je préfère un multiplicateur plus proche de la taille maximale des entiers, afin que la clé de hachage marche bien aussi sur les chaines plus courtes.
Le dernier modulo 101 ci-dessus doit correspondre à la taille voulu de la table de hachage. Mias rien n'interdit en fait d'utiliser une autre valeur. Mais attention: cela ne fonctionne à peu près bien que si cette valeur (101 ici) est petite par rapport à la taile maximale d'un entier(sinon les statistiques de distribution sont trop déséquilibrées en faveur des entiers les plus faibles).
Parmi les nombres premiers intéressants pour le multiplicateur (la multiplication peut être remplacée matériellement avec des additions ou soustractions si on cable les décalages binaire) :
- 31 : 5 bits (binaire : 11111) ; peut être réalisée par 1 soustraction
- 47 : 6 bits (binaire : 1 0 1111) ; peut être réalisée par 1 soustraction et 1 addition
- 59 : 6 bits (binaire : 111 0 11) ; peut être réalisée par 1 soustraction et 1 addition
- 61 : 6 bits (binaire : 1111 0 1) ; peut être réalisée par 1 soustraction et 1 addition
- 67 : 7 bits (binaire : 1 0000 11) ; peut être réalisée par 1 soustraction et 1 addition
- 97 : 7 bits (binaire : 11 0000 1) ; peut être réalisée par 1 soustraction et 1 addition
Personnellement je préfère très nettement à 31 le multiplicateur 97 qui donne d'excellent résultats quelle que soit la taille des tables de hachage (généralement limitée à une longueur de moins de 16 bits, et souvent voisine de 10 à 12 bits pour 1024 à 4096 entrées), et permet d'indexer et distribuer correctement des clés de 1 ou 2 caractères comme les noms de variables sans augmenter le nombre de collisions ou enles distribuant plus équitablement entre les différents "hash buckets".
Pour des tables de hachage courtes (par exemple des tables de symboles ou noms de variables ou listes de propriétés nommées ou tableaux associatifs), en général on devrait choisir comme nombre premier une valeur inférieure à la taille de la table de hachage telle que son carré dépasse cette taille,ce quiassure une distribution équitable dès le deuxième caractère haché. Autrement dit, le multiplicateur premier utilisé devrait avoir au moins la moitié du nombre de bits codant la taille de latable de hachage (et il est inutile de prendre un multiplicateur dépassant de plusd'1 bit la moitié du nombre de bits pour coder la taille de la table de hachage).
Pour des tables de hachage assez grandes (codant des grandes chaines telles que des fichiers entiers), il vaut mieux utiliser un algorithme de hachage plus sécurisé et très bien réparti comme MD5 ou SHA1, dont il suffira seulement d'extraire le nombre de bits nécessaires pour former la table de hachage.
9 avril 2005 à 19:51
La plupart des auteurs C l'utilisent dans leurs ouvrages.