Après une petite discussion en aparté, il s'est avéré que certaines personnes étaient intéressées pour en savoir d'avantages. Je vais tenter une explication plus approfondie.
Déjà, un tableau c'est quoi ? On commence par les tableaux indexés, les plus simples.
Il faut retourner dans nos premiers pas en C pour le comprendre. Une variable est simplement une adresse vers une zone mémoire. Typiquement, on va écrire var -> 0x001C. Quand on demande la valeur de la variable, on va en réalité lire la zone mémoire que la variable pointe. Ça c'est la base.
Une petite parenthèse : on peut lire plus d'une zone mémoire. Par exemple, quand on déclare des structures, ce sont des zones de mémoires (théoriquement contiguës, mais pas nécessairement, bref passons) qui regroupent plusieurs données.
Maintenant, un tableau c'est quoi ? Un tableau est nécessaire contiguë cette fois, c'est à dire que toutes les zones mémoires se suivent, il n'existe pas de zone vide ou libre d'une case à une autre. Pourquoi nécessairement contiguës ? Quand on accède à une entrée d'un tableau, on prend la valeur de la variable à laquelle on ajoute un décalage. En fait, on écrit ça de cette façon :
(*var) + i, c'est à dire que l'on prend l'adresse de la zone mémoire du tableau avec
*var (notation C) et on ajoute un décalage
i. Pour améliorer la lecture, C a une syntaxe alternative que l'on retrouve en PHP et d'autres langages, à savoir :
var. Un petit schéma pour expliquer tout ça : Code : Tout sélectionner
0x0012 <- *var
0x0013 <- *var + 1
0x0014 <- *var + 2
0x0015 <- donc var[3]
0x0016 <- var[4]
0x0017 <- etc. On comprend alors pourquoi la zone mémoire doit être contiguë ! Si on a un espace vide entre
var[3] et
var[4], alors comment effectuer le décalage comme il faut ?
On comprend aussi pourquoi on parle de tableaux indexés. En effet, on a notre adresse mémoire, et on ajoute un index (ou un décalage) pour accéder à une valeur.
Quelles sont les limitations ce système ?
Imaginer un tableau de plusieurs milliers d'entrées, alors : existe-t-il une zone mémoire suffisamment grande pour accueillir le tableau ? Il faudrait peut-être segmenter la mémoire, charger de nouvelles pages, faire des transferts de la mémoire physiques à la mémoire virtuelle, on aura des défauts de pages dans tous les sens, bref … Ce n'est pas du tout pratique !
On a alors trouvé l'idée des listes, et plus particulièrement des listes chaînées.
Le principe est simple : peu importe que la mémoire soit contiguë ou pas, chaque entrée/élément de la liste est disséminé en mémoire. Les éléments sont liés entre eux à travers les pointeurs. Typiquement on dit que le début de la liste est à un endroit précis de la mémoire (qu'il ne faut pas perdre, sinon galère pour retrouver …), on lit la valeur, et on demande à l'élément de nous dire où se trouve l'élément suivant. On a un chaînage entre les éléments :
Chaque
next contient l'adresse mémoire de la case suivante.
Comparaison entre les deux systèmes :
Lecture (donc recherche etc.) :
• un tableau est très rapide pour la lecture, il suffit de faire une simple addition ;
• une liste est lente pour la lecture, e.g. si on veut le 42ème élément, on doit lire les 41 premiers.
Insertion (on peut parler d'écriture, donc de tri etc.) :
• une insertion dans un tableau est très très lent et coûteux en mémoire : on doit décaler tous les éléments et si on n'a pas assez de place, on doit chercher un nouvel emplacement suffisamment grand (s'il n'existe pas, on recommence le partionnement, la segmentation etc.) ;
• une insertion dans une liste est triviale et très rapide : il suffit de modifier les pointeurs et le tour est joué.
Selon l'utilisation que l'on veut avoir, on choisira avec attention un tableau ou une liste.
Limitations des tableaux indexés : si on veut des clés un peu plus sophistiquées que des entiers incrémentés de 1, on peut toujours utiliser les listes mais on perd l'avantage des tableaux. (Exercice : comment utiliser les listes pour contenir valeurs ? Il suffit d'utiliser les structures, qui sont des types composés, tout bêtement). On aimerait conserver la rapidité des tableaux mais avec des clés différentes, comme des chaînes de caractères (réflexion : une chaîne de caractères n'est qu'un bête tableau indexé de caractères !).
Pour ça, on a trouvé les tableaux de hachages. Qu'est-ce que cette bête ? Ça permet une association clé/valeur à travers une table de symboles.
Le principe est d'associer la clé à un tableau d'index. Et chaque index est associé à une valeur. Typiquement :
Code : Tout sélectionner
clés index valeurs
hop 117 valeurA
taga 51 valeurB
daa 12 valeurC
zzz 42 valeurD Comment trouver l'index à partir de la clé ? C'est la fonction de hashage qui doit théoriquement s'en charger. En effet, un hash est censé fournir un entier unique qui va nous servir de clé. Ensuite, comment se fait la liaison entre l'index et la valeur ? On se base sur le fonctionnement d'un tableau indexé cette fois-ci, à savoir que l'on applique un décalage de la valeur de l'index sur l'adresse mémoire initiale du tableau.
On peut améliorer le système avec des liaisons plus fines, des indexations bi-directionnelles et ce genre de chose, mais bon, j'explique le principe général
.
Ça nous permet alors d'avoir des clés de plusieurs types pour un tableau.
Mais surtout, on peut parler de tableau … associatif !
En réalité, il existe deux façons répandues de coder les tableaux associatifs : à travers des tableaux de hachages ou des arbres équilibrés. Ceux qui ont fait de la programmation fonctionnelle avec Scheme par exemple connaissent bien ça. La notion de paires y est très forte. C'est une autre façon d'utiliser les tableaux associatifs.
Petit état des lieux rapides : un tableau indexé est forcément plus rapide que tout. On a un minimum d'opérations, on ne peut pas rivaliser. Un tableau associatif par hachage est plus lent mais les opérations (lecture et écriture) restent très proche d'un tableau indexé. Certes, on a plus d'opérations (rien que le hachage par exemple coûte un peu de calcul), mais c'est négligeable. Un tableau associatif par arbre équilibré à d'autres avantages et inconvénients que je ne développerai pas ici (je n'ai même pas abordé la notion d'arbre aussi).
On peut donc utiliser les tableaux associatifs car ils offrent de grands services et sont très raisonnables en terme de coût (calcul, mémoire, complexité etc.).
Revenons à nos moutons !
Et PHP dans tout ça ? PHP utilise uniquement des
HashTables (tableau de hachage). Je n'ai jamais vu qu'il utilisait autre chose dans les sources. En réalité, il utilise une structure qui contient le tableau et d'autres informations, comme la taille (voir la structure
Bucket — sac, différent d'un ensemble ou d'une liste — et la variable
nKeyLength si mes souvenirs sont bons) par exemple.
Un tableau de hachage donc. Ce qui nous permet d'utiliser des clés qui sont des entiers ou des chaînes de caractères. Dans tous les cas, il transforme la clé en hash, on trouve l'index dans la table des index, et on retrouve la valeur de la clé.
Quelles sont le type de clés pour PHP ?
Petit rappel sur les types. PHP a un typage dynamique (
grosso modo non déclaré) et faible. Faible ne signifie pas qu'il est mauvais mais qu'il permet une conversion de type implicite aisée. PHP appelle ça le
type juggling, on peut aussi parler de transtypage (ou de
cast). Concrètement, c'est le fait de pouvoir passer d'un type à l'autre : d'un entier à une chaîne, d'une chaîne à un booléen etc. Dans PHP, cette notion de conversion implicite est très présente. En effet, il nous permet beaucoup de conversions que dans d'autres langages à typage faible. Conséquence immédiate : plus grande facilité dans le maniement des données mais des résultats parfois étranges,
i.e. non triviaux, voire même des bugs introuvables … Il faut donc manipuler les conversions implicites de types avec beaucoup de précautions.
Retour à nos tableaux. Les clés peuvent être de deux types (plus un cas particulier) : soit un nombre (entier —
integer — ou flottant —
float ou
double, PHP ne fait pas la différence —), soit une chaîne de caractères.
Donc :
$a = array();
$a[42] = 'hello';
$a['seven'] = 'world';
$a['3'] = '!';
sont des notations tout à fait justes dans PHP.
Maintenant, le cas particulier dont je parlais.
On trouve la syntaxe suivante :
$a[] = 'dummy value';
qui signifie que l'on prend la dernière clé entière — après conversion en entier — (on n'oublie pas la notion de hash, ce n'est pas l'index mais la clé dont on parle, elle est donc typée soit en entier ou en chaîne de caractères) et on lui ajoute 1. Petite parenthèse encore, PHP considère
[ et
] comme un opérateur.
Un exemple est plus parlant :
$a['7'] = 'a';
$a[] = 'b';
$a[42] = 'c';
$a[] = 'd';
print_r($a);
affichera :
Le caractère 7 est converti en entier, donc ça devient
(string) 7 => (int) 7. On veut auto-incrémenter, ça passe donc à
(int) 8 etc. On a l'impression d'avoir un tableau indexé, mais on est toujours dans un tableau de hachage. Si on était dans un tableau indexé, les clés seraient successives,
i.e. on commencerait forcément à 0 pour avoir une suite :
u_n = n pour les index suivants.
Grosso modo, on aurait une numérotation.
Oui mais que fait PHP quand il auto-incrémente ? On rappelle que l'on peut mélanger le type des clés car on est dans un tableau de hachage à double type : nombre et chaîne de caractères.
On a dit qu'il prenait la dernière clé … donc il est obligé de parcourir tout le tableau pour chaque incrémentation. Si on commence à 0, on va dire qu'il est dans un mode « normal », ou plutôt naturel. Il va se comporter comme un tableau indexé et ne va se poser aucune question. La dernière clé utilisée sera la taille du tableau - 1, trivialement.
Si on commence à mélanger les clés (nombre et chaîne), il va devoir se rappeler de l'index le plus grand : la taille du tableau ne suffit plus, il faut une temporisation quelque part.
Enfin, si en plus on a des entiers qui ne se suivent pas et que l'on a fait des manipulations étranges ou douteuses, PHP va être obligé de relire l'ensemble du tableau pour retrouver la clé (puis la temporiser, jusqu'à une prochaine manipulation étrange).
Ça explique la différence de temps pour l'insertion (l'écriture) dans un tableau de hachage par PHP.
Quoi faire alors ?
Si on utilise un tableau avec des clés entières, on essaye de conserver cette notion tout le long. C'est plus facile pour le développeur car il aura des traitements standards et plus facile pour PHP. Si on utilise des chaînes de caractères en clés, on ne va pas tout d'un coup utiliser un entier pour les raisons d'uniformité citées précédemment. Et de plus, il serait totalement incohérent de vouloir auto-incrémenter un tableau dont les clés sont des chaînes de caractères !
PHP permet de faire beaucoup de choses et n'est pas regardant sur la méthodologie, toutefois il est bon d'avoir une certaine logique et de s'y tenir. On y gagnera à tous les niveaux : PHP sera content et nous aussi.
Wala, c'était un « petit » rappel sur les tableaux
. Satisfait ?
Pour aller plus loin (j'aimerais bien que vous répondiez au moins au deux dernières questions car en rapport avec le sujet, histoire de voir si vous avez suivit
) :
• on peut s'intéresser aux arbres (c'est passionnant) qui ont des applications incroyables ;
• on peut s'intéresser aux arbres équilibrés pour pouvoir tenir le comparatif avec les tableaux de hachages (pour représenter des tableaux associatifs, on le rappelle) ;
• on peut lire les sources de PHP : php5.x.x/ext/standard/arrray.c et php_array.h ;
• pourquoi on ne déclare jamais la taille d'un tableau en PHP ?
• comment la mémoire est gérée par PHP à propos des tableaux, comme la suppression/libération (réponse dans les sources) ?
Et bien sûr, on peut toujours m'en demander d'avantages si je peux y répondre
.
et là j'aurais parié moins.