Questions d'entretiens chez Java Collections

Cet article fait partie d'une série: • Questions d'entretien sur les collections Java (article actuel) • Questions d'entretien sur Java Type System

• Questions d’entretien sur Java Concurrency (+ réponses)

• Questions d'entretien sur la structure des classes Java et l'initialisation

• Questions d'entrevue Java 8 (+ réponses)

• Questions d’entrevue sur la gestion de la mémoire dans Java (+ réponses)

• Questions d'entrevue Java Generics (+ réponses)

• Questions d’entretien sur le contrôle de flux Java (+ réponses)

• Questions d’entretien sur les exceptions Java (+ réponses)

• Questions d'entrevue sur les annotations Java (+ réponses)

• Principales questions d'entrevue Spring Framework

1. Introduction

Les collections Java sont un sujet souvent abordé lors des entretiens techniques pour les développeurs Java. Cet article passe en revue certaines questions importantes qui sont posées le plus souvent et qui peuvent être difficiles à résoudre.

2. Questions

Q1. Décrivez la hiérarchie des types de collections. Quelles sont les principales interfaces et quelles sont les différences entre elles?

L' interface Iterable représente toute collection qui peut être itérée à l'aide de la boucle for-each . L' interface Collection hérite de Iterable et ajoute des méthodes génériques pour vérifier si un élément est dans une collection, ajouter et supprimer des éléments de la collection, déterminer sa taille, etc.

Les interfaces List , Set et Queue héritent de l' interface Collection .

List est une collection ordonnée, et ses éléments sont accessibles par leur index dans la liste.

Set est une collection non ordonnée avec des éléments distincts, similaire à la notion mathématique d'un ensemble.

Queue est une collection avec des méthodes supplémentaires pour ajouter, supprimer et examiner des éléments, utiles pour conserver des éléments avant le traitement.

L' interface de carte fait également partie du cadre de collecte, mais elle n'étend pas Collection . C'est intentionnel, pour souligner la différence entre les collections et les mappages qui sont difficiles à rassembler sous une abstraction commune. L'interface Map représente une structure de données clé-valeur avec des clés uniques et pas plus d'une valeur pour chaque clé.

Q2. Décrivez diverses implémentations de l'interface de carte et leurs différences de cas d'utilisation.

L'une des implémentations les plus utilisées de l' interface Map est le HashMap . Il s'agit d'une structure de données de carte de hachage typique qui permet d'accéder aux éléments en temps constant, ou O (1), mais ne conserve pas l'ordre et n'est pas thread-safe .

Pour conserver l'ordre d'insertion des éléments, vous pouvez utiliser la classe LinkedHashMap qui étend le HashMap et lie en outre les éléments dans une liste liée, avec une surcharge prévisible.

La classe TreeMap stocke ses éléments dans une structure arborescente rouge-noire, qui permet d'accéder aux éléments en temps logarithmique, ou O (log (n)). Il est plus lent que le HashMap dans la plupart des cas, mais il permet de garder les éléments dans l'ordre selon certains Comparator .

Le ConcurrentHashMap est une implémentation thread-safe d'une carte de hachage. Il fournit une simultanéité totale des récupérations (car l' opération get n'implique pas de verrouillage) et une concurrence élevée attendue des mises à jour.

La classe Hashtable est en Java depuis la version 1.0. Il n'est pas obsolète mais est généralement considéré comme obsolète. Il s'agit d'une carte de hachage thread-safe, mais contrairement à ConcurrentHashMap , toutes ses méthodes sont simplement synchronisées , ce qui signifie que toutes les opérations sur cette carte bloquent, même la récupération de valeurs indépendantes.

Q3. Expliquez la différence entre Linkedlist et Arraylist.

ArrayList est une implémentation de l'interface List basée sur un tableau. ArrayList gère en interne le redimensionnement de ce tableau lorsque les éléments sont ajoutés ou supprimés. Vous pouvez accéder à ses éléments en temps constant par leur index dans le tableau. Cependant, l'insertion ou la suppression d'un élément implique le décalage de tous les éléments conséquents, ce qui peut être lent si le tableau est énorme et que l'élément inséré ou supprimé est proche du début de la liste.

LinkedList est une liste à double lien: des éléments uniques sont placés dans desobjets Node qui ont des références au nœud précédent et suivant. Cette implémentation peut sembler plus efficace que ArrayList si vous avez de nombreuses insertions ou suppressions dans différentes parties de la liste, en particulier si la liste est volumineuse.

Dans la plupart des cas, cependant, ArrayList surpasse LinkedList . Même le déplacement des éléments dans ArrayList , tout en étant une opération O (n), est implémenté sous la forme d'un appel System.arraycopy () très rapide . Il peut même apparaître plus rapidement que l' insertion O (1) de LinkedList qui nécessite d'instancier un objet Node et de mettre à jour plusieurs références sous le capot. LinkedList peut également avoir une surcharge de mémoire importante en raison de la création de plusieurs petits objets Node .

Q4. Quelle est la différence entre Hashset et Treeset?

Les classes HashSet et TreeSet implémentent l' interface Set et représentent des ensembles d'éléments distincts. De plus, TreeSet implémente l' interface NavigableSet . Cette interface définit des méthodes qui tirent parti de l'ordre des éléments.

HashSet est basé en interne sur un HashMap , et TreeSet est soutenu par une instance TreeMap , qui définit leurs propriétés: HashSet ne conserve pas les éléments dans un ordre particulier. L'itération sur les éléments d'un HashSet les produit dans un ordre aléatoire . TreeSet , d'autre part, produit des éléments dans l'ordre selon un comparateur prédéfini .

Q5. Comment Hashmap est-il implémenté en Java? Comment sa mise en œuvre utilise-t-elle les méthodes Hashcode et Equals des objets? Quelle est la complexité temporelle de la mise et de l'obtention d'un élément à partir d'une telle structure?

La classe HashMap représente une structure de données de carte de hachage typique avec certains choix de conception.

Le HashMap est soutenu par un tableau redimensionnable qui a une taille de puissance de deux. Lorsque l'élément est ajouté à un HashMap , d'abord son hashCode est calculé (une valeur int ). Ensuite, un certain nombre de bits inférieurs de cette valeur sont utilisés comme index de tableau. Cet index pointe directement vers la cellule du tableau (appelée compartiment) où cette paire clé-valeur doit être placée. L'accès à un élément par son index dans un tableau est une opération O (1) très rapide, qui est la caractéristique principale d'une structure de carte de hachage.

A hashCode is not unique, however, and even for different hashCodes, we may receive the same array position. This is called a collision. There is more than one way of resolving collisions in the hash map data structures. In Java's HashMap, each bucket actually refers not to a single object, but to a red-black tree of all objects that landed in this bucket (prior to Java 8, this was a linked list).

So when the HashMap has determined the bucket for a key, it has to traverse this tree to put the key-value pair in its place. If a pair with such key already exists in the bucket, it is replaced with a new one.

To retrieve the object by its key, the HashMap again has to calculate the hashCode for the key, find the corresponding bucket, traverse the tree, call equals on keys in the tree and find the matching one.

HashMap has O(1) complexity, or constant-time complexity, of putting and getting the elements. Of course, lots of collisions could degrade the performance to O(log(n)) time complexity in the worst case, when all elements land in a single bucket. This is usually solved by providing a good hash function with a uniform distribution.

When the HashMap internal array is filled (more on that in the next question), it is automatically resized to be twice as large. This operation infers rehashing (rebuilding of internal data structures), which is costly, so you should plan the size of your HashMap beforehand.

Q6. What Is the Purpose of the Initial Capacity and Load Factor Parameters of a Hashmap? What Are Their Default Values?

The initialCapacity argument of the HashMap constructor affects the size of the internal data structure of the HashMap, but reasoning about the actual size of a map is a bit tricky. The HashMap‘s internal data structure is an array with the power-of-two size. So the initialCapacity argument value is increased to the next power-of-two (for instance, if you set it to 10, the actual size of the internal array will be 16).

The load factor of a HashMap is the ratio of the element count divided by the bucket count (i.e. internal array size). For instance, if a 16-bucket HashMap contains 12 elements, its load factor is 12/16 = 0.75. A high load factor means a lot of collisions, which in turn means that the map should be resized to the next power of two. So the loadFactor argument is a maximum value of the load factor of a map. When the map achieves this load factor, it resizes its internal array to the next power-of-two value.

The initialCapacity is 16 by default, and the loadFactor is 0.75 by default, so you could put 12 elements in a HashMap that was instantiated with the default constructor, and it would not resize. The same goes for the HashSet, which is backed by a HashMap instance internally.

Consequently, it is not trivial to come up with initialCapacity that satisfies your needs. This is why the Guava library has Maps.newHashMapWithExpectedSize() and Sets.newHashSetWithExpectedSize() methods that allow you to build a HashMap or a HashSet that can hold the expected number of elements without resizing.

Q7. Describe Special Collections for Enums. What Are the Benefits of Their Implementation Compared to Regular Collections?

EnumSet and EnumMap are special implementations of Set and Map interfaces correspondingly. You should always use these implementations when you're dealing with enums because they are very efficient.

An EnumSet is just a bit vector with “ones” in the positions corresponding to ordinal values of enums present in the set. To check if an enum value is in the set, the implementation simply has to check if the corresponding bit in the vector is a “one”, which is a very easy operation. Similarly, an EnumMap is an array accessed with enum's ordinal value as an index. In the case of EnumMap, there is no need to calculate hash codes or resolve collisions.

Q8. What Is the Difference Between Fail-Fast and Fail-Safe Iterators?

Iterators for different collections are either fail-fast or fail-safe, depending on how they react to concurrent modifications. The concurrent modification is not only a modification of collection from another thread but also modification from the same thread but using another iterator or modifying the collection directly.

Fail-fast iterators (those returned by HashMap, ArrayList, and other non-thread-safe collections) iterate over the collection's internal data structure, and they throw ConcurrentModificationException as soon as they detect a concurrent modification.

Fail-safe iterators (returned by thread-safe collections such as ConcurrentHashMap, CopyOnWriteArrayList) create a copy of the structure they iterate upon. They guarantee safety from concurrent modifications. Their drawbacks include excessive memory consumption and iteration over possibly out-of-date data in case the collection was modified.

Q9. How Can You Use Comparable and Comparator Interfaces to Sort Collections?

The Comparable interface is an interface for objects that can be compared according to some order. Its single method is compareTo, which operates on two values: the object itself and the argument object of the same type. For instance, Integer, Long, and other numeric types implement this interface. String also implements this interface, and its compareTo method compares strings in lexicographical order.

The Comparable interface allows to sort lists of corresponding objects with the Collections.sort() method and uphold the iteration order in collections that implement SortedSet and SortedMap. If your objects can be sorted using some logic, they should implement the Comparable interface.

The Comparable interface usually is implemented using natural ordering of the elements. For instance, all Integer numbers are ordered from lesser to greater values. But sometimes you may want to implement another kind of ordering, for instance, to sort the numbers in descending order. The Comparator interface can help here.

The class of the objects you want to sort does not need to implement this interface. You simply create an implementing class and define the compare method which receives two objects and decides how to order them. You may then use the instance of this class to override the natural ordering of the Collections.sort() method or SortedSet and SortedMap instances.

As the Comparator interface is a functional interface, you may replace it with a lambda expression, as in the following example. It shows ordering a list using a natural ordering (Integer‘s Comparable interface) and using a custom iterator (Comparator interface).

List list1 = Arrays.asList(5, 2, 3, 4, 1); Collections.sort(list1); assertEquals(new Integer(1), list1.get(0)); List list1 = Arrays.asList(5, 2, 3, 4, 1); Collections.sort(list1, (a, b) -> b - a); assertEquals(new Integer(5), list1.get(0));
Suivant » Questions d'entretiens avec Java Type System