Changes between Version 22 and Version 23 of CaoCourseTme2

Timestamp:

Feb 16, 2007, 8:04:24 PM (19 years ago)

Author:

franck

Comment:

--

CaoCourseTme2

@@ -56 +56 @@
 ou une structure de données quelconque.
 Le principal objectif de cette structure est d'accélérer la recherche d'un élément
-par sa clé, en essayant d'éviter de parcourir l'ensemble de tous les éléments de
-cet ensemble en effectivement séquenciellement une comparaison sur la valeur de 
-la clé pour chaque élément de l'ensemble. 
-
-On accède donc à un élément à partir de sa clé. Les deux principales actions
-sont l'ajout d'un élément (add) et la recherche d'un élément (get).
+par sa clé. 
+
+Pour représenter un ensemble de couple (clé, valeur) la méthode la plus simple
+consiste à les réunir dans une liste chainée.
+La recherche d'un élément se fait alors par un parcours de la liste, donc de
+l'ensemble des éléments.
+Cette solution n'est évidemment pas satisfaisante si le nombre d'élément 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.      
+On définit ensuite une fonction, que l'on nomme fonction de hachage, donnant 
+un index de case à partir de la clé d'un élément.
+Un élément doit être rangé dans la liste chainée associée à la case définie par la fonction de hachage
+appliquée sur la clé de cet élément.
+
+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. 
+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. 
+Cela signifie que deux éléments de 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
+est du même ordre de grandeur que le nombre d'éléments présents, le temps de
+recherche est en O(1), c'est à dire indépendant du nombre d'éléments, (même pour
+un million d'éléments).
+ 
+Les deux principales actions sont l'ajout d'un élément (add) et la recherche d'un élément (get).
   * La fonction get() prend en paramètre la clé de l'élément recherché. Si l'élément existe, elle rend la valeur associée.
   * La fonction add() prend en paramètre le couple (clé, valeur). Si l'élément existe, elle change sa valeur, sinon elle créé l'élément.