[ABD] Structure primaire du fichier : Hachage avec chaînage externe

Le fichier dans une base des données est vu comme une suite ou un ensemble d'enregistrements. Ces enregistrements sont répartis sur plusieurs blocs. Vu la différence entre la taille de la base des données et le buffer utilisé par le SGBD dans la mémoire centrale pour effectuer les différentes opérations, il est nécessaire de choisir l'organisation la plus adéquate pour limiter le nombre d'accès disque qui sont des milliers de fois moins rapide que les accès à la mémoire centrale.
Cet objectif peut être atteint en utilisant deux approches :

• Par jouer sur l'arrangement des enrtegistrements dans le fichier. En effet, l'approche la plus intuitive est de ranger les enregistrements dans l'ordre de leur arrivée. Cette approche est la moins performante si elle n'est pas associée à une autre approche : la recherche devient très coûteuse parce qu'il faut parcourir tout le fichier à chaque fois. Alors, il faut ranger les enregistrements d'une manière à limiter les accès disque et rendre la recherche plus efficace.
• Par l'ajout d'une structure secondaire. Cette structure n'aura pas comme rôle le stockage des données comme le fichier primaire mais elle facilitera l'accès à ces données. Les index sont un exemple de ces structures.

Dans cet exemple de core, nous visons à simuler l'utilisation du hachage : une méthode qui s'inscrit dans la première appoche. Le hachage range les enregistrements suivant la valeur de l'un de ses champs, appelé clé de hachage. Ainsi, la position du nouvel enregistrement à insérer n'est pas la prochaine position vide, mais, c'est la position donnée par la fonction de hachage sur la valeur de la clé du hachage (généralement la clé primaire) pour le nouvel enregistrement. Par conséquent, les deux opérations d'écriture et de lecture se limitent à un seul accès disque.
Cette approche a deux inconvénients majeurs :

• Il faut avoir, au préalable, une estimation sur les données à sauvegarder. Il est aussi nécessaire de réserver un certain nombre de blocs même si le fichier est vide.
• Les collisions (les conflits) : lorsque deux enregistrements différents auront la même positions (les deux clés de hachage donnent la même valeur), on parle d'une collision (conflit). La résolution des conflit (quelque soit la méthode) peut limiter les performances obtenues par l'utilisation du hachage.

Dans le code du projet, nous allons utiliser le chaînage externe pour résoudre les conflits. Cette solution consiste à créer une liste linéaire chaînée dans cahque position. Cette liste va contenir toutes les valeurs en collision. Pour lire d'avantage sur cette approche, vous pouvez vous référer au cours de M. Zegour par ici.
Le projet est construit sur une seule classe : Page. Cette classe nous permet de stocker des données (des enregistrements) et de faire la recherche (une recherche séquentielle rapide). La Page contient aussi un pointeur vers la Page suivante : cela peut être utilisé pour le chaînage ou bien, tout simplement, ignoré.

public class Page {
    
    /**
     * La taille de la page.
     * Le nombre des enregistrements que la page peut contenir (le facteur de blocage, bfr).
     */
    public static final int TAILLE = 2;
    
    /**
     * Le contenu de la page.
     * Dans cet exemple, le contenu est réduit à une simple valeur (la clé de hachage) mais, en réalité, on parle d'un
     * enregistrement complet.
     */
    public int[] contenu;
    
    /**
     * Le degrée de remplissage de la page.
     * Pour connaître est ce qu'une page est pleine ou pas.
     */
    public int placesOccupees;
    
    /**
     * Un pointeur vers la page suivante.
     * Ce pointeur est nécessaire pour créer des listes linéaires chaînées des pages.
     */
    public Page suivant;

    /**
     * Constructeur par défaut.
     */
    public Page() {
        contenu = new int[TAILLE];
        for (int i = 0; i < contenu.length; i++) {
            contenu[i] = -1;
        }
        placesOccupees = 0;
        suivant = null;
    }

    public int[] getContenu() {
        return contenu;
    }

    public void setContenu(int[] contenu) {
        this.contenu = contenu;
    }

    public int getPlacesOccupees() {
        return placesOccupees;
    }

    public void setPlacesOccupees(int placesOccupees) {
        this.placesOccupees = placesOccupees;
    }

    public Page getSuivant() {
        return suivant;
    }

    public void setSuivant(Page suivant) {
        this.suivant = suivant;
    }

    /**
     * Vérifie si la page contient une valeur ou pas.
     * @param valeur La valeur à rechercher dans la page.
     * @return Vrai si la page contient la valeur, faux autrement.
     */
    public boolean contient(int valeur){
        boolean contient = false;
        int i = 0;
        while(i < TAILLE && !contient){
            if(contenu[i] == valeur)
                contient = true;
            i++;
        }
        return contient;
    }
    
    /**
     * Ajouter une valeur à la page.
     * A la fin  de l'exécution, la page va contenir la valeur (soit elle l'a contenue dès le début ou bien après son ajout).
     * Si la page est pleine, la valeur faux est retournée pour indiquer que l'opération d'ajout à échoué.
     * @param valeur La valeur à ajouter à la page.
     * @return Vrai si l'opération d'ajout a réussi, Faux autrement.
     */
    public boolean ajouterValeur(int valeur){
        boolean reponse = false;
        
        if(contient(valeur))
            reponse = true;
        
        if(!contient(valeur) && placesOccupees < TAILLE){
            contenu[placesOccupees] = valeur;
            placesOccupees++;
            reponse = true;
        }
        
        return reponse;
    }
    
    /**
     * Une représentation du contenu de la page sous forme d'une chaîne de caractère.
     * Seulement le contenu est inclu.<br/>
     * Si la page suivante n'est pas null, elle sera aussi inclue. Le chaînage est représenté par le symbole "==>".
     * @return La chaîne qui représente la page.
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        
        sb.append("Page {\n");
        for (int i = 0; i < contenu.length; i++) {
            sb.append("\t" + contenu[i] + "\n");
        }
        sb.append("}");
        
        if(getSuivant() != null){
            sb.append(" == > " + getSuivant().toString());
        }
        sb.append("\n");
        
        return sb.toString();
    }
        
}

Le projet contient deux gestionnaires :

• Un gestionnaire séquentiel : qui range les enregistrements dans l'ordre de leur arrivée.
• Un gestionnaire qui utilise le hachage par chaînage externe.

Ce dernier voit chaque position comme une liste linéaire chaînée et tente d'ajouter la nouvelle valeur au fichier en commençant par la première page et en passant vers la page suivante en utilisant le pointeur "suivant".
Si on arrive à la fin de la liste (suivant == null) sans pouvoir ajouter l'élément, alors un nouveau noeud est ajouté à la liste et l'élément est ajouté à ce dernier noeud :

    public void ajouterValeur(int valeur) {
        int position = hach(valeur);
        Page page = pages[position];

        while(!page.ajouterValeur(valeur)){
            if(page.getSuivant() == null)
                page.setSuivant(new Page());
            page = page.getSuivant();
        }
    }

Le code source du projet peut être obtenu par ici. Dans ce projet, nous allons créer les deux gestionnaires, faire des insértion et ensuite effectuer des recherches (on recherche les même éléments. On peut voir rapidement que l'approche séquentielle peut atteindre 7 accès disques tant dit que l'appproche par hachage ne dépasse jamais 2 accès disques.
Il est possible d'exécuter directement le fichier jar du projet qui se trouve dans le dossier "dist":

java -jar ABD06.jar 

Si l'affichage est trop vite, il est possible de mettre la sortie du projet dans un fichier texte par la commande suivante.

java -jar ABD06.jar >> test.txt