:: Enseignements :: Master :: M1 :: 2013-2014 :: Java Avancé ::

Hash or Ash

On souhaite développer une structure de données pemettant de stocker des chaînes de caractère et de savoir si celle-ci sont contenue ou non dans la structure de donnée.

Exercice 1 - My first Hash

On cherche, dans un premier temps, à écrire une classe Hash permettant de stocker des chaînes de caractères et de vérifier si une chaîne de caractères est stockée par la classe.
Pour cet exercice, nous utiliserons le hachage fermé ; qui s'il y a collision stocke l'élement dans la case suivante ; avec une table dont la taille est une puissance de 2. De plus, dans un premier temps, nous considèrerons que la table ne se redimensionne pas.
Le test JUnit de l'exercice est: HashTest.java.

Rappeler comment marche le hachage fermé et à quoi sert la fonction de hashage hashCode, que faire si la valeur de hashCode est négative, pourquoi il faut faire un modulo sur la taille du tableau et qu'est ce qu'une collision.
Quelle est la particularité de la représentation binaire d'un nombre qui est une puissance de 2. Quelle est la particularité de la représentation binaire d'un nombre qui est une puissance de 2 moins 1.
Ecrire un constructeur prenant en paramètre un nombre maximum d'élements qui vérifie que ce nombre est une puissance de 2 et alloue la structure de donnée.
Ecrire une méthode add qui permet d'ajouter des chaînes de caractères (si celle-ci n'existe déjà pas).
Ecrire une méthode dump de debug (pas public) qui affiche le contenu complet du tableau.
Vous pouvez utiliser la classe java.util.Arrays.
Que doit-on faire si on ajoute la chaine de caractère est null ?
Expliquer pourquoi il n'est pas nécessaire de changer le code pour cela.
Ecrire une méthode contains qui renvoie vrai si l'élement est dans la structure de données.
Refactoriser votre code pour éviter la duplication de code.
Ecrire la méthode toString qui affiche les élements présent séparé par des virgules (sans la dernière) et l'ensemble des éléments entre '[' et ']'.
On cherche à lever une exception lorsque la table est pleine, comment doit-on faire ?
Implanter la solution retenue.

Exercice 2 - My second Hash

On cherche à améloirer la structure de données du premier exercice. On créera pour cela une nouvelle classe nommée Hash2 qui en plus d'améloirer la vitesse d'exécution, pourra se redimensionner automatiquement.
Le test JUnit de l'exercice est: Hash2Test.java.

Domment remplacer l'opération de modulo % par un masque utilisant le et bit à bit &.
Modifier le constructeur pour prendre n'importe quel valeur positive et utiliser la méthode Integer.highestOneBit pour trouver la première puissance de 2 supérieur au nombre donné.
Expliquer pourquoi il ne faut pas attendre que la table soit plein avant de redimensionner celle-ci.
Ecrire le code permettant de redimensionner la table quand le nombre d'élement est supérieur à la moitié de la taille du tableau.
Attention, à bien transférer correctement les valeurs de l'ancien tableau au nouveau !
Ecrire une méthode addAll, qui permet de recopier un Hash2 dans le Hash2 courant.
Faite les refactoring qui s'impose.
Ecrire une méthode intersect qui renvoie vrai si deux Hash2 ont au moins une chaine de caractères. en commun.
Expliquer pourquoi il est interressant de regarder le nombre d'élements de chaque Hash2 avant d'effectuer l'algorithme.