Framework de collections Java - Java collections framework
Le framework de collections Java est un ensemble de classes et d' interfaces qui implémentent des structures de données de collection couramment réutilisables .
Bien qu'appelé framework , il fonctionne à la manière d' une bibliothèque . Le framework de collections fournit les deux interfaces qui définissent diverses collections et classes qui les implémentent.
Différences avec les tableaux
Les collections et les tableaux sont similaires dans la mesure où ils contiennent tous deux des références à des objets et peuvent être gérés en tant que groupe. Cependant, contrairement aux tableaux, les collections n'ont pas besoin de se voir attribuer une certaine capacité lorsqu'elles sont instanciées. Les collections peuvent également augmenter et réduire leur taille automatiquement lorsque des objets sont ajoutés ou supprimés. Les collections ne peuvent pas contenir d'éléments de type de données de base (types primitifs) tels que int, long ou double ; au lieu de cela, ils contiennent des classes Wrapper telles que Integer, Long ou Double.
Histoire
Les implémentations de collection dans les versions pré- JDK 1.2 de la plate-forme Java comprenaient peu de classes de structure de données, mais ne contenaient pas de framework de collections. Les méthodes standard pour regrouper les objets Java étaient via le tableau, les classes Vector et Hashtable, qui n'étaient malheureusement pas faciles à étendre et n'implémentaient pas d'interface membre standard.
Pour répondre aux besoins de collecte réutilisables structures de données , plusieurs cadres indépendants ont été développés, les plus utilisés étant Doug Lea de paquet Collections et ObjectSpace Bibliothèque Collection générique (JGL), dont l' objectif principal était la cohérence avec le C ++ Standard Template Library (STL) .
Le cadre des collections a été conçu et développé principalement par Joshua Bloch , et a été introduit dans JDK 1.2 . Il a réutilisé de nombreuses idées et classes du package Collections de Doug Lea , qui a été déprécié en conséquence. Sun Microsystems a choisi de ne pas utiliser les idées de JGL, car ils voulaient un framework compact, et la cohérence avec C++ n'était pas l'un de leurs objectifs.
Doug Lea a ensuite développé un package de concurrence , comprenant de nouvelles classes liées à la collection. Une version mise à jour de ces utilitaires de simultanéité a été incluse dans JDK 5.0 à partir de JSR 166 .
Architecture
Presque toutes les collections en Java sont dérivées de l'interface java.util.Collection. Collection définit les éléments de base de toutes les collections. L'interface indique les méthodes add() et remove() pour l'ajout et la suppression d'une collection respectivement. La méthode toArray() est également requise, qui convertit la collection en un simple tableau de tous les éléments de la collection. Enfin, la méthode contains() vérifie si un élément spécifié est dans la collection. L'interface Collection est une sous-interface de java.lang.Iterable, donc toute collection peut être la cible d'une instruction for-each. (L'interface Iterable fournit la méthode iterator() utilisée par les instructions for-each.) Toutes les collections ont un itérateur qui parcourt tous les éléments de la collection. De plus, Collection est un générique. N'importe quelle collection peut être écrite pour stocker n'importe quelle classe. Par exemple, Collection<String> peut contenir des chaînes et les éléments de la collection peuvent être utilisés en tant que chaînes sans aucun transtypage requis. Notez que les crochets angulaires < > peuvent contenir un argument de type qui spécifie le type de la collection.
Trois types de collecte
Il existe trois types génériques de collection : les listes ordonnées, les dictionnaires/cartes et les ensembles.
Les listes ordonnées permettent au programmeur d'insérer des éléments dans un certain ordre et de récupérer ces éléments dans le même ordre. Un exemple est une liste d'attente. Les interfaces de base pour les listes ordonnées sont appelées Liste et File d'attente.
Les dictionnaires/cartes stockent les références aux objets avec une clé de recherche pour accéder aux valeurs de l'objet. Un exemple de clé est une carte d'identité. L'interface de base pour les dictionnaires/cartes s'appelle Map.
Les ensembles sont des collections non ordonnées qui peuvent être itérées et contiennent chaque élément au plus une fois. L'interface de base pour les ensembles s'appelle Set.
Interface de liste
Les listes sont implémentées dans le framework des collections via l'interface java.util.List. Il définit une liste comme étant essentiellement une version plus flexible d'un tableau. Les éléments ont un ordre spécifique et les éléments en double sont autorisés. Les éléments peuvent être placés dans une position spécifique. Ils peuvent également être recherchés dans la liste. Voici deux exemples de classes concrètes qui implémentent List :
- java.util.ArrayList, qui implémente la liste sous forme de tableau. Chaque fois que des fonctions spécifiques à une liste sont requises, la classe déplace les éléments dans le tableau afin de le faire.
- java.util.LinkedList. Cette classe stocke les éléments dans des nœuds qui ont chacun un pointeur vers les nœuds précédents et suivants de la liste. La liste peut être parcourue en suivant les pointeurs, et des éléments peuvent être ajoutés ou supprimés simplement en changeant les pointeurs pour placer le nœud à sa place.
Classe de pile
Les piles sont créées à l'aide de java.util.Stack. La pile propose des méthodes pour mettre un nouvel objet sur la pile (méthode push()) et pour récupérer des objets de la pile (méthode pop()). Une pile renvoie l'objet en fonction du dernier entré, premier sorti (LIFO), par exemple l'objet qui a été placé en dernier sur la pile est renvoyé en premier. java.util.Stack est une implémentation standard d'une pile fournie par Java. La classe Stack représente une pile d'objets dernier entré, premier sorti (LIFO). Il étend la classe java.util.Vector avec cinq opérations qui permettent de traiter un vecteur comme une pile. Les opérations push et pop habituelles sont fournies, ainsi qu'une méthode pour jeter un coup d'œil à l'élément supérieur de la pile, une méthode pour tester si la pile est vide et une méthode pour rechercher un élément dans la pile et découvrir à quelle distance il est du haut. Lorsqu'une pile est créée pour la première fois, elle ne contient aucun élément.
Interfaces de file d'attente
L'interface java.util.Queue définit la structure de données de file d'attente, qui stocke les éléments dans l'ordre dans lequel ils sont insérés. Les nouveaux ajouts vont à la fin de la ligne et les éléments sont supprimés du devant. Il crée un système premier entré, premier sorti. Cette interface est implémentée par java.util.LinkedList, java.util.ArrayDeque et java.util.PriorityQueue. LinkedList, bien sûr, implémente également l'interface List et peut également être utilisée comme telle. Mais il a aussi les méthodes Queue. ArrayDeque implémente la file d'attente sous forme de tableau. LinkedList et ArrayDeque implémentent également l'interface java.util.Deque, ce qui lui donne plus de flexibilité.
java.util.Queue peut être utilisé de manière plus flexible avec sa sous-interface, java.util.concurrent.BlockingQueue. L'interface BlockingQueue fonctionne comme une file d'attente normale, mais les ajouts et suppressions de la file d'attente sont bloquants. Si remove est appelé sur une file d'attente vide, il peut être configuré pour attendre un temps spécifié ou indéfiniment pour qu'un élément apparaisse dans la file d'attente. De même, l'ajout d'un élément est soumis à une restriction de capacité facultative sur la file d'attente, et la méthode peut attendre que de l'espace se libère dans la file d'attente avant de revenir.
java.util.PriorityQueue implémente java.util.Queue, mais le modifie également. Au lieu que les éléments soient classés dans l'ordre dans lequel ils sont insérés, ils sont classés par priorité. La méthode utilisée pour déterminer la priorité est soit la méthode compareTo() dans les éléments, soit une méthode donnée dans le constructeur. La classe crée cela en utilisant un tas pour garder les éléments triés.
Interfaces de file d'attente à double extrémité (deque)
L'interface java.util.Queue est étendue par la sous-interface java.util.Deque. Deque crée une file d'attente double. Alors qu'une file d'attente régulière n'autorise que les insertions à l'arrière et les retraits à l'avant, le deque permet aux insertions ou aux retraits d'avoir lieu à la fois à l'avant et à l'arrière. Un deque est comme une file d'attente qui peut être utilisée en avant ou en arrière, ou les deux à la fois. De plus, un itérateur avant et arrière peut être généré. L'interface Deque est implémentée par java.util.ArrayDeque et java.util.LinkedList.
L'interface java.util.concurrent.BlockingDeque fonctionne de manière similaire à java.util.concurrent.BlockingQueue. Les mêmes méthodes d'insertion et de retrait avec des délais d'attente pour que l'insertion ou le retrait devienne possible sont fournies. Cependant, l'interface offre également la flexibilité d'un deque. Les insertions et les retraits peuvent avoir lieu aux deux extrémités. La fonction de blocage est combinée avec la fonction deque.
Définir les interfaces
L'interface java.util.Set de Java définit l'ensemble. Un ensemble ne peut pas contenir d'éléments en double. De plus, l'ensemble n'a pas d'ordre défini. En tant que tels, les éléments ne peuvent pas être trouvés par index. Set est implémenté par java.util.HashSet, java.util.LinkedHashSet et java.util.TreeSet. HashSet utilise une table de hachage. Plus précisément, il utilise un java.util.HashMap pour stocker les hachages et les éléments et pour éviter les doublons. java.util.LinkedHashSet étend cela en créant une liste doublement liée qui lie tous les éléments par leur ordre d'insertion. Cela garantit que l'ordre d'itération sur l'ensemble est prévisible. java.util.TreeSet utilise un arbre rouge-noir implémenté par un java.util.TreeMap. L'arbre rouge-noir s'assure qu'il n'y a pas de doublons. De plus, il permet à TreeSet d'implémenter java.util.SortedSet.
L'interface java.util.Set est étendue par l'interface java.util.SortedSet. Contrairement à un ensemble normal, les éléments d'un ensemble trié sont triés, soit par la méthode compareTo() de l'élément, soit par une méthode fournie au constructeur de l'ensemble trié. Les premier et dernier éléments de l'ensemble trié peuvent être récupérés et des sous-ensembles peuvent être créés via des valeurs minimales et maximales, ainsi qu'un début ou une fin au début ou à la fin de l'ensemble trié. L'interface SortedSet est implémentée par java.util.TreeSet.
java.util.SortedSet est encore étendu via l'interface java.util.NavigableSet. C'est similaire à SortedSet, mais il existe quelques méthodes supplémentaires. Les méthodes floor(), Ceiling(), lower() et upper() trouvent un élément dans l'ensemble qui est proche du paramètre. De plus, un itérateur descendant sur les éléments de l'ensemble est fourni. Comme avec SortedSet, java.util.TreeSet implémente NavigableSet.
Interfaces cartographiques
Les cartes sont définies par l'interface java.util.Map en Java. Les cartes sont des structures de données simples qui associent une clé à un élément. Cela permet à la carte d'être très flexible. Si la clé est le code de hachage de l'élément, la carte est essentiellement un ensemble. S'il ne s'agit que d'un nombre croissant, cela devient une liste. Les cartes sont implémentées par java.util.HashMap, java.util.LinkedHashMap et java.util.TreeMap. HashMap utilise une table de hachage . Les hachages des clés sont utilisés pour trouver les éléments dans différents buckets. LinkedHashMap étend cela en créant une liste doublement liée entre les éléments, leur permettant d'être accessibles dans l'ordre dans lequel ils ont été insérés dans la carte. TreeMap, contrairement à HashMap et LinkedHashMap, utilise un arbre rouge-noir. Les clés sont utilisées comme valeurs pour les nœuds de l'arborescence, et les nœuds pointent vers les éléments de la carte.
L'interface java.util.Map est étendue par sa sous-interface, java.util.SortedMap. Cette interface définit une carte qui est triée par les clés fournies. En utilisant, encore une fois, la méthode compareTo() ou une méthode fournie dans le constructeur de la carte triée, les paires clé-élément sont triées par les clés. Les première et dernière touches de la carte peuvent être appelées. De plus, des sous-cartes peuvent être créées à partir de clés minimales et maximales. SortedMap est implémenté par java.util.TreeMap.
L'interface java.util.NavigableMap étend java.util.SortedMap de diverses manières. Des méthodes peuvent être appelées pour trouver la clé ou l'entrée de carte la plus proche de la clé donnée dans les deux sens. La carte peut également être inversée et un itérateur dans l'ordre inverse peut être généré à partir de celle-ci. Il est implémenté par java.util.TreeMap.
Extensions du framework de collections Java
Le framework de collections Java est étendu par la bibliothèque Apache Commons Collections, qui ajoute des types de collection tels qu'un sac et une carte bidirectionnelle, ainsi que des utilitaires pour créer des unions et des intersections.
Google a publié ses propres bibliothèques de collections dans le cadre des bibliothèques de goyave .