Le début du chemin
Aujourd'hui, je voudrais parler d'un sujet aussi intéressant que le «
Java Collections Framework » ou, en termes simples, des collections. La majeure partie du travail du code consiste à traiter les données sous une forme ou une autre. Obtenez une liste d'utilisateurs, obtenez une liste d'adresses, etc. Triez-les d’une manière ou d’une autre, effectuez une recherche, comparez-les. C'est pourquoi la connaissance des collections est considérée comme une compétence essentielle. C'est pourquoi je veux en parler. De plus, l'une des questions les plus courantes lors des entretiens avec les développeurs Java concerne les collections. Par exemple, « dessinez une hiérarchie de collections ». Le compilateur en ligne nous aidera dans notre démarche. Par exemple, vous pouvez utiliser " Tutorialspoint
Online Java Compiler " ou
Repl.it. Le chemin pour connaître toutes les structures de données commence par les variables ordinaires (Variables). Sur le site Web d'Oracle, divers sujets sont représentés sous forme de « chemins » ou de sentiers. Ainsi, le chemin pour découvrir Java s'appelle «
Trail : Apprendre le langage Java : Table des matières ». Et les bases du langage (c'est-à-dire les bases du langage) commencent par les variables. Par conséquent, écrivons un code simple :
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
C'est bon en tout, sauf qu'on comprend que ce code n'est bon et beau que pour une variable. Que faire s'il y en a plusieurs ? Les tableaux ont été inventés pour stocker des données d'un seul type. Dans le même Trail d'Oracle, il existe une section distincte dédiée aux tableaux. Cette section s'appelle : "
Tableaux ". Travailler avec des tableaux est également assez simple :
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
Les tableaux résolvent le problème du stockage de plusieurs valeurs au même endroit. Mais cela impose une limitation : la taille du tableau est constante. Si, comme dans l’exemple, nous disons que taille = 2, alors elle est égale à deux. C'est tout. Si nous voulons un tableau plus grand, nous devons créer une nouvelle instance. De plus, trouver un élément est également une tâche délicate pour un tableau. Il existe une méthode
Arrays.binarySearch, mais cette recherche ne fonctionne que sur un tableau trié (pour un tableau non trié, le résultat est indéfini ou simplement imprévisible). Autrement dit, la recherche nous obligera à trier à chaque fois. La suppression efface également simplement la valeur. Par conséquent, nous ne savons toujours pas combien de données se trouvent réellement dans le tableau, nous savons seulement combien de cellules se trouvent dans le tableau. Pour rafraîchir vos connaissances sur les tableaux :
Et suite au développement du langage Java, le Java Collections Framework est apparu dans JDK 1.2, dont nous parlerons aujourd'hui.
Collection
Commencez à chiffrer dès le début. Pourquoi des collections ? Le terme lui-même vient de choses comme « théorie des types » et « types de données abstraits ». Mais si vous ne regardez pas les questions élevées, alors lorsque nous avons plusieurs choses, nous pouvons les appeler un « ensemble de choses ». Ceux qui collectionnent des objets. En général, le mot recueillir lui-même vient du lat. collectio "rassembler, collectionner". Autrement dit, une collection est une collection de quelque chose, un conteneur pour certains éléments. Nous avons donc une collection d’éléments. Ce que nous pourrions vouloir en faire :
Comme vous pouvez le constater, nous pouvons vouloir des choses assez logiques. Nous comprenons également que nous pouvons vouloir faire quelque chose avec plusieurs collections :
En conséquence, les développeurs Java ont écrit l'interface java.util.Collection pour décrire ce comportement général pour toutes les collections . L’interface Collection est l’endroit où proviennent toutes les collections. La collection est une idée, c'est une idée de la façon dont toutes les collections devraient se comporter. Par conséquent, le terme « Collection » est exprimé comme une interface. Naturellement, une interface a besoin d’implémentations. L'interface
java.util.Collectiona une classe abstraite
AbstractCollection, c'est-à-dire une « collection abstraite », qui représente le squelette d'autres implémentations (comme écrit dans le JavaDoc au-dessus de la classe
java.util.AbstractCollection). En parlant de collections, revenons en arrière et rappelons-nous que nous voulons les parcourir. Cela signifie que nous voulons parcourir les éléments un par un. C'est une notion très importante. L'interface est donc
Collectionhéritée de
Iterable. C'est très important parce que... premièrement, tout ce qui est Iterable doit pouvoir renvoyer un Iterator en fonction de son contenu. Et deuxièmement, tout ce qui Iterable peut être utilisé en boucle
for-each-loop. Et c'est à l'aide d'un itérateur
AbstractCollectionque des méthodes telles que
contains,
toArray, sont implémentées
remove. Et le chemin vers la compréhension des collections commence par l'une des structures de données les plus courantes - une liste, c'est-à-dire
List.
Listes
Ainsi, les listes occupent une place importante dans la hiérarchie des collections :
Comme nous pouvons le voir, les listes implémentent l' interface
java.util.List . Les listes expriment que nous avons une collection d’éléments disposés dans un certain ordre les uns après les autres. Chaque élément possède un index (comme dans un tableau). Généralement, une liste permet d'avoir des éléments ayant la même valeur. Comme nous l'avons dit plus haut,
Listil connaît l'index de l'élément. Cela vous permet d'obtenir (
get) un élément par index ou de définir une valeur pour un index spécifique (
set). Les méthodes de collection
add,
addAll,
removepermettent de spécifier l'index à partir duquel les exécuter. De plus, y
Listpossède sa propre version d'un itérateur appelé
ListIterator. Cet itérateur connaît l'index de l'élément, il peut donc itérer non seulement vers l'avant, mais aussi vers l'arrière. Il peut même être créé à partir d’un endroit précis de la collection. Parmi toutes les implémentations, il y en a deux les plus couramment utilisées :
ArrayListet
LinkedList. Premièrement,
ArrayListil s'agit d'une liste (
List) basée sur un tableau (
Array). Cela vous permet d'obtenir un "accès aléatoire"
aux éléments. L'accès aléatoire est la possibilité de récupérer immédiatement un élément par index, plutôt que de parcourir tous les éléments jusqu'à ce que nous trouvions l'élément avec l'index souhaité. C'est le tableau comme base qui permet d'y parvenir. Au contraire,
LinkedListil s'agit d'une liste chaînée. Chaque entrée d'une liste chaînée est représentée sous la forme
Entry, qui stocke les données elles-mêmes, ainsi qu'un lien vers la suivante (suivante) et la précédente (précédente)
Entry. Implémente ainsi
LinkedList"l'accès séquentiel
" . Il est clair que pour trouver le 5ème élément il faudra passer du premier élément au dernier, car nous n'avons pas d'accès direct au cinquième élément. On ne peut y accéder qu'à partir du 4ème élément. La différence dans leur concept est donnée ci-dessous :
Au travail, comme vous le comprenez, il y a aussi une différence. Par exemple, ajouter des éléments. Les
LinkedListéléments sont simplement reliés comme les maillons d’une chaîne. Mais
ArrayListil stocke les éléments dans un tableau. Et un tableau, comme nous le savons, ne peut pas changer de taille. Comment ça marche alors
ArrayList? Et cela fonctionne très simplement. Lorsque l'espace dans le tableau est épuisé, il augmente de 1,5 fois. Voici le code du zoom :
int newCapacity = oldCapacity + (oldCapacity >> 1); Une autre différence de fonctionnement réside dans tout décalage des éléments. Par exemple, lors de l'ajout ou de la suppression d'éléments au milieu. Pour supprimer d'
LinkedListun élément, supprimez simplement les références à cet élément. Dans le cas de ,
ArrayListon est obligé de décaler les éléments à chaque fois en utilisant le
System.arraycopy. Ainsi, plus il y a d’éléments, plus il faudra effectuer d’actions. Une description plus détaillée peut être trouvée dans ces articles :
Après avoir examiné ArrayList, on ne peut s'empêcher de se souvenir de son « prédécesseur », la classe
java.util.Vector . Cela diffère
Vectoren
ArrayListce que les méthodes de travail avec la collection (ajout, suppression, etc.) sont synchronisées. Autrement dit, si un thread (
Thread) ajoute des éléments, alors les autres threads attendront que le premier thread termine son travail. Étant donné que la sécurité des threads n'est souvent pas requise, il est recommandé d'utiliser la classe dans de tels cas
ArrayList, comme indiqué explicitement dans le JavaDoc de la classe
Vector. De plus,
Vectorsa taille augmente non pas de 1,5 fois,
ArrayListmais de 2 fois. Sinon, le comportement est le même :
Vectorle stockage des éléments sous forme de tableau est masqué et l'ajout/suppression d'éléments a les mêmes conséquences que dans
ArrayList. En fait,
Vectornous nous en souvenons pour une raison. Si nous regardons dans la Javadoc, nous verrons dans "Direct Known Subclasses" une structure telle que
java.util.Stack . La pile est une structure intéressante qui est une
last-in-first-outstructure LIFO (dernier entré, premier sorti). Stack traduit de l'anglais est une pile (comme une pile de livres, par exemple). La pile implémente des méthodes supplémentaires :
peek(look, look),
pop(push),
push(push). La méthode
peekse traduit par regarder (par exemple,
jeter un œil à l'intérieur du sac est traduit par «
regarder à l'intérieur du sac », et
jeter un coup d'œil à travers le trou de la serrure est traduit par «
jeter un coup d'œil à travers le trou de la serrure »). Cette méthode vous permet de regarder le « haut » de la pile, c'est-à-dire récupère le dernier élément sans le supprimer (c'est-à-dire sans le supprimer) de la pile. La méthode
pushpousse (ajoute) un nouvel élément sur la pile et le renvoie, et la méthode element
poppousse (supprime) et renvoie celui supprimé. Dans les trois cas (c'est-à-dire peek, pop et push), nous travaillons uniquement avec le dernier élément (c'est-à-dire le « haut de la pile »). C'est la principale caractéristique de la structure de la pile. À propos, il existe une tâche intéressante pour comprendre les piles, décrite dans le livre "A Programmer's Career" (Cracking Coding Interview). Il existe une tâche intéressante où, en utilisant la structure "pile" (LIFO), vous devez implémenter la "file d'attente" » (FIFO). Ça devrait ressembler à ça:
Une analyse de cette tâche peut être trouvée ici : "
Implémenter une file d'attente à l'aide de piles - La file d'attente ADT (" Implémenter une file d'attente à l'aide de piles " sur LeetCode) ". Nous passons donc en douceur à une nouvelle structure de données : une file d'attente.
File d'attente
Une file d'attente est une structure qui nous est familière de la vie. Files d'attente dans les magasins, chez les médecins. Celui qui est arrivé en premier (First In) sera le premier à quitter la file d'attente (First Out). En Java, une file d'attente est représentée par l' interface
java.util.Queue . Selon le Javadoc de la file d'attente, la file d'attente ajoute les méthodes suivantes :
Comme vous pouvez le voir, il existe des méthodes de commande (le fait de ne pas les exécuter comporte une exception) et il existe des méthodes de requête (l'impossibilité de les exécuter n'entraîne pas d'erreurs). Il est également possible de récupérer l'élément sans le supprimer (peek ou élément). L'interface de file d'attente a également un successeur utile -
Deque . C'est ce qu'on appelle la « file d'attente bidirectionnelle ». Autrement dit, une telle file d'attente vous permet d'utiliser cette structure dès le début et depuis la fin. La documentation indique que "Deques peut également être utilisé comme piles LIFO (Last-In-First-Out). Cette interface doit être utilisée de préférence à l'ancienne classe Stack.", c'est-à-dire qu'il est recommandé d'utiliser les implémentations Deque au lieu de Empiler. Le Javadoc montre quelles méthodes l'interface Deque décrit :
Voyons quelles sont les implémentations disponibles. Et nous verrons un fait intéressant - LinkedList est entré dans le camp de la file d'attente) Autrement dit, LinkedList implémente à la fois
List, et
Deque. Mais il existe aussi des « files d'attente uniquement », par exemple
PriorityQueue. On ne se souvient pas souvent d'elle, mais en vain. Premièrement, vous ne pouvez pas utiliser d'"objets non comparables" dans cette file d'attente, c'est-à-dire soit Comparator doit être spécifié, soit tous les objets doivent être comparables. Deuxièmement, "cette implémentation fournit un temps O(log(n)) pour les méthodes de mise en file d'attente et de retrait de la file d'attente". La complexité logarithmique est là pour une raison. Implémentation de PriorityQueue basée sur le tas. Le Javadoc dit : "File d'attente prioritaire représentée comme un tas binaire équilibré". Le stockage lui-même est un tableau ordinaire. Qui grandit quand c'est nécessaire. Lorsque le tas est petit, il augmente 2 fois. Et puis de 50 %. Commentaire du code : "Doublez la taille si petit ; sinon augmentez de 50 %". La file d'attente prioritaire et le tas binaire sont un sujet distinct. Alors pour plus d'informations :
En tant qu'implémentation,
java.util.Dequevous pouvez utiliser la classe
java.util.ArrayDeque . Autrement dit, les listes peuvent être implémentées à l'aide d'une liste chaînée et d'un tableau, et les files d'attente peuvent également être implémentées à l'aide d'un tableau ou d'une liste chaînée. Les interfaces
Queueet
Dequeont des descendants représentant la « file d'attente de blocage » :
BlockingQueueet
BlockingDeque. Voici le changement d'interface par rapport aux files d'attente classiques :
Examinons quelques exemples de files d'attente bloquantes. Mais ils sont intéressants. Par exemple, BlockingQueue est implémenté par :
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Mais
BlockingDequeils implémentent tout à partir des Collection Frameworks standard
LinkedBlockingDeque. Chaque file d'attente fait l'objet d'une revue distincte. Et dans le cadre de cette revue, nous décrirons la hiérarchie des classes non seulement avec
List, mais aussi avec
Queue:
Comme nous pouvons le voir sur le diagramme, les interfaces et les classes du Java Collections Framework sont étroitement liées. Ajoutons une autre branche de la hiérarchie -
Set.
Ensemble
Set– traduit par « ensemble ». Elle diffère d'une file d'attente et d'une liste
Setpar sa plus grande abstraction sur le stockage des éléments.
Set- comme un sac d'objets, où l'on ne sait pas comment se trouvent les objets et dans quel ordre ils sont disposés. En Java, un tel ensemble est représenté par l' interface
java.util.Set . Comme le dit la documentation,
Setil s'agit d'une "collection qui ne contient aucun élément en double". Fait intéressant, l'interface elle-même
Setn'ajoute pas de nouvelles méthodes à l'interface
Collection, mais clarifie uniquement les exigences (sur ce qui ne doit pas contenir de doublons). De plus, de la description précédente, il s'ensuit que vous ne pouvez pas simplement
Seten extraire un élément. L'itérateur est utilisé pour obtenir des éléments.
Setest associé à plusieurs autres interfaces. Le premier est
SortedSet. Comme son nom l'indique,
SortedSetcela indique qu'un tel ensemble est trié et que, par conséquent, les éléments implémentent l'interface
Comparableou sont spécifiés
Comparator. De plus,
SortedSetil propose plusieurs méthodes intéressantes :
De plus, il existe des méthodes
first(plus petit élément par valeur) et
last(plus grand élément par valeur). Il
SortedSety a un héritier -
NavigableSet. Le but de cette interface est de décrire les méthodes de navigation nécessaires pour identifier plus précisément les éléments appropriés. Une chose intéressante est
NavigableSetqu'il ajoute à l'itérateur habituel (qui va du plus petit au plus grand) un itérateur pour l'ordre inverse -
descendingIterator. De plus,
NavigableSetil permet d'utiliser la méthode
descendingSetpour obtenir une vue de soi (View), dans laquelle les éléments sont dans l'ordre inverse. Ceci est appelé
Viewparce que grâce à l'élément résultant, vous pouvez modifier les éléments de l'original
Set. Autrement dit, il s’agit essentiellement d’une représentation des données originales d’une manière différente, et non d’une copie de celles-ci. Fait intéressant,
NavigableSetcomme
Queue, peut gérer des éléments
pollFirst(minimaux) et
pollLast(maximaux). Autrement dit, il récupère cet élément et le supprime de l'ensemble. Quels types d’implémentations existe-t-il ? Premièrement, l'implémentation la plus connue est basée sur un code de hachage -
HashSet . Une autre implémentation tout aussi connue est basée sur un arbre rouge-noir -
TreeSet . Complétons notre schéma :
Au sein des collections, reste à démêler la hiérarchie : les ermites. Ce qui, à première vue, se démarque -
java.util.Map.
Plans
Les cartes sont une structure de données dans laquelle les données sont stockées par clé. Par exemple, la clé peut être un identifiant ou un code de ville. Et c'est par cette clé que les données seront recherchées. Il est intéressant de noter que les cartes sont affichées séparément. Selon les développeurs (voir «
FAQ sur la conception de l'API des collections Java »), le mappage clé-valeur n'est pas une collection. Et les cartes peuvent plus rapidement être considérées comme une collection de clés, une collection de valeurs, une collection de paires clé-valeur. C'est un animal tellement intéressant. Quelles méthodes les cartes proposent-elles ? Regardons l'interface API Java
java.util.Map . Parce que Puisque les cartes ne sont pas des collections (elles n’héritent pas des collections), elles ne contiennent pas de fichier
contains. Et c'est logique. Une carte se compose de clés et de valeurs. Lequel de ces éléments la méthode doit-elle vérifier
containset comment ne pas se tromper ? Par conséquent, l'interface
Mapa deux versions différentes :
containsKey(contient une clé) et
containsValue(contient une valeur). Son utilisation
keySetpermet d'obtenir un jeu de clés (le même
Set). Et en utilisant la méthode,
valuesnous pouvons obtenir une collection de valeurs sur la carte. Les clés de la carte sont uniques, ce qui est souligné par la structure des données
Set. Les valeurs peuvent être répétées, ce qui est souligné par la structure des données Collection. De plus, en utilisant la méthode,
entrySetnous pouvons obtenir un ensemble de paires clé-valeur. Vous pouvez en savoir plus sur les implémentations de cartes disponibles dans les analyses les plus détaillées :
J'aimerais aussi voir ce qui est
HashMaptrès similaire à
HashSet, et
TreeMapà
TreeSet. Ils ont même des interfaces similaires :
NavigableSetet
NavigableMap,
SortedSetet
SortedMap. Notre carte finale ressemblera donc à ceci :
On peut terminer par le fait intéressant que la collection
Setutilise en interne
Map, où les valeurs ajoutées sont des clés, et la valeur est la même partout. C'est intéressant car il
Mapne s'agit pas d'une collection et de return
Set, qui est une collection mais qui est en fait implémentée en tant que
Map. Un peu surréaliste, mais c'est comme ça que ça s'est passé)
Conclusion
La bonne nouvelle est que cela met fin à cet examen. La mauvaise nouvelle est qu’il s’agit d’un article très critique. Chaque implémentation de chacune des collections mérite un article séparé, et aussi pour chaque algorithme caché à nos yeux. Mais le but de cette revue est de rappeler de quoi il s’agit et quelles sont les connexions entre les interfaces. J'espère qu'après une lecture réfléchie, vous pourrez dessiner de mémoire un schéma des collections.
Bon, comme d'habitude, quelques liens :
#Viacheslav
GO TO FULL VERSION