Guide Complet des Collections Java (Java 21+)

Table des Matières

Sommaire

Introduction aux Collections Java
Interface Collection et Hiérarchie
Collections de Type List
1. ArrayList
2. LinkedList
3. Vector
4. Stack
Collections de Type Set
Collections de Type Map
Collections de Type Queue et Deque
1. ArrayDeque
Collections Concurrentes
Collections Spécialisées
Comparaison des Performances
Bonnes Pratiques

Introduction aux Collections Java

Le Java Collections Framework (JCF) est une architecture unifiée pour représenter et manipuler des collections d'objets. Introduit en Java 1.2 et constamment amélioré, il fournit des interfaces standard, des implémentations concrètes et des algorithmes pour traiter des groupes d'objets.

Avantages du Framework

Réduction de l'effort de programmation : APIs standardisées
Amélioration des performances : Implémentations optimisées
Interopérabilité : Collections compatibles entre elles
Facilité d'apprentissage : Interface cohérente

Interface Collection et Hiérarchie

Hiérarchie des Interfaces

Iterable<E>
    └── Collection<E>
        ├── List<E>
        ├── Set<E>
        │   └── SortedSet<E>
        │       └── NavigableSet<E>
        └── Queue<E>
            └── Deque<E>

Map<K,V>
    ├── SortedMap<K,V>
    │   └── NavigableMap<K,V>
    └── ConcurrentMap<K,V>

Opérations Communes (Interface Collection)

Opération	Description	Complexité Générale
`add(E e)`	Ajoute un élément	O(1) à O(log n)
`remove(Object o)`	Supprime un élément	O(1) à O(n)
`contains(Object o)`	Vérifie la présence	O(1) à O(n)
`size()`	Retourne la taille	O(1)
`isEmpty()`	Vérifie si vide	O(1)
`clear()`	Vide la collection	O(1) à O(n)

Collections de Type List

Les List sont des collections ordonnées qui permettent les doublons et l'accès par index.

ArrayList

Spécifications Techniques :

Structure interne : Tableau dynamique redimensionnable
Capacité initiale : 10 éléments (par défaut)
Facteur de croissance : 1.5x (capacity = oldCapacity + (oldCapacity >> 1))
Thread-safety : Non synchronisée
Ordre d'insertion : Préservé

Complexités Algorithmiques :

Opération	Complexité Temporelle	Complexité Spatiale	Détails
`get(int index)`	O(1)	O(1)	Accès direct par index
`set(int index, E element)`	O(1)	O(1)	Modification directe
`add(E e)`	O(1) amortie	O(1)	O(n) lors du redimensionnement
`add(int index, E element)`	O(n)	O(1)	Décalage des éléments suivants
`remove(int index)`	O(n)	O(1)	Décalage des éléments suivants
`remove(Object o)`	O(n)	O(1)	Recherche linéaire puis suppression
`contains(Object o)`	O(n)	O(1)	Recherche linéaire
`indexOf(Object o)`	O(n)	O(1)	Recherche linéaire
`clear()`	O(n)	O(1)	Mise à null de tous les éléments

Détails d'Implémentation :

L'ArrayList utilise un tableau interne Object[] elementData pour stocker les éléments. Lors de l'ajout d'un élément, si la capacité est insuffisante, un nouveau tableau de taille oldCapacity + (oldCapacity >> 1) est créé et les éléments sont copiés.

// Exemple de redimensionnement interne (simplifié)
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // croissance de 50%
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Cas d'Usage Recommandés :

Accès fréquent par index
Ajouts principalement en fin de liste
Lecture intensive avec peu de modifications
Quand la taille finale est approximativement connue

Anti-Patterns :

Insertions/suppressions fréquentes au milieu
Synchronisation manuelle pour multi-threading
Très grandes listes avec mémoire limitée

LinkedList

Spécifications Techniques :

Structure interne : Liste doublement chaînée
Nœuds : Chaque élément contient des références vers le précédent et le suivant
Thread-safety : Non synchronisée
Implémente : List, Deque

Complexités Algorithmiques :

Opération	Complexité Temporelle	Complexité Spatiale	Détails
`get(int index)`	O(n)	O(1)	Parcours depuis head/tail
`set(int index, E element)`	O(n)	O(1)	Parcours puis modification
`add(E e)`	O(1)	O(1)	Ajout en fin (linkLast)
`add(int index, E element)`	O(n)	O(1)	Parcours puis insertion
`addFirst(E e)`	O(1)	O(1)	Insertion en tête
`addLast(E e)`	O(1)	O(1)	Insertion en queue
`remove(int index)`	O(n)	O(1)	Parcours puis suppression
`removeFirst()`	O(1)	O(1)	Suppression en tête
`removeLast()`	O(1)	O(1)	Suppression en queue
`contains(Object o)`	O(n)	O(1)	Parcours complet possible

Détails d'Implémentation :

La LinkedList maintient des références vers le premier (first) et dernier (last) nœud. Chaque nœud contient l'élément et les références next et prev.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Optimisation get(index) :
La méthode get(index) optimise le parcours en commençant par le côté le plus proche :

if (index < (size >> 1)) {
    // Parcours depuis le début
} else {
    // Parcours depuis la fin
}

Cas d'Usage Recommandés :

Insertions/suppressions fréquentes en début/fin
Implémentation de pile (Stack) ou file (Queue)
Quand la taille varie beaucoup dynamiquement
Peu d'accès par index

Vector

Spécifications Techniques :

Structure interne : Tableau dynamique (comme ArrayList)
Thread-safety : Synchronisée (toutes les méthodes sont synchronized)
Capacité initiale : 10 éléments (par défaut)
Facteur de croissance : 2x par défaut (configurable)
Statut : Legacy (Java 1.0), utilisation déconseillée

Complexités Algorithmiques :
Identiques à ArrayList, mais avec overhead de synchronisation :

Opération	Complexité Temporelle	Overhead	Détails
`get(int index)`	O(1) + sync	~50-100ns	Acquisition/libération verrou
`add(E e)`	O(1) amortie + sync	~50-100ns	Synchronisation sur this
Toutes opérations	Même que ArrayList	Constant	Coût de synchronisation

Alternatives Recommandées :

Collections.synchronizedList(new ArrayList<>()) pour synchronisation
CopyOnWriteArrayList pour lecture intensive
ArrayList avec verrous externes pour contrôle fin

Stack

Spécifications Techniques :

Hérite de : Vector
Principe : LIFO (Last In, First Out)
Thread-safety : Synchronisée (héritée de Vector)
Statut : Legacy, utilisation déconseillée

Complexités Algorithmiques :

Opération	Complexité Temporelle	Alternative Recommandée
`push(E item)`	O(1) + sync	`Deque.addFirst()`
`pop()`	O(1) + sync	`Deque.removeFirst()`
`peek()`	O(1) + sync	`Deque.peekFirst()`

Alternative Moderne :

Deque<String> stack = new ArrayDeque<>();
stack.push("element");    // equivalent à addFirst()
String top = stack.pop(); // equivalent à removeFirst()

Collections de Type Set

Les Set sont des collections qui n'autorisent pas les doublons. L'unicité est déterminée par les méthodes equals() et hashCode().

HashSet

Spécifications Techniques :

Structure interne : Table de hachage (HashMap interne)
Capacité initiale : 16 buckets
Facteur de charge : 0.75 (redimensionnement à 75% de remplissage)
Résolution collisions : Chaînage (listes chaînées + arbres rouges-noirs pour buckets > 8 éléments)
Thread-safety : Non synchronisée

Complexités Algorithmiques :

Opération	Complexité Temporelle	Complexité Spatiale	Détails
`add(E e)`	O(1) moyen, O(n) pire cas	O(1)	O(n) si rehashing nécessaire
`remove(Object o)`	O(1) moyen, O(log n) pire cas	O(1)	O(log n) si bucket transformé en arbre
`contains(Object o)`	O(1) moyen, O(log n) pire cas	O(1)	Même principe que remove
`size()`	O(1)	O(1)	Variable maintenue
`clear()`	O(n)	O(1)	Parcours des buckets
`iterator()`	O(1) création	O(1) par next()	Parcours des buckets non-vides

Détails d'Implémentation :

Le HashSet utilise un HashMap interne où les éléments du set sont les clés, et une constante PRESENT est la valeur :

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

Gestion des Collisions (Java 8+) :

Buckets <= 8 éléments : Liste chaînée simple
Buckets > 8 éléments : Arbre rouge-noir (TreeNode)
Retour à liste chaînée : Si bucket redescend à <= 6 éléments

Calcul du Hash :

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Cas d'Usage Recommandés :

Vérification rapide d'appartenance
Élimination des doublons
Opérations mathématiques sur ensembles (union, intersection)
Quand l'ordre n'est pas important

LinkedHashSet

Spécifications Techniques :

Hérite de : HashSet
Structure interne : HashMap + Liste doublement chaînée
Ordre : Préserve l'ordre d'insertion
Overhead mémoire : ~2x par rapport à HashSet (références supplémentaires)

Complexités Algorithmiques :

Opération	Complexité Temporelle	Overhead vs HashSet
`add(E e)`	O(1) moyen	Maintenance liste chaînée
`remove(Object o)`	O(1) moyen	Suppression des liens
`contains(Object o)`	O(1) moyen	Identique
`iterator()`	O(1) par élément	Parcours ordonné

Détails d'Implémentation :

Utilise une classe Entry étendue avec des références before et after :

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Cas d'Usage Recommandés :

Besoin de performance HashSet + ordre préservé
Cache LRU (avec accessOrder=true)
Sérialisation déterministe

TreeSet

Spécifications Techniques :

Structure interne : Arbre rouge-noir auto-équilibré (TreeMap interne)
Ordre : Tri naturel (Comparable) ou Comparator fourni
Éléments : Doivent être comparables entre eux
Thread-safety : Non synchronisée

Complexités Algorithmiques :

Opération	Complexité Temporelle	Complexité Spatiale	Détails
`add(E e)`	O(log n)	O(1)	Insertion avec rééquilibrage
`remove(Object o)`	O(log n)	O(1)	Suppression avec rééquilibrage
`contains(Object o)`	O(log n)	O(1)	Recherche binaire dans l'arbre
`first()`	O(log n)	O(1)	Descendre à gauche complètement
`last()`	O(log n)	O(1)	Descendre à droite complètement
`lower(E e)`	O(log n)	O(1)	Plus grand élément < e
`higher(E e)`	O(log n)	O(1)	Plus petit élément > e
`subSet(from, to)`	O(log n)	O(1) vue	Vue sur sous-ensemble

Fonctionnalités NavigableSet :

TreeSet<Integer> set = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9));

// Opérations de navigation
set.lower(5);     // 3 (plus grand < 5)
set.floor(5);     // 5 (plus grand <= 5)
set.ceiling(5);   // 5 (plus petit >= 5)
set.higher(5);    // 7 (plus petit > 5)

// Vues
set.headSet(5);           // [1, 3] (< 5)
set.tailSet(5);           // [5, 7, 9] (>= 5)
set.subSet(3, 8);         // [3, 5, 7] ([3, 8[)

Cas d'Usage Recommandés :

Éléments toujours triés
Recherches par plages (range queries)
Opérations de navigation (plus proche, précédent/suivant)
Implémentation d'algorithmes nécessitant l'ordre

EnumSet

Spécifications Techniques :

Optimisation spéciale : Pour les enums uniquement
Structure interne : Bit vector (long[] pour >64 éléments)
Implémentations : RegularEnumSet (<= 64 éléments), JumboEnumSet (> 64)
Performance : Extrêmement rapide

Complexités Algorithmiques :

Opération	Complexité Temporelle	Détails
`add(E e)`	O(1)	Opération bit à bit
`remove(E e)`	O(1)	Opération bit à bit
`contains(E e)`	O(1)	Test de bit
`size()`	O(1)	Compteur maintenu
Union/Intersection	O(1)	Opérations bitwise

Exemple d'Implémentation Interne (RegularEnumSet) :

class RegularEnumSet<E extends Enum<E>> extends EnumSet<E> {
    private long elements = 0L;

    public boolean add(E e) {
        long oldElements = elements;
        elements |= (1L << e.ordinal());
        return elements != oldElements;
    }

    public boolean contains(Object o) {
        if (o == null || o.getClass() != elementType)
            return false;
        return (elements & (1L << ((Enum<?>) o).ordinal())) != 0;
    }
}

Cas d'Usage Recommandés :

Collections d'énumérations (flags, options)
Opérations sur ensembles d'enums très fréquentes
Remplacement efficace de masques de bits

Collections de Type Map

Les Map associent des clés uniques à des valeurs. Elles ne héritent pas de Collection mais font partie intégrante du framework.

HashMap

Spécifications Techniques :

Structure interne : Table de hachage avec résolution par chaînage
Capacité initiale : 16 buckets
Facteur de charge : 0.75
Résolution collisions : Listes chaînées → Arbres rouge-noir (seuil : 8 éléments)
Clés null : Une seule autorisée
Valeurs null : Multiples autorisées

Complexités Algorithmiques :

Opération	Complexité Temporelle	Complexité Spatiale	Détails
`put(K key, V value)`	O(1) moyen, O(log n) pire	O(1)	O(n) lors du rehashing
`get(Object key)`	O(1) moyen, O(log n) pire	O(1)	O(log n) si bucket en arbre
`remove(Object key)`	O(1) moyen, O(log n) pire	O(1)	Même principe que get
`containsKey(Object key)`	O(1) moyen, O(log n) pire	O(1)	Équivalent à get
`containsValue(Object value)`	O(n)	O(1)	Parcours de toutes les valeurs
`keySet()`	O(1)	O(1) vue	Vue sur les clés
`values()`	O(1)	O(1) vue	Vue sur les valeurs
`entrySet()`	O(1)	O(1) vue	Vue sur les paires clé-valeur

Évolution de la Structure Interne (Java 8+) :

Buckets <= 6 éléments : Liste chaînée simple
6 < Buckets <= 8 éléments : Liste chaînée (pas de transformation)
Buckets > 8 éléments : Transformation en arbre rouge-noir
Arbre < 6 éléments : Retour à liste chaînée

Processus de Rehashing :

// Quand size > threshold (capacity * loadFactor)
void resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int newCap = oldCap << 1; // Doubler la capacité

    // Redistribuer tous les éléments
    for (int j = 0; j < oldCap; ++j) {
        // Répartir les éléments entre ancien et nouvel index
        // Utilise le bit supplémentaire du hash
    }
}

Calcul de l'Index de Bucket :

// Java utilise cette optimisation au lieu de % pour les puissances de 2
int index = (capacity - 1) & hash(key);

Cas d'Usage Recommandés :

Association clé-valeur généraliste
Cache avec accès rapide par clé
Index/dictionnaire de données
Compteurs et groupements

LinkedHashMap

Spécifications Techniques :

Hérite de : HashMap<K,V>
Ordre : Insertion (par défaut) ou accès (accessOrder=true)
Structure supplémentaire : Liste doublement chaînée
Overhead mémoire : ~30% par rapport à HashMap

Complexités Algorithmiques :

Opération	Complexité Temporelle	Overhead vs HashMap
`put(K key, V value)`	O(1) moyen	Maintenance ordre
`get(Object key)`	O(1) moyen	Possible réorganisation (accessOrder)
Toutes autres	Identique HashMap	Maintenance liste chaînée

Mode Access Order (LRU) :

// Cache LRU de taille fixe
Map<String, String> lruCache = new LinkedHashMap<String, String>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > MAX_CACHE_SIZE;
    }
};

Détails d'Implémentation :

Étend les nœuds HashMap avec des références d'ordre :

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Cas d'Usage Recommandés :

Cache LRU (Least Recently Used)
Préservation d'ordre avec performance HashMap
Sérialisation déterministe
Historique d'accès

TreeMap

Spécifications Techniques :

Structure interne : Arbre rouge-noir auto-équilibré
Ordre : Tri naturel des clés (Comparable) ou Comparator
Clés null : Interdites (ClassCastException)
Valeurs null : Autorisées

Complexités Algorithmiques :

Opération	Complexité Temporelle	Complexité Spatiale	Détails
`put(K key, V value)`	O(log n)	O(1)	Insertion avec rééquilibrage
`get(Object key)`	O(log n)	O(1)	Recherche binaire
`remove(Object key)`	O(log n)	O(1)	Suppression avec rééquilibrage
`firstKey()`	O(log n)	O(1)	Minimum de l'arbre
`lastKey()`	O(log n)	O(1)	Maximum de l'arbre
`lowerKey(K key)`	O(log n)	O(1)	Plus grande clé < key
`higherKey(K key)`	O(log n)	O(1)	Plus petite clé > key
`subMap(from, to)`	O(log n)	O(1) vue	Vue sur sous-carte

Opérations NavigableMap Avancées :

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "one");
map.put(3, "three");
map.put(5, "five");
map.put(7, "seven");

// Navigation
map.lowerKey(5);        // 3 (plus grande clé < 5)
map.floorKey(5);        // 5 (plus grande clé <= 5)
map.ceilingKey(5);      // 5 (plus petite clé >= 5)
map.higherKey(5);       // 7 (plus petite clé > 5)

// Vues sur plages
map.headMap(5);         // {1=one, 3=three} (< 5)
map.tailMap(5);         // {5=five, 7=seven} (>= 5)
map.subMap(3, 7);       // {3=three, 5=five} ([3, 7[)

// Navigation inverse
map.descendingMap();    // Vue en ordre décroissant

Cas d'Usage Recommandés :

Clés toujours triées nécessaires
Requêtes par plages (range queries)
Navigation dans l'espace des clés
Implémentation d'index ordonnés

Hashtable

Spécifications Techniques :

Thread-safety : Synchronisée (toutes méthodes synchronized)
Clés/Valeurs null : Interdites (NullPointerException)
Statut : Legacy (Java 1.0), utilisation déconseillée
Structure : Table de hachage simple (pas d'arbres)

Complexités Algorithmiques :
Identiques à HashMap mais avec overhead de synchronisation constant sur toutes opérations.

Alternatives Modernes :

Collections.synchronizedMap(new HashMap<>()) pour synchronisation
ConcurrentHashMap pour concurrent haute performance
HashMap avec verrous externes pour contrôle fin

Properties

Spécifications Techniques :

Hérite de : Hashtable<Object,Object>
Usage spécifique : Configuration (clés/valeurs String)
Fonctionnalités : Load/store depuis fichiers .properties
Hiérarchie : Support des propriétés par défaut

Méthodes Spécifiques :

Méthode	Description	Complexité
`load(InputStream)`	Charge depuis fichier	O(n)
`store(OutputStream, String)`	Sauvegarde dans fichier	O(n)
`getProperty(String key)`	Récupère propriété (avec défaut)	O(1) moyen
`setProperty(String key, String value)`	Définit propriété	O(1) moyen

Collections de Type Queue et Deque

Les Queue implémentent une file (FIFO - First In, First Out) et les Deque permettent l'insertion/suppression aux deux extrémités.

ArrayDeque

Spécifications Techniques :

Structure interne : Tableau circulaire redimensionnable
Capacité initiale : 16 éléments (doit être puissance de 2)
Redimensionnement : Double la taille quand pleine
Thread-safety : Non synchronisée
Null : Interdit (utilisé comme sentinel)

Complexités Algorithmiques :

Opération	Complexité Temporelle	Complexité Spatiale	Détails
`addFirst(E e)`	O(1) amortie	O(1)	Décrémente head circulaire
`addLast(E e)`	O(1) amortie	O(1)	Incrémente tail circulaire
`removeFirst()`	O(1)	O(1)	Retourne et inc

Collections Concurrentes

Les collections concurrentes sont optimisées pour l'utilisation multi-threadée, offrant de meilleures performances que les collections synchronisées traditionnelles.

ConcurrentHashMap

Spécifications Techniques :

Structure interne : Segmentation avec verrouillage fin (Java 8+ : CAS + synchronized sur nœuds)
Thread-safety : Thread-safe sans synchronisation globale
Null : Clés et valeurs null interdites
Opérations atomiques : putIfAbsent, replace, compute, merge
Parallélisme : Optimisé pour lecture concurrente massive

Complexités Algorithmiques :

Opération	Complexité Temporelle	Concurrence	Détails
`put(K key, V value)`	O(1) moyen, O(log n) pire	Lock-free lecture	CAS + synchronized sur bucket si nécessaire
`get(Object key)`	O(1) moyen, O(log n) pire	Complètement lock-free	Volatile reads, pas de verrous
`remove(Object key)`	O(1) moyen, O(log n) pire	Lock sur bucket uniquement	Synchronisation fine
`size()`	O(1)	Lock-free	Compteur approximatif maintenu
`compute(K, BiFunction)`	O(1) moyen, O(log n) pire	Lock sur bucket	Opération atomique
`merge(K, V, BiFunction)`	O(1) moyen, O(log n) pire	Lock sur bucket	Combine valeur existante

Architecture Interne (Java 8+) :

// Utilisation de CAS (Compare-And-Swap) pour les updates
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

// Synchronisation fine sur les head nodes seulement
synchronized (f) {  // f = first node of bucket
    if (tabAt(tab, i) == f) {
        // Modification du bucket
    }
}

Mécanismes d'Optimisation :

Forwarding Nodes : Pendant le redimensionnement, redirige vers nouvelle table
Help Transfer : Les threads en lecture aident au transfert des données
Lazy Propagation : Les mises à jour de taille sont propagées paresseusement
Tree Bins : Buckets > 8 éléments transformés en arbres rouge-noir

Opérations Atomiques Avancées :

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// Atomique : ajout si absent
map.putIfAbsent("key", 1);

// Atomique : remplacement conditionnel
map.replace("key", oldValue, newValue);

// Atomique : calcul de nouvelle valeur
map.compute("key", (k, v) -> (v == null) ? 1 : v + 1);

// Atomique : fusion de valeurs
map.merge("key", 1, Integer::sum);  // Compteur atomique

Itération et Vues :

Weak Consistency : Les itérateurs reflètent l'état à un moment donné
No ConcurrentModificationException : Itération sûre même avec modifications
Parallel Bulk Operations : forEach, search, reduce parallèles

Cas d'Usage Recommandés :

Cache partagé haute performance
Compteurs concurrents (avec merge)
Index thread-safe avec lectures massives
Remplacement de HashMap + synchronization

ConcurrentLinkedQueue

Spécifications Techniques :

Structure interne : File liée lock-free (algorithme Michael & Scott)
Principe : FIFO strict
Thread-safety : Complètement lock-free (CAS uniquement)
Null : Interdit
Unbounded : Taille limitée uniquement par la mémoire

Complexités Algorithmiques :

Opération	Complexité Temporelle	Concurrence	Détails
`offer(E e)`	O(1)	Lock-free	CAS sur tail
`poll()`	O(1) amortie	Lock-free	CAS sur head, possible retry
`peek()`	O(1)	Lock-free	Lecture volatile
`size()`	O(n)	Lock-free	Parcours complet (coûteux!)
`isEmpty()`	O(1)	Lock-free	Test head.next

Algorithme Michael & Scott (Simplifié) :

public boolean offer(E e) {
    Node<E> newNode = new Node<>(e);
    for (Node<E> t = tail, p = t;;) {
        Node<E> q = p.next;
        if (q == null) {
            // p est le dernier nœud
            if (p.casNext(null, newNode)) {
                // CAS réussi, ajuster tail si nécessaire
                casTail(t, newNode);
                return true;
            }
        } else {
            // Avancer p vers la fin
            p = (p != t && t != (t = tail)) ? t : q;
        }
    }
}

Particularités de l'Implémentation :

Lazy tail updates : tail peut ne pas pointer sur le dernier nœud
Help mechanism : Les threads s'entraident pour maintenir les invariants
ABA problem resistant : Utilisation de marqueurs pour éviter ABA

Cas d'Usage Recommandés :

Producer-consumer patterns haute performance
Pipeline de traitement multi-threadé
Event queuing sans contention
Alternative lock-free à LinkedBlockingQueue

ConcurrentLinkedDeque

Spécifications Techniques :

Structure interne : Deque liée lock-free bidirectionnelle
Thread-safety : Lock-free avec CAS
Opérations : Insertion/suppression aux deux extrémités
Null : Interdit

Complexités Algorithmiques :

Opération	Complexité Temporelle	Concurrence
`addFirst(E e)`	O(1)	Lock-free
`addLast(E e)`	O(1)	Lock-free
`removeFirst()`	O(1) amortie	Lock-free
`removeLast()`	O(1) amortie	Lock-free
`size()`	O(n)	Lock-free (coûteux)

Cas d'Usage Recommandés :

Work-stealing queues
Stack et queue concurrents
Double-ended producer-consumer

BlockingQueue Implementations

Les BlockingQueue offrent des opérations bloquantes pour la synchronisation inter-threads.

ArrayBlockingQueue

Spécifications Techniques :

Structure interne : Tableau circulaire de taille fixe
Blocking : ReentrantLock + Conditions (notEmpty, notFull)
Bounded : Capacité définie à la création
Fairness : Optionnelle (ordre FIFO des threads bloqués)

Complexités Algorithmiques :

Opération	Complexité Temporelle	Blocking	Détails
`put(E e)`	O(1)	Bloque si pleine	Attend jusqu'à espace disponible
`take()`	O(1)	Bloque si vide	Attend jusqu'à élément disponible
`offer(E e, long timeout, TimeUnit)`	O(1)	Timeout	Bloque avec limite temporelle
`offer(E e)`	O(1)	Non-bloquant	Retourne false si pleine
`poll()`	O(1)	Non-bloquant	Retourne null si vide

Implémentation des Opérations Bloquantes :

public void put(E e) throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == items.length)
            notFull.await();  // Bloque jusqu'à espace libre
        enqueue(e);
    } finally {
        lock.unlock();
    }
}

Cas d'Usage Recommandés :

Producer-consumer avec buffer fixe
Rate limiting (capacité = débit maximum)
Backpressure handling

LinkedBlockingQueue

Spécifications Techniques :

Structure interne : Liste liée (optionnellement bornée)
Capacité : Integer.MAX_VALUE par défaut
Locking : Deux locks séparés (takeLock, putLock)
Performance : Meilleure que ArrayBlockingQueue pour fort débit

Optimisation Two-Lock :

private final ReentrantLock takeLock = new ReentrantLock();
private final ReentrantLock putLock = new ReentrantLock();

// Permet concurrent put() et take()
public void put(E e) throws InterruptedException {
    putLock.lockInterruptibly();
    try {
        // Logique put
    } finally {
        putLock.unlock();
    }
}

Cas d'Usage Recommandés :

Producer-consumer avec débit élevé
Buffer flexible (unbounded ou bounded)
Pipeline asynchrone

PriorityBlockingQueue

Spécifications Techniques :

Structure interne : Tas binaire (binary heap) redimensionnable
Ordre : Priorité (Comparable ou Comparator)
Unbounded : Capacité illimitée
Thread-safety : Un seul lock global

Complexités Algorithmiques :

Opération	Complexité Temporelle	Blocking
`put(E e)`	O(log n)	Jamais (unbounded)
`take()`	O(log n)	Si vide
`peek()`	O(1)	Non-bloquant

Cas d'Usage Recommandés :

Task scheduling avec priorités
Event processing ordonné
Load balancing pondéré

DelayQueue

Spécifications Techniques :

Structure interne : PriorityQueue + délai d'expiration
Condition : Éléments disponibles seulement après expiration
Interface Delayed : getDelay() retourne temps restant

Cas d'Usage Recommandés :

Scheduled task execution
Cache avec TTL (Time To Live)
Rate limiting avec fenêtres temporelles

CopyOnWriteArrayList

Spécifications Techniques :

Stratégie : Copie complète du tableau à chaque modification
Thread-safety : Lectures complètement lock-free
Itérateurs : Snapshot à un instant T (pas de ConcurrentModificationException)
Performance : Optimisé pour lecture intensive, écritures rares

Complexités Algorithmiques :

Opération	Complexité Temporelle	Concurrence	Mémoire
`get(int index)`	O(1)	Lock-free	O(1)
`add(E e)`	O(n)	Synchronized	O(n) copie
`set(int index, E element)`	O(n)	Synchronized	O(n) copie
`remove(int index)`	O(n)	Synchronized	O(n) copie
`iterator()`	O(1)	Lock-free	O(1) référence

Mécanisme Copy-on-Write :

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);  // Copie complète
        newElements[len] = e;
        setArray(newElements);  // Atomic reference update
        return true;
    } finally {
        lock.unlock();
    }
}

Avantages/Inconvénients :

Avantages :

Lectures complètement lock-free
Itérateurs thread-safe sans synchronisation
Consistance forte pour les lecteurs

Inconvénients :

Écritures très coûteuses (O(n) + allocation mémoire)
Utilisation mémoire élevée pendant les modifications
Pas adapté aux modifications fréquentes

Cas d'Usage Recommandés :

Configuration partagée (lecture fréquente, update rare)
Liste d'observers/listeners
Cache read-mostly
Event subscribers lists

Collections Spécialisées

Ces collections répondent à des besoins spécifiques et offrent des optimisations particulières.

WeakHashMap

Spécifications Techniques :

Références : Clés stockées comme WeakReference
Garbage Collection : Entrées supprimées automatiquement quand clé collectée
Thread-safety : Non synchronisée
Usage principal : Cache avec gestion mémoire automatique

Complexités Algorithmiques :
Identiques à HashMap, avec overhead de gestion des WeakReference.

Mécanisme de Nettoyage :

private void expungeStaleEntries() {
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            Entry<K,V> e = (Entry<K,V>) x;
            int i = indexFor(e.hash, table.length);
            // Supprimer l'entrée de la table
        }
    }
}

Cas d'Usage Recommandés :

Cache avec éviction automatique
Metadata associée aux objets
Registry d'objets sans empêcher GC
Observer pattern avec cleanup automatique

Anti-Patterns :

Clés de type String literals (jamais collectées)
Clés primitives boxées (pool d'Integer)
Attente de collecte immédiate

IdentityHashMap

Spécifications Techniques :

Égalité : Utilise == au lieu de equals() pour les clés
Hashing : System.identityHashCode() au lieu de hashCode()
Structure : Arrays parallèles (pas de chaînage)
Capacité : Doit être puissance de 2

Complexités Algorithmiques :

Opération	Complexité Temporelle	Détails
`put(K key, V value)`	O(1) moyen, O(n) pire	Probing linéaire
`get(Object key)`	O(1) moyen, O(n) pire	Probing linéaire

Particularités d'Implémentation :

// Utilisation d'arrays parallèles au lieu de Entry objects
transient Object[] table; // [key0, val0, key1, val1, ...]

private int hash(Object x) {
    int h = System.identityHashCode(x);
    // Multiplication par constante de Knuth
    return ((h << 1) - (h << 8)) & (capacity - 1);
}

Cas d'Usage Recommandés :

Serialization/deserialization (éviter cycles)
Deep copy avec tracking d'objets
Debugging et profiling tools
Graph algorithms (éviter revisites)

EnumMap

Spécifications Techniques :

Structure interne : Simple array indexé par enum.ordinal()
Performance : Plus rapide que HashMap pour enums
Ordre : Ordre naturel des enum (déclaration)
Null : Clés null interdites, valeurs autorisées

Complexités Algorithmiques :

Opération	Complexité Temporelle	Détails
`put(K key, V value)`	O(1)	Accès direct array[key.ordinal()]
`get(Object key)`	O(1)	Accès direct
`remove(Object key)`	O(1)	Mise à null + décrémente size
`containsKey(Object key)`	O(1)	Test null sur array[ordinal]

Implémentation Interne :

public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V> {
    private transient Object[] vals;  // Valeurs indexées par ordinal
    private transient boolean[] hasMapping; // Présence d'un mapping

    public V put(K key, V value) {
        int index = key.ordinal();
        Object oldValue = vals[index];
        vals[index] = value;
        if (!hasMapping[index]) {
            hasMapping[index] = true;
            size++;
        }
        return (V) oldValue;
    }
}

Cas d'Usage Recommandés :

Mapping enum -> valeur (configuration, états)
State machines implementation
Remplacement efficace de switch/if sur enums
Statistiques par catégorie (enum)

BitSet

Spécifications Techniques :

Structure interne : Array de long (64 bits par élément)
Indexation : Bits indexés de 0 à Integer.MAX_VALUE
Opérations : Bitwise operations optimisées
Auto-extension : Grandit automatiquement si nécessaire

Complexités Algorithmiques :

Opération	Complexité Temporelle	Détails
`set(int bitIndex)`	O(1)	Opération bitwise
`get(int bitIndex)`	O(1)	Opération bitwise
`clear(int bitIndex)`	O(1)	Opération bitwise
`nextSetBit(int fromIndex)`	O(n/64) moyen	Parcours des longs
`and(BitSet set)`	O(min(size1, size2))	AND bitwise
`or(BitSet set)`	O(max(size1, size2))	OR bitwise
`cardinality()`	O(size/64)	Comptage des bits (Long.bitCount)

Opérations Bitwise Optimisées :

BitSet set1 = new BitSet();
BitSet set2 = new BitSet();

// Opérations ensemblistes efficaces
set1.and(set2);    // Intersection : set1 ∩ set2
set1.or(set2);     // Union : set1 ∪ set2
set1.xor(set2);    // Différence symétrique : set1 ⊕ set2
set1.andNot(set2); // Différence : set1 - set2

// Itération optimisée
for (int i = set1.nextSetBit(0); i >= 0; i = set1.nextSetBit(i + 1)) {
    // Traiter bit i
}

Cas d'Usage Recommandés :

Ensemble d'entiers avec plage dense
Filtres de Bloom (implémentation)
Masques de permissions/flags
Algorithmes sur graphes (visited sets)
Optimisation mémoire pour boolean arrays

Comparaison des Performances

Benchmarks par Type d'Opération

Opérations d'Accès (Get/Contains)

Collection	Complexité	Nano/op (indicatif)	Cas Optimal
`ArrayList.get(index)`	O(1)	2-5 ns	Accès direct array
`LinkedList.get(index)`	O(n)	50-500 ns	Index proche début/fin
`HashSet.contains()`	O(1) moyen	15-30 ns	Bonne distribution hash
`TreeSet.contains()`	O(log n)	40-80 ns	Arbre équilibré
`HashMap.get()`	O(1) moyen	10-25 ns	Pas de collisions
`TreeMap.get()`	O(log n)	50-100 ns	Arbre équilibré
`ConcurrentHashMap.get()`	O(1) moyen	15-35 ns	Lecture lock-free

Opérations d'Insertion (Add/Put)

Collection	Complexité	Nano/op (indicatif)	Notes
`ArrayList.add()`	O(1) amortie	5-15 ns	Sans redimensionnement
`LinkedList.add()`	O(1)	25-50 ns	Allocation nœud
`HashSet.add()`	O(1) moyen	20-40 ns	Sans collision
`TreeSet.add()`	O(log n)	60-120 ns	Avec rééquilibrage
`HashMap.put()`	O(1) moyen	15-35 ns	Sans collision
`TreeMap.put()`	O(log n)	70-140 ns	Avec rééquilibrage
`ConcurrentHashMap.put()`	O(1) moyen	30-60 ns	CAS + sync bucket

Opérations de Suppression (Remove)

Collection	Complexité	Nano/op (indicatif)	Performance Relative
`ArrayList.remove(index)`	O(n)	100-1000 ns	Décalage éléments
`LinkedList.remove(index)`	O(n)	200-2000 ns	Parcours + unlink
`HashSet.remove()`	O(1) moyen	25-50 ns	Hash lookup
`TreeSet.remove()`	O(log n)	80-160 ns	Rééquilibrage
`HashMap.remove()`	O(1) moyen	20-45 ns	Hash lookup
`TreeMap.remove()`	O(log n)	90-180 ns	Rééquilibrage

Utilisation Mémoire

Overhead par Élément

Collection	Overhead/Élément	Base + Facteur	Notes
`ArrayList<Integer>`	~4 bytes	16 + 4n	Array + Integer wrapper
`LinkedList<Integer>`	~24 bytes	48 + 24n	3 références + Integer
`HashSet<Integer>`	~32 bytes	64 + 32n	HashMap.Entry + Integer
`TreeSet<Integer>`	~40 bytes	48 + 40n	TreeMap.Entry + Integer
`HashMap<Integer,String>`	~48 bytes	64 + 48n	Entry + Integer + String ref
`ConcurrentHashMap<Integer,String>`	~56 bytes	64 + 56n	Extra metadata

Facteurs de Charge et Redimensionnement

Collection	Facteur de Charge	Capacité Initiale	Croissance
`HashMap`	0.75	16	2x
`HashSet`	0.75	16	2x
`ArrayList`	N/A	10	1.5x
`Vector`	N/A	10	2x
`ConcurrentHashMap`	0.75	16	2x

Recommandations par Cas d'Usage

Lectures Intensives (90%+ reads)

// Accès par index fréquent
List<T> list = new ArrayList<>();

// Lookup rapide, pas d'ordre
Set<T> set = new HashSet<>();
Map<K,V> map = new HashMap<>();

// Concurrent, lecture lock-free
Map<K,V> concMap = new ConcurrentHashMap<>();
List<T> snapshots = new CopyOnWriteArrayList<>();

Modifications Fréquentes

// Insertions/suppressions aux extrémités
Deque<T> deque = new ArrayDeque<>();

// Insertions/suppressions quelconques
Set<T> set = new HashSet<>();  // Plus rapide que TreeSet

// Ordre requis avec modifications
Map<K,V> map = new LinkedHashMap<>();  // Plus rapide que TreeMap

Contraintes Mémoire

// Minimum overhead
ArrayList<T> list = new ArrayList<>(exactSize);

// Enum mapping ultra-efficace
EnumMap<MyEnum, T> enumMap = new EnumMap<>(MyEnum.class);

// Ensemble d'entiers dense
BitSet bitSet = new BitSet();

// Cache auto-cleanup
WeakHashMap<K,V> cache = new WeakHashMap<>();

Multi-threading Haute Performance

// Map partagée haute perf
ConcurrentHashMap<K,V> map = new ConcurrentHashMap<>();

// Queue producer-consumer
BlockingQueue<T> queue = new LinkedBlockingQueue<>();

// Lock-free pour throughput maximum
Queue<T> lockFreeQueue = new ConcurrentLinkedQueue<>();

Bonnes Pratiques

Choix de Collection

Arbre de Décision

Besoin d'ordre ?
├─ Non
│  ├─ Doublons autorisés ? → List (ArrayList/LinkedList)
│  └─ Pas de doublons ? → Set (HashSet/LinkedHashSet)
└─ Oui
   ├─ Ordre naturel/custom ? → TreeSet/TreeMap
   ├─ Ordre d'insertion ? → LinkedHashSet/LinkedHashMap
   └─ Ordre par index ? → List (ArrayList preferred)

Multi-threading ?
├─ Lecture majoritaire ? → CopyOnWriteArrayList
├─ Producer-Consumer ? → BlockingQueue implementations
└─ General purpose ? → ConcurrentHashMap/ConcurrentLinkedQueue

Matrices de Choix

Pour Collections Simples :

Critère	ArrayList	LinkedList	HashSet	TreeSet	ArrayDeque
Accès par index	⭐⭐⭐⭐⭐	⭐	N/A	N/A	N/A
Insert début/fin	⭐⭐	⭐⭐⭐⭐⭐	N/A	N/A	⭐⭐⭐⭐⭐
Insert milieu	⭐	⭐	N/A	N/A	N/A
Recherche	⭐	⭐	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	⭐
Ordre requis	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	⭐	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐
Mémoire	⭐⭐⭐⭐	⭐⭐	⭐⭐⭐	⭐⭐	⭐⭐⭐⭐

Pour Maps :

Critère	HashMap	LinkedHashMap	TreeMap	ConcurrentHashMap
Performance get/put	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐⭐
Ordre insertion	⭐	⭐⭐⭐⭐⭐	⭐	⭐
Ordre naturel	⭐	⭐	⭐⭐⭐⭐⭐	⭐
Thread-safety	⭐	⭐	⭐	⭐⭐⭐⭐⭐
Navigation	⭐	⭐	⭐⭐⭐⭐⭐	⭐
Mémoire	⭐⭐⭐⭐	⭐⭐⭐	⭐⭐	⭐⭐⭐

Optimisations de Performance

Dimensionnement Initial

// BIEN : éviter les redimensionnements
List<String> list = new ArrayList<>(expectedSize);
Map<String, String> map = new HashMap<>(expectedSize * 4 / 3 + 1); // Facteur 0.75

// MAL : redimensionnements multiples
List<String> list = new ArrayList<>();  // Default 10
Map<String, String> map = new HashMap<>();  // Default 16

Réutilisation et Pooling

// BIEN : réutiliser les collections temporaires
private final List<String> tempList = new ArrayList<>();

public void process(Collection<String> input) {
    tempList.clear();  // Réinitialiser sans réallocation
    // ... logique de traitement
}

// MAL : création répétée
public void process(Collection<String> input) {
    List<String> tempList = new ArrayList<>();  // Allocation à chaque appel
    // ... logique de traitement
}

Choix d'Itération Optimale

// BIEN : itération optimisée selon le type
List<String> list = new ArrayList<>();
for (int i = 0, size = list.size(); i < size; i++) {
    String item = list.get(i);  // O(1) pour ArrayList
}

// BIEN : enhanced for ou stream pour LinkedList
LinkedList<String> linkedList = new LinkedList<>();
for (String item : linkedList) {  // O(1) par élément
    // traitement
}

// MAL : get(index) sur LinkedList
for (int i = 0; i < linkedList.size(); i++) {
    String item = linkedList.get(i);  // O(n) par accès = O(n²) total !
}

Bulk Operations

// BIEN : opérations bulk
Collection<String> source = Arrays.asList("a", "b", "c");
List<String> target = new ArrayList<>();
target.addAll(source);  // Une seule opération

// MAL : ajouts individuels
for (String item : source) {
    target.add(item);  // Multiple redimensionnements possibles
}

// BIEN : removeIf pour filtrage
list.removeIf(item -> item.startsWith("temp"));

// MAL : itération avec suppression manuelle
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    if (iter.next().startsWith("temp")) {
        iter.remove();  // Plus verbeux et potentiellement moins efficace
    }
}

Thread Safety et Concurrence

Synchronisation Appropriée

// BIEN : ConcurrentHashMap pour usage concurrent
Map<String, String> concurrentMap = new ConcurrentHashMap<>();

// BIEN : Collections.synchronizedXxx pour compatibilité
Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>());
synchronized (syncMap) {  // Synchronisation externe pour itération
    for (Entry<String, String> entry : syncMap.entrySet()) {
        // traitement thread-safe
    }
}

// MAL : HashMap sans synchronisation en environnement concurrent
Map<String, String> unsafeMap = new HashMap<>();  // Race conditions

Stratégies Concurrentes

// Pattern Producer-Consumer
BlockingQueue<Task> taskQueue = new LinkedBlockingQueue<>(1000);

// Producer
class Producer implements Runnable {
    public void run() {
        try {
            while (!Thread.currentThread().isInterrupted()) {
                Task task = generateTask();
                taskQueue.put(task);  // Bloque si queue pleine
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

// Consumer
class Consumer implements Runnable {
    public void run() {
        try {
            while (!Thread.currentThread().isInterrupted()) {
                Task task = taskQueue.take();  // Bloque si queue vide
                processTask(task);
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

// Cache Concurrent avec Compute
ConcurrentHashMap<String, ExpensiveObject> cache = new ConcurrentHashMap<>();

public ExpensiveObject getOrCompute(String key) {
    return cache.computeIfAbsent(key, k -> {
        // Calcul coûteux exécuté une seule fois par clé
        return createExpensiveObject(k);
    });
}

Gestion Mémoire

Éviter les Fuites Mémoire

// PROBLÈME : références fortes dans WeakHashMap values
WeakHashMap<Object, List<Object>> badCache = new WeakHashMap<>();
Object key = new Object();
List<Object> value = new ArrayList<>();
value.add(key);  // Référence circulaire ! key ne sera jamais collecté
badCache.put(key, value);

// SOLUTION : éviter les références circulaires
WeakHashMap<Object, String> goodCache = new WeakHashMap<>();
goodCache.put(key, key.toString());  // Pas de référence vers la clé

// PROBLÈME : listener non supprimé
List<EventListener> listeners = new ArrayList<>();
public void addListener(EventListener listener) {
    listeners.add(listener);  // Référence forte
}
// SOLUTION : WeakReference ou explicit removal
Set<WeakReference<EventListener>> listeners = new ConcurrentHashMap<>().newKeySet();

Optimisation Mémoire

// BIEN : taille appropriée pour éviter waste
List<String> list = new ArrayList<>(exactSize);
Map<String, Integer> map = new HashMap<>(size * 4 / 3 + 1);

// BIEN : trimToSize après construction
ArrayList<String> list = new ArrayList<>();
// ... populate list
list.trimToSize();  // Libère espace inutilisé

// BIEN : utiliser les collections spécialisées
EnumMap<Status, Handler> handlers = new EnumMap<>(Status.class);  // Plus efficace que HashMap
BitSet flags = new BitSet();  // Plus efficace que Set<Integer> pour indices denses

Sérialisation et Persistance

Sérialisation Personnalisée

public class CustomMap extends HashMap<String, String> {
    private static final long serialVersionUID = 1L;

    // Optimiser la sérialisation
    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(size());
        for (Entry<String, String> entry : entrySet()) {
            out.writeUTF(entry.getKey());
            out.writeUTF(entry.getValue());
        }
    }

    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        int size = in.readInt();
        for (int i = 0; i < size; i++) {
            put(in.readUTF(), in.readUTF());
        }
    }
}

Collections Immutables (Java 9+)

// BIEN : collections immutables factory methods
List<String> immutableList = List.of("a", "b", "c");
Set<String> immutableSet = Set.of("x", "y", "z");
Map<String, Integer> immutableMap = Map.of("one", 1, "two", 2);

// BIEN : collecteurs vers immutables
List<String> result = stream
    .filter(predicate)
    .collect(Collectors.toUnmodifiableList());

// ATTENTION : null non autorisé dans les factory methods
List<String> list = List.of("a", null, "b");  // NullPointerException !

Debugging et Monitoring

Outils de Diagnostic

// Monitoring de performance
public class CollectionProfiler {
    private final Map<String, Long> operationTimes = new ConcurrentHashMap<>();

    public <T> T timeOperation(String operationName, Supplier<T> operation) {
        long start = System.nanoTime();
        try {
            return operation.get();
        } finally {
            long duration = System.nanoTime() - start;
            operationTimes.merge(operationName, duration, Long::sum);
        }
    }

    public void printStats() {
        operationTimes.entrySet().stream()
            .sorted(Map.Entry.<String, Long>comparingByValue().reversed())
            .forEach(entry -> System.out.printf("%s: %d ns%n",
                entry.getKey(), entry.getValue()));
    }
}

// Usage
CollectionProfiler profiler = new CollectionProfiler();
List<String> result = profiler.timeOperation("list-creation",
    () -> new ArrayList<>(Arrays.asList("a", "b", "c")));

Validation et Tests

// Tests de performance comparatifs
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class CollectionBenchmark {

    @Benchmark
    public boolean arrayListContains() {
        return arrayList.contains(searchElement);
    }

    @Benchmark
    public boolean hashSetContains() {
        return hashSet.contains(searchElement);
    }
}

// Tests de thread-safety
public class ConcurrencyTest {
    @Test
    public void testConcurrentModification() {
        ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>();

        // Lancer plusieurs threads de modification
        ExecutorService executor = Executors.newFixedThreadPool(10);
        CountDownLatch latch = new CountDownLatch(1000);

        for (int i = 0; i < 1000; i++) {
            final int key = i;
            executor.submit(() -> {
                try {
                    map.put(key, "value" + key);
                    assertNotNull(map.get(key));
                } finally {
                    latch.countDown();
                }
            });
        }

        latch.await();
        assertEquals(1000, map.size());
    }
}

Anti-Patterns Courants

Éviter ces Erreurs

// ❌ MAL : modification pendant itération
List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
for (String item : list) {
    if (condition(item)) {
        list.remove(item);  // ConcurrentModificationException !
    }
}

// ✅ BIEN : utiliser Iterator.remove() ou removeIf()
list.removeIf(this::condition);

// ❌ MAL : comparaison référentielle sur collections
Map<String, String> map1 = new HashMap<>();
Map<String, String> map2 = new HashMap<>();
if (map1 == map2) {  // Toujours false même si contenu identique
}

// ✅ BIEN : utiliser equals()
if (map1.equals(map2)) {  // Compare le contenu
}

// ❌ MAL : utiliser Vector/Hashtable/Stack
Vector<String> vector = new Vector<>();  // Legacy, synchronisation inefficace
Stack<String> stack = new Stack<>();     // Hérite de Vector

// ✅ BIEN : alternatives modernes
List<String> list = Collections.synchronizedList(new ArrayList<>());
Deque<String> stack = new ArrayDeque<>();

// ❌ MAL : ne pas initialiser la capacité
Map<String, String> map = new HashMap<>();  // 16 -> 32 -> 64 -> ...
for (int i = 0; i < 1000; i++) {
    map.put("key" + i, "value" + i);  // Multiples redimensionnements
}

// ✅ BIEN : capacité appropriée
Map<String, String> map = new HashMap<>(1334);  // 1000 / 0.75 + margin

Patterns Avancés

Builder Pattern pour Collections

public class CollectionBuilder<T> {
    private final List<T> items = new ArrayList<>();

    public static <T> CollectionBuilder<T> builder() {
        return new CollectionBuilder<>();
    }

    public CollectionBuilder<T> add(T item) {
        items.add(item);
        return this;
    }

    public CollectionBuilder<T> addIf(boolean condition, T item) {
        if (condition) items.add(item);
        return this;
    }

    public List<T> toList() {
        return new ArrayList<>(items);
    }

    public Set<T> toSet() {
        return new LinkedHashSet<>(items);
    }
}

// Usage
List<String> result = CollectionBuilder.<String>builder()
    .add("always")
    .addIf(condition, "conditional")
    .add("final")
    .toList();

Decorateur pour Logging

public class LoggingMap<K, V> implements Map<K, V> {
    private final Map<K, V> delegate;
    private final Logger logger;

    public LoggingMap(Map<K, V> delegate) {
        this.delegate = delegate;
        this.logger = LoggerFactory.getLogger(delegate.getClass());
    }

    @Override
    public V put(K key, V value) {
        logger.debug("PUT: {} -> {}", key, value);
        V previous = delegate.put(key, value);
        logger.debug("PUT result: previous = {}", previous);
        return previous;
    }

    @Override
    public V get(Object key) {
        V result = delegate.get(key);
        logger.debug("GET: {} -> {}", key, result);
        return result;
    }

    // Déléguer toutes les autres méthodes...
}

Cache avec Politique d'Éviction

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(16, 0.75f, true);  // accessOrder = true
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }

    // Thread-safe version
    public synchronized V putIfAbsent(K key, V value) {
        return super.putIfAbsent(key, value);
    }
}

// Usage avancé avec TTL
public class TTLCache<K, V> {
    private final Map<K, CacheEntry<V>> cache = new ConcurrentHashMap<>();
    private final long ttlMillis;

    private static class CacheEntry<V> {
        final V value;
        final long timestamp;

        CacheEntry(V value) {
            this.value = value;
            this.timestamp = System.currentTimeMillis();
        }

        boolean isExpired(long ttl) {
            return System.currentTimeMillis() - timestamp > ttl;
        }
    }

    public TTLCache(long ttlMillis) {
        this.ttlMillis = ttlMillis;

        // Nettoyage périodique
        ScheduledExecutorService cleaner = Executors.newSingleThreadScheduledExecutor();
        cleaner.scheduleAtFixedRate(this::cleanup, ttlMillis, ttlMillis, TimeUnit.MILLISECONDS);
    }

    public V get(K key) {
        CacheEntry<V> entry = cache.get(key);
        if (entry == null || entry.isExpired(ttlMillis)) {
            cache.remove(key);
            return null;
        }
        return entry.value;
    }

    public void put(K key, V value) {
        cache.put(key, new CacheEntry<>(value));
    }

    private void cleanup() {
        cache.entrySet().removeIf(entry -> entry.getValue().isExpired(ttlMillis));
    }
}

Migration et Compatibilité

Migration Legacy vers Moderne

// Migration Vector -> ArrayList
// AVANT
Vector<String> vector = new Vector<>();
synchronized(vector) {
    for (String item : vector) {
        process(item);
    }
}

// APRÈS - Option 1: Collections.synchronizedList
List<String> list = Collections.synchronizedList(new ArrayList<>());
synchronized(list) {
    for (String item : list) {
        process(item);
    }
}

// APRÈS - Option 2: CopyOnWriteArrayList (si lecture majoritaire)
List<String> list = new CopyOnWriteArrayList<>();
for (String item : list) {  // Pas de synchronisation nécessaire
    process(item);
}

// Migration Hashtable -> ConcurrentHashMap
// AVANT
Hashtable<String, String> table = new Hashtable<>();

// APRÈS
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
// Opérations atomiques disponibles
map.computeIfAbsent("key", k -> expensiveComputation(k));

Interopérabilité

// Conversion entre types
public class CollectionUtils {

    // Array -> Collection
    public static <T> Set<T> arrayToSet(T[] array) {
        return new HashSet<>(Arrays.asList(array));
    }

    // Collection -> Array (type-safe)
    public static <T> T[] collectionToArray(Collection<T> collection, T[] array) {
        return collection.toArray(array);
    }

    // Defensive copying
    public static <T> List<T> defensiveCopy(List<T> original) {
        return original == null ? new ArrayList<>() : new ArrayList<>(original);
    }

    // Union sans doublons
    public static <T> Set<T> union(Collection<T> c1, Collection<T> c2) {
        Set<T> result = new HashSet<>(c1);
        result.addAll(c2);
        return result;
    }

    // Intersection
    public static <T> Set<T> intersection(Collection<T> c1, Collection<T> c2) {
        Set<T> result = new HashSet<>(c1);
        result.retainAll(c2);
        return result;
    }
}

Conclusion

Ce guide couvre les aspects essentiels des collections Java modernes, de leurs spécifications techniques aux bonnes pratiques d'utilisation. Les points clés à retenir :

Principes Fondamentaux

Choisir la bonne collection selon les patterns d'accès (lecture/écriture, ordre, unicité)
Dimensionner appropriément pour éviter les redimensionnements coûteux
Considérer la thread-safety dès la conception pour les environnements concurrents
Optimiser pour le cas d'usage plutôt que pour la généralité

Collections Haute Performance

HashMap/HashSet pour l'accès général O(1)
ArrayList pour l'accès séquentiel et par index
ArrayDeque pour les structures LIFO/FIFO
ConcurrentHashMap pour la concurrence haute performance
Collections spécialisées (EnumMap, BitSet) pour les cas spécifiques

Éviter les Pièges

Collections legacy (Vector, Hashtable, Stack)
Modification pendant itération sans Iterator
Mauvais dimensionnement initial
Synchronisation inefficace
Fuites mémoire avec WeakHashMap

La maîtrise des collections Java est essentielle pour écrire du code performant, maintenable et thread-safe. Ce guide fournit les bases techniques nécessaires pour faire les bons choix architecturaux.