Tableau associatif

En informatique, un tableau associatif (aussi appelé dictionnaire ou table d'association) est un type de données associant à un ensemble de clefs, un ensemble correspondant de valeurs. Chaque clef est associée à une seule valeur (au plus) : un tableau associatif correspond donc à une application de domaine fini en mathématiques. Du point de vue du programmeur, le tableau associatif peut être vu comme une généralisation du tableau : alors que le tableau traditionnel associe des entiers consécutifs à des valeurs, le tableau associatif associe des clefs d'un type arbitraire à des valeurs d'un autre type. Les opérations usuellement fournies par un tableau associatif sont : ajout : association d'une nouvelle valeur à une nouvelle clef ; modification : association d'une nouvelle valeur à une ancienne clef ; suppression : suppression d'une clef ; recherche : détermination de la valeur associée à une clef, si elle existe. Les tableaux associatifs sont utilisés couramment en informatique, par exemple dans les systèmes de fichiers, pour gérer la table des symboles des compilateurs durant l'analyse lexicale, pour accéder à la mémoire virtuelle, ou pour router les paquets dans un routeur. On peut voir un annuaire téléphonique comme un tableau associatif, où les noms constituent les clefs et les numéros de téléphone les valeurs. Un autre exemple est celui d'un dictionnaire (au sens traditionnel), où les mots sont les clefs et les définitions les valeurs. Une table de base de données constitue également un tableau associatif dans lequel les valeurs sont des enregistrements complets (lignes). Une base de données entière peut être vue comme un ensemble de tableaux associatifs liés par les contraintes que constituent les règles d'Edgar Codd. 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).