Bonsoir, je suis confronté à un problème j'ai un fichier à traiter dans le cadre d'un devoir qui contient un nombre important de donnée type identifiant, nom, prenom, moyenne générale, nom ecole, sexe ,etc .... Et je dois gérer cela avec une table de hachage. J'ai donc créé une structure qui contient ces paramètres mais ne sait pas comment indexer ces structures dans un table de hachage ? (Pour gérer les collisions la structure contient un pointeur vers l'élève suivant). L'application typique par la suite est :
- la recherche des 50 meilleur(e)s filles ou garçon du fichier
- le classement des écoles en fonction de
-rechercher une personne via son identifiant
J'aurai besoin de piste pour savoir comment faire les fonctions de hachage ?
Le mieux, c'est de tester plusieurs fonctions de hachages sur tes données (parmis les connues efficaces), pour voir laquelle provoque le moins de collisions. Le problème, c'est que ça prend du temps.
La recherche des 50 meilleur(e)s n'est pas vraiment le même problème (tu vas devoir parcourir toutes tes données, pour déterminer ça, donc une complexité en O(n) ). Si cette recherche doit être effectuée plusieurs fois, une solution est de stocker le résultat et ne le mettre à jour qu'en cas de modification des données. (même chose pour le classement).
Ensuite, l'acces à une des données de la hashtable (une de tes structures) doit se faire en temps constant (ou presque). Si tu ne récupères tes structures que via leur identifiant, le hash doit porter sur celui-ci afin de ne pas avoir à 'chercher' le bon résultat à chaque fois.
En supposant que ta hashtable est en fonction de l'identifiant, si tu veux accéder à une personne avec son nom, il va falloir tout parcourir jusqu'à trouver le bon. Tu peux aussi créer une deuxième hashtable sur le nom/prénom si tu veux et ainsi de suite. Mais c'est toujours un tableau supplémentaire à gérer, et en cas de suppression/ajout d'une donnée, il faut l'ajouter à toutes les hashtable existantes).
Enfin, prend garde : ta fonction de hashage dépend de la taille du tableau (de ta hashtable). En effet, s'il y a 64 places, ta fonction de hashage va te donner un nombre entre 0 et 63. Si tu augmente la taille de ta hashtable (disons 128 désormais), tu vas devoir mettre à jour les éléments existants. Pour un exemple simple, si tu avais un hash qui (en interne) avait donné le nombre 65 (alors que la taille de ta hashtable était 64), il va faire 65 % 64, soit 1 (l'élément sera placé à l'indice 1). Après avoir augmenté la taille du tableau, le même élément donnera toujours le même hash (en interne) 65, mais cette fois-ci, il va faire 65 % 128, soit 65.
J'espère ne pas avoir été trop brouillon
J'aime les bandes dessinées, manhuas, manhwas, mangas, comics... Du coup j'ai fait aralosbd.fr !
Mais une recherche dans une table de hashage, c'est trouver rapidement si une clé existe, et si elle existe dire ou lire la donnée.
Donc pour la 3e question (trouver un élève via son identifiant), pas de soucis !
Tu fais une table assez grande et ta fonction de hashage te renvoie l'identifiant modulo la taille de la table, et tu trouves super vite ton étudiant.
Mais pour tes deux premières questions, les classements, pour moi ça n'a rien à voir avec une table de hashage ! C'est plutôt des algorithmes de tri à lancer.
J'aime les bandes dessinées, manhuas, manhwas, mangas, comics... Du coup j'ai fait aralosbd.fr !
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html