Loading AI tools
De Wikipédia, l'encyclopédie libre
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 :
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). Dans les routeurs, pour l'accès à la mémoire virtuelle, ou plus généralement quand le temps d'accès est très limité, un tableau associatif peut être implémenté au niveau matériel (voir mémoire adressable par contenu).
Dans la suite, n désigne le nombre d'éléments du tableau associatif.
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 :
Une manière inefficace (mais simple), de réaliser un tableau associatif (introduite dans Lisp en 1957) 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 :
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.
Code source C++ utilisant un tableau associatif via la classe map
de la bibliothèque standard :
#include <map>
#include <string>
using namespace std;
int main()
{
map <string, string> repertoire;
repertoire["Jean Dupont"] = "01.02.03.04.05";
repertoire["François Martin"] = "02.03.04.05.06";
repertoire["Louis Durand"] = "03.04.05.06.07";
return 0;
}
Le tableau associatif ci-dessus est aussi appelé dictionnaire notamment parce qu'il permet de faire des recherches rapides, sans parcourir le tableau entier.
Le langage OCaml fournit trois sortes de tableaux associatifs dans sa bibliothèque standard. La plus simple est une liste de paires :
# let m = ["Sally Smart", "555-9999";
"John Doe", "555-1212";
"J. Random Hacker", "553-1337"];;
val m : (string * string) list =
[("Sally Smart", "555-9999"); ("John Doe", "555-1212");
("J. Random Hacker", "553-1337")]
# List.assoc "John Doe" m;;
- : string = "555-1212"
La seconde est une table de hachage polymorphe :
# let m = Hashtbl.create 3;;
val m : ('_a, '_b) Hashtbl.t = <abstr>
# Hashtbl.add m "Sally Smart" "555-9999";
Hashtbl.add m "John Doe" "555-1212";
Hashtbl.add m "J. Random Hacker" "553-1337";;
- : unit = ()
# Hashtbl.find m "John Doe";;
- : string = "555-1212"
Enfin, la dernière est un dictionnaire purement applicatif (réalisé par des arbres AVL) :
# include (Map.Make(String));;
...
# let m = empty
|> add "Sally Smart" "555-9999"
|> add "John Doe" "555-1212"
|> add "J. Random Hacker" "553-1337";;
val m : string t = <abstr>
# find "John Doe" m;;
- : string = "555-1212"
Les listes de paires et les dictionnaires sont des structures de données persistantes, car purement fonctionnelles. Les tables de hachage sont au contraire des structures de données impératives, de meilleure efficacité que les listes et les AVL en général[réf. nécessaire].
En Javascript, les tableaux associatifs sont appelés objets, la classe de base se nommant Object
.
// définition de l'objet
const agenda = {
lundi: 'dodo',
mardi: 'dodo',
mercredi: 'resto'
}
// ajout dynamique de clés/valeurs
agenda.jeudi = 'apero'
// modification des clés/valeurs existante
agenda.mardi = 'apero'
delete agenda.lundi
// Pour obtenir une liste des clés
const jours = Object.keys(agenda)
// Pour obtenir une liste des valeurs
const activités = Object.values(agenda)
// Plusieurs manières de faire une boucle sur ces valeurs
for (const key in agenda) {
const value = agenda[key]
console.log(`${key} c'est ${value} : ça va être super bien`)
}
// ou bien
Object.keys(agenda).forEach(key => {
const value = agenda[key]
console.log(`${key} c'est ${value} : ça va être super bien`)
})
À noter que c'est de cette notation d'objet en javascript que vient le format standard d'échange de données JavaScript Object Notation, abrégé en JSON.
Code source PHP utilisant un tableau associatif :
$dico = array( "lundi"=>"dodo",
"mardi"=>"dodo",
"mercredi"=>"resto" );
echo $dico["lundi"];
foreach($dico as $key=>$value)
{
echo "Le $key c'est $value.";
}
Le même code en Perl :
%dico = (
lundi => 'dodo',
mardi => 'dodo',
mercredi => 'resto'
);
print "$dico{lundi}\n";
foreach $key (sort keys %dico)
{
print "Le $key c'est $dico{$key}.\n";
}
Sortie écran dans les deux cas :
dodo Le lundi c'est dodo Le mardi c'est dodo Le mercredi c'est resto
Code source Python créant et affichant le contenu d'un tableau associatif, plus communément appelé dictionnaire :
monuments = {"La tour Eiffel": "à Paris",
"La statue de la liberté": "à New-York",
"Le nombre de visiteurs de la tour Eiffel": 6930000
}
for clef in monuments.keys():
print("{} est {}".format(clef, monuments[clef]))
Comme le montre l'exemple, les dictionnaires peuvent contenir n'importe quel type de variable ou d'objets. Cette caractéristique est d'ailleurs aussi valable pour les listes ou les tuples. Le résultat sera :
La tour Eiffel est à Paris La statue de la liberté est à New-York Le nombre de visiteurs de la tour Eiffel est 6930000
Monuments est un tableau associatif de chaînes = [["La tour Eiffel", "à Paris"],
["La statue de la liberté", "à New-York"],
["Le nombre de visiteurs de la tour Eiffel", 6930000]
]
// Parcourt les monuments
POUR TOUT Valeur, Cle de Monuments
Trace("[%sCle%] est [%sValeur%]")
FIN
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.