Changes between Version 54 and Version 55 of CaoCourseTme2

Timestamp:

Feb 18, 2007, 3:42:05 PM (18 years ago)

Author:

alain

Comment:

--

CaoCourseTme2

@@ -50 +50 @@
 ce qui n'est pas très efficace si le nombre d'éléments est grand.
 
-Pour accélérer la recherche, on créé un tableau de listes chainées. Le nombre de
-cases de ce tableau doit être de l'ordre de grandeur du nombre maximal d'éléments
-que l'on souhaite gérer. Si on veut gérer 1000 éléments, il faut un tableau
-d'environ 1000 cases.      
+Pour accélérer la recherche, on créé un tableau de listes chainées. 
 On définit ensuite une fonction, que l'on nomme '''fonction de hachage''', 
 qui calcule l'index d'une case à partir de la clé.
 Tout élément doit être rangé dans la liste chainée associée à la case du tableau 
-définie par l'index calculé par la fonction de hachage.
-
-Pour que cette méthode soit efficace, il faut que les éléments se répartissent
-aussi uniformément que possible dans les différentes cases de la table. 
+définie par l'index calculé par la fonction de hachage.  
+
+Dans la pratique, il n'est pas possible d'éviter les collisions, et deux éléments 
+ayant des clés différentes peuvent avoir le même index de hachage.
+Pour que la méthode soit efficace, il faut que les éléments se répartissent
+aussi uniformément que possible dans les différentes cases de la table, et qu'il n'y ait
+qu'un petit nombre d'éléments dans chaque case du tableau. Le nombre de case du tableau
+doit donc être du même ordre de grandeur que le nombre total d'éléments à stocker.
+De plus, le nombre de case du tableau est généralement un nombre premier.
+
 Il existe plusieurs méthodes de calcul de l'index, nous vous
 donnons celle proposé par Donald Knuth.
-Dans la pratique, il n'est pas possible d'éviter les collisions, et deux éléments 
-ayant des clés différentes peuvent avoir le même index de hachage.
-
-En résumé, pour ranger 1000 éléments, on fabrique un tableau de 1000 listes chainées avec l'espoir que la plupart des listes ne contiendront qu'un seul élément et qu'il n'y aura 
-qu'un tout petit nombre de listes contenant plus d'un élément.
 
 La propriété principale d'une table de hachage est que, si la taille de la table
@@ -129 +127 @@
 
  *  Faîte un dessin représentatif de la valeur de la variable locale {{{root}}} de la fonction {{{hte_create}}} si {{{nb_list==10}}} juste avant l'appel return. 
- *  La fonction {{{hte_hash}}} peut-elle provoquer une erreur de segment ? Comment y remedier proprement ?
+ *  La fonction {{{hte_hash}}} peut-elle provoquer une erreur de segmentation ? Comment y remedier proprement ?
  *  Dans la fonction {{{hte_create}}} comment fait-on pour tester le retour de {{{malloc}}} ? à quoi celà sert-il ?
 
@@ -136 +134 @@
 Le fichier attachment:dico.c rassemble les fonctions d'accès à une table de hachage utilisé comme dictionnaire.
 
- *  Le type {{{hte_data_t}}} n'est pas défini ici. Est-ce grave ? Où devra-t-il être défini ? 
+ *  Le type {{{hte_data_t}}} n'est pas défini dans le fichier ''dico.c''. Pourquoi ? Où devra-t-il être défini ? 
  *  Pourquoi teste-on key dans la fonction {{{hte_get}}} ?
  *  Pourquoi définit on la structure {{{hte_item_s}}} ici ?