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

Bonjour! Combien d’heures faut-il pour devenir maître dans quelque chose ? J’ai souvent entendu quelque chose comme : « Pour devenir maître en quoi que ce soit, il faut y consacrer 10 000 heures ». Un chiffre effrayant, n'est-ce pas ? Cependant, je me demande si c'est vrai ? Et j'essaie constamment de comprendre combien d'heures j'ai déjà investies dans la maîtrise de l'art de la programmation. Et lorsque je franchirai ces 10 000 heures tant convoitées et que je deviendrai un maître, ressentirai-je cette différence ? Ou les ai-je déjà enjambés il y a longtemps sans m'en rendre compte ? D’une manière ou d’une autre, pour devenir programmeur, vous n’avez pas besoin d’investir autant de temps. L’essentiel est de l’utiliser à bon escient. Votre objectif principal est de réussir l’entretien. Et lors des entretiens avec les nouveaux arrivants, la première chose qu'ils demandent est la théorie, il faut donc être fort dans ce domaine. En fait, lors de la préparation de l'entretien, votre tâche est de découvrir toutes vos lacunes dans la théorie de base d'un développeur Java et de les combler de connaissances. Et aujourd'hui, je vais vous aider dans cette affaire, car je suis ici pour continuer à analyser les questions les plus populaires. Alors continuons !

89. En quoi ArrayList est-il différent de LinkedList ?

C'est l'une des questions les plus populaires avec la question sur la structure interne de HashMap . Pas un seul entretien n'est complet sans cela, et par conséquent, la réponse devrait « rebondir sur vos dents ». En plus des noms évidents - différents - ils diffèrent par leur structure interne. Auparavant, nous avons examiné la structure interne d' ArrayList et de LinkedList , je n'entrerai donc pas dans les détails de leur implémentation. Permettez-moi juste de vous rappeler qu'ArrayList est implémenté sur la base d'un tableau interne, qui est augmenté selon les besoins selon la formule :

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

Dans le même temps, LinkedList est implémenté sur la base d'une liste interne doublement liée, c'est-à-dire que chaque élément a un lien vers le précédent et le suivant, à l'exclusion des valeurs qui sont le début/la fin de la liste. Les gens aiment poser cette question sous le format : « Quel est le meilleur : ArrayList ou LinkedList ? », en espérant vous surprendre. Après tout, si vous indiquez l’une d’entre elles comme réponse, ce sera la mauvaise réponse. Au lieu de cela, vous devez clarifier de quelle situation spécifique vous parlez : accès à un index ou insertion au milieu d'une liste. En fonction de la réponse, vous pourrez expliquer votre choix. J'ai déjà décrit comment ArrayList et LinkedList fonctionnent dans une situation ou une autre. Résumons cela en les mettant sur la même page pour comparaison : Ajouter un élément (ajouter)

1. L'ajout d'un nouvel élément sans spécifier d'index comme emplacement se produira automatiquement à la fin des deux listes. Dans une LinkedList, le nouvel élément deviendra la nouvelle queue (seule la réécriture de la paire de liens se produit - complexité algorithmique O(1) ).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

En bout de ligne : dans LinkedList, la complexité algorithmique variera de O(1) à O(n/2) . Autrement dit, plus l'insertion est proche de la fin ou du début de la liste, plus elle est rapide. En même temps, pour ArrayList cela va de O(1) à O(n) : plus l’insertion est proche de la fin de la liste, plus elle est rapide. Définition d'un élément (set) Cette opération écrit un élément à la position spécifiée dans la liste, en écrasant le précédent, le cas échéant. Dans LinkedList, cette opération sera similaire à l'ajout, car La plus grande difficulté ici est de trouver l’élément. La réécriture d'un élément se fera en réécrivant une paire de liens, donc ici aussi la complexité algorithmique variera de O(1) à O(n/2) selon la distance de la position à la fin ou au début de la liste. À ce moment-là, la cellule requise sera trouvée dans ArrayList pour cette opération d'indexation et un nouvel élément y sera écrit. La recherche d'index, comme cette opération, a une complexité algorithmique de O(1) . Prendre un élément par index (get) Dans LinkedList, la prise d'un élément se fera selon le même principe que la recherche d'autres opérations - en fonction de la distance par rapport à la fin ou au début, c'est-à-dire de O(1) à O(n/2) . Dans ArrayList , comme je l'ai dit plus tôt, trouver un élément dans un tableau par index a une complexité O(1) . Supprimer un élément par index (supprimer) Pour LinkedList, son principe de fonctionnement fonctionne également ici : d'abord l'élément est trouvé, puis les liens sont écrasés - les voisins de l'élément commencent à se référer les uns aux autres, perdant les références à cet élément, ce qui sera ensuite supprimé par le garbage collector. Autrement dit, la complexité algorithmique est toujours la même - de O(1) à O(n/2) . Pour ArrayList , cette opération est plus similaire à l'opération d'ajout d'un nouvel élément (add). Tout d'abord, l'élément requis est trouvé - O(1) , puis il est supprimé et tous les éléments qui se trouvaient à sa droite sont déplacés d'une unité vers la gauche pour combler l'espace résultant. L'opération de suppression aura la même complexité algorithmique que l'opération d'ajout - de O(1) à O(n) . Plus la suppression est proche de la fin de la liste, moins elle est complexe sur le plan algorithmique. En fait, c'étaient toutes les opérations principales. Permettez-moi de vous rappeler : lorsque vous comparez ces deux listes, vous devez clarifier de quelle situation spécifique nous parlons, et vous pourrez alors répondre sans ambiguïté à la question posée.

90. En quoi ArrayList est-il différent de HashSet ?

Si ArrayList et LinkedList pouvaient être comparés en termes d'opérations - ce qui est mieux - alors il n'est pas si facile de comparer ArrayList avec HashSet , car ce sont des collections complètement différentes. Vous pouvez comparer un plat sucré avec un autre, mais cela fonctionnera avec un plat de viande - ils sont trop différents. Cependant, je vais essayer de donner quelques différences entre eux :

• ArrayList implémente l' interface List , tandis que HashSet implémente l' interface Set ;

• Dans ArrayList, l'accès est possible par index d'élément : l' opération get a une complexité algorithmique de O(1) , et dans HashSet, l'élément requis ne peut être obtenu que par force brute, et cela va de O(1) à O(n) ;

• ArrayList autorise les éléments en double. Dans un HashSet, tous les éléments sont uniques : ajouter un élément à un HashSet dont l'analogue est déjà présent dans la collection ne fonctionnera pas (les doublons sont vérifiés à l'aide du hashcode, d'où le nom de cette collection) ;

• ArrayList est implémenté à l'aide d'un tableau interne et HashSet est implémenté à l'aide d'un HashMap interne ;

• Un ArrayList conserve l'ordre d'insertion des éléments, tandis qu'un HashSet est un ensemble non ordonné et ne conserve pas l'ordre des éléments ;

• ArrayList autorise n'importe quel nombre de valeurs vides (nulles), une seule valeur nulle peut être insérée dans un HashSet (après tout, l'unicité des éléments).

91. Pourquoi existe-t-il une telle variété d'implémentations de tableaux dynamiques en Java ?

Eh bien, c'est plutôt une question philosophique. Eh bien, pourquoi proposent-ils autant de nouvelles technologies différentes ? Pour le confort. En fait, c’est la même chose avec un grand nombre d’implémentations de tableaux dynamiques. Aucun d’entre eux ne peut être qualifié de meilleur ou d’idéal. Chacun a un avantage dans une situation spécifique. Et notre tâche est de connaître leurs différences, leurs forces/faiblesses : afin de pouvoir utiliser celle qui convient le mieux dans la bonne situation.

92. Pourquoi existe-t-il une telle variété d'implémentations de stockage clé-valeur en Java ?

Ici, la situation est la même que pour les implémentations de tableaux dynamiques. Il n’y a pas de meilleur : chacun a ses forces et ses faiblesses. Et nous devons bien entendu tirer le meilleur parti de nos atouts. Exemple : le package concurrent, qui contient de nombreuses technologies multithread, possède ses propres collections Concurrent . Le même ConcurrentHashMap présente un avantage en termes de sécurité du travail multithread avec des données par rapport à un HashMap classique , mais dans un environnement non multithread, il perd en vitesse. Eh bien, les implémentations, qui ne sont pas les plus solides dans toutes les situations, cessent progressivement d'être utilisées. Exemple : Hashtable était initialement destiné à être un HashMap thread-safe , mais ConcurrentHashMap l'a surpassé dans un environnement multithread et Hashtable a finalement été oublié et n'est plus utilisé.

93. Comment trier une collection d'éléments ?

La première chose à dire est que la classe d'élément de collection doit implémenter l' interface Comparable et sa méthode compareTo . Ou vous avez besoin d'une classe qui implémente Comaprator avec sa méthode de comparaison . Vous pouvez en savoir plus à leur sujet dans cet article . Les deux méthodes spécifient comment comparer les objets d’un type donné. Lors du tri, cela est d’une importance cruciale, car vous devez comprendre le principe selon lequel les éléments peuvent être comparés. La principale façon de procéder consiste à implémenter Comparable , implémenté directement dans la classe que vous souhaitez trier. Dans le même temps, l’utilisation de Comparator est moins courante. Disons que vous utilisez une classe d'une bibliothèque qui n'a pas d' implémentation Comparable , mais vous devrez la trier d'une manière ou d'une autre. Sans pouvoir changer le code de cette classe (sauf en l'étendant), vous pouvez écrire une implémentation de Comparator , dans laquelle vous indiquez sur quel principe vous souhaitez comparer les objets de cette classe. Et encore un exemple. Disons que vous avez besoin de principes différents pour trier des objets du même type, vous écrivez donc plusieurs comparateurs que vous utilisez dans différentes situations. En règle générale, de nombreuses classes prêtes à l'emploi implémentent déjà l' interface Comparable - la même String . En fait, lorsque vous les utilisez, vous n’avez pas à vous soucier de la manière de les comparer. Il vous suffit de les prendre et de les utiliser. La première et la plus évidente consiste à utiliser une collection de type TreeSet ou TreeMap , qui stocke les éléments dans un ordre déjà trié en fonction du comparateur de classes d'éléments. N'oubliez pas que TreeMap trie les clés, mais pas les valeurs. Si vous utilisez l' implémentation Comparator au lieu de Comparable , vous devrez transmettre son objet au constructeur de collection lors de la création :

TreeSet treeSet = new TreeSet(customComparator);

Mais que se passe-t-il si vous avez un autre type de collection ? Comment faire le tri ? Dans ce cas, la deuxième méthode de la classe utilitaire Collections convient - la méthode sort() . C'est statique, donc tout ce dont vous avez besoin est le nom de la classe et une méthode à laquelle la liste requise est transmise. Par exemple:

Collections.sort(someList);

Si vous n'utilisez pas Comparable , mais plutôt une implémentation de Comparator , vous devez le passer comme deuxième paramètre :

Collections.sort(someList, customComparator);

En conséquence, l'ordre interne des éléments de la liste passée changera : elle sera triée selon le comparateur d'éléments. Je note que la liste d'éléments transférée doit être mutable, c'est-à-dire mutable, sinon la méthode ne fonctionnera pas et une UnsupportedOperationException sera levée . Comme troisième méthode, vous pouvez utiliser l' opération de tri Stream , qui trie les éléments de la collection si l' implémentation Comparable est utilisée :

someList = someList.stream().sorted().collect(Collectors.toList());

si Comparateur :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

Vous pouvez en savoir plus sur Stream dans cet article . La quatrième méthode consiste à implémenter manuellement le tri, tel que le tri à bulles ou le tri par fusion .

Objet de classe. Égal à et HashCode

94. Donnez une brève description de l'objet de classe en Java

Dans la deuxième partie de l'analyse, nous avons déjà parlé des méthodes de la classe Object , et je vous rappelle que la classe Object est l'ancêtre de toutes les classes en Java. Il dispose de 11 méthodes qui, par conséquent, sont héritées par toutes les classes. Des informations sur les 11 méthodes peuvent être trouvées dans la deuxième partie de la discussion.

95. À quoi servent Equals et HashCode en Java ?

hashCode() est une méthode de la classe Object héritée par toutes les classes. Sa tâche est de générer un nombre qui représente un objet spécifique. Un exemple d'utilisation de cette méthode est son utilisation dans un HashMap sur un objet clé pour déterminer davantage le hashcode local, qui déterminera la cellule du tableau interne (bucket) dans laquelle la paire sera stockée. Nous avons parlé en détail du travail de HashMap dans la partie 9 de l'analyse , nous ne nous attarderons donc pas trop là-dessus. De plus, en règle générale, cette méthode est utilisée dans la méthode equals() comme l'un de ses principaux outils pour déterminer l'identité des objets. equals() est une méthode de la classe Object dont le travail consiste à comparer des objets et à déterminer s'ils sont égaux ou non. Cette méthode est utilisée partout où nous devons comparer des objets, car la comparaison habituelle utilisant == ne convient pas aux objets, car compare uniquement les liens vers eux.

96. Parlez-nous du contrat entre Equals et HashCode en Java ?

La première chose que je dirai est que pour que les méthodes equals() et hashCode() fonctionnent correctement , elles doivent être correctement remplacées. Après cela, ils doivent suivre les règles :

• les objets identiques pour lesquels la comparaison via égal renvoie vrai doivent avoir des codes de hachage identiques ;
• les objets avec les mêmes codes de hachage peuvent ne pas toujours être égaux.

À ce stade, nous ferons une pause jusqu’à la prochaine partie de l’analyse !