Chapitre 7: Collections Java — Le guide d'entrevue
Objectif
Ce chapitre couvre tout ce qu'il faut savoir sur les Collections Java pour une entrevue : quand utiliser quoi, les différences entre List.of() et new ArrayList<>(), les pièges courants, et les questions classiques.
1. La hiérarchie des Collections
Iterable
│
Collection
╱ │ ╲
List Set Queue
╱ │ │ ╲ │
ArrayList │ HashSet │ LinkedList
LinkedList │ TreeSet │ PriorityQueue
│ LinkedHashSet
Vector
(legacy)
Map (pas une Collection !)
╱ │ ╲
HashMap TreeMap LinkedHashMap
│
ConcurrentHashMap
2. List.of() vs new ArrayList — Mutable vs Immuable
La différence fondamentale
| Création | Type | Modifiable ? | Accepte null ? |
|---|---|---|---|
List.of("a", "b") | Liste immuable | Non | Non |
new ArrayList<>(List.of("a", "b")) | Liste modifiable | Oui | Oui |
Collections.unmodifiableList(list) | Vue immuable | Non (mais l'originale oui) | Oui |
List.copyOf(list) | Copie immuable | Non | Non |
Exemples concrets
// IMMUABLE — ne peut PAS être modifiée
List<String> immutable = List.of("a", "b", "c");
immutable.add("d"); // 💥 UnsupportedOperationException
immutable.remove(0); // 💥 UnsupportedOperationException
immutable.set(0, "x"); // 💥 UnsupportedOperationException
// MODIFIABLE — peut être modifiée
List<String> mutable = new ArrayList<>();
mutable.add("a"); // ✅ OK
mutable.add("b"); // ✅ OK
mutable.remove(0); // ✅ OK
mutable.set(0, "x"); // ✅ OK
// Créer une liste modifiable à partir d'une immuable
List<String> mutable2 = new ArrayList<>(List.of("a", "b", "c"));
mutable2.add("d"); // ✅ OK
Map.of() et Set.of() — même principe
// Map immuable
Map<String, Integer> map = Map.of("a", 1, "b", 2);
map.put("c", 3); // 💥 UnsupportedOperationException
// Map modifiable
Map<String, Integer> map2 = new HashMap<>(Map.of("a", 1, "b", 2));
map2.put("c", 3); // ✅ OK
// Set immuable
Set<String> set = Set.of("a", "b", "c");
set.add("d"); // 💥 UnsupportedOperationException
// Set modifiable
Set<String> set2 = new HashSet<>(Set.of("a", "b", "c"));
set2.add("d"); // ✅ OK
Collections.emptyList() vs List.of()
// Les deux retournent une liste vide immuable
List<String> empty1 = Collections.emptyList(); // Java 5+
List<String> empty2 = List.of(); // Java 9+ (préféré)
// Les deux sont équivalentes, List.of() est plus moderne
Quand utiliser quoi ?
| Situation | Utiliser | Pourquoi |
|---|---|---|
| Constantes, configurations | List.of() | Immuable, thread-safe |
| Construire une liste progressivement | new ArrayList<>() | Besoin d'ajouter des éléments |
| Retour de méthode (cas vide) | List.of() ou Collections.emptyList() | Jamais retourner null |
| DTO / Records | List.copyOf() | Copie défensive, garantit l'immuabilité |
| Tests unitaires | List.of() | Concis et clair |
Phrase d'entrevue
"List.of() creates an immutable list — it's compact, null-safe, and thread-safe. new ArrayList<>() creates a mutable list that I can modify. I use List.of() for constants and return values, ArrayList for building collections."
3. ArrayList vs LinkedList
ArrayList (tableau dynamique) :
┌───┬───┬───┬───┬───┬───┬───┬ ┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │...│ ← accès direct par index
└───┴───┴───┴───┴───┴───┴───┴ ┘
LinkedList (liste doublement chaînée) :
null ← [A] ⇄ [B] ⇄ [C] ⇄ [D] → null
| Opération | ArrayList | LinkedList |
|---|---|---|
get(index) | O(1) | O(n) |
add(element) (fin) | O(1) amorti | O(1) |
add(index, element) (milieu) | O(n) | O(1) si on a le noeud |
remove(index) | O(n) | O(1) si on a le noeud |
| Mémoire | Compacte | Plus lourde (pointeurs) |
| Cache CPU | Bonne (éléments contigus) | Mauvaise (éléments dispersés) |
En pratique
Utilisez ArrayList dans 99% des cas. LinkedList est rarement plus rapide en pratique à cause de la localité du cache CPU. Même pour des insertions fréquentes, ArrayList est souvent plus rapide.
Phrase d'entrevue
"I almost always use ArrayList. LinkedList has better theoretical complexity for insertions, but ArrayList wins in practice due to CPU cache locality. LinkedList is useful as a Queue (FIFO) via the Deque interface."
4. HashMap — Comment ça fonctionne ?
Structure interne
HashMap (Java 8+) :
┌──────────────────────────────┐
│ Buckets (tableau) │
├──────┬───────────────────────┤
│ [0] │ null │
│ [1] │ → Entry(key1, val1) │
│ [2] │ null │
│ [3] │ → Entry(key2, val2) → Entry(key3, val3) ← collision !
│ [4] │ null │
│ ... │ │
│ [n] │ → Entry(keyN, valN) │
└──────┴───────────────────────┘
Si une liste chaînée dans un bucket dépasse 8 éléments → convertie en arbre rouge-noir (O(log n))
Comment ça marche ?
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
// Étape 1 : hashCode("Alice") → 63650026
// Étape 2 : 63650026 % taille_tableau → index du bucket
// Étape 3 : Stocke Entry("Alice", 25) dans ce bucket
Collision = même bucket
// Si deux clés ont le même index de bucket :
map.put("Alice", 25); // bucket 3
map.put("Bob", 30); // bucket 3 aussi (collision)
// Java crée une liste chaînée dans le bucket 3 :
// bucket[3] → Entry("Alice", 25) → Entry("Bob", 30)
// Pour retrouver "Bob", Java parcourt la liste et utilise equals()
Complexités
| Opération | Cas moyen | Pire cas (beaucoup de collisions) |
|---|---|---|
put() | O(1) | O(log n) (arbre depuis Java 8) |
get() | O(1) | O(log n) |
remove() | O(1) | O(log n) |
containsKey() | O(1) | O(log n) |
containsValue() | O(n) | O(n) |
5. HashMap vs TreeMap vs LinkedHashMap
| Map | Ordre | Complexité | Quand l'utiliser |
|---|---|---|---|
| HashMap | Aucun ordre garanti | O(1) | Défaut, le plus rapide |
| TreeMap | Trié par clé (naturel ou Comparator) | O(log n) | Besoin de clés triées |
| LinkedHashMap | Ordre d'insertion | O(1) | Besoin de l'ordre d'insertion |
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("banana", 2);
hashMap.put("apple", 1);
hashMap.put("cherry", 3);
// Itération : ordre quelconque
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("banana", 2);
treeMap.put("apple", 1);
treeMap.put("cherry", 3);
// Itération : apple → banana → cherry (alphabétique)
Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("banana", 2);
linkedMap.put("apple", 1);
linkedMap.put("cherry", 3);
// Itération : banana → apple → cherry (ordre d'insertion)
6. HashSet vs TreeSet vs LinkedHashSet
| Set | Ordre | Doublons | Complexité |
|---|---|---|---|
| HashSet | Aucun | Non | O(1) |
| TreeSet | Trié | Non | O(log n) |
| LinkedHashSet | Ordre d'insertion | Non | O(1) |
// HashSet = le plus utilisé
Set<String> unique = new HashSet<>(List.of("b", "a", "c", "a"));
// → [a, b, c] (sans doublon, ordre quelconque)
// TreeSet = trié automatiquement
Set<String> sorted = new TreeSet<>(List.of("banana", "apple", "cherry"));
// → [apple, banana, cherry]
Rappel
HashSet utilise hashCode() et equals() pour détecter les doublons. Si vos objets custom n'implémentent pas ces méthodes, le Set ne fonctionnera pas correctement.
7. Queue et Deque
// Queue (FIFO : First In, First Out) — file d'attente
Queue<String> queue = new LinkedList<>();
queue.offer("premier"); // ajouter à la fin
queue.offer("deuxième");
queue.offer("troisième");
queue.poll(); // retirer du début → "premier"
// Deque (Double-Ended Queue) — pile ou file
Deque<String> deque = new ArrayDeque<>();
// Comme Stack (LIFO) :
deque.push("a");
deque.push("b");
deque.pop(); // → "b" (dernier entré, premier sorti)
// Comme Queue (FIFO) :
deque.offerLast("a");
deque.offerLast("b");
deque.pollFirst(); // → "a" (premier entré, premier sorti)
Ne pas utiliser Stack
java.util.Stack est une classe legacy (Java 1.0) synchronisée inutilement. Utilisez ArrayDeque à la place.
// ❌ Legacy
Stack<String> stack = new Stack<>();
// ✅ Moderne
Deque<String> stack = new ArrayDeque<>();
8. Itération sur les Collections
Les 5 façons d'itérer
List<String> names = List.of("Alice", "Bob", "Charlie");
// 1. For-each (le plus courant)
for (String name : names) {
System.out.println(name);
}
// 2. Stream API (fonctionnel)
names.stream()
.filter(n -> n.startsWith("A"))
.forEach(System.out::println);
// 3. forEach avec lambda
names.forEach(name -> System.out.println(name));
// 4. Iterator (quand on doit supprimer en itérant)
Iterator<String> it = names.iterator();
while (it.hasNext()) {
String name = it.next();
if (name.equals("Bob")) it.remove();
}
// 5. For classique avec index (uniquement ArrayList)
for (int i = 0; i < names.size(); i++) {
System.out.println(names.get(i));
}
Piège : ConcurrentModificationException
// ❌ ERREUR — modifier une liste pendant un for-each
List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
if (s.equals("b")) list.remove(s); // 💥 ConcurrentModificationException
}
// ✅ Solution 1 : Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
if (it.next().equals("b")) it.remove(); // OK
}
// ✅ Solution 2 : removeIf (Java 8+)
list.removeIf(s -> s.equals("b")); // OK, plus concis
// ✅ Solution 3 : Stream + filter (crée une nouvelle liste)
List<String> filtered = list.stream()
.filter(s -> !s.equals("b"))
.toList();
Phrase d'entrevue
"You can't modify a collection while iterating with for-each. I use Iterator.remove(), removeIf(), or streams to safely remove elements during iteration."
9. Collections thread-safe
| Collection | Thread-safe ? | Alternative thread-safe |
|---|---|---|
ArrayList | Non | CopyOnWriteArrayList ou Collections.synchronizedList() |
HashMap | Non | ConcurrentHashMap |
HashSet | Non | ConcurrentHashMap.newKeySet() |
LinkedList | Non | ConcurrentLinkedQueue |
// ❌ HashMap n'est PAS thread-safe
Map<String, Integer> map = new HashMap<>();
// ✅ ConcurrentHashMap est thread-safe SANS synchronisation globale
Map<String, Integer> map = new ConcurrentHashMap<>();
// ❌ Hashtable est thread-safe mais LEGACY et lent (synchronisé partout)
Map<String, Integer> map = new Hashtable<>(); // NE PAS UTILISER
Phrase d'entrevue
"For concurrent access, I use ConcurrentHashMap instead of HashMap — it uses lock striping for better throughput than the legacy synchronized Hashtable."
10. Stream API — Résumé rapide
List<User> users = getUsers();
// Filtrer
List<User> active = users.stream()
.filter(User::isActive)
.toList();
// Transformer
List<String> emails = users.stream()
.map(User::getEmail)
.toList();
// Trier
List<User> sorted = users.stream()
.sorted(Comparator.comparing(User::getName))
.toList();
// Grouper
Map<String, List<User>> byRole = users.stream()
.collect(Collectors.groupingBy(User::getRole));
// Réduire (somme, max, min)
double totalSalary = users.stream()
.mapToDouble(User::getSalary)
.sum();
// Vérifier
boolean anyAdmin = users.stream().anyMatch(u -> "ADMIN".equals(u.getRole()));
boolean allActive = users.stream().allMatch(User::isActive);
boolean noneBlocked = users.stream().noneMatch(User::isBlocked);
Les opérations
| Type | Exemples | Retourne |
|---|---|---|
| Intermédiaires (lazy) | filter, map, sorted, distinct, limit, skip | Stream |
| Terminales (exécutent) | toList, collect, forEach, count, sum, reduce, anyMatch | Résultat |
Phrase d'entrevue
"Streams are lazy — intermediate operations like filter and map don't execute until a terminal operation like toList() is called. I use streams for declarative, readable data processing."
Tableau récapitulatif — Quelle collection utiliser ?
| Besoin | Collection | Pourquoi |
|---|---|---|
| Liste ordonnée, accès par index | ArrayList | O(1) pour get/set |
| Pas de doublons | HashSet | O(1) pour add/contains |
| Pas de doublons + ordre trié | TreeSet | O(log n), trié |
| Clé → Valeur | HashMap | O(1) pour put/get |
| Clé → Valeur, trié par clé | TreeMap | O(log n), trié |
| FIFO (file d'attente) | ArrayDeque | Plus rapide que LinkedList |
| LIFO (pile) | ArrayDeque | Remplace Stack (legacy) |
| Thread-safe Map | ConcurrentHashMap | Lock striping |
| Liste immuable | List.of() | Thread-safe, compacte |