:: Enseignements :: ESIPE :: E4INFO :: 2013-2014 :: Java Avancé ::

Hash or Ash

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

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'élément 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 la différence entre hachage fermé et ouvert. A quoi sert la fonction de hachage hashCode? Que faire si la valeur de hashCode est négative? Pourquoi faut-il faire un modulo sur la taille du tableau? 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'éléments qui vérifie que ce nombre est une puissance de 2 et alloue la structure de données.
Ecrire une méthode add qui permet d'ajouter des chaînes de caractères (si celle-ci n'existe pas déjà).
Ecrire une méthode dump de debug (pas publique) qui affiche le contenu complet du tableau.
Vous pouvez utiliser la classe java.util.Arrays.
Que doit-on faire si on ajoute une chaîne de caractères qui 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'élément 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ésents, séparés 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éliorer la structure de données du premier exercice. On créera pour cela une nouvelle classe nommée Hash2 qui, en plus d'améliorer la vitesse d'exécution, pourra se redimensionner automatiquement.
Le test JUnit de l'exercice est: Hash2Test.java.

Comment remplacer l'opération de modulo % par un masque utilisant le et bit à bit &.
Modifier le constructeur pour prendre n'importe quelle valeur positive et utiliser la méthode Integer.highestOneBit pour trouver la première puissance de 2 supérieure au nombre donné.
Expliquer pourquoi il ne faut pas attendre que la table soit pleine avant de redimensionner celle-ci.
Ecrire le code permettant de redimensionner la table quand le nombre d'éléments 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.
Faites les refactoring qui s'impose.
Ecrire une méthode intersect qui renvoie vrai si deux Hash2 ont au moins une chaîne de caractères. en commun.
Expliquer pourquoi il est intéressant de regarder le nombre d'élements de chaque Hash2 avant d'effectuer l'algorithme.