8. Tables de hachage

8.1. Notion de table de hachage

Une table de hachage est une structure de données qui associe des clés à des valeurs. Une telle structure doit au moins exposer deux fonctionnalités :
  • une méthode de type put(key, value), qui permet d'associer un objet à une clé ;
  • une méthode de type get(key), qui retourne la valeur qui a été associée à cette clé, ou null s'il n'y en a pas.
  • une méthode de type remove(key), qui supprime la clé de cette table, et la valeur qui lui est associée.
Il est bien sûr de la responsabilité de l'implémentation d'enregister les clés et les valeurs, et les associations qui existent entre elles. En Java, une table de hachage entretient trois ensembles.
  • Le premier est l'ensemble de ses clés. Il ne peut pas y avoir deux fois la même clé dans une table de hachage, cet ensemble ne peut donc pas posséder de doublon, il s'agit d'un Set.
  • Le deuxième est l'ensemble de ses valeurs. À la différence des clés, une même valeur peut être associée à plusieurs clés différentes. Cet ensemble est donc une Collection.
  • Le troisième est l'ensemble de ses entrées. Une entrée est un couple formé par une clé et la valeur qui lui a été associée.
Notons que ces trois ensembles ont nécessairement même cardinal.

8.2. Interface Map

Cette interface modélise la forme la plus simple d'une table de hachage. Comme prévu, elle expose les méthodes de base suivantes.
  • put(K key, V value) et get(K key) : ces deux méthodes permettent d'associer une clé à une valeur, et de récupérer cette valeur à partir de cette clé, respectivement.
  • remove(K key) : permet de supprimer la clé passée en paramètre de cette table, et la valeur associée.
  • keySet() : retourne l'ensemble de toutes les clés de cette table de hachage. Cet ensemble ne peut pas contenir de doublons, il s'agit d'un Set<K>, donc les éléments sont de type K. Cet ensemble est une vue sur les clés de la table de hachage. Donc les éléments ajoutés à cette table seront vus dans ce Set. Il supporte les méthodes remove() et removeAll(), mais pas les méthodes d'ajout d'éléments. Retirer une clé de cet ensemble retire également la valeur qui lui est associée.
  • values() : retourne l'ensemble de toutes les valeurs stockées dans cette table de hachage. À la différence de l'ensemble des clés, l'ensemble des valeurs peut contenir des doublons. Il est donc de type Collection<V>. Cette collection est également une vue sur la table : toute valeur ajoutée à la table sera vue dans cette collection. Elle supporte les méthode remove() et removeAll(), qui ont pour effet de retirer également la clé associée à cette valeur, mais pas les méthodes d'ajout.
  • entrySet() : retourne l'ensemble des entrées de cette table de hachage. Cet ensemble est un Set, dont les éléments sont de type Map.Entry. Nous allons voir l'interface Map.Entry dans la suite de cette partie. Cet ensemble est lui aussi une vue sur la table, qui reflète donc les modifications qui peuvent y être faites. Il supporte les opérations de retrait d'éléments, mais pas les opérations d'ajout.
Plusieurs autres méthodes utilitaires sont ajoutées à cette interface.
  • clear() : efface tout le contenu de la table.
  • size() et isEmpty() : retourne le cardinal de la table, et un booléen qui indique si cette table est vide ou pas.
  • putAll(Map map) : permet d'ajouter toutes les clés de la table passée en paramètre à la table courante.
  • containsKey(K key) et containsValue(V value) : permettent de tester si la clé ou la valeur passée en paramètre sont présentes dans cette table.
Comme on le voit, les méthodes exposées ne sont pas nombreuses, et assez simples à comprendre.

8.3. Interface Map.Entry

Cette interface permet de modéliser les couples (clé, valeur) d'une table de hachage. Elle expose deux méthodes : getKey() et getValue(), qui retournent bien sûr la clé et la valeur de ce couple. La seule façon d'obtenir un objet de type Map.Entry est de faire un appel à la méthode Map.entrySet(), et d'itérer sur le Set obtenu en retour. Cet objet est une vue sur la table. Il possède également une méthode setValue(V value), qui permet de modifier la valeur associée à une clé durant une itération.

8.4. Interface SortedMap

L'interface SortedMap permet de stocker des tables de hachage triées dans l'ordre de ses clés. De la même façon que pour SortedSet, cet ordre peut être défini de deux façons, soit par le fait que les clés de cette table sont des objets Comparable, soit en donnant un objet Comparator à la construction de la table. Rappelons que les classes enveloppe des types primitifs, et la classe String sont toutes des classes Comparable. On retrouve des méthodes conçues sur le même modèle que SortedSet.
  • firstKey() et lastKey() : retournent respectivement la plus petite clé et la plus grande.
  • headMap(K toKey) et tailMap(K fromKey) : retournent des vues sur la table maître, contenant les premières clés jusqu'à toKey, et les dernières clés à partir de fromKey, respectivement.
  • subMap(K fromKey, K, toKey) : retourne une vue sur la table maître, de la clé fromKey, à la clé toKey.
Tout comme pour SortedSet, le fait que la borne donnée lors de la construction de ces vues sur la table maître suit une logique obscure, qui impose de toute façon de consulter la documentation à chaque utilisation, ce qui a incité, en Java 6, à créer une interface supplémentaire : NavigableMap.

8.5. Interface NavigableMap

L'interface NavigableMap est une extension de SortedMap, qui complète le jeu de méthodes de sélection de vues sur la table maître.
  • ceilingKey(K key) et floorKey(K key) : retournent respectivement la plus petite clé supérieure ou égale, et la plus grande inférieure ou égale à la clé passée en paramètre.
  • ceilingEntry(K key) et floorEntry(K key) : retournent respectivement la plus petite clé supérieure ou égale, et la plus grande inférieure ou égale à la clé passée en paramètre.
  • higherKey(K key) et lowerKey(K key) : retournent respectivement la plus petite clé strictement supérieure, et la plus grande strictement inférieure à la clé passée en paramètre.
  • higherEntry(K key) et lowerEntry(K key) : retournent respectivement la plus petite clé strictement supérieure, et la plus grande strictement inférieure à la clé passée en paramètre.
  • firstEntry() et lastEntry() : retournent respectivement la plus petite entrée de cette table, et la plus grande.
  • headMap(K sup, boolean inclusive) et tailMap(K inf, boolean inclusive) : retournent des vues sur la table maître, dont les clés sont plus petites et plus grandes respectivement que la borne passée en paramètre. Le fait que l'inégalité soit stricte ou non est réglée par la valeur du boolean inclusive.
  • subMap(K fromKey, K, toKey) et subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) : retournent une vue sur la table maître, contenant les entrées dont les clés sont plus grandes que fromKey et plus petites que toKey. Le fait que les bornes soient ou non incluses dans la vue retournée est réglé par les deux booléens fromInclusive et toInclusive.
  • navigableKeySet() et descendingKeySet() retournent deux vues sur les clés de la table maître, triés dans l'ordre de cette table et dans son ordre inverse respectivement. Les ensembles retournés sont de type NavigableSet et supportent les opérations de suppression.
  • pollFirstEntry() et pollLastEntry() : retirent de la table, et retournent l'entrée dont la clé est la plus petite, respectivement la plus grande, de cette table.
  • navigableKeySet() et descendingKeySet() : retournent une vue sur l'ensemble des clés de cette table, dans l'ordre croissant et dans l'ordre décroissant respectivement. Cette vue supporte les opérations d'effacement, mais pas les opérations d'ajout.
  • descendingMap() : retourne une vue qui expose cette même table dans l'ordre inverse. Cela signifie que si l'on itère sur les éléments (clés ou entrées) de cette vue, cette itération se fera dans l'ordre décroissant des clés de la table maître.

8.6. Implémentations

L'API Java Collection nous fournit trois implémentations de l'interface Map :
  • Hashtable est présente depuis Java 1.0, et est synchronisée ;
  • HashMap autorise les valeurs nulles, et n'est pas synchronisée ;
  • LinkedHashMap étend HashMap et entretient une liste chaînée permettant d'itérer sur les entrées dans un ordre fixe.
L'interface SortedMap ne possède qu'une unique implémentation : TreeMap. Cette classe implémente également NavigableMap, extension de SortedMap. Si l'on doit utiliser TreeMap comme classe d'implémentation, autant utiliser l'interface NavigableMap, qui offre un jeu de méthodes beaucoup plus riche. Enfin, NavigableMap ne possède aussi que TreeMap comme implémentation.

8.7. Exemples d'utilisation

Voyons quelques exemples d'utilisation de ces tables de hachage. Commençons par remplir une table, et itérons dessus.

Exemple 13. Utilisation d'une table de type HashMap

// dans une méthode main
 // création de quelques marins
Marin m1 =  new Marin("Surcouf",  "Alain") ;
Marin m2 =  new Marin("Tabarly",  "Eric") ;
Marin m3 =  new Marin("Auguin",  "Christophe") ;
Marin m4 =  new Marin("Surcouf",  "Robert") ;

 // création d'une table dont les clés sont des String
 // et les valeurs des marins
Map<String, Marin> map =  new HashMap<String, Marin>() ;

 // ajout de nos marins à cette table
 // remarquons que deux ajouts possèdent la même clé
map.put(m1.getNom(), m1) ;
map.put(m2.getNom(), m2) ;
map.put(m3.getNom(), m3) ;
map.put(m4.getNom(), m4) ;

 // première interrogation de la table
System.out.println("[Surcouf] -> " + map.get("Surcouf")) ;
System.out.println("Eléments : " + map.size()) ;

 // parcours de la table par ses entrées
 for (Map.Entry<String, Marin> entry : map.entrySet()) {
   System.out.println("[" + entry.getKey() +  "] -> " + entry.getValue()) ;
}

L'exécution de ce code donne le résultat suivant.
[Surcouf] -> Surcouf Robert
Eléments : 3
[Tabarly] -> Tabarly Eric
[Surcouf] -> Surcouf Robert
[Auguin] -> Auguin Christophe
Alors que l'on a ajouté quatre marins dans notre table, seulement trois se retrouvent effectivement dedans. Cela est dû au fait que deux de ces marins ont même nom, et sont donc associés à la même clé. Le deuxième ajout écrase donc le premier. Prenons à présent le même exemple, avec une SortedMap. Nos clés sont des String. Cette classe est Comparable, nous n'avons donc pas besoin de fournir de Comparator à notre table triée.

Exemple 14. Utilisation d'une table de type TreeMap

Marin m1 =  new Marin("Surcouf",  "Robert") ;
Marin m2 =  new Marin("Tabarly",  "Eric") ;
Marin m3 =  new Marin("Auguin",  "Christophe") ;

NavigableMap<String, Marin> map =  new TreeMap<String, Marin>() ;
map.put(m1.getNom(), m1) ;
map.put(m2.getNom(), m2) ;
map.put(m3.getNom(), m3) ;

System.out.println("Eléments : " + map.size()) ;

 for (Map.Entry<String, Marin> entry : map.entrySet()) {
   System.out.println("[" + entry.getKey() +  "] -> " + entry.getValue()) ;
}

 // construction d'une vue en ordre inverse
System.out.println("Inversion...") ;
NavigableMap<String, Marin> reversedMap = map.descendingMap() ;
 for (Map.Entry<String, Marin> entry : reversedMap.entrySet()) {
   System.out.println("[" + entry.getKey() +  "] -> " + entry.getValue()) ;
}

 // suppression de Tabarly de la table maître
 // observons ce qui se passe pour la vue
System.out.println("Suppression de Tabarly...") ;
map.remove("Tabarly") ;
 for (Map.Entry<String, Marin> entry : reversedMap.entrySet()) {
    System.out.println("[" + entry.getKey() +  "] -> " + entry.getValue()) ;
}

L'exécution de ce code nous donne bien le résultat attendu.
Eléments : 3
[Auguin] -> Auguin Christophe
[Surcouf] -> Surcouf Robert
[Tabarly] -> Tabarly Eric
Inversion...
[Tabarly] -> Tabarly Eric
[Surcouf] -> Surcouf Robert
[Auguin] -> Auguin Christophe
Suppression de Tabarly...
[Surcouf] -> Surcouf Robert
[Auguin] -> Auguin Christophe
On constate bien que notre table s'est triée automatiquement par ordre croissant de clé. De plus, la vue décroissante que l'on a créée dessus a bien pris en compte l'effacement de Tabarly.
Java API avancées
Retour au blog Java le soir
Cours & Tutoriaux
Table des matières
API Collection
1. Introduction
2. Interface Collection
2.1. Notion de Collection
2.2. Détail des méthodes disponibles
2.3. Interface Iterator
2.4. Implémentation, exemples d'utilisation
3. Interface List
3.1. Notion de List
3.2. Détail des méthodes disponibles
3.3. Interface ListIterator
3.4. Implémentations, exemples d'utilisation
4. Interface Set
4.1. Notion de Set
4.2. Implémentations HashSet et LinkedHashSet
4.3. Exemples d'utilisation
5. Interface SortedSet
5.1. Notion de SortedSet
5.2. Détails des méthodes disponibles
5.3. Exemples d'utilisation
6. Interface NavigableSet
6.1. Notion de NavigableSet
6.2. Détails des méthodes disponibles
6.3. Exemple d'utilisation
7. Interfaces Queue et Deque
7.1. Notion de file d'attente
7.2. Détail des méthodes disponibles
7.3. Utilisation des interfaces Queue et Deque
8. Tables de hachage
8.1. Notion de table de hachage
8.2. Interface Map
8.3. Interface Map.Entry
8.4. Interface SortedMap
8.5. Interface NavigableMap
8.6. Implémentations
8.7. Exemples d'utilisation
9. Classes utilitaires Collections et Arrays
9.1. Introduction
9.2. Classe Arrays
9.3. Classe Collections
Génériques
1. Introduction
2. Un premier exemple
2.1. Une première classe générique
2.2. Une première méthode générique
3. Contraindre un type générique
3.1. Problème posé
3.2. Contraindre un type générique
4. Implémentation des génériques
4.1. Type erasure
4.2. Types génériques et casts
4.3. Type générique et exception
4.4. Construction d'une instance générique
4.5. Génériques et membres statiques
4.6. Collisions de méthodes génériques
4.7. Implémentation de plusieurs types identiques
5. Type <?>
5.1. Introduction
5.2. Type ? extension d'un type
5.3. Type ? super-type d'un type
Expressions régulières
1. Introduction
2. Mise en œuvre des expressions régulières
2.1. Fonctionnement d'une regexp
2.2. Fonctionnement de l'API en Java
2.3. Un premier exemple
2.4. Classe Pattern
2.5. Classe Matcher
2.6. Utilisation des méthode find() et group()
2.7. Méthodes de remplacement
2.8. Sélection de régions
3. Syntaxe des expressions régulières
3.1. Notion de classe
3.2. Étude d'un cas réel
3.3. Recherche d'un mot précis
3.4. Recherche de deux mots précis
3.5. Recherche d'un mot commençant par une lettre donnée
3.6. Cas de mots comportant des caractères accentués
3.7. Recherche sur les lignes
Introspection
1. Introduction
2. La classe Class
2.1. Utilisation de Class
2.2. Méthodes disponibles
2.3. Remarque sur la propriété Accessible
2.4. Type d'une classe
2.5. Création d'une instance à partir d'un objet Class
2.6. Cas des énumérations
3. Les classes Method et Constructor
3.1. Utilisation de Method
3.2. Utilisation de Constructor
3.3. Méthodes disponibles
3.4. Invocation d'une méthode par introspection
4. La classe Field
4.1. Utilisation de Field
4.2. Méthodes disponibles
4.3. Accès à un champ par introspection
5. La classe Modifier
Programmation concurrente
1. Introduction
2. Lançons nos premiers threads
2.1. Introduction
2.2. Un premier thread, extension de Thread
2.3. Un deuxième thread, implémentation de Runnable
2.4. Remarque sur la méthode Thread.sleep(long)
2.5. Arrêter un thread
3. Concurrence d'accès
3.1. Notion d'état
3.2. Exemple de concurrence d'accès sur un état
3.3. Analyse de la concurrence d'accès
3.4. Solution au problème
3.5. Champs volatile
4. Synchronisation
4.1. Définition d'un bloc synchronisé
4.2. Fonctionnement d'un bloc synchronisé
4.3. Notion de deadlock
4.4. Bonnes pratiques pour la synchronisation de threads
5. Opérations atomiques
5.1. Atomicité d'une opération
5.2. Solutions disponibles
5.3. Variables atomiques
6. Collections synchronisées et concurrentes
6.1. Introduction
6.2. Position du problème
6.3. Solutions proposées
7. Files d'attente
7.1. Introduction, pattern producteur / consommateur
7.2. Interface BlockingQueue<E>
7.3. Implémentations de BlockingQueue
7.4. Exemple de producteur / consommateur
7.5. Arrêter un producteur / consommateur : pilule empoisonnée
8. Classes utilitaires de l'API Concurrent
8.1. Introduction
8.2. Énumération TimeUnit
8.3. Interface Callable<V>
8.4. Interfaces Future<V> et RunnableFuture<V>
8.5. Interface ScheduledFuture<V> et RunnableScheduledFuture<V>
9. Pattern executor
9.1. Notion de réserve de threads
9.2. Interface Executor
9.3. Interface ExecutorService
9.4. Interface ScheduledExecutorService
9.5. Classe Executors
9.6. Pattern de lancement de tâches
10. Classes de contrôle d'accès
10.1. Introduction
10.2. Interfaces Lock et ReadWriteLock
10.3. Notion de verrou réentrant
10.4. Classe RentrantLock
10.5. Classe ReadWriteRentrantLock
11. Sémaphores, barrières et latches
11.1. Introduction
11.2. Notion de sémaphore, classe Semaphore
11.3. Notion de latch, classe CountDownLatch
11.4. Notion de barrière, classe CyclicBarrier