Structures de données : tableaux, listes, arbres, tables de hachage

Un algorithme travaille sur des données, et la disposition de ces données décide de ce qu’il peut faire rapidement. Une structure de données, c’est cette disposition plus les opérations qu’elle permet — trouver, insérer, supprimer, parcourir dans l’ordre — chacune avec son coût au sens du grand O. Sur une vraie machine, la disposition décide aussi du bon fonctionnement des caches, ce qui peut compter tout autant.

Les tableaux

Un tableau range ses éléments les uns après les autres dans un seul bloc de mémoire. L’élément i se trouve à :

adresse de l’élément i = base + i × taille d’un élément

C’est une multiplication et une addition, quel que soit i : l’accès par indice est en O(1). Le x86 intègre cette formule dans ses modes d’adressage : mov eax, DWORD PTR [rsi+rcx*4] lit l’élément rcx d’un tableau d’int qui commence en rsi, en une seule instruction.

Le prix, c’est la rigidité. Insérer ou supprimer au milieu oblige à décaler tout ce qui suit, soit O(n). Un tableau dynamique (std::vector en C++, list en Python, Vec en Rust) grandit en allouant un bloc plus grand — d’un facteur constant, par exemple 2, ou 1,5 dans certaines implémentations — puis en recopiant. La plupart des ajouts coûtent alors O(1), et la recopie occasionnelle se répartit en O(1) par ajout : c’est un coût amorti en O(1).

Les listes chaînées

Une liste chaînée range chaque élément dans son propre nœud, avec un pointeur vers le suivant. Insérer ou retirer un nœud, une fois au bon endroit, coûte O(1) : il suffit de réécrire quelques pointeurs. Mais trouver l’élément i oblige à suivre i pointeurs, soit O(n).

Le tableau des grands O dit peu de chose du coût réel d’un parcours de liste. Les deux démos ci-dessous additionnent les mêmes 64 nombres, d’abord depuis un tableau, puis depuis une liste chaînée dont les nœuds sont dispersés en mémoire, un par ligne de cache, et chaînés dans un ordre mélangé — comme le sont d’habitude des nœuds alloués à des moments différents. Les deux passent par le même cache : 1 Ko, lignes de 64 octets.

Le tableau provoque 4 défauts pour 64 éléments : chaque ligne de 64 octets contient 16 int, donc un défaut apporte gratuitement les 15 suivants. La liste provoque 65 défauts — un par nœud, plus un pour le pointeur head — pour exactement les mêmes additions. Chaque nœud coûte deux accès, lire sa valeur et son pointeur next, et ils partagent une ligne : environ la moitié des accès réussissent. Mais chaque nœud est une nouvelle ligne.

C’est pire sur un vrai CPU que ne le laissent croire ces chiffres. Dans la boucle sur le tableau, l’adresse de l’élément suivant est connue à l’avance : un cœur à exécution dans le désordre et le préchargeur matériel peuvent aller chercher plusieurs lignes à la fois. Dans la liste, l’adresse du nœud suivant est la valeur qu’on charge : chaque défaut doit se terminer avant que le suivant puisse même commencer. C’est la poursuite de pointeurs (pointer chasing), qui sérialise tous les accès mémoire. Voilà pourquoi les listes chaînées sont souvent bien plus lentes que les tableaux en pratique, même pour des opérations où leur grand O est meilleur.

Piles et files

Deux structures simples se définissent par leur ordre d’accès plutôt que par leur disposition :

• une pile est « dernier entré, premier sorti » : push et pop au même bout. Un tableau avec un indice de sommet fait les deux en O(1). La pile d’appels est exactement cela, avec rsp comme indice de sommet.
• une file est « premier entré, premier sorti » : on ajoute à l’arrière, on retire à l’avant. Un tampon circulaire — un tableau dont les indices avant et arrière reviennent au début — fait les deux en O(1). Les frappes clavier, les paquets réseau et l’audio transitent par des tampons circulaires.

Les tables de hachage

Une table de hachage trouve une valeur par sa clé en O(1) en moyenne. Une fonction de hachage transforme la clé en nombre, et ce nombre modulo la taille de la table donne un compartiment (bucket), où l’entrée est rangée. Des clés différentes tombent parfois dans le même compartiment — une collision — et il existe deux façons classiques de la gérer :

• le chaînage : chaque compartiment contient une petite liste d’entrées ;
• l’adressage ouvert : en cas de collision, on essaie les compartiments suivants jusqu’à en trouver un libre. Les entrées restent dans un seul tableau, ce qui est bien plus favorable au cache.

La table reste rapide tant que son taux de remplissage — entrées divisées par compartiments — reste bas. Quand il devient trop élevé, la table alloue un tableau plus grand et réinsère tout. Comme la croissance d’un tableau dynamique, c’est O(n) de temps en temps et O(1) amorti par insertion.

Le pire cas est bien réel : si de nombreuses clés tombent dans le même compartiment, chaque recherche devient O(n). Des attaquants peuvent le provoquer exprès en envoyant des clés choisies pour entrer en collision, une attaque par déni de service appelée hash flooding. C’est pourquoi Python et Rust hachent les chaînes avec SipHash, une fonction de hachage paramétrée par un secret aléatoire, qui rend les collisions imprévisibles.

Les arbres

Un arbre binaire de recherche garde ses clés dans l’ordre : tout ce qui est dans le sous-arbre gauche d’un nœud est plus petit, tout ce qui est dans le droit est plus grand. Une recherche descend un seul chemin depuis la racine : elle coûte autant d’étapes que l’arbre est haut.

• si l’arbre est équilibré, sa hauteur vaut environ log₂ n, et recherche, insertion et suppression sont en O(log n), tout en gardant les clés triées. Les arbres rouge-noir et AVL se rééquilibrent à chaque insertion pour le garantir ; std::map en C++ et TreeMap en Java sont des arbres rouge-noir ;
• si rien ne le rééquilibre, insérer des clés déjà triées construit un arbre qui n’est qu’une longue chaîne, et chaque opération dégénère en O(n).

Les arbres binaires ont le problème de cache des listes chaînées : chaque descente est un pointeur à suivre. Un B-arbre règle cela avec des nœuds larges, qui contiennent chacun des dizaines ou des centaines de clés, avec un enfant par intervalle entre elles. L’arbre ne fait plus que quelques niveaux, et chaque nœud remplit une page de disque ou quelques lignes de cache. C’est pourquoi presque tous les index de bases de données et la plupart des systèmes de fichiers utilisent des B-arbres ou leur variante, les arbres B+.

Un tas (heap) est un arbre rangé dans un tableau : les enfants de l’élément i sont en 2i + 1 et 2i + 2. Il donne toujours le plus petit (ou le plus grand) élément en O(1), et insère ou retire en O(log n). C’est la file de priorité standard, et la structure au cœur du tri par tas.

Choisir une structure

Le conseil habituel découle des démos : commencer par un tableau, ou une table de hachage pour chercher par clé, et ne recourir aux structures à pointeurs que lorsque leurs opérations sont vraiment nécessaires.

À retenir

• Une structure de données, c’est une disposition en mémoire plus des opérations. Ses coûts en grand O et son motif d’accès comptent tous les deux.
• Les tableaux accèdent par indice en O(1) grâce à l’arithmétique d’adresses et sont favorables au cache. Les tableaux dynamiques ajoutent en O(1) amorti.
• Les listes chaînées insèrent en O(1) mais poursuivent des pointeurs : un défaut de cache par nœud, et des défauts qui ne peuvent pas se chevaucher.
• Les tables de hachage trouvent en O(1) en moyenne, à condition d’un bon hachage, d’un taux de remplissage bas et d’une protection contre les attaques par collision.
• Les arbres équilibrés gardent les clés triées avec des opérations en O(log n). Les B-arbres utilisent des nœuds larges pour réduire le nombre de niveaux, d’où leur usage dans les bases de données et les systèmes de fichiers.