Structures de données essentielles : du tableau à la table de hachage

Tableau, liste chaînée, pile, file, table de hachage : à quoi elles servent et leurs coûts.

Choisir la bonne structure de données, c’est déjà résoudre la moitié du problème. Voici les incontournables, avec leurs coûts d’opérations.

Tableau (array)

Accès par index en O(1), mais taille fixe et insertion au milieu coûteuse (O(n)). La base de tout.

Liste chaînée

Insertion/suppression en O(1) si on tient le nœud, mais accès en O(n). Utile quand on insère/retire beaucoup aux extrémités.

Pile et file

Pile (LIFO) : dernier entré, premier sorti. Ex. annuler/refaire, appels de fonctions.
File (FIFO) : premier entré, premier sorti. Ex. files d’attente, parcours en largeur.

Table de hachage

La star : insertion, recherche et suppression en O(1) en moyenne. Le secret : une fonction de hachage qui répartit les clés.

Map<String, Integer> stock = new HashMap<>();
stock.put("pommes", 12);
stock.merge("pommes", 3, Integer::sum); // 15
Integer n = stock.getOrDefault("poires", 0); // 0

Attention : en cas de collisions massives, on peut dégénérer vers O(n). D’où l’importance d’un bon hashCode() — un grand classique des questions Java.

Le bon réflexe

Avant de coder, demande-toi : qu’est-ce que je fais le plus souvent ? Beaucoup de recherches par clé → table de hachage. Beaucoup d’insertions aux bords → file ou liste. Accès aléatoire par position → tableau. La structure suit l’usage.