Please enable JavaScript.

Coggle requires JavaScript to display documents.

Les tables de dispersion (Fonction de hachage (:warning: Doit absolument…

- - - - Dictionnaires
        
        Doit supporter
        
        Insertion d’un élément
        
        :timer_clock: 3 opérations de temps
        « presque toujours » en O(1) si les données sont stockées dans une table de dispersion
        
        Trouver un élément (déterminer si un élément est présent)
        
        Suppression d’un élément
      - Tables de dispersion
  - - - Arbres binaires de recherche (tels que les arbres
        AVL)
        
        Doit supporter
        
        :check: Ils supportent efficacement le tri et les opérations min() et max()
        
        :timer_clock: Temps d’exécution pour les recherches, les insertions et les suppressions se font en temps O(log n) pour un arbre AVL contenant n éléments
        
        :green_cross: Les élément sont positionnés dans le conteneur en fonction d’une relation d’ordre avec les autres éléments
- - - - Surcharger operator== pour le prédicat de comparaison entre les clés
      - Fournir
        
        2) La classe pour les objets valeurs
        
        3) la classe (foncteur) pour le hachage des clés
        
        1) La classe pour les objets clés
- - - - Chaque liste contient les clés qui hachent à
        la même valeur d’index
      - h(x) nous donne la liste à utiliser pour
        trouver(x), enlever(x) et ajouter(x)
      - Pour le cas d’un map: chaque noeud contient
        une paire (clé, valeur)
    - - On « re-hachera » tous les éléments après avoir augmenter la taille du tableau, ce qui entraînera le dépeuplement des listes chaînée
      - :timer_clock: Le temps d’exécution moyen des
        recherches/insertions/suppressions dans une table de hachage avec
        chaînage externe est en O(1) lorsque le taux d’occupation λ ≤ 1.
      - :timer_clock: Puisque le re-hachage s’effectue lorsque n = N+1, le coût total du rehachage est donc en Θ(n)
  - - - Lorsque qu’une clé entre en collision avec une autre, on positionne cette clé dans une autre position de la table (ré-adressage)
    - - Le champ état prend la valeur
        
        ACTIVE
        
        Si cet entrée contient une clé valide
        
        DELETED
        
        Si cette entrée a déjà contenu une clé mais que celle-ci a été
        retirée par la suite avec une opération enlever(x)
        
        EMPTY
        
        Si cette entrée est vide et n’a jamais contenu une clé
    - - Le sondage f utilisé est linéaire, i.e., f(i) = i
        
        Cela signifie qu’après avoir subi la ième collision, on tente d’aller à
        la case ( h(x) + i ) mod N
        
        S’il y a encore une collision (un élément se trouve dans la case
        ( h(x) + i mod N) ), on ira à ( h(x) + i + 1 ) mod N
        
        :red_cross: Creer du regroupement primaire
    - - Consiste à utiliser f(i) = i2
        
        Donc après i collisions on examine la case hi(x) = ( h(x) + i2 ) mod N
        
        De cette façon, on saute de plus en plus loin à chaque sondage
        
        :check: Cela élimine la formation de regroupements primaires
        
        :warning: Pour l'utiliser il faut vérifier ses 2 conditions
        
        S’assurer qu’au moins la moitié des cases de la table sont dans l’état
        EMPTY
        
        On a une table de dispersion dont la taille est un nombre premier
        
        lambda doit être au maximum de 0.5
      - Pour éviter le «regroupement secondaire»
        
        Double hachage
        
        Consiste à calculer séquentiellement les positions h0(x),
        h1(x), h2(x), … avec hi(x) = ( h(x) + f(i) ) mod N avec f(i) = i * h’(x) où h’(x)
        est une seconde fonction de hachage
        
        Il faut alors éviter d’avoir h’(x) = 0 (ex: h’(x) = c(x) mod R pour R<N) car,
        dans ce cas, tous les x tels que h’(x) = 0 produiront h0(x) = h1(x) = h2(x), …et une nouvelle case vide ne pourra jamais être trouvée!