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
    Theorie
    • Théorie 5.2: Map avec hachage
      • Fonction et table de hachage
      • Quoi faire en cas de collision?
      • Implantation d’un map avec hachage
      • Efficacité

    Théorie 5.2: Map avec hachage #

    Fonction et table de hachage #

    • On veut éviter de chercher l’indice de la clé avec un indexOf

    • On utiliser une fonction de hachage, c-à-d une méthode qui va

      • calculer un indice pour chaque clé
      • sans chercher d’information sur les autres clés
    • Une clé hachable doit implanter la méthode indice qui retourne l’indice de la clé

    public abstract class CleHachable <T extends Object> extends Cle<T> {
    	
    	public CleHachable(T valeurJava) {
    		super(valeurJava);
    	}
    
    	public abstract int indice();
    }
    
    • Voici par exemple une clé hachable quand la clé est une chaîne:
    public class ChaineHashb extends CleHachable<String> {
    
    	public ChaineHashb(String valeurJava) {
    		super(valeurJava);
    	}
    
    	@Override
    	public int indice() {
    		return getValeur().length();
    	}
    
    }
    
    • l’indice est simplement la longueur de la clé

    • Une fois qu’on a un indice, on peut mémoriser la valeur dans un tableau

    List<Character> valeurs = new ArrayList<>();
    
    cle01 = new ChaineHashb("v");
    cle02 = new ChaineHashb("yf");
    cle03 = new ChaineHashb("asf");
    
    map.put(cle01, 'a'):
    
        // la clé est "v",   l'indice est 1 (la longueur)
        int indice01 = cle01.indice();
        valeurs.set(indice01, 'a');
    
    map.put(cle02, 'b'):
    
        // la clé est "yf",  l'indice est 2 (la longueur)
        int indice02 = cle02.indice();
        valeurs.set(indice02, 'b');
    
    map.put(cle03, 'c'):
    
        // la clé est "asf", l'indice est 3 (la longueur)
        int indice03 = cle03.indice();
        valeurs.set(indice03, 'c');
    
    • IMPORTANT: la fonction de hachage ne doit pas être aléatoire
      • sinon on ne peut plus retrouver une valeur mémorisée par indice!

    Quoi faire en cas de collision? #

    • Quoi faire s’il y a une collision, c-à-d si deux clés ont le même indice?
    List<Character> valeurs = new ArrayList<>();
    
    cle01 = new ChaineHashb("x");
    cle02 = new ChaineHashb("y");
    
    map.put(cle01, 'a'):
    
        // la clé est "x", l'indice est 1 (la longueur)
        int indice01 = cle01.indice();
        valeurs.set(indice01, 'a');
    
    map.put(cle02, 'b'):
    
        // la clé est "y", l'indice est encore 1!
        int indice02 = cle02.indice();
        valeurs.set(indice02, 'b');      
    
        // oups! On vient d'écraser la paire "x":'a'
    
    • En fait, on ne peut pas associer un indice directement à une valeur

    • Il faut plutôt associer l’indice à un map naïf:

    MapJava<Cle,Character>[] valeurs = new MapJava<Cle,Character>[1000];
    
    cle01 = new ChaineHashb("x");
    cle02 = new ChaineHashb("y");
    cle03 = new ChaineHashb("z");
    
    map.put(cle01, 'a'):
    
        // la clé est "x", l'indice est 1 (la longueur)
        int indice01 = cle01.indice();
    
        // insérer d'abord un map à l'indice
        valeurs[indice01] = new MapJavaNaif<>();
    
        valeurs[indice01].put(cle01, 'a');
    
    map.put(cle02, 'b'):
    
        // la clé est "y",  l'indice est encore 1
        int indice02 = cle02.indice();
        valeurs[indice02].put(cle02, 'b');
    
    map.put(cle03, 'c'):
    
        // la clé est "z", l'indice est encore 1
        int indice03 = cle03.indice();
        valeurs[indice03].put(cle03, 'c');
    
    • S’il n’y a pas souvent de collision:

      • on accède aux valeurs surtout par indice
      • le map naïf associé à l’indice va contenir très peu de valeurs
      • c’est alors efficace
    • Au contraire, s’il y beaucoup de collisions:

      • on accède presque toujours aux mêmes indices
      • le map naïf associé à un indice va contenir beaucoup de valeurs
      • on accède donc aux valeurs surtout en cherchant la clé
      • c’est alors inefficace
    • Donc, une bonne fonction de hachage doit:

      • retourner le plus souvent possible un indice différent
      • retourner toujours le même indice pour la même clé (ne pas être aléatoire)

    Implantation d’un map avec hachage #

    • Voici le début de l’implantation
    public class   MapHash <C extends CleHachable<?>, V extends Object> 
           extends MapJava<C,V> {
    	
    	private static final int TAILLE_TABLE_HACHAGE = 1000;
    	
    	@SuppressWarnings("unchecked")
    	private MapJavaNaif<C,V>[] table = new MapJavaNaif[TAILLE_TABLE_HACHAGE];
    	private int taille = 0;
    
    • IMPORTANT:
      • la méthode CleHachable.indice peut retourner un indice >= table.length
      • il faut adapter l’indice à la table de notre tableau
      • habituellement, on fait ça avec l’opérateur modulo %

    Efficacité #

    • L’efficacité dépend du nombre de collisions, ce qui dépend en fait de:

      • la taille de la table de hachage
      • la qualité de la fonction de hachage
    • On a encore le compromis temps/espace mémoire:

      • pour obtenir plus d’efficacité en temps, on va utiliser plus d’espace mémoire
    • Exemple:

    • La fonction Hashc est très efficace, alors que
      • Hashb est un peu efficace
      • Hasha équivaut à l’implantation naïve
    Creative Commons License Creative Commons Attribution Creative Commons ShareAlike
    • Théorie 5.2: Map avec hachage
      • Fonction et table de hachage
      • Quoi faire en cas de collision?
      • Implantation d’un map avec hachage
      • Efficacité