Ce qu'ils pourraient demander lors d'un entretien : Structures de données en Java. Partie 2

PARTIE 1 Nous parlons maintenant de la base que tout développeur Java devrait connaître. À propos de ce savoir classique à partir duquel tout commence. Aujourd'hui, je voudrais aborder l'un des sujets fondamentaux de toute interview : les structures de données en Java . Alors, au lieu de tourner autour du pot, commençons. Découvrez la suite de la liste des questions qui pourraient vous être posées sur ce sujet lors d'un entretien.

6. Parlez-nous de la liste

List est une interface qui représente une structure ordonnée d’objets, appelée liste. Le « truc » de cette structure est que les éléments contenus dans la List peuvent être insérés, modifiés ou supprimés par index, c'est-à-dire l'identifiant interne de la List . En d’autres termes, index signifie : « combien d’éléments se trouvent au début de la liste ». Le premier élément List a l’index 0, le second a l’index 1, et ainsi de suite. Le cinquième élément est donc à quatre éléments du début de la liste. Comme mentionné ci-dessus, l'ordre dans lequel les éléments sont ajoutés à une liste est important. C'est pourquoi la structure des données est appelée liste . Nous listons les méthodes propres à cette structure qui visent à travailler avec des éléments par index :

• get - renvoie l'élément à la position spécifiée (par valeur d'index),
• supprimer - supprime l'élément à la position spécifiée,
• set - remplace l'élément à la position spécifiée par l'élément spécifié dans la méthode.

Les principales implémentations sont ArrayList et LinkedList . Nous en reparlerons un peu plus tard. Vector est une liste thread-safe, donc chaque méthode de cette classe est synchronisée. Mais gardez à l’esprit que si vous souhaitez sécuriser certaines actions de liste, vous allez synchroniser toute une séquence d’opérations. Et la synchronisation des opérations individuelles est à la fois moins sécurisée et beaucoup plus lente. Bien sûr, Vector dispose également d'un système de verrouillage, même si vous n'avez pas besoin du verrou. Par conséquent, cette classe est désormais considérée comme obsolète et n’est plus utilisée. À propos : ArrayList est similaire à Vector , mais n'utilise pas de verrouillage, il est donc utilisé partout. Stack est une sous-classe de la classe Vector avec un constructeur par défaut et toutes les méthodes de la classe Vector , plus quelques-unes des siennes (nous en reparlerons plus tard). À titre d'exemple, vous pouvez imaginer le processus comme une pile de dossiers contenant des documents. Vous placez un dossier en haut de la pile et vous ne pouvez prendre ces dossiers que dans l'ordre inverse, en commençant par le haut. En fait, il s'agit d'un mécanisme de type LIFO , c'est-à-dire Last In First Out , le dernier arrivé est le premier à partir. La pile implémente ses propres méthodes :

• push - ajoute l'élément transmis en haut de la pile ;
• peek - renvoie l'élément qui se trouve en haut de la pile ;
• pop - renvoie également l'élément qui se trouve en haut de la pile, mais le supprime ;
• vide - vérifie si la pile est vide - vrai ou non - faux ;
• search - recherche dans la pile un élément donné. Si un élément est trouvé, son numéro de séquence par rapport au haut de la pile est renvoyé. Si l'élément n'est pas trouvé, la valeur -1 est renvoyée.

Pour le moment, la sous-classe Stack n'est pas réellement utilisée en raison de sa simplicité et de son manque de flexibilité, mais vous pouvez néanmoins la rencontrer. Par exemple, lorsque vous recevez une erreur et que dans la console, vous voyez une pile de messages à ce sujet. Vous pouvez en savoir plus sur la pile et la file d'attente dans cet article .

7. Parlez-nous de la carte

Comme indiqué ci-dessus, une Map est une collection qui possède une structure distincte d'interfaces et de leurs implémentations. C'est distinct car ici les valeurs ne sont pas stockées une à la fois, mais dans une paire « clé-valeur ». Méthodes de base de la carte :

• put(K key, V value) - ajout d'un élément à la Map ;
• get(Object key) - recherche une valeur par clé ;
• containKey(Object key) — vérifie la carte pour la présence de cette clé ;
• containValue(Object value) - vérifie la carte pour la présence de cette valeur ;
• remove(Object key) - suppression d'une valeur par sa clé.

Comme vous pouvez le constater, la plupart des opérations fonctionnent à l'aide d'une clé. En règle générale, les objets immuables sont choisis comme clés . Un exemple typique de cet objet est String . Implémentations de cartes de base :

1. HashMap - conçu pour stocker des valeurs dans un ordre aléatoire, mais vous permet de rechercher rapidement des éléments cartographiques. Vous permet de spécifier une clé à l'aide du mot-clé null , mais pas plus d'une fois, car les paires avec les mêmes clés sont écrites les unes sur les autres. La condition principale est l'unicité des clés : les valeurs peuvent être répétées (il peut y avoir plusieurs valeurs nulles).
2. LinkedHashMap est un analogue de HashMap qui stocke les valeurs dans l'ordre dans lequel elles ont été ajoutées. En conséquence, comme LinkedList , il a un en-tête - la tête d'une liste doublement chaînée. Une fois initialisé, il pointe vers lui-même.

   LinkedHashMap a également un accessOrder qui spécifie comment les éléments seront accessibles lorsque l'itérateur est utilisé. Si accessOrder est faux, l'accès sera effectué dans l'ordre dans lequel les éléments ont été insérés. Si c'est vrai, les éléments seront dans l'ordre du dernier accès (le dernier élément accédé sera placé à la fin).

3. TreeMap est une carte qui trie les éléments par valeurs clés. Similaire à TreeSet , mais pour les paires basées sur des valeurs clés. Pour définir les règles de tri TreeMap , les clés doivent implémenter l'interface Comparable . Sinon, il devrait y avoir un comparateur orienté clé (celui qui est spécifié dans le constructeur TreeMap ), un TreeSet - implémenté avec un objet TreeMap à l'intérieur, dans lequel, en fait, toute la magie se produit.

   Vous pouvez en savoir plus sur le tri dans TreeMap à l'aide d'arbres rouge-noir dans l'article sur les fonctionnalités de TreeMap .

4. Hashtable est similaire à HashMap , mais ne permet pas de stocker des valeurs nulles sous forme de clés ou de valeurs. Il est soigneusement synchronisé d’un point de vue multi-thread, ce qui signifie qu’il est sécurisé d’un point de vue multi-thread. Mais cette implémentation est obsolète et lente, vous ne verrez donc plus Hashtable dans des projets plus ou moins nouveaux.

8. ArrayList contre LinkedList. Lequel est-il préférable d’utiliser ?

Cette question est peut-être la plus populaire sur les structures de données et comporte certains pièges. Avant d'y répondre, apprenons-en davantage sur ces structures de données. ArrayList implémente l' interface List et fonctionne sur un tableau interne étendu selon les besoins. Lorsque le tableau interne est complètement rempli et qu'un nouvel élément doit être inséré, un nouveau tableau est créé avec une taille de (oldSize * 1.5) +1. Après cela, toutes les données de l'ancien tableau sont copiées dans le nouvel élément + nouvel élément et l'ancien sera supprimé par le ramasse-miettes . La méthode add ajoute un élément à la dernière cellule vide du tableau. Autrement dit, si nous y avons déjà 3 éléments, le suivant sera ajouté à la 4ème cellule. Passons en revue les performances des méthodes de base :

• get(int index) - prendre un élément dans un tableau par index est le plus rapide en O(1) ;
• add(Object obj) - s'il y a suffisamment d'espace dans le tableau interne pour un nouvel élément, alors avec une insertion normale, du temps O(1) sera dépensé , puisque l'ajout est ciblé sur la dernière cellule.

  Si nous devons créer un nouveau tableau et y copier le contenu, alors notre temps sera directement proportionnel au nombre d'éléments dans le tableau O(n) ;

• remove(int index) - lors de la suppression d'un élément, par exemple, du milieu, nous obtiendrons un temps O(n/2), car nous devrons déplacer les éléments à droite de celui-ci d'une cellule en arrière. En conséquence, si vous supprimez depuis le début de la liste, alors O(n), depuis la fin - O(1);
• add(int index, Object obj) - une situation similaire à la suppression : lors de l'ajout au milieu, nous devrons avancer les éléments de droite d'une cellule, donc le temps est O(n/2). Bien sûr, depuis le début - O(n), depuis la fin - O(1) ;
• set(int index, Object obj) - ici la situation est différente, puisqu'il vous suffit de trouver l'élément souhaité et de l'écrire sans déplacer le reste, donc O(1).

En savoir plus sur ArrayList dans cet article . LinkedList implémente deux interfaces à la fois - List et Queue , et possède donc des propriétés et des méthodes inhérentes aux deux structures de données. Depuis List, il a accédé à un élément par index, depuis Queue - la présence d'une "tête" et d'une "queue". En interne, il est implémenté sous la forme d’une structure de données représentant une liste doublement chaînée. C'est-à-dire que chaque élément a un lien vers le suivant et le précédent, à l'exception de la « queue » et de la « tête ».

• get(int index) - lors de la recherche d'un élément qui se trouve au milieu de la liste, il commence à rechercher tous les éléments dans l'ordre jusqu'à ce que celui souhaité soit trouvé. Logiquement, la recherche devrait prendre O(n/2) , mais LinkedList a également une queue, donc la recherche est effectuée simultanément des deux côtés. En conséquence, le temps est réduit à O(n/4) .

  Si l'élément est proche du début de la liste ou de la fin, alors l'heure sera O(1) ;

• add(Object obj) - lors de l'ajout d'un nouvel élément, l'élément « tail » aura un lien vers l'élément suivant ajouté, et le nouveau recevra un lien vers cet élément précédent et deviendra la nouvelle « tail ». En conséquence, le temps sera O(1) ;
• remove(int index) - logique similaire à la méthode get(int index) . Pour supprimer un élément du milieu de la liste, vous devez d’abord le retrouver. C'est encore O(n/4) , alors que la suppression elle-même ne prend rien, puisqu'elle change seulement le pointeur des objets voisins (ils commencent à se référer les uns aux autres). Si l'élément est au début ou à la fin, alors encore - O(1) ;
• add(int index, Object obj) et set(int index, Object obj) - les méthodes auront une complexité temporelle identique à get(int index) , puisque la plupart du temps est passé à rechercher l'élément. Par conséquent, pour le milieu de la liste - O(n/4) , pour le début - O(1).

Plus d'informations sur l'utilisation de LinkedList sont décrites dans cet article . Regardons tout cela dans un tableau : Comme vous l’avez probablement déjà compris, il est impossible de répondre sans ambiguïté à cette question. Après tout, dans différentes situations, ils travaillent à des vitesses différentes. Par conséquent, lorsqu'on vous pose une question comme celle-ci, vous devez immédiatement demander sur quoi cette liste sera axée et quelles opérations seront le plus souvent effectuées. À partir de là, donnez une réponse, mais en expliquant pourquoi. Résumons notre comparaison : ArrayList :

• le meilleur choix si l'opération la plus fréquente consiste à rechercher un élément, à écraser un élément ;
• le pire choix si l'opération est une insertion et une suppression au début-milieu, car les opérations de décalage des éléments à droite auront lieu.

Liste liée :

• le meilleur choix si notre opération fréquente est l'insertion et la suppression au début-milieu ;
• pire choix si l’opération la plus courante est la recherche.

9. Comment les éléments sont-ils stockés dans un HashMap ?

La collection HashMap contient un tableau interne Node[] table , dont les cellules sont également appelées buckets . Le nœud contient :

• clé - lien vers la clé,
• valeur - référence à la valeur,
• hachage - valeur de hachage,
• next - lien vers le prochain nœud .

Une cellule du tableau table[] peut contenir une référence à un objet Node avec un lien vers l' élément Node suivant , et elle peut avoir un lien vers un autre, et ainsi de suite... De ce fait, ces éléments Node peuvent former un liste chaînée unique , avec des éléments avec un lien vers le suivant. Dans ce cas, la valeur de hachage des éléments d'une chaîne est la même. Après une courte digression, regardons comment les éléments sont stockés dans un HashMap :

1. La clé est vérifiée pour null . Si c'est null , alors la clé sera stockée dans la cellule table[0] car le code de hachage pour null est toujours 0.
2. Si la clé n'est pas null , alors la méthode hashcode() de l'objet clé est appelée , qui renverra son code de hachage. Ce code de hachage est utilisé pour déterminer la cellule du tableau où l'objet Node sera stocké.
3. Ensuite, ce hashcode est placé dans la méthode interne hash() , qui calcule le hashcode, mais dans la taille du tableau table[] .
4. Ensuite, en fonction de la valeur de hachage, Node est placé dans une cellule spécifique du tableau table[] .
5. Si la cellule table[] utilisée pour enregistrer l' élément Node actuel n'est pas vide, mais contient déjà un élément, alors les éléments Node sont itérés sur la valeur suivante jusqu'à ce que le dernier élément soit atteint. C'est-à-dire celui dont le champ suivant est null .

   Lors de cette recherche, la clé de l' objet Node protégé est comparée aux clés de ceux recherchés :

   • si une correspondance est trouvée, la recherche se terminera et le nouveau nœud écrasera le nœud dans lequel la correspondance a été trouvée (seul son champ de valeur sera écrasé ) ;
   • si aucune correspondance de clé n'est trouvée, alors le nouveau nœud deviendra le dernier de cette liste et le précédent aura un lien suivant vers lui.

La question revient souvent lors des entretiens : qu'est-ce qu'un conflit ? La situation dans laquelle une cellule du tableau table[] stocke non pas un élément, mais une chaîne de deux ou plus, est appelée une collision . Dans les cas normaux où un seul élément est stocké dans une seule cellule table[] , l'accès aux éléments d' un HashMap a une complexité temporelle O(1) constante . Mais lorsqu'une cellule avec l'élément souhaité contient une chaîne d'éléments ( collision ), alors O(n) , puisque dans ce cas le temps est directement proportionnel au nombre d'éléments à trier.

10. Expliquez l'itérateur

Dans le diagramme de mappage de la hiérarchie de collection ci-dessus, l'interface de collection était le point de départ de toute la hiérarchie, mais en pratique, ce n'est pas tout à fait comme ça. La collection hérite d'une interface avec une méthode iterator() , qui renvoie un objet qui implémente l' interface Iterator<E> . L'interface de l'Itérateur ressemble à ceci :

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - en appelant cette méthode, vous pouvez obtenir l'élément suivant. hasNext() - vous permet de savoir s'il existe un élément suivant et si la fin de la collection a été atteinte. Et quand il y a encore des éléments, hasNext() retournera true . En règle générale, hasNext() est appelée avant la méthode next() , car next() lancera une NoSuchElementException lorsqu'elle atteindra la fin de la collection . Remove() - Supprime l'élément récupéré lors du dernier appel à next() . Le but de Iterator est de parcourir les éléments. Par exemple:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

En fait, la boucle for-each est implémentée sous le capot à l'aide d'un itérateur. Vous pouvez en savoir plus à ce sujet ici . List fournit sa propre version d'un itérateur, mais une version plus cool et plus sophistiquée - ListIterator . Cette interface étend Iterator et dispose de méthodes supplémentaires :

• hasPrevious renverra true s'il y a un élément précédent dans la collection, false sinon ;
• previous renvoie l'élément actuel et passe au précédent ; s'il n'y en a pas, une NoSuchElementException est levée ;
• add insérera l'objet passé avant l'élément qui sera renvoyé par le prochain appel à next() ;
• set attribue à l'élément actuel une référence à l'objet passé ;
• nextIndex renvoie l'index de l'élément suivant. Si rien de tel n’existe, alors la taille de la liste est renvoyée ;
• previousIndex renvoie l'index de l'élément précédent. S'il n'y en a pas, alors le nombre -1 est renvoyé.

Eh bien, c'est tout pour moi aujourd'hui. J'espère qu'après avoir lu cet article, vous êtes encore plus proche de votre rêve le plus cher : devenir développeur.