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.
ArrayList(tableau redimensionnable) : le choix par défaut pourList. Accès par index en O(1).LinkedList(liste chaînée) est rarement préférable : son seul vrai avantage, l'ajout/suppression en O(1) en tête ou en queue, est mieux couvert parArrayDeque.HashMap/HashSet: les plus rapides (O(1) en moyenne), mais aucun ordre garanti.LinkedHashMap/LinkedHashSet: mêmes performances, en conservant l'ordre d'insertion.TreeMap/TreeSet: plus lentes (O(log n)), mais toujours triées.
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.
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
Listbasé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 pourList.- LinkedList
Implémentation de
List(etDeque) 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,LinkedHashMapetLinkedHashSetreposent dessus.- hashCode() / equals()
Deux méthodes liées par un contrat strict : si
a.equals(b)est vrai, alorsa.hashCode() == b.hashCode()doit être vrai. Une classe utilisée comme clé deMapou élément deSetdoit 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
Comparableou fournis avec unComparator.- LinkedHashMap / LinkedHashSet
Variantes de
HashMap/HashSetqui 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.
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.