Table de hachage - Limiter les collisions - Programme de test
Limiter les collisions:
Le risque de collision est d'autant plus important que la table d'indexation est remplie. En supposant que la fonction de hachage soit parfaite: les clés sont uniformément réparties. Alors la probabilité de collision est égale au taux de remplissage de la table d'index. Une table d'indexation remplie à 10% donnera 10% de risque de collision.
Dimensionnement de la table d'index:
Supposons que l'on ne veuille pas plus de 10% de collision; alors la table d'index devra pouvoir contenir 10 fois plus d'index que de nombre d'enregistrement. Si on prévoit 1 000 000 d'enregistrements, alors la table d'indexation devra contenir 10 000 000 d'index. Si chaque index occupe 4 octets (integer long), la table d'index occupera 40 Mo environ!
Efficacité de la fonction de hachage:
Idéalement elle devra retourner des clés uniformément réparties et uniques. En pratique, il n'y a pas de fonction de hachage parfaitement polyvalente. Il faut trouver la fonction la plus adaptée aux chaînes à "coder" par tâtonnement.
One-at-a-time hash est une bonne fonction de hachage, et à vous d'en expérimenter d'autres à l'aide du petit programme ci-joint.
Petit programme de test:
J'ai écrit un programme simple permet de comparer différents algorithmes de hachage, et tester le votre: Vous aurez besoin d'un fichier de termes/expressions à indexer, chaque terme doit être délimiter par un caractère newline '\n' et la longueur de chaque terme ne doit pas depasser 999 caractères (vous pouvez facilement changer cette limite).
Le code source est ici: hashfonction.c Un fichier d'essai (liste de mots) est ici: french.zip
Voici le résultat:
-=-=-=-Test les fonctions de hachage-=-=-=-
Taille de la table (nombre d'entrées) t:0xFFFF,s:0xFFFFF,m:0xFFFFFF,l:0xFFFFFFF :s
Nom du fichier:english.txt
Simple lecture du fichier
Nombre de ligne:634699 Nombre de tics horloge: 350000
Taille de la table:1048575 entrées => On va la remplir.
Entrez le nombre d'ajout (0:maximum):200000
Fonction One-at-a-time hash
Nombre d'ajout atteint
Taille de l'index:1941112
Taille de la table:1048575 200000 ajouts 21768 collisions
Taux de remplissage:0.190735 Taux de collisions:0.108840
Nombre de tics horloge: 280000
Fonction Rotating hash
Nombre d'ajout atteint
Taille de l'index:1977952
Taille de la table:1048575 200000 ajouts 34534 collisions
Taux de remplissage:0.190735 Taux de collisions:0.172670
Nombre de tics horloge: 560000
Fonction Bernstein's hash
Nombre d'ajout atteint
Taille de l'index:1942100
Taille de la table:1048575 200000 ajouts 22231 collisions
Taux de remplissage:0.190735 Taux de collisions:0.111155
Nombre de tics horloge: 250000
Fonction Votre hash
Nombre d'ajout atteint
Taille de l'index:2537715
Taille de la table:1048575 200000 ajouts 369798 collisions
Taux de remplissage:0.190735 Taux de collisions:1.848990
Nombre de tics horloge: 520000
Le programme:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
////////////////////////FONCTIONS A TESTER///////////////////////////
// One-at-a-time hash
unsigned int hash_key_1(char* nom,unsigned int lg_table_index) {
unsigned int key_val=0;
while (*nom != '\0') {
key_val+=(int)*nom;
key_val+=key_val<<10;
key_val^=key_val>>6;
nom++; //passe au caractere suivante
}
key_val+=key_val<<3;
key_val^=key_val>>11;
key_val+=key_val<<15;
return (key_val & lg_table_index);
}
// rotating hash
unsigned int hash_key_2(char* nom, int lg_table_index) {
unsigned int key_val=0;
while (*nom != '\0') {
key_val = (key_val<<4)^(key_val>>28)^(int)*nom;
nom++; //passe au caractere suivante
}
key_val = key_val ^ (key_val>>10) ^ (key_val>>20);
return (key_val & lg_table_index);
}
// Bernstein's hash
unsigned int hash_key_3(char* nom, int lg_table_index) {
unsigned int key_val=0;
while (*nom != '\0') {
key_val = (33*key_val)+(int)*nom;
nom++; //passe au caractere suivante
}
return (key_val & lg_table_index);
}
// Mettez votre fonction de hachage ici
// exemple d'un tres mauvais algorithme
unsigned int hash_key_4(char* nom, int lg_table_index) {
unsigned int key_val=0;
while (*nom != '\0') {
key_val = (key_val+(int)*nom)<<1;
nom++; //passe au caractere suivante
}
//ne pas oublier le masque 'lg_table_index' pour eviter de deborder
return (key_val & lg_table_index);
}
//////////////////////////////////////////////////////////////////
//attention integer sur 4 octets
main() {
unsigned int lg_table_index; //taille de la table d'index 0xFFFF, 0xFFFFF, 0xFFFFFF
unsigned int *index_table; //la table d'index
clock_t tick1,tick2;
FILE *fp;
char* str_ptr;
char nom_fichier[500]; //fichier à charger
char nom[1000]; //chaine à "numériser"
unsigned int key; //valeur numerique 'hash' de la chaine
unsigned int i,index,nbajout,ajout,collision;
unsigned int lg_nom;
char dim[10]; //un caractere taille de la table d'index
// 1 - calcul la cle a partir du nom
// 2 - stock la position de chaque nom dans index_table[]
if (sizeof(int) != 4) { printf("Les integers doivent être sur 4 octets!\n"); exit(-1); }
printf("\n-=-=-=-Test les fonctions de hachage-=-=-=-\n");
printf("\nTaille de la table (nombre d'entrées) t:0xFFFF,s:0xFFFFF,m:0xFFFFFF,l:0xFFFFFFF :");
scanf("%10s",dim);
switch (dim[0]) {
case 't': lg_table_index=0xFFFF; break;
case 's': lg_table_index=0xFFFFF; break;
case 'm': lg_table_index=0xFFFFFF; break;
case 'l': lg_table_index=0xFFFFFFF; break;
default: lg_table_index=0xFFFFFF;
}
//dimensionne la table d'index
if ((index_table=(unsigned int*)malloc(lg_table_index*sizeof(int)))==NULL) {
printf("\nErreur allocation mémoire\n");
exit(-1);
}
printf("\nNom du fichier:");
scanf("%s",nom_fichier);
///////////////////////////////////////////////////////
ajout=0;
if ((fp=fopen(nom_fichier,"r")) == NULL) {printf("Probeme ouverture du fichier\n"); exit(-1);}
tick1=clock();
while (fgets(nom,1000,fp) != NULL) {
if ((str_ptr=strchr(nom,'\n'))!=NULL) *str_ptr='\0'; //supprime le LF
if ((str_ptr=strchr(nom,'\r'))!=NULL) *str_ptr='\0'; //supprime le CR
ajout++;
}
tick2=clock();
printf("\nSimple lecture du fichier\nNombre de ligne:%u Nombre de tics horloge:%7ld\n",ajout,tick2-tick1);
if (ajout > lg_table_index) printf("\nAttention le nombre de ligne dépasse la taille de la table d'index!\n");
printf("\nTaille de la table:%u entrées => On va la remplir.\nEntrez le nombre d'ajout (0:maximum):",lg_table_index);
scanf("%u",&nbajout);
if (nbajout == 0) {nbajout=ajout; printf("Lit tout le fichier\n");}
/////////////////////////////////////////////////////////
printf("\nFonction One-at-a-time hash \n");
index=ajout=collision=0;
for (i=0;i<=lg_table_index;i++) index_table[i]=0;
fp=fopen(nom_fichier,"r");
tick1=clock();
while (fgets(nom,1000,fp) != NULL) {
if ((str_ptr=strchr(nom,'\n'))!=NULL) *str_ptr='\0'; //supprime le LF
if ((str_ptr=strchr(nom,'\r'))!=NULL) *str_ptr='\0'; //supprime le CR
key=hash_key_1(nom,lg_table_index); //calcul la cle
if (key > lg_table_index) { printf("Erreur! key depasse %u\n",lg_table_index); goto fin1;} //theoriquement inutile
if (index_table[key] != 0) collision++;
else {
ajout++;
index_table[key]=index; //stock l'index dans index_table
lg_nom=strlen(nom)+1; //le nom et le caractere null
index=index+lg_nom; //position du prochain nom
if (0xFFFFFFFF-index < lg_nom) {printf("Depassement de l'index\n"); goto fin1;}
if (ajout >=nbajout) {printf("Nombre d'ajout atteint\n"); goto fin1;}
}
}
printf("Fin de fichier ou erreur de lecture\n");
fin1:
tick2=clock();
fclose(fp);
printf("Taille de l'index:%u\n",index);
printf("Taille de la table:%u %u ajouts %u collisions\n",lg_table_index,ajout,collision);
printf("Taux de remplissage:%f Taux de collisions:%f\n",(float)ajout/(float)lg_table_index,(float)collision/(float)ajout);
printf("Nombre de tics horloge:%7ld\n",tick2-tick1);
////////////////////////////////////////////////////////////////
printf("\nFonction Rotating hash \n");
index=ajout=collision=0;
for (i=0;i<=lg_table_index;i++) index_table[i]=0;
fp=fopen(nom_fichier,"r");
tick2=clock();
while (fgets(nom,1000,fp) != NULL) {
if ((str_ptr=strchr(nom,'\n'))!=NULL) *str_ptr='\0'; //supprime le LF
if ((str_ptr=strchr(nom,'\r'))!=NULL) *str_ptr='\0'; //supprime le CR
key=hash_key_2(nom,lg_table_index); //calcul la cle
if (key > lg_table_index) { printf("Erreur! key depasse %u\n",lg_table_index); goto fin2;} //theoriquement inutile
if (index_table[key] != 0) collision++;
else {
ajout++;
index_table[key]=index; //stock l'index dans index_table
lg_nom=strlen(nom)+1; //le nom et le caractere null
index=index+lg_nom; //position du prochain nom
if (0xFFFFFFFF-index < lg_nom) {printf("Depassement de l'index\n"); goto fin2;}
if (ajout >=nbajout) {printf("Nombre d'ajout atteint\n"); goto fin2;}
}
}
printf("Fin de fichier ou erreur de lecture\n");
fin2:
tick2=clock();
fclose(fp);
printf("Taille de l'index:%u\n",index);
printf("Taille de la table:%u %u ajouts %u collisions\n",lg_table_index,ajout,collision);
printf("Taux de remplissage:%f Taux de collisions:%f\n",(float)ajout/(float)lg_table_index,(float)collision/(float)ajout);
printf("Nombre de tics horloge:%7ld\n",tick2-tick1);
////////////////////////////////////////////////////////////////
printf("\nFonction Bernstein's hash \n");
index=ajout=collision=0;
for (i=0;i<=lg_table_index;i++) index_table[i]=0;
fp=fopen(nom_fichier,"r");
tick1=clock();
while (fgets(nom,1000,fp) != NULL) {
if ((str_ptr=strchr(nom,'\n'))!=NULL) *str_ptr='\0'; //supprime le LF
if ((str_ptr=strchr(nom,'\r'))!=NULL) *str_ptr='\0'; //supprime le CR
key=hash_key_3(nom,lg_table_index); //calcul la cle
if (key > lg_table_index) { printf("Erreur! key depasse %u\n",lg_table_index); goto fin3;} //theoriquement inutile
if (index_table[key] != 0) collision++;
else {
ajout++;
index_table[key]=index; //stock l'index dans index_table
lg_nom=strlen(nom)+1; //le nom et le caractere null
index=index+lg_nom; //position du prochain nom
if (0xFFFFFFFF-index < lg_nom) {printf("Depassement de l'index\n"); goto fin3;}
if (ajout >=nbajout) {printf("Nombre d'ajout atteint\n"); goto fin3;}
}
}
printf("Fin de fichier ou erreur de lecture\n");
fin3:
tick2=clock();
fclose(fp);
printf("Taille de l'index:%u\n",index);
printf("Taille de la table:%u %u ajouts %u collisions\n",lg_table_index,ajout,collision);
printf("Taux de remplissage:%f Taux de collisions:%f\n",(float)ajout/(float)lg_table_index,(float)collision/(float)ajout);
printf("Nombre de tics horloge:%7ld\n",tick2-tick1);
////////////////////////////////////////////////////////////////
printf("\nFonction Votre hash \n");
index=ajout=collision=0;
for (i=0;i<=lg_table_index;i++) index_table[i]=0;
fp=fopen(nom_fichier,"r");
tick1=clock();
while (fgets(nom,1000,fp) != NULL) {
if ((str_ptr=strchr(nom,'\n'))!=NULL) *str_ptr='\0'; //supprime le LF
if ((str_ptr=strchr(nom,'\r'))!=NULL) *str_ptr='\0'; //supprime le CR
key=hash_key_4(nom,lg_table_index); //calcul la cle
if (key > lg_table_index) { printf("Erreur! key depasse %u\n",lg_table_index); goto fin4;} //theoriquement inutile
if (index_table[key] != 0) collision++;
else {
ajout++;
index_table[key]=index; //stock l'index dans index_table
lg_nom=strlen(nom)+1; //le nom et le caractere null
index=index+lg_nom; //position du prochain nom
if (0xFFFFFFFF-index < lg_nom) {printf("Depassement de l'index\n"); goto fin4;}
if (ajout >=nbajout) {printf("Nombre d'ajout atteint\n"); goto fin4;}
}
}
printf("Fin de fichier ou erreur de lecture\n");
fin4:
tick2=clock();
fclose(fp);
printf("Taille de l'index:%u\n",index);
printf("Taille de la table:%u %u ajouts %u collisions\n",lg_table_index,ajout,collision);
printf("Taux de remplissage:%f Taux de collisions:%f\n",(float)ajout/(float)lg_table_index,(float)collision/(float)ajout);
printf("Nombre de tics horloge:%7ld\n",tick2-tick1);
}
//JP Redonnet - 14 janvier 2009
//Test les fonctions de hachage
//Ce petit programme sans pretention est libre, à vous de l'ameliorer
//n'oubliez pas de m'en parvenir une copie - Merci
//Comme il n'y a pas de valeur negative tous les entiers sont non-signés
//les entiers doivent être sur 4 octets (long int)
/https%3A%2F%2Fassets.over-blog.com%2Ft%2Fcedistic%2Fcamera.png)
/https%3A%2F%2Fstorage.canalblog.com%2F69%2F60%2F343710%2F104576493_o.jpg)