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.

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.

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


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.


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