Tables de Hachage
Table of Contents
1 Tables de hachages et types de clés
Une table de hachage est une structure permettant de stocker des associations entre des clés et des valeurs. Les types des clés et des valeurs peuvent être quelconque. Toutefois, dans ce TP, on ne prendra pour clés que des entiers.
2 Implementation d'une table de hachage
2.1 Présentation
Il s'agit de programmer une table de hachage à l'aide d'un tableau de taille fixé lors de la création de la table de hachage et de listes chaînées pour gérer les éventuelles collisions. Le squelette de cet objet est fournit dans le fichier TableHachage.java :
Pour simplifier, les clés seront nécessairement des entiers dans notre
implémentation. Les valeurs, par contre, pourront être de type
quelconque. Le type TableHachage est donc paramétré, comme vous l'avez
vu en programmation.
2.2 Exercice
Que doivent contenir les cases du tableau tableau (ie le type noté XXX
dans le source fourni) ?
Complétez l'implémentation proposée. Vous pouvez vous inspirer de
votre implémentation de Maillon en TP de programmation pour réaliser
votre liste chaînée, après l'avoir modifiée pour l'adapter aux besoins
de ce TP, ou utiliser les deux classes suivantes : Liste.java
et Maillon.java.
2.3 Remarque : table de hachage en java
En réalité, si on a besoin de tables de hachage en java, on utilise
directement la bibliothèque standard qui les implémente. Vous pouvez
regarder la documentation du type HashMap en particulier.
3 Utilisation des tables de hachage
3.1 Présentation du problème
Considérons N entiers données. Étant donné un entier S, on cherche à
trouver si possible deux entiers parmi la liste initiale dont la somme
vaut S.
3.1.1 Algorithme naïf
Il s'agit ici de tester toutes les paires (soit un algorithme en
O(n²)) en calculant la somme à chaque fois et en comparant le résultat
à S.
3.1.2 Algorithme d'appariement
Si on trie les entiers, on peut ensuite se contenter d'apparier (en
sommant) le max et le min, puis on réduit le max ou on augmente le min
suivant si la somme courante est plus grande ou plus petite que
S. Quelle est la complexité de cet algorithme ?
3.1.3 Algorithme avec l'utilisation d'une table de hachage
Pour chaque entier x, on stocke S-x dans une table de hachage, puis,
pour chaque entier x, on cherche si x est présent dans la
table. Quelle est la complexité de cet algorithme ?
3.2 Exercices
Complétez le squelette du fichier TrouveCouple.java
pour implémenter les différents algorithmes proposés. Si vous avez le temps, vous pouvez réduire/supprimer les affichages et faire des mesures de performance des différents algorithmes quand vous avez un grand nombre de nombres.