Formations — 1 037 leçons en français

Accueil › Java › Choisir la bonne implémentation

Choisir la bonne implémentation

Les collectionsdebutant

Le nom de l'interface (List, Set, Map) dit ce qu'on peut faire ; le choix de l'implémentation détermine à quel coût.

Map<String, Integer> stockRapide = new HashMap<>();       // pas d'ordre garanti, le plus rapide
Map<String, Integer> stockOrdonne = new LinkedHashMap<>(); // ordre d'insertion conservé
Map<String, Integer> stockTrie = new TreeMap<>();          // toujours trié par clé

HashMap et HashSet reposent sur une table de hachage : chaque clé est rangée dans une case déterminée par son hashCode(). Deux clés equals doivent obligatoirement avoir le même hashCode() — sinon la table ne les retrouve plus. Une classe utilisée comme clé doit donc redéfinir equals() et hashCode() ensemble.

Que stockez-vous ? des couples clé → valeur des éléments sans doublon une liste ordonnée doublons permis Quel ordre vous faut-il ? aucun HashMap insertion LinkedHashMap trié par clé TreeMap aucun HashSet insertion LinkedHashSet trié TreeSet accès par index, le défaut ArrayList file ou pile ArrayDeque Hachage (HashMap, HashSet) : la classe de la clé doit redéfinir equals() ET hashCode(). Tri (TreeMap, TreeSet) : elle doit être Comparable, ou recevoir un Comparator.
LinkedList n'apparaît pas volontairement : son seul avantage réel est couvert par ArrayDeque, qui est plus rapide en pratique.

Les termes à connaître

ArrayList

Implémentation de List basée sur un tableau redimensionnable. Accès par index en O(1), ajout en fin en O(1) amorti, insertion/suppression ailleurs qu'en fin en O(n) (décalage des éléments). Le choix par défaut pour List.

LinkedList

Implémentation de List (et Deque) basée sur une liste doublement chaînée. Ajout/suppression en tête ou en queue en O(1), mais accès par index en O(n) : rarement le bon choix face à ArrayList.

Table de hachage (hashing)

Structure qui range les éléments dans des cases (« buckets ») déterminées par leur hashCode(). Elle permet de retrouver un élément en temps constant en moyenne, sans le comparer à tous les autres. HashMap, HashSet, LinkedHashMap et LinkedHashSet reposent dessus.

hashCode() / equals()

Deux méthodes liées par un contrat strict : si a.equals(b) est vrai, alors a.hashCode() == b.hashCode() doit être vrai. Une classe utilisée comme clé de Map ou élément de Set doit redéfinir les deux ensemble, jamais une seule.

Facteur de charge (load factor)

Seuil de remplissage (0.75 par défaut) au-delà duquel une table de hachage se redimensionne (généralement en doublant sa capacité) et redistribue tous ses éléments. Capacité initiale par défaut : 16.

TreeMap / TreeSet

Implémentations basées sur un arbre rouge-noir équilibré : les clés (ou éléments) sont toujours triées, et les opérations de base coûtent O(log n), garanti. Les clés/éléments doivent être Comparable ou fournis avec un Comparator.

LinkedHashMap / LinkedHashSet

Variantes de HashMap/HashSet qui ajoutent une liste doublement chaînée entre les entrées pour conserver l'ordre d'insertion (ou l'ordre d'accès, en option). Mêmes performances qu'une table de hachage classique, avec un léger surcoût mémoire.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.