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
      • Fonction de hachage
        • C’est quoi
        • Utilisable / pas utilisable (valide / invalide)
        • Bonne (efficace) Vs mauvaise (pas efficace)
      • Avantages / inconvénients du Map par hachage
        • Avantages
        • Inconvénients

    Révision, fonction de hachage #

    Map par hachage #

    • J’obtiens une paire (clé,valeur)

      • trouver l’indice dans la table où mettre la clé
      • mettre la valeur à côté de la clé
    • J’obtiens plusieurs paires (clé, valeur)

      • j’essaie de mettre les clés à différents endroit dans le tableau
    • Si deux clés vont au même endroit, j’utilise des listes (ou un MapNaif) pour gérer la collision

    Fonction de hachage #

    C’est quoi #

    1. C’est le bout de code qui reçoit la clé et qui
      • l’indice dans la table de hachage où mettre la paire clé/valeur

    Utilisable / pas utilisable (valide / invalide) #

    1. Inutilisable / invalide

      • indice aléatoire
      • si l’indice donné dépend d’une information autre que la clé
        • l’heure de la journée, le nom de l’usager, etc.
    2. Utilisable / valide

      • calculer l’indice uniquement avec la clé (pas de hasard ou d’information externe)

      • un put avec une clé doit absolument utiliser le même indice qu’un get avec cette clé

    Bonne (efficace) Vs mauvaise (pas efficace) #

    1. Bonne (effificace)

      • dépend seulement de la clé (utilisable)
      • évite les collisions (souvent donne différents indices pour différentes clés)
      • éparpille ou distribue les clés un peu partout dans la table
    2. Mauvaise (pas efficace)

      • dépend seulement de la clé (utilisable)
      • donne toujours le même indice
      • s’en va toujours au même endroit dans le tableau

    Avantages / inconvénients du Map par hachage #

    Avantages #

    1. Avec une bonne fonction de hachage, c’est temps constant O(1) pour retrouver une clé

    Inconvénients #

    1. Utilise plus d’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
      • Fonction de hachage
        • C’est quoi
        • Utilisable / pas utilisable (valide / invalide)
        • Bonne (efficace) Vs mauvaise (pas efficace)
      • Avantages / inconvénients du Map par hachage
        • Avantages
        • Inconvénients