Choisir une structure de données
Parmi 1023 clés, une recherche linéaire d'une clé absente fait 1023 comparaisons, la recherche dichotomique en fait 10, et une table de hachage de 1023 alvéoles en a fait au plus 6 dans le labo.
Partir des questions qu'on posera
Aucune structure n'est la meilleure en tout. Chacune rend certaines opérations bon marché en en rendant d'autres coûteuses : pour choisir, il faut donc lister ce que ton programme fera le plus souvent. Le cours 6.006 du MIT répartit les possibilités en deux interfaces. Une séquence garde les éléments dans un ordre que tu décides (premier, deuxième, troisième), et on demande les éléments par position. Un ensemble garde les éléments par clé, et on demande si une clé est présente, ou la plus petite clé, ou la clé suivant une clé donnée. Un ensemble sans les questions d'ordre s'appelle un dictionnaire.
Quelques situations courantes et la réponse habituelle :
- Lire des éléments par position, ajouter à la fin : un tableau dynamique (un tableau JavaScript).
- Historique d'annulation, parenthèses à associer, parcours en profondeur : une pile, c'est-à-dire un tableau utilisé seulement à sa fin.
- Tâches traitées dans l'ordre d'arrivée, parcours en largeur : une file, avec un indice head ou un tampon circulaire plutôt que shift sur un long tableau.
- Chercher des choses par nom ou par identifiant : une table de hachage, c'est-à-dire Map ou Set en JavaScript.
- Garder les clés triées pendant les insertions et les suppressions, demander la clé suivante : un arbre binaire de recherche équilibré.
- Beaucoup d'insertions et de suppressions à un endroit qu'on tient déjà : une liste chaînée.
La même recherche dans cinq structures
Le labo ci-dessous stocke les mêmes clés de cinq façons et compte les comparaisons nécessaires pour trouver l'une d'elles. Les clés sont 15, 127 ou 1023 nombres entiers aléatoires. Le tableau non trié utilise la recherche linéaire. Le tableau trié utilise la recherche dichotomique. L'arbre équilibré a été construit en insérant d'abord les clés du milieu : il est donc aussi bas que possible. L'autre arbre a été construit à partir des clés dans l'ordre croissant : c'est donc une chaîne. La table de hachage a autant d'alvéoles que de clés et compte 1 pour le calcul de h(k).
Fais glisser pour tourner. Fais défiler ou pince pour zoomer.
Avec 15 clés, les différences sont faibles : la recherche linéaire demande 8 comparaisons en moyenne et la recherche dichotomique environ 3.3. Avec 1023 clés, elles ne le sont plus. La recherche linéaire fait en moyenne 512 comparaisons et en demande 1023 pour une clé absente, alors que la recherche dichotomique et l'arbre équilibré n'en demandent jamais plus de 10. L'arbre en chaîne est aussi mauvais que la recherche linéaire. La table de hachage reste entre 2.3 et 2.5 en moyenne à toutes les tailles car ses chaînes restent courtes, et dans ce labo son pire cas pour 1023 clés a été de 6. C'est pourquoi Map est le choix par défaut pour les recherches, et pourquoi les structures triées ne valent la peine que si l'on a aussi besoin de l'ordre.
| Par position | Obtenir l'élément i | Insérer ou supprimer au début |
|---|---|---|
| Tableau dynamique | 1 | n |
| Liste chaînée | n | 1 |
| Tableau trié | 1 | n |
| Par clé | Trouver | Insérer | Clé suivante |
|---|---|---|---|
| Tableau ou liste | n | n | n |
| Tableau trié | log n | n | log n |
| Table de hachage | 1 en moyenne | 1 en moyenne | n |
| ABR équilibré | log n | log n | log n |
Chaque case de ces deux tableaux donne l'ordre de croissance du coût pour n éléments, d'après les tableaux des notes de cours 2, 4 et 7 du MIT. Les tables de hachage et les arbres de recherche n'apparaissent que dans le second tableau car ils fonctionnent par clé, pas par position. Dans un tableau non trié ou une liste, insérer une clé coûte n car il faut d'abord vérifier qu'elle n'y est pas déjà. Le tableau trié trouve vite, mais il doit déplacer des valeurs pour faire de la place à une nouvelle clé.
Map ou objet ?
Les programmes JavaScript utilisent souvent un objet ordinaire comme dictionnaire, en écrivant prices["apple"]. MDN donne des raisons de préférer Map quand les clés viennent des données : un objet a un prototype, il contient donc des clés par défaut qui pourraient entrer en conflit avec les tiennes ; une Map peut utiliser n'importe quelle valeur comme clé, pas seulement des chaînes et des symboles ; sa taille est une simple propriété, map.size ; et on la parcourt dans l'ordre d'insertion. Les objets restent le choix naturel pour les enregistrements à ensemble fixe de champs nommés.
- 1953: La note d'IBM de H. P. Luhn propose le hachage dans des alvéoles avec chaînage.
- Vers 1956: L'IPL de Newell, Shaw et Simon apporte les listes chaînées.
- 1957: Bauer et Samelson déposent un brevet pour la méthode de la pile ; Fortran sort avec les tableaux.
- 1962: Adelson-Velsky et Landis publient l'arbre AVL, le premier arbre de recherche équilibré.
- 2015: ECMAScript 2015 ajoute Map et Set à JavaScript.
- Une recherche linéaire d'une clé absente parmi 1023 clés fait combien de comparaisons ?
- La recherche dichotomique parmi 1023 clés triées fait au plus combien de comparaisons ?
- Recherche linéaire sur 15 clés : quel est le nombre moyen de comparaisons sur l'ensemble des 15 clés ?
- Un ABR construit à partir de 127 clés insérées dans l'ordre croissant : combien de comparaisons pour la plus grande clé ?
- Un éditeur de texte a besoin de la fonction Annuler. Quelle structure convient ?
- File
- Pile
- Table de hachage
- Tableau trié
- Un serveur d'impression doit traiter les travaux dans leur ordre d'arrivée. Quelle structure convient ?
- File
- Pile
- ABR
- Liste chaînée utilisée comme une pile
- Tu dois chercher la fiche d'un utilisateur par son identifiant de nombreuses fois par seconde. Quel est le choix habituel en JavaScript ?
- Un tableau parcouru avec une boucle
- Une Map dont les clés sont les identifiants
- Une pile
- Une liste chaînée
- Tu dois garder des clés triées pendant les insertions et les suppressions, et tu demandes souvent la clé immédiatement supérieure. Quelle structure convient le mieux ?
- Table de hachage
- ABR équilibré
- File
- Tableau non trié
- Dans le vocabulaire du MIT 6.006, comment appelle-t-on un ensemble sans les opérations d'ordre ?
- une séquence
- un dictionnaire
- une pile
- une file
- D'après MDN, pourquoi un objet ordinaire peut-il être risqué comme dictionnaire pour des clés qui viennent des données ?
- Les objets ne peuvent pas contenir de chaînes
- Son prototype apporte des clés par défaut qui peuvent entrer en conflit avec les tiennes
- Les objets sont toujours plus lents que les tableaux
- Les objets oublient les valeurs au bout d'une seconde
- Choisis d'après les opérations que tu feras le plus souvent.
- Séquence : tableau, liste chaînée, pile, file. Ensemble : table de hachage, ABR.
- Pour 1023 clés : recherche linéaire jusqu'à 1023 comparaisons, recherche dichotomique et arbre équilibré jusqu'à 10.
- Map est le dictionnaire habituel en JavaScript ; utilise un arbre équilibré quand tu as aussi besoin de l'ordre.
Sources de ce cours (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
Consulté le: 2026-10-18