Tableau associatif - Définition

Structures de données pour les tableaux associatifs

Les tableaux associatifs sont le plus souvent utilisés lorsque l'opération de recherche est la plus fréquente. Pour cette raison, la conception privilégie le plus souvent cette opération, au détriment de l'efficacité de l'ajout et de l'occupation mémoire par rapport d'autres structures de données (telles que les listes d'association). Dans de rares cas, un tableau associatif peut être implémenté à un niveau matériel (voir mémoire adressable par contenu).

Représentations efficaces

Deux structures de données se montrent efficaces pour représenter les tableaux associatifs : la table de hachage et l'arbre équilibré. Les avantages et inconvénients respectifs de ces deux solutions sont les suivants :

• Les tables de hachage ont une meilleure complexité en moyenne pour l'insertion et la recherche (O(1)), alors que les arbres équilibrés ont une meilleure complexité dans le pire des cas (O(log(n)), au lieu de O(n) pour les tables de hachage).
• Les tables de hachage ont une représentation mémoire généralement plus compacte.
• Les arbres équilibrés peuvent aisément fournir des structures de données persistantes, ce qui est particulièrement mis en avant dans la programmation fonctionnelle.
• Les tables de hachage nécessitent la définition d'une bonne fonction de hachage, ce qui peut être difficile à réaliser dans certains cas, alors que les arbres équilibrés ne demandent qu'un ordre total sur les clefs. Inversement, les tables de hachage peuvent être utilisées sur des clefs non ordonnées.
• Les arbres équilibrés préservent l'ordre des clefs, permettant notamment d'effectuer un parcours des clefs dans l'ordre ou de localiser efficacement une clé proche d'une valeur donnée. Les tables de hachage, en revanche, ne préservent pas l'ordre des clefs (lorsqu'il existe).

Listes d'association

Une manière inefficace (mais simple), de réaliser un tableau associatif est une liste d'association, liste chaînée de paires clef-valeur. La recherche consiste alors à parcourir séquentiellement la liste jusqu'à trouver une clef donnée ; elle est donc de complexité O(n). La liste d'association possède les avantages suivants :

• Aucune fonction sur les clefs n'est nécessaire (telle qu'une relation d'ordre ou une fonction de hachage).
• L'ajout est réalisable en temps constant (il suffit de l'effectuer en tête de liste).
• Pour de très petits tableaux associatifs (premiers téléphones mobiles, par exemple), les listes d'associations consomment moins de mémoire que d'autres structures de données.

Représentations spécialisées

Si les clefs ont un type particulier, il est parfois possible d'obtenir de meilleures performances en utilisant une structure de données spécialisée. Par exemple, il est possible d'utiliser un arbre de Patricia si les clefs sont des entiers (lorsque les clefs sont trop clairsemées pour qu'un tableau traditionnel puisse être utilisé). D'une manière plus générale, un trie peut être utilisé dès que les clefs ont une structure de mots. On évite alors de nombreuses comparaisons lorsque plusieurs clefs ont des préfixes communs, ce qui est le cas par exemple dans les tables de routage.