ntro.ca

        • Contrats de classe
        • Liens utiles
        • Calendrier
        • Calendrier groupe 2
        • Calendrier groupes 1, 3
        • Structure du cours
        • Évaluations
        • Matériel à se procurer
        • Les profs
          • Marc-Olivier Tremblay
          • Mathieu Bergeron
        • Module 1.1: installation + trier des cartes
        • Module 1.2: rappels POO
        • Module 1.3: tableau d'objets
        • Examen 1
        • Module 2.1: données JSON
        • Module 2.2: données en Java
        • Module 2.3: récursivité
        • Examen 2
        • Module 3.1: structure générique
        • Module 3.2: efficacité (1)
        • Module 3.3: efficacité (2)
        • Examen 3
        • Module 4.1: liste naïve
        • Module 4.2: liste par tableau
        • Module 4.3: liste chaînée
        • Examen 4
        • Module 5.1: mappage naïf
        • Module 5.2: mappage par hachage
        • Module 5.3: mappage par arbre
        • Examen 5
        • Équipes
          • Horaire groupe 1
          • Horaire groupe 2
          • Horaire groupe 3
          • Groupe 1
          • Groupe 2
          • Groupe 3
        • Projets vedettes 2022
        • Projets vedettes 2023
        • Projets vedettes 2024
        • Projets vedettes 2025
        • Survol
        • Structure
        • Calendrier
        • Calendrier des séances
        • Évaluations
        • Exemples de jeu
        • Exemples de pages
        • Réponses à vos questions
        • Module 1: créer le projet
        • Module 2: concevoir l'application
        • Module 3: vues NtroFx
        • Module 4: modèle et navigation
        • Module 5: ajouter le dorsal, modifier le modèle
        • Module 7: améliorer l'affichage
        • Module 8: jeu en 2d
        • Module 9: client/serveur
        • Module 10: plusieurs instances du même modèle
        • TP1
        • Examen 1
        • TP2
        • Examen 2
        • Projet de fin de session
        • Calendrier
        • Structure du cours
        • Évaluations
        • Contrat de classe
        • Le prof
        • 01: Windows et Word
          • Astuces et raccourcis
        • 02: Word
        • 03: Word
          • Exercice Word: insertion d'éléments spéciaux
          • Exercice Word: tableaux
        • 04: Word
          • Exercice Word: références
          • TP01: Word (15%)
        • 05: PowerPoint
          • TP02: PowerPoint (10%)
        • 06: Examen Word (20%)
        • 07: Excel
        • 08: Excel
        • 09: Excel
          • TP03: Excel (15%)
        • 10: Excel
        • 11: Examen Excel (20%)
        • 12: Access
        • 13: Access
        • 14: Access
        • 15: Examen Access
      • Sondage H2023 (dept. info)
      • Vision H2023 (dept. info)
      • P1) exercices interactifs de lecture
      • P2) transition Excel vers Python
        • Atelier 2: un exemple
      • Jquery
      • Jquery Ui
      • Point de vue sur l'IA
    Révision, fonction de hachage
    • Révision, fonction de hachage
      • Map par hachage
      • Fonctione de hachage
        • Utilisable (valide) / pas utilisable (pas valide)
        • Bonnes (efficace)
        • Mauvaises (pas efficace)
      • Avantages / inconvénients du Map Hash

    Révision, fonction de hachage #

    Map par hachage #

    • Pour faire put(cle, ...), je trouve un indice dans la table

    • Pour faire plusieurs put() avec différentes clés, on essaie de répartir sur plusieurs indices

    • Si je dois aller 2 fois dans le même indice: collision

      • en cas de collision, on peut utiliser un map naif

    Fonctione de hachage #

    1. L’idée est de trouver un incide à partir de clé
      • avec l’indice on va aller dans la table

    Utilisable (valide) / pas utilisable (pas valide) #

    1. Utilisable: indice utilisé pour le le put(cle,...) doit être le même re-caculé plus tard pour le get(cle)

    2. Utilisable: on calcule l’indice uniquement avec les informations de la clé.

    3. Pas utilisable: on pas toujours le même indice pour la même clé.

    4. Pas utilisable: si on calcule l’indice avec du hasard ou encore une information externe à la clé (heure de la journée, nom de l’usager, etc).

    Bonnes (efficace) #

    1. Si la fonction de hachage va placer / distribuer les éléments un peu partout

    Mauvaises (pas efficace) #

    1. Si la fonction retourne toujours le même indice

    Avantages / inconvénients du Map Hash #

    1. Avantages

      • Efficacité: temps constant O(1) pour put/get
    2. Inconvénient

      • Prend plus espace mémoire que réellement nécessaire
    Creative Commons License Creative Commons Attribution Creative Commons ShareAlike
    • Révision, fonction de hachage
      • Map par hachage
      • Fonctione de hachage
        • Utilisable (valide) / pas utilisable (pas valide)
        • Bonnes (efficace)
        • Mauvaises (pas efficace)
      • Avantages / inconvénients du Map Hash