Corrigé 7.  Enoncé

1. Hachage virtuel linéaire

Structure de données

    TYPE Typecase = STRUCTURE
        Nb     : ENTIER
        Tab     : TABLEAU [1..B] DE Typeqq
        Lien    : POINTEUR (Typecase)
    FIN

Paramètres

N                         : nombre initial de cases.
B                         : capacité de la case.
L                         : nombre de fois que la fonction change.
P                         : prochaine case à éclater.
Smin                   : seuil minimal.
Smax                : seuil maximal.
A                       : taux de chargement courant.
Nb_données    : nombre courant de données.
Nb_cases        : nombre courant de cases.
Tabhvl             : tableau de M cases de type typecase.

Si P est une adresse de case de type POINTEUR(Typecase) alors on définit les fonctions suivantes :

Nb(P)        : accès au champ Nb de P.
Lien(P)    : accès au champ Lien de P.
Tab(P)        : accès au champ Tab de P.
Tab(I)(P)    : accès au champ Tab(I) de P.

On peut aussi les utiliser comme variables et donc leur affecter des valeurs. Par exemple, on peut écrire Nb(P) := N.

Module d'initialisation

    Lire(N, B, Smin, Smax)
    Nb_données := 0 ; Nb_cases := N
    L, P := 0
    POUR I = 0, M - 1 :
        Tabhvl(I).Lien := NIL
        Tabhvl(I).Nb := 0
    FINPOUR

   
Module T de transformation donnée --> adresse

Soit H (L, K ) la fonction définie comme suit :

    H := K Mod (2L*N)

Le module de transformation donnée-adresse est le suivant :

    Adr := H(L, D)
    SI Adr < P : Adr := H(L+1, D) FSI
    T := Adr


Module de recherche d'une donnée D

Recherche(D, K, Trouv, Indice, Zoneprimaire, Prec_lien, Lien ) :

En entrée : la donnée D à rechercher.

En sortie : la classe K de D ; Trouv : existence de D ; Indice : indice de D s'il existe ;
Si Zoneprimaire = VRAI, alors D existe dans une case primaire sinon D est dans une case secondaire. Si D existe dans une case secondaire, Lien est l'adresse de cette case ; Prec_lien sa case précédente.

Soit Zone une variable de type Typecase.

    K := T(D)
    Prec_lien := NIL
    Zoneprimaire := VRAI
    Recherche_case( D, Tabhvl(K), Trouv, Indice );
    SI NON Trouv :
        Lien := Tabhvl(K).Lien
        TANTQUE NON Trouv ET Lien <> NIL :
            Zoneprimaire := FAUX
            Zone.Nb := Nb(Lien)
            Zone.Tab := Tab(Lien)
            Zone.Lien := Lien(Lien)
            Recherche_case(D, Zone, Trouv, Indice)
            SI NON Trouv :
                Preclien := Lien ; Lien := Lien(Lien)
            FSI
        FINTANTQUE
    FSI

Le module Recherche_case (D , Zone, Trouv , I ), de recherche à l'intérieur d'une case, est défini comme suit :

En entrée : D la donnée à rechercher; Zone : la case dont laquelle on fait la recherche.
En sortie : Trouv = VRAI si D existe dans la case, FAUX sinon. Si Trouv = VRAI , I est l'indice de D dans la case.

    I := 1; Trouv := FAUX;
    TANTQUE I<= Zone.Nb ET NON Trouv :
        SI Zone.Tab(I) = D
            Trouv := VRAI
        SINON I := I + 1 FSI
    FINTANTQUE

Module d'insertion d'une donnée D

    Recherche ( D, K, Trouv, Indice, Zprim, Preclien, Lien)
    SI Trouv :
        "D existe"
    SINON
        Ajouter ( D, K, Zprim, Preclien )
        Nb_données := Nb_données + 1
        A := Nb_données / ( Nb_cases * B)
        SI A >= Smax : éclater(P) FSI
    FSI

Le module Ajouter (D , K, Zprim , Lien) qui rajoute une donnée à une classe est le suivant :

En entrée     : l'élément D à rajouter ; K classe de D .
En sortie     : Zprim = VRAI si D est rajoutée dans une case primaire sinon dans une case secondaire. Si Zprim est FAUX, Lien est la case secondaire dans laquelle on rajoute D.

    SI Zprim
        SI Tabhvl(K).Nb < B
            Tabhvl(K).Nb := Tabhvl(K).Nb + 1
            Tabhvl(K).Tab( Tabhvl(K).Nb ) := D
        SINON
            Allouer (P, Typecase)
            Nb_cases := Nb_cases + 1
            Tabhvl(K).Lien := P
            Nb(P) := 1 ; Lien(P) := NIL ; Tab(1)(P) := D
        FSI
    SINON
        SI Nb(Lien) < B
            Nb(Lien) := Nb(Lien) + 1
            Tab( Nb(Lien) )(Lien) := D
        SINON
            Allouer (P, Typecase)
            Nb_cases := Nb_cases + 1
            Lien(Lien) := P
            Nb(P):= 1 ; Lien(P):= NIL; Tab(1)(P) := D
        FSI
    FSI

Le module éclater (K) qui éclate une case K est défini comme suit :

    Partager(K)
    P := P + 1
    SI P = N * 2L : L := L + 1 ; P := 0 FSI

Le module Partager(K) qui partage les données de la classe k par la fonction HL+1 est le suivant :

    Pos := P + 2l.N
    Nb_cases := Nb_cases + 1
    N, M := 0
    Générer_llc(K, Q);
    TANTQUE Q <> NIL :
        Adr := H(L+1, Valeur(Q) )
        SI Adr <> K : Ranger ( Valeur(Q), Adr, N, Lien )
        SINON Ranger ( Valeur(Q), K, M, Lien) FSI
        R :=Q
        Q:=Suivant(Q)
        Libérer(R)
    FINTANTQUE

Les données sont distribuées entre la case K et la nouvelle case ajoutée à la fin : P + 2L.N. Ce module utilise le module Générer_llc qui construit la liste linéaire chaînée Q de toutes les données de la classe k avant de les distribuer entre les deux cases concernées.

Le module Ranger ( Val , Pos , N , Lien ) permettant de ranger la valeur Val dans la classe Pos est :

N désigne le nombre d'éléments déjà rangés et Lien l'adresse de la zone secondaire courante dans le cas o� N est supérieur à B. N et Lien sont à la fois des paramètres d'entrée et de sortie.

    SI N < B :
        N := N + 1
        Tabhvl(Pos).Nb := N
        Tabhvl(Pos).Tab( N ) := Val
    SINON
        SI (N Mod B) <> 0 (* N non multiple de B *)
            Nb(Lien) := Nb(Lien) + 1
            N := N + 1
            Tab( Nb(Lien) )(Lien) := Val
        SINON
            Allouer(P, Typecase)
            Nb_cases := Nb_cases + 1
            SI N<>B : Lien(Lien) := P
            SINON Tabhvl(Pos).Lien := P FSI
            N:=N+1
            Lien := P
            Nb(Lien):= 1 ;Lien(Lien):= NIL;
            Tab(1)(Lien):= Val
        FSI
    FSI

Module de suppression

Avant de décrire le module de suppression, commençons par définir les modules suivants :
- Le module Enlever (D , K, Indice , Zprim , Preclien, Lien) qui enlève la donnée D de la classe K est défini comme suit :

Si Zprim est VRAI, alors D est dans une case primaire et Indice est son rang.
Si Zprim est FAUX, alors D est dans une case secondaire et Indice est son rang. Dans ce dernier cas, Lien est l'adresse de sa case secondaire et Prec_lien l'adresse de la case précédente.
Enlever une donnée consiste à la remplacer par la dernière donnée de la classe. Ceci est fait pour éviter la formation de "trous". Ce module utilise le module Recherche_dernière_case pour trouver la dernière donnée de la classe k.

- Le module Fusionner ( k ) est défini comme suit :

    P := P - 1
    SI P < 0 : L := L -1 ; P := N * 2l - 1 FSI
    Transfert( P + 2l. N)
    Tabhvl(Pos).Lien := NIL
    Tabhvl(Pos).Nb := 0

- Le module Transfert (Pos) permet de transférer toutes les données de la dernière case Pos dans la classe P.

Une expression formelle de l'algorithme de suppression est la suivante :

    Recherche ( D, K, Trouv, Indice, Zprim, Preclien, Lien)
    SI Not Trouv
        "D n'existe pas "
    SINON
        Enlever( D, K, Indice, Zprim, Preclien, Lien);
        Nb_données := Nb_données - 1;
        A := Nb_données / ( Nb_cases * B );
        SI A <= Smin : Fusionner(P) FSI
    FSI