#include <iostream.h> #include <string.h> char ligne[32]; unsigned HashCode (char *ligne) { unsigned HashCode; HashCode=0; for (int i=0;i< strlen(ligne);i++) HashCode=ligne[i]+31*HashCode; return HashCode%101; } void main() { cout<<"Entrez une ligne : "<<endl; cin>>ligne; cout<<"valeur"<<HashCode(ligne)<<endl; }
C'est vrai que c'est une fonction sympa et la plus courrante et la plus simple en programmation C.La plupart des auteurs C l'utilisent dans leurs ouvrages.
c'est un simple hachage par multiplication et congruence. Pour que çamarche ilfaut que le multiplicateur utilisé soit premier et impair (à cause de la congruence modulo 2^n sur le résultat de la multiplication des entiers)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 additionPersonnellement 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.
Notons toutefois que MD5 n'est pas "uniformément" réparti. J'ai cru lire que des chercheurs avaient démontré la non-uniformé des hachages MD5, qui, lorsqu'on passe à la fonction certains ensembles bien particuliers, se comporte de façon non prévue (en convergeant vers un certain hachage par exemple). Mais ... MD5 est encore largement suffisant pour une table de hachage, et très rapide. La différence entre MD5 et SHA-1 au niveau des tables de hachage est négligeable (peut-être que le SHA-1 va un peu plus lentement).Cordialement, Bacterius !PS : si une fonction de hachage cryptographique intéresse quelqu'un, allez voir ma fonction "LEA" sur delphifr ...
Si, si, le MD5 est bien réparti. Mais l'erreur courante dans son utilisation comme clé de hachage ne se situe pas là: elle vient du fait que trop souvent on prend des tailles de tables de hachage qui sont des puissances de 2, afin de simplement tronquer les bits nécessaires du hachage MD5, et que ça marche très bien, mais qu'ensuite on lève la restriction sur la taille en puissance de 2 des tables. Dans ce cas, le modulo final pour transformer la clé MD5 (ou SHA1 ou même tout autre algorithme sécurisé fournissant une clé binaire de longueur fixe uniformément distribuée) n'est plus équilibré, ce qui favorise alors les premiers entiers (ce qui rond l'uniformité de la distribution).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);
Se souvenir du profil
Mot de passe oublié ? / Activation de compteCréer un compte
1 976 076 membres 18 nouveaux aujourd'hui 16 318 membres club