table de hachage avec hcreate hcreate_r hsearch et hsearch_r

Version imprimable

Salut à tous,

j'ai un drôle de problème concernant une table de hachage créée par hcreate. J'aurais vraiment besoin de votre aide. Premièrement, est-ce que qqun aurait un exemple utilisant hcreat_r et hsearch_r car j'aimerais jouer sur deux tables. Deuxièmement je ne parviens pas à voir comment faire pour agrandir la table quand celle-ci est pleine. Et troisièmement, le plus drole des problèmes est qu'il a l'air de me looper des recherches de clés ... En fait je lis dans un fichier des mots, il se peut que le même mot revienne plusieurs fois. J'aimerais attribuer un index à chaque mot différent et pour ce faire je dis que la clé dans ma table est le mot (chaine de caractères) et la donnée est l'index.

Un premier problème est de gérer la taille de la table car je ne connais pas à l'avance le nombre de mot différent. Est-ce que qqun saurais me dire comment on fait pour aggrandir la table ? Est-ce qu'il suffit de refaire hcreate (X) ? si oui, X est la taille globale de la table ou bien on a rajouté X à la table existant ? Un deuxième problème est que suivant la taille de la table que je lui donne au départ (j'ai abandonné l'idée de l'aggrandir) il a l'air de se gourer dans les recherches des clés. Je m'explique, par exemple, quand je fais une table de 10 éléments par hcreate(10) il parvient à en mettre plus que 10 dedans mais ne met pas nécessairement les 10premiers qu'il a trouvé dans le fichier (les 10 différents). Tandis que quand je lui dis de faire une taille 1000 par exemple là il en oublie 3 (sur les 36 mots différents que j'ai dans le texte). Il y a l'air qu'il fait comme si le mot est déjà dedans mais ce n'est pas le cas ... Ca fait des heures que je tente de comprendre pourquoi et c'est la raison qui me pousse à vous demander un petit exemple d'utilisation (ne me donner pas celui dans man hcreate car je me suis basé sur lui pour faire mon prog et ça va pas).

Et si qqun sait se servir de hcreate_r et hsearch_r c'est encore mieux, surtout pour m'expliquer ce qu'est l'argument **ret.

Voici une esquisse de mon prog, c'est juste une esquisse, je n'écris que ce qui est utilise, par ex dans main() je note pas les bazards avec arg, c'est fait exprès ...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 int main(){ int count = 0; ENTRY item, *p_item; char mot[100]; //les mots sont plus petits que 100caractères. hcreate(100); while(scanf(file, %s, mot)!=EOF){ item.key = mot; item.data = count+1; pitem = hsearch(item, FIND); //Juste pour voir si est dans la table et si faut augmenter count if(pitem==NULL){ count++; //on augmente le count pour le prochain mot vu que le courant n'est pas dans la table. } pitem = hsearch(item, ENTER); //Si n'est pas dans la table, le rajoute (action ENTER) if(pitem == NULL){ //La table est pleine mais je ne sais pas comment faire pour l'agrandir. } } }

13/03/2006, 11h02
HRS

hcreate et hsearch ne me semblent pas être des fonctions standards

Quels OS, compilateur utilisez-vous ?
13/03/2006, 11h17
zul

hcreate et hsearch sont POSIX, les versions reentrantes sont un ajout GNU.
hcreate_r n'a pas d'argument ENTRY ** ret d'apres ma documentation. l'argument ret de la foncton hsearch_r retourne l'adresse de l'ENTRY trouvé ( je suppose ). Voir la documentation plus complete que le man sur http://www.gnu.org/software/libc/man...-Function.html

Pour le reste de tes interrogations, je te laisse lire les premieres lignes de la doc.

Salut,

je suis aussi sur hsearch en ce moment, je viens de tomber sur ton post.
Si tu veux un exemple, en voici un donné par un man sur mon linux :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
       The following program inserts 24 items in to a hash table, then  prints
       some of them.
 
           #include <stdio.h>
           #include <stdlib.h>
           #include <search.h>
 
           char *data[] = { "alpha", "bravo", "charlie", "delta",
                "echo", "foxtrot", "golf", "hotel", "india", "juliet",
                "kilo", "lima", "mike", "november", "oscar", "papa",
                "quebec", "romeo", "sierra", "tango", "uniform",
                "victor", "whisky", "x-ray", "yankee", "zulu"
           };
 
           int main() {
             ENTRY e, *ep;
             int i;
 
             /* starting with small table, and letting it grow does not work */
             hcreate(30);
             for (i = 0; i < 24; i++) {
                 e.key = data[i];
                 /* data is just an integer, instead of a
                    pointer to something */
                 e.data = (void *)i;
                 ep = hsearch(e, ENTER);
                 /* there should be no failures */
                 if (ep == NULL) {
                   fprintf(stderr, "entry failed\n");
                   exit(1);
                 }
             }
             for (i = 22; i < 26; i++) {
                 /* print two entries from the table, and
                    show that two are not in the table */
                 e.key = data[i];
                 ep = hsearch(e, FIND);
                 printf("%9.9s -> %9.9s:%d\n", e.key,
                        ep ? ep->key : "NULL",
                        ep ? (int)(ep->data) : 0);
             }
             return 0;
           }

Et la doc de la librairie GNU standard (donc c'est bien standard HRS ????!) précise bien qu'on ne peut pas augmenter la taille du hash (et ils recommandent d'ailleurs de ne pas remplire audessus de 80%).

Par contre avec les fonctions hcreate_r et companie tu as peux etre une solution, en créant plusieurs hash... genre tu arrive à 80% d'un hash de x ENTRY, t'en crée un autre et tous ces hash tu les "pointes" avec un tableau de pointeurs sur htable non?

Bon courage

Yan

19/03/2007, 10h34
wonderyan

Merde on est en 2007 !