Analyse des questions et réponses des entretiens pour développeur Java. Partie 9

Feu d'artifice! Être programmeur n’est pas facile. Vous devez constamment apprendre, toujours apprendre quelque chose de nouveau. Mais, comme dans toute autre entreprise, le plus difficile est de se lancer, de faire le premier pas vers son objectif. Et puisque vous êtes assis sur ce site et que vous lisez cet article, vous avez franchi la première étape. Cela signifie que vous devez maintenant avancer délibérément vers votre objectif, sans ralentir ni vous arrêter en cours de route. Si je comprends bien, votre objectif est de devenir développeur Java ou d'approfondir vos connaissances si vous en êtes un. Si tel est le cas, alors vous êtes au bon endroit, car nous continuerons d'analyser une liste complète de plus de 250 questions d'entretien pour les développeurs Java. Nous allons continuer!

Collections

84. Parlez-nous des itérateurs et de leur utilisation

Les collections sont l'un des sujets favoris dans tout entretien avec un développeur Java, et lorsqu'ils parlent de la hiérarchie des collections, les candidats disent souvent que cela commence par l' interface Collection . Mais ce n'est pas vrai, car au-dessus de cette interface il y en a une autre - Iterable . Cette interface représente la méthode iterator() , qui vous permet d'appeler un objet Iterator pour la collection actuelle. Et quel est exactement cet objet Iterator ? Un itérateur est un objet qui offre la possibilité de se déplacer dans une collection et de parcourir des éléments sans que l'utilisateur ait besoin de connaître l'implémentation d'une collection particulière. C'est-à-dire qu'il s'agit d'une sorte de pointeur vers les éléments de la collection, qui, pour ainsi dire, regardent un certain endroit de celle-ci. L'itérateur a les méthodes suivantes :

• hasNext() - renvoie true s'il y a un élément situé après le pointeur (cette méthode permet de savoir si la fin de la collection a été atteinte) ;
• next() - renvoie l'élément suivant après le pointeur. S'il n'y en a pas, NoSuchElementException est levée . Autrement dit, avant d'utiliser cette méthode, il est préférable de s'assurer que l'élément existe - en utilisant hasNext() ;
• Remove() - supprime le dernier élément reçu de la collection à l'aide de la méthode next() . Si next() n'a jamais été appelé avant l'appel de remove() , une exception sera levée - IllegalStateException ;
• forEachRemaining(<Consumer>) - effectue l'action passée avec chaque élément de la collection (la méthode est apparue dans Java 8).

Voici un petit exemple d'itération dans une liste et de suppression de tous ses éléments à l'aide des méthodes d'itération décrites :

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

La console affichera : Cela signifie que la suppression des éléments a réussi. Une fois que nous avions un itérateur, nous pourrions utiliser une méthode pour imprimer tous les éléments à l’écran :

iterator.forEachRemaining(x -> System.out.print(x));

Mais après cela, l'itérateur deviendrait impropre à une utilisation ultérieure, car il parcourrait toute la liste et un itérateur normal ne dispose pas de méthodes de retour en arrière. Ici, nous abordons progressivement LinkedList , à savoir sa méthode listIterator() , qui renvoie un type d'itérateur modernisé - ListIterator . Outre les méthodes d'itération classiques (standard), celle-ci en comporte d'autres :

• add(<Element>) - insère un nouvel élément dans la liste ;
• hasPrevious() - renvoie true s'il y a un élément situé avant le pointeur (qu'il y ait un élément précédent) ;
• nextIndex() - renvoie l'index dans la liste de l'élément suivant après le pointeur ;
• previous() - renvoie l'élément précédent (jusqu'au pointeur) ;
• previousIndex() - renvoie l'index de l'élément précédent ;
• set(<Element>) - Remplace le dernier élément renvoyé par la méthode next() ou previous() .

Comme vous pouvez le constater, la fonctionnalité de cet itérateur est bien plus intéressante : il permet de se déplacer dans les deux sens et libère les mains lorsque l'on travaille avec des éléments. De plus, lorsque les gens parlent d’itérateurs, ils font parfois référence au modèle lui-même. Pour éviter d'avoir des ennuis et en parler de manière convaincante, lisez cet article sur le modèle Iterator .

85. Quelle est la hiérarchie de collection dans Java Collection Framework ?

Il existe deux hiérarchies de collections en Java. La première hiérarchie est la hiérarchie Collection elle-même avec la structure suivante : Elle est à son tour divisée en sous-collections suivantes :

• Set est une interface qui décrit une telle structure de données comme un ensemble contenant des éléments uniques (non répétitifs) non ordonnés. L'interface a des implémentations standard - TreeSet , HashSet et LinkedHashSet .
• List est une interface qui décrit une structure de données qui stocke une séquence ordonnée d'objets. Les instances contenues dans une liste peuvent être insérées et supprimées par leur index dans cette collection (analogue à un tableau, mais avec redimensionnement dynamique). L'interface a des implémentations standards - ArrayList , Vector ( considérées comme obsolètes et non réellement utilisées ) et LinkedList .
• La file d'attente est une interface qui décrit une structure de données qui stocke les éléments sous la forme d'une file d'attente qui suit la règle FIFO - First In First Out . L'interface a les implémentations standards suivantes : LinkedList (oui, elle implémente également Queue ) et PriotityQueue .

La deuxième hiérarchie de collections est Map , qui a la structure suivante : Dans cette collection, il n'y a pas de divisions en sous-collections (puisque la hiérarchie Map elle-même est quelque chose comme une sous-collection, mais séparée). Les implémentations de cartes standard sont Hashtable (considérée comme obsolète), LinkedHashMap et TreeMap . En fait, lorsqu'on l'interroge sur Collection , il s'agit généralement des deux hiérarchies.

86. Quelle est la structure interne d’une ArrayList ?

ArrayList est similaire à un tableau, mais avec la possibilité de se développer dynamiquement. Qu'est-ce que ça veut dire? Le fait est qu'ArrayList fonctionne sur la base d'un tableau régulier, à savoir qu'il stocke les éléments dans un tableau interne (sa taille par défaut est de 10 cellules). Lorsque le tableau interne est plein, un nouveau tableau est créé dont la taille est déterminée par la formule :

<размерТекущегоМассива> * 3 / 2  + 1

Autrement dit, si la taille de notre tableau est de 10, la taille du nouveau sera : 10 * 3 / 2 + 1 = 16. Ensuite, toutes les valeurs du premier (ancien) tableau y sont copiées à l'aide du méthode native System.arraycopy () et le premier tableau est supprimé. En fait, c'est ainsi que l'extensibilité dynamique d'ArrayList est implémentée . Regardons les méthodes ArrayList les plus utilisées : 1. add(<Elelement>) - ajoute un élément à la fin du tableau (jusqu'à la dernière cellule vide), et vérifie d'abord s'il y a de l'espace dans ce tableau. S'il n'y est pas, un nouveau tableau est créé dans lequel les éléments sont copiés. La complexité logarithmique de cette opération est O(1). Il existe une méthode similaire - add(<Index>,<Elelement>) . Il ajoute un élément non pas à la fin de la liste (tableau), mais à une cellule spécifique avec l'index fourni en argument. Dans ce cas, la complexité logarithmique différera selon l'endroit où elle est ajoutée :

• si c'était approximativement le début de la liste, la complexité logarithmique sera proche de O(N), car tous les éléments situés à droite du nouveau devront être déplacés d'une cellule vers la droite ;
• si l'élément est inséré au milieu - O(N/2) car nous devons déplacer seulement la moitié des éléments de la liste d’une cellule vers la droite.

Autrement dit, la complexité logarithmique de cette méthode va de O(N) à O(1) selon l'endroit où l'élément est inséré. 2. set(<Index>,<Elelement>) - écrit un élément à la position spécifiée dans la liste. S'il y a déjà un élément à cette position, l'écrase. La complexité logarithmique de cette opération est O(1), car il n'y a pas de décalage : seulement une recherche par index dans le tableau, qui, on s'en souvient, a une complexité de O(1), et l'écriture de l'élément. 3. remove(<index>) - suppression d'un élément par son index dans le tableau interne. Lors de la suppression d'un élément qui ne se trouve pas à la fin de la liste, vous devez déplacer tous les éléments à droite de celui-ci d'une cellule vers la gauche pour combler l'espace laissé après la suppression de l'élément. Par conséquent, la complexité logarithmique sera la même que celle de add(<Index>,<Elelement>) si l'élément était au milieu - O(N/2) - car vous devez décaler la moitié des éléments d'un vers la gauche. En conséquence, si c'était au début - O(N). Eh bien, si à la fin c’est O(1), il n’est pas nécessaire de déplacer quoi que ce soit. Pour ceux qui souhaitent approfondir ce sujet, je laisserai ce lien vers un article avec analyse de la classe ArrayList .

87. Quelle est la structure interne de LinkedList ?

Si ArrayList contient des éléments dans un tableau interne, alors LinkedList se présente sous la forme d'une liste doublement chaînée. Cela signifie que chaque élément contient un lien vers l'élément précédent ( previous ) et le suivant ( next ). Le premier élément n'a pas de lien vers le précédent (c'est le premier), mais il est considéré comme la tête de liste, et la LinkedList a un lien directement vers lui. Le dernier élément, en fait, n'a pas d'élément suivant, c'est la queue de la liste, et il existe donc un lien direct vers celui-ci dans la LinkedList elle-même . Par conséquent, la complexité logarithmique de l’accès à la tête ou à la queue d’une liste est O(1). Dans ArrayList, lorsque la liste s'agrandissait, le tableau interne augmentait, mais ici tout se passe plus simplement - lors de l'ajout d'un élément, quelques liens changent simplement. Examinons quelques-unes des méthodes LinkedlList les plus utilisées : 1. add(<Elelement>) - ajout à la fin de la liste, c'est-à-dire après le dernier élément (5), un lien vers le nouvel élément sera ajouté comme next . Le nouvel élément aura un lien vers le dernier (5) comme l'élément précédent . La complexité logarithmique d'une telle opération sera O(1), puisque seul un lien vers le dernier élément est nécessaire, et comme vous vous en souvenez, la queue a un lien direct depuis LinkedList et la complexité logarithmique pour y accéder est minime. 2. add(<Index>,<Elelement>) - ajout d'un élément par index. Lors de l'ajout d'un élément, par exemple, au milieu d'une liste, les éléments de la tête et de la queue (des deux côtés) sont d'abord itérés jusqu'à ce que l'emplacement souhaité soit trouvé. Si nous voulons insérer un élément entre le troisième et le quatrième (dans la figure ci-dessus), alors lors de la recherche du bon endroit, le lien suivant du troisième élément pointera déjà vers le nouveau. Pour le nouveau, le lien précédent pointera vers le troisième. Ainsi, le lien du quatrième élément - précédent - pointera déjà vers le nouvel élément, et le lien suivant du nouvel élément pointera vers le quatrième élément : La complexité logarithmique de cette méthode dépendra de l'index donné au nouvel élément :

• s'il est proche de la tête ou de la queue, il s'approchera de O(1), puisqu'il ne sera pas réellement nécessaire de parcourir les éléments ;
• s'il est proche du milieu, alors O(N/2) - les éléments de la tête et de la queue seront triés simultanément jusqu'à ce que l'élément requis soit trouvé.

3. set(<Index>,<Elelement>) - écrit un élément à la position spécifiée dans la liste. La complexité logarithmique de cette opération va de O(1) à O(N/2), encore une fois en fonction de la proximité de l'élément par rapport à la tête, à la queue ou au milieu. 4. remove(<index>) - supprime un élément de la liste, faisant essentiellement en sorte que l'élément qui précède celui qui est supprimé ( previous ) fasse référence à l'élément qui vient après celui qui est supprimé ( next ). Et vice versa : pour que l'élément qui vient après celui à supprimer fasse référence à celui qui précède celui à supprimer : Le résultat est un processus inverse de l'ajout par index ( add(<Index>,<Elelement>) ). Pour ceux qui souhaitent en savoir plus sur la structure interne de LinkedList , je recommande la lecture de cet article .

88. Quelle est la structure interne d’un HashMap ?

Peut-être l'une des questions les plus fréquemment posées lors d'un entretien avec un développeur Java. HashMap v fonctionne avec des paires clé-valeur . Comment sont-ils stockés dans le HashMapv lui-même ? À l’intérieur du HashMap se trouve un tableau de nœuds :

Node<K,V>[] table

Par défaut, la taille du tableau est de 16, et elle double à chaque fois qu'il est rempli d'éléments (lorsque LOAD_FACTOR est atteint - un certain pourcentage de plénitude, par défaut il est de 0,75 ). Chaque nœud stocke un hachage de la clé, une clé, une valeur et un lien vers l'élément suivant : En fait, « lien vers l'élément suivant » signifie que nous avons affaire à une liste à chaînage unique, où chaque élément contient un lien vers le prochain. Autrement dit, HashMap stocke les données dans un tableau de listes à lien unique. Mais je noterai tout de suite : lorsqu'une cellule du tableau a un lien vers une liste similaire à lien unique composée de plus d'un élément, ce n'est pas bon. Ce phénomène est appelé collision . Mais tout d’abord. Voyons comment une nouvelle paire est enregistrée à l'aide de la méthode put . Tout d’abord, le hachCode() de la clé est récupéré. Par conséquent, pour que hashmap fonctionne correctement , vous devez prendre des classes dans lesquelles cette méthode est remplacée en tant que clés. Ce code de hachage est ensuite utilisé dans la méthode interne - hash() - pour déterminer le nombre dans la taille du tableau . Ensuite, en utilisant le numéro reçu, on accède à une cellule spécifique du tableau . Nous avons ici deux cas :

1. La cellule est vide - la nouvelle valeur Node y est stockée .
2. La cellule n'est pas vide - la valeur des clés est comparée. S'ils sont égaux, la nouvelle valeur du nœud écrase l'ancienne, s'ils ne sont pas égaux, l'élément suivant est accédé et comparé à sa clé... Et ainsi de suite jusqu'à ce que la nouvelle valeur écrase une ancienne ou atteigne la fin du liste chaînée unique et y sera stockée comme dernier élément.

Lors de la recherche d'un élément par clé ( méthode get(<key>) ), le hashCode de la clé est calculé, puis sa valeur dans le tableau à l'aide de hash() , et en utilisant le nombre résultant, la cellule du tableau est trouvée , dans lequel la recherche est déjà effectuée en énumérant les nœuds et en comparant la clé du nœud souhaité avec la clé du nœud actuel. Les opérations dans Map, dans une situation idéale, ont une complexité algorithmique de O(1), car elles accèdent à un tableau, et comme vous vous en souvenez, quel que soit le nombre d'éléments, les opérations sur un tableau ont une complexité de O(1) . Mais c'est l'idéal. Lorsque la cellule du tableau utilisée n'est pas vide (2) et qu'il y a déjà quelques nœuds là-bas, la complexité algorithmique se transforme en O(N) linéaire, car il faut désormais parcourir les éléments avant de trouver la bonne place. Je ne peux m'empêcher de mentionner ceci : à partir de Java 8, si un nœud de liste mono-lié a plus de 8 éléments (collisions), il se transforme en un arbre binaire. Dans ce cas, la complexité algorithmique ne sera plus O(N), mais O(log(N)) - c'est une autre affaire, n'est-ce pas ? HashMap est un sujet important et les gens aiment poser des questions à ce sujet lors d'entretiens. Je vous conseille donc de le comprendre en détail (pour qu'il rebondisse sur vos dents). Personnellement, je n'ai pas eu d'entretien sans questions HashMap . Vous pouvez trouver une analyse approfondie de HashMap dans cet article . C'est tout pour aujourd'hui, à suivre...