Reduire les collisions: Double et triple table de hachage
Optimiser la méthode:
Si la probabilité P est d'avoir une collision à une adresse donnée, alors la probabilité d'avoir une autre collision à la même adresse est de PxP en supposant que les deux événements soient indépendants.
En supposant que la probabilité d'une collision est de 10%, une deuxième collision aurait une probabilité de 0.1x0.1=1% et une troisième collision, une probabilité de 0.1x0.1x0.1=0.1%
Donc en multipliant la table de hachage, il devrait être possible de limiter fortement la recherche linéaire.
Le petit programme ci-contre tente de vérifier cette hypothèse, le code source est ici: hashfonction.c
Le test a été fait sur un dictionnaire d'anglais ( à charger ici ) Wordlist de 634 699 mots (environ 7 Mo). La fonction de hachage est one-at-a-time et la taille de la table de hachage est de 0xFFFFF (1048575 index de 4 octets = 4.2 Mo)
Conclusion: Une table donne 33.3% de collision, deux tables donnent 4.7% de collision et finalement trois tables ne donnent plus que 0.6% de collision.
Le fait d'utiliser 3 tables permet de diviser par 55 le nombre de collision. En contre-partie, la mémoire requise est 3 fois plus importantes, le temps recherche (lookup) sera aussi légérement pénalisé par deux tests supplémentaires (un exemple plus complet sera posté dans mon prochain message).
----- Résultats à la console ----------------------------------------------------------
Chaques lignes doivent se terminer par un newline
Entrez le nom du fichier:english.txt
Boucle vide
Nb de ligne:634699
Nombre de ticks horloge: 370000
Taille de la table:1048575 entrees => On va la remplir.
Entrez le nombre d'ajout (0:max):0
Simple table
Taille de l'index:5036092
ajouts_t1:476046 collisions:158653
Taux de remplissage:0.453993 Taux de collisions:0.333272
Nombre de ticks horloge: 800000
Double table
Taille de l'index:6473165
ajouts_t1:476046 ajouts_t2:129927 collisions:28726
Taux de remplissage:0.288951 Taux de collisions:0.047405
Nombre de ticks horloge: 840000
Triple table
Taille de l'index:6749092
ajouts_t1:476046 ajouts_t2:129927 ajouts_t3:24669 collisions:4057
Taux de remplissage:0.200476 Taux de collisions:0.006433
Nombre de ticks horloge: 860000
----------------------------------------------------------------------------------------------------------
Le programme:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#define LGTABLEINDEX 0xFFFFF //nombre max d'index possible
#define LGLIGNE 1000 //lg max de chaque chaine de caracteres
//contient la position de chaque mot dans la table
unsigned int index_table1[LGTABLEINDEX]; //contiendra le premier index
unsigned int index_table2[LGTABLEINDEX]; //contiendra le deuxieme index si collision
unsigned int index_table3[LGTABLEINDEX]; //contiendra le troisieme index si deuxieme collision
//fonction de hachage: One-at-a-time hashing
unsigned int hash_key(char* nom) {
unsigned int key_val=0;
while (*nom != '\0') {
key_val+=(int)*nom;
key_val+=key_val<<10;
key_val^=key_val>>6;
nom++;
}
key_val+=key_val<<3;
key_val^=key_val>>11;
key_val+=key_val<<15;
return (key_val & LGTABLEINDEX);
}
main() {
FILE *fp;
char fichier[100];
clock_t tick1,tick2;
char* str_ptr;
char nom[LGLIGNE];
int cont=1;
unsigned int key;
unsigned int i;
unsigned int index;
unsigned int nbajout,ajout_table1,ajout_table2,ajout_table3,ajout_T,collision;
unsigned int lg_nom;
// 1 - calcul la cle a partir du nom
// 2 - stock la position de chaque nom dans index_table[]
// 3 - stock les noms dans table[] (chaque nom est delimite par le caractere NULL)
/////////////////////////////////////////////////////////
printf("\nChaques lignes doivent se terminer par un newline\nEntrez le nom du fichier:");
scanf("%100s",fichier);
ajout_table1=0;
if ((fp=fopen(fichier,"r")) == NULL) {printf("\nErreur lecture fichier\n"); exit(-1);}
tick1=clock();
while (fgets(nom,LGLIGNE,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_table1++;
}
tick2=clock();
fclose(fp);
printf("Boucle vide\n");
printf("Nb de ligne:%u\n",ajout_table1);
printf("Nombre de ticks horloge:%7ld\n",tick2-tick1);
////////////////////////////////////////////////////////
printf("\nTaille de la table:%u entrees => On va la remplir.\nEntrez le nombre d'ajout (0:max):",LGTABLEINDEX);
scanf("%u",&nbajout);
if (nbajout == 0) nbajout=ajout_table1;
////////////////////////////////////////////////////////
index=1,ajout_table1=0,collision=0;
for (i=0;i<=LGTABLEINDEX;i++) index_table1[i]=0;
fp=fopen(fichier,"r");
tick1=clock();
while (fgets(nom,LGLIGNE,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(nom); //calcul la cle
if (key > LGTABLEINDEX) printf("Erreur! key depasse %u",LGTABLEINDEX); //theoriquement inutile
if (index_table1[key] != 0) collision++;
else {
ajout_table1++;
index_table1[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("\nDepassement de l'index\n"); break;}
if (ajout_table1 >=nbajout) {printf("\nNombre d'ajout atteint\n"); break;}
}
}
tick2=clock();
ajout_T=ajout_table1+ajout_table2;
fclose(fp);
printf("\nSimple table\n");
printf("Taille de l'index:%u\n",index);
printf("ajouts_t1:%u collisions:%u\n",ajout_table1,collision);
printf("Taux de remplissage:%f Taux de collisions:%f\n",(float)ajout_table1/(float)LGTABLEINDEX,(float)collision/(float)ajout_table1);
printf("Nombre de ticks horloge:%7ld\n",tick2-tick1);
////////////////////////////////////////////////////////
index=1,ajout_table1=0,ajout_table2=0,ajout_T=0,collision=0;
for (i=0;i<=LGTABLEINDEX;i++) index_table1[i]=0;
for (i=0;i<=LGTABLEINDEX;i++) index_table2[i]=0;
fp=fopen(fichier,"r");
tick1=clock();
while (fgets(nom,LGLIGNE,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(nom); //calcul la cle
if (key > LGTABLEINDEX) printf("Erreur! key depasse %u",LGTABLEINDEX); //theoriquement inutile
if (index_table1[key] != 0) {
if (index_table2[key] != 0) collision++;
else {
ajout_table2++;
index_table2[key]=index; //stock l'index dans index_table2
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"); break;}
if ((ajout_table1+ajout_table2) >=nbajout) {printf("Nombre d'ajout atteint\n"); break;}
}
}
else {
ajout_table1++;
index_table1[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("\nDepassement de l'index\n"); break;}
if ((ajout_table1+ajout_table2) >=nbajout) {printf("\nNombre d'ajout atteint\n"); break;}
}
}
tick2=clock();
ajout_T=ajout_table1+ajout_table2;
fclose(fp);
printf("\nDouble table\n");
printf("Taille de l'index:%u\n",index);
printf("ajouts_t1:%u ajouts_t2:%u collisions:%u\n",ajout_table1,ajout_table2,collision);
printf("Taux de remplissage:%f Taux de collisions:%f\n",0.5*(float)ajout_T/(float)LGTABLEINDEX,(float)collision/(float)ajout_T);
printf("Nombre de ticks horloge:%7ld\n",tick2-tick1);
////////////////////////////////////////////////////////
index=1,ajout_table1=0,ajout_table2=0,ajout_table3=0,ajout_T=0,collision=0;
for (i=0;i<=LGTABLEINDEX;i++) index_table1[i]=0;
for (i=0;i<=LGTABLEINDEX;i++) index_table2[i]=0;
for (i=0;i<=LGTABLEINDEX;i++) index_table3[i]=0;
fp=fopen(fichier,"r");
tick1=clock();
while (fgets(nom,LGLIGNE,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(nom); //calcul la cle
if (key > LGTABLEINDEX) printf("Erreur! key depasse %u",LGTABLEINDEX); //theoriquement inutile
if (index_table1[key] != 0) {
if (index_table2[key] != 0) {
if (index_table3[key] != 0) collision++;
else {
ajout_table3++;
index_table3[key]=index; //stock l'index dans index_table3
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"); break;}
if ((ajout_table1+ajout_table2+ajout_table3) >=nbajout) {printf("Nombre d'ajout atteint\n"); break;}
}
}
else {
ajout_table2++;
index_table2[key]=index; //stock l'index dans index_table2
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"); break;}
if ((ajout_table1+ajout_table2) >=nbajout) {printf("Nombre d'ajout atteint\n"); break;}
}
}
else {
ajout_table1++;
index_table1[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("\nDepassement de l'index\n"); break;}
if ((ajout_table1+ajout_table2) >=nbajout) {printf("\nNombre d'ajout atteint\n"); break;}
}
}
tick2=clock();
ajout_T=ajout_table1+ajout_table2+ajout_table3;
fclose(fp);
printf("\nTriple table\n");
printf("Taille de l'index:%u\n",index);
printf("ajouts_t1:%u ajouts_t2:%u ajouts_t3:%u collisions:%u\n",ajout_table1,ajout_table2,ajout_table3,collision);
printf("Taux de remplissage:%f Taux de collisions:%f\n",(float)ajout_T/(3*(float)LGTABLEINDEX),(float)collision/(float)ajout_T);
printf("Nombre de ticks horloge:%7ld\n",tick2-tick1);
}
//Auteur:Jean-Pierre Redonnet - 15 Janvier 2009
//redonnetbrouk@aol.com
//Petit programme test un algorithme de hachage
//Vous etes libre de le modifier, merci de m'en faire parvenir une copie
/https%3A%2F%2Fassets.over-blog.com%2Ft%2Fcedistic%2Fcamera.png)
/https%3A%2F%2Fstorage.canalblog.com%2F69%2F60%2F343710%2F104576493_o.jpg)