TD2 Tables de hachage 1. Diagramme d'instances ------------------------ +-----------------+ | h: TableHachage | +-----------------+ | nbPaquets = 8 | | nbElements = 7 | +-----------------+ | | | +-----------------+ | t: TablePaquets | +-----------------+ | | +------------+ +-----| p0: Paquet | | +------------+ | | +------------+ +-------------+ +-----| p1: Paquet |------| 11: Integer | | +------------+ +-------------+ | | +------------+ +-------------+ +-----| p2: Paquet |------| -2: Integer | | +------------+ +-------------+ | | +------------+ +-------------+ +-----| p3: Paquet |------| 17: Integer | | +------------+ +-------------+ | | +------------+ +-----| p4: Paquet | | +------------+ | | +------------+ +-------------+ +-----| p5: Paquet |------| 7: Integer | | +------------+ +-------------+ | | +------------+ +-----| p6: Paquet | | +------------+ | | +------------+ +-------------+ +-----| p7: Paquet |------| -3: Integer | +------------+ +-------------+ | +-------------+ +---------| 5: Integer | | +-------------+ | +-------------+ +---------| 13: Integer | +-------------+ 2. Séquence des opérations -------------------------- La séquence décrite ne concerne que le cas où le paramètre [elt] est différent de [null] (dans le cas contraire la spécification indique que le résultat doit être [false], et aucun calcul n'est nécessaire). On suppose donc que le paramètre a déjà été testé, et on se place dans le cas non [null]. Exemple A : elt = 11 Exemple B : elt = 8 Dans ce cas, la table de hachage utilise son opération d'obtention d'un indice de paquet [TableHachage::indicePaquet]. Pour cela, elle appelle l'opération [T::code] d'obtention du code de l'élément [elt] passé en paramètre et obtient un code [c], dont elle déduit un indice [i] dans le bon intervalle avec une opération de modulo. Exemple A : c = 11*3 = 33 i = 33%8 = 1 Exemple B : c = 8*3 = 24 i = 24%8 = 0 Puis utilisation de l'opération de récupération d'un paquet du tableau [TablePaquets::paquet], à laquelle on passe le paramètre [i]. On obtient en retour un paquet [p], et on utilise l'opération de test d'appartenance [Paquet::contient] d'un élément à ce paquet [p]. Exemple A : p = t.paquet(1) = p1 Exemple B : p = t.paquet(0) = p0 Enfin, on renvoie le résultat donné par cette dernière opération. Exemple A : resultat = p1.contient(11) = true Exemple B : resultat = p0.contient(8) = false 3. Effets et satisfaction des préconditions ------------------------------------------- TableHachage::indicePaquet(T elt) La précondition permet d'appeler directement les opérations de [elt] sans sans tester au préalable qu'il n'est pas [null] (on peut envisager de tester cette précondition avec un [assert] à des fins de débogage). Pour garantir que cette condition est satisfaite à chaque appel, c'est à l'opération appelante de tester au préalable. TablePaquets::paquet(int i) La précondition permet d'éviter de tester le respect des bornes du tableau et de prévoir un cas d'erreur. Elle est satisfaite car le paramètre fourni est le résultat d'un appel à [TableHachage::indicePaquet], dont la postcondition assure le respect des bornes. Implicitement, [T::code] et [Paquet::contient] demandent que leur paramètre implicite ne soit pas [null]. Pour [T::code] c'est garanti par le fait que [elt] ait déjà été vérifié, et pour [Paquet::contient] par la postcondition de [TablePaquets::paquet]. Ainsi, à l'intérieur de ce système dont nous maîtrisons chaque composant, nous pouvons simplifier la description et le code de plusieurs méthodes en supposant que leurs paramètres vérifient certaines propriétés (les préconditions). Cela vaut car en parallèle, nous faisons en sorte que ces méthodes ne soient jamais appelées dans des contextes dans lesquels ces propriétés ne seraient pas valides. 4. Changement de précondition ----------------------------- Nous ne maîtrisons pas le contexte d'appel de [TableHachage::contient] par le client. Il faut donc prendre des mesures pour éviter qu'un mauvais paramètre ne perturbe le reste de la chaîne. Notamment : - la précondition doit être documentée publiquement - on peut aussi, et c'est même recommandé, vouloir faire un test pour déclencher une exception en cas de paramètre illégal plutôt que d'attendre que cela ait une conséquence imprévue ailleurs ; cette exception doit également être documentée 5. Retirer un élément --------------------- Selon la spécification actuelle, un paquet peut contenir plusieurs occurrences de l'élément à retirer. L'opération [Paquet::retire] ne retirant qu'une occurrence, et ne faisant pas de retour particulier en cas d'absence de l'élément, on a besoin de tester la présence de l'élément, et d'itérer jusqu'à sa disparition complète. Si on avait un invariant selon lequel les paquets ne contiennent pas de doublons, on pourrait se contenter d'un appel à [Paquet::retire]. Pour garantir que cet invariant est satisfait, on peut inclure dans la postcondition de [TableHachage::ajoute] la contrainte que cette opération ne modifie pas la table lorsque l'élément est déjà présent. On a donc : Nouvel invariant - Aucun élément n'apparaît deux fois dans un paquet Spécification de TableHachage::ajoute(T elt) - Précondition : [elt] n'est pas [null] - Résultat : néant - Postcondition : [elt] est ajouté à la table s'il n'y était pas déjà ; dans ce cas l'attribut [nbElements] est incrémenté, et sinon la table n'est pas modifiée Diagramme de séquence correspondant : On précise déjà que la séquence d'opérations n'est exécutée que lorsque [elt] n'est pas [null] (si [elt] est [null] on s'arrête immédiatement). Comme pour [contient] on commence par calculer l'indice [i] du paquet et récupérer le paquet [p]. Ensuite, on utilise [Paquet::contient] pour tester la présence de l'élément. À partir de là, deux possibilités : 1/ si l'élément était présent on s'arrête 2/ sinon on utilise [Paquet::ajoute] (et on incrémente mais cela n'apparaît pas vraiment dans le diagramme comme une opération, on peut se contenter de mettre un commentaire) 6. Augmentation du nombre de paquets ------------------------------------ On modifie l'opération [TableHachage::ajoute]. On ajoute en postcondition que si [nbElements]/[nbPaquets] est plus grand que [seuilCharge], alors [nbPaquet] est doublé, [tableau] est remplacé par un nouveau tableau de la bonne taille, et de nouveaux paquets sont formés, qui contiennent exactement les éléments précédents, plus l'élément qui vient d'être ajouté. Sur le diagramme de séquence correspondant on peut observer la création d'une nouvelle instance de [TablePaquet] et la disparition de l'instance d'origine, comme dans le fragment suivant. h:TableHachage t: TablePaquets | | | TablePaquets(2 x nbPaquets) | |--------------------------------> newt: TablePaquets | | | | | ajoute(oldelt) | | |----------------------------------------->| [pour chaque | | ok | oldelt de t] | |<-----------------------------------------| | | | | | | | | | X | | [à la fin l'ancienne | | table disparaît]