Atelier 5.2: implanter un mappage par hachage

Atelier 5.2: implanter un mappage par hachage #

Recopier des classes à partir de l'atelier5_1 #

  • Recopier les classes suivantes:

    • MapNaif
    • TesteurDeMapAbstrait
    • TesteurDeMapNaif

Créer la classe ChaineHasha (une mauvaise fonction de hachage) #

  • Ajouter la classe suivante au paquet atelier5_2

    • Nom de la classe: ChaineHasha

  • Débuter l’implantation comme suit:

public class ChaineHasha  extends CleHachable<String> {

    public ChaineHasha(String valeurJava) {
        super(valeurJava);
    }

    @Override
    public int indice() {

        // TODO: une mauvaise fonction de hachage
        
    }
}

Créer la classe ChaineHashb (une fonction de hachage moyenne) #

  • Ajouter la classe suivante au paquet atelier5_2

    • Nom de la classe: ChaineHashb

  • Débuter l’implantation comme suit:

public class ChaineHashb extends CleHachable<String> {

    public ChaineHashb(String valeurJava) {
        super(valeurJava);
    }

    @Override
    public int indice() {

        // TODO: une fonction de hachage "moyenne"
        
    }
}

Créer la classe ChaineHashc (une bonne fonction de hachage) #

  • Ajouter la classe suivante au paquet atelier5_2

    • Nom de la classe: ChaineHashc

  • Débuter l’implantation comme suit:

public class ChaineHashc extends CleHachable<String> {

    public ChaineHashc(String valeurJava) {
        super(valeurJava);
    }

    @Override
    public int indice() {

        // TODO: un bonne fonction de hachage
        
    }

}

Créer la classe MapHash #

  • Ajouter la classe suivante au paquet atelier5_2

    • Nom de la classe: MapHash

  • Débuter l’implantation comme suit:

public class MapHash <C extends CleHachable<?>, V extends Object> extends MapJava<C,V> {
    
    private static final int TAILLE_TABLE_HACHAGE = 20;
    
    private MapNaif<C,V>[] table = new MapNaif[TAILLE_TABLE_HACHAGE];
    private int taille = 0;

    public MapNaif<C, V>[] getTable() {
        return table;
    }

    public void setTable(MapNaif<C, V>[] table) {
        this.table = table;
    }

    public int getTaille() {
        return taille;
    }

    public void setTaille(int taille) {
        this.taille = taille;
    }

    private int indiceTable(C c) {
        int indiceBrut = c.indice();
        return indiceBrut % TAILLE_TABLE_HACHAGE;
    }

    @Override
    public void put(C c, V v) {
        // TODO
    }

    @Override
    public V get(C c) {
        // TODO
    }

    @Override
    public void clear() {
        // TODO
    }

    @Override
    public int size() {
        // TODO
    }

    @Override
    public boolean isEmpty() {
        // TODO
    }

    @Override
    public boolean containsKey(C c) {
        // TODO
    }

    @Override
    public boolean containsValue(V v) {
        // TODO
    }

    @Override
    public void remove(C c) {
        // TODO
    }

    @Override
    public List<C> keys() {
        // TODO
    }
}

Créer la classe TesteurDeMapHasha #

  • Ajouter la classe suivante au paquet atelier5_2

    • Nom de la classe: TesteurDeMapHasha

  • Implanter comme suit:

public class TesteurDeMapHasha extends TesteurDeMapAbstrait {

    @Override
    public MapJava<Cle<String>, Integer> nouveauMap() {
        return new MapHash();
    }

    @Override
    public CleHachable<String> nouvelleCle(String valeur) {
        return new ChaineHasha(valeur);
    }
}

Créer la classe TesteurDeMapHashb #

  • Ajouter la classe suivante au paquet atelier5_2

    • Nom de la classe: TesteurDeMapHashb

  • Implanter comme suit:

public class TesteurDeMapHashb extends TesteurDeMapAbstrait {

    @Override
    public MapJava<Cle<String>, Integer> nouveauMap() {
        return new MapHash();
    }

    @Override
    public CleHachable<String> nouvelleCle(String valeur) {
        return new ChaineHashb(valeur);
    }
}

Créer la classe TesteurDeMapHashc #

  • Ajouter la classe suivante au paquet atelier5_2

    • Nom de la classe: TesteurDeMapHashc

  • Implanter comme suit:

public class TesteurDeMapHashc extends TesteurDeMapAbstrait {

    @Override
    public MapJava<Cle<String>, Integer> nouveauMap() {
        return new MapHash();
    }

    @Override
    public CleHachable<String> nouvelleCle(String valeur) {
        return new ChaineHashc(valeur);
    }
}

Créer la classe MonAtelier5_2 #

  • Ajouter la classe suivante au paquet atelier5_2

    • Nom de la classe: MonAtelier5_2

  • Implanter comme suit:

public class MonAtelier5_2 extends Atelier5_2 {
    
    public static void main(String[] args) {
        
        (new MonAtelier5_2()).valider();
    }

    @Override
    public TesteurDeMap fournirTesteurDeMapNaif() {
        return new TesteurDeMapNaif();
    }

    @Override
    public TesteurDeMap fournirTesteurDeMapHasha() {
        return new TesteurDeMapHasha();
    }

    @Override
    public TesteurDeMap fournirTesteurDeMapHashb() {
        return new TesteurDeMapHashb();
    }

    @Override
    public TesteurDeMap fournirTesteurDeMapHashc() {
        return new TesteurDeMapHashc();
    }
}

Compléter les implantations #

  • Utiliser l’outil de validation pour tester votre code

  • vous pouvez aussi afficher les fichiers html:

    • MapHasha.html
    • MapHashb.html
    • MapHashc.html
    • (à la racine du projet)

Tester l’efficacité du code #

  • Les méthodes de votre TesteurDeMapAbstrait seront appelées

    • typiquement, utiliser une boucle pour effectuer une opération un certain nombre de fois

  • Vous devriez avoir des résultats similaires aux résultats ci-bas

    • fairePlusieursAjoutsAleatoires:
    • fairePlusieursModificationsAleatoires:
    • fairePlusieursRetraitsAleatoires:

    • accederAuxClesDansOrdre:

      • (*) ce graphe semble varier beaucoup d’un ordi à l’autre
Creative Commons License Creative Commons Attribution Creative Commons ShareAlike