Une analyse approfondie de la façon dont les tableaux PHP prennent en charge de manière flexible plusieurs types de données

Cet article vous apporte des connaissances pertinentes sur PHP. Il présente principalement comment les tableaux peuvent prendre en charge de manière flexible plusieurs types de données. Les amis intéressés peuvent jeter un œil ci-dessous.

En PHP, le traitement applicatif des structures de données de tableaux est très fréquemment utilisé. Par rapport aux langages fortement typés tels que Java et C++, les tableaux de PHP sont tout simplement trop simples à utiliser et peuvent stocker différents types de données. les types de données (tels que les nombres, les chaînes et même les objets, etc.) apportent une grande commodité au développement.

Sur la base des puissantes fonctionnalités des tableaux PHP, nous pouvons facilement implémenter des structures de données plus complexes, telles que des piles, des files d'attente, des listes, des ensembles, des dictionnaires, etc.

Avez-vous hâte de savoir : Comment PHP implémente-t-il les tableaux ?

1. La structure de données sous-jacente du tableau PHP

Le tableau PHP est implémenté en interne à l'aide de la structure HashTable, parlons donc d'abord brièvement de HashTable !

HashTable, également connue sous le nom de table de hachage, est une structure qui accède efficacement aux données via une clé-valeur. Une table de hachage est une combinaison d'un tableau et d'une liste chaînée, intégrant l'adressage rapide d'un tableau et l'insertion rapide d'une liste chaînée.

HashTable est principalement divisé en deux liens :

1. Fonction de hachage : La fonction de hachage convertit la valeur à trouver en un index numérique, et l'index numérique peut trouver rapidement l'emplacement de la valeur.

2. Collision de hachage : Idéalement, après le passage de différentes valeurs par la fonction de hachage, les résultats seront différents ; si différentes valeurs ont le même numéro après le hachage, nous appelons cela une collision de hachage.

Ainsi, lors de l'application de HashTable, vous devez faire face au problème de collision de hachage. Il existe deux solutions principales : la méthode de liste chaînée et la méthode d'adressage ouverte.

Dans le fichier zend_type.h, vous pouvez trouver la définition de la structure principale de HashTable comme suit :

type zend_array

Sélectionnez quelques membres clés à introduire :

• gc : comptage de références, utilisation du garbage collection .

• arData : Le tableau qui stocke les éléments dans la table de hachage, sa mémoire est continue, arData pointe vers la position de départ du tableau

• nTableSize : La capacité totale du tableau, c'est-à-dire le nombre ; d'éléments pouvant être hébergés, la mémoire d'arData La taille est déterminée en fonction de cette valeur. Sa taille est la puissance de 2, avec un minimum de 8, puis augmente en séquence selon 8, 16, 32... ;

Type Bucket

Bucket La structure est relativement simple, principalement utilisée pour stocker la clé et la valeur de l'élément, ainsi qu'un entier h (valeur de hachage, ou valeur de hachage).

• Si l'élément est un index numérique, sa valeur est la valeur de l'index numérique

• S'il s'agit d'un index de chaîne, alors sa valeur est la valeur de hachage de la clé calculée via l'algorithme Time33 ; La valeur de

h est utilisée pour finalement cartographier l'emplacement de stockage de l'élément.

2. Implémentation de base du tableau PHP

Dans la partie ci-dessus, nous avons découvert la structure des données de zend_array, puis regardons l'initialisation du tableau :

L'initialisation du tableau est principalement pour le paramétrage des membres de HashTable, la mémoire d'arData ne sera pas allouée immédiatement lors de l'initialisation. La mémoire d'arData sera allouée après l'insertion du premier élément.

Afin de mieux comprendre l'ensemble de la structure de hachage, donnons un exemple pour illustrer cette structure :

$data = array(
    'hello' => 'haha',
    1       => 'me to'
    'world' => 'world', 
    2       => 2
);
unset($data[1]);

Alors, à quoi devrait ressembler la structure de hachage ci-dessus ? À quoi doit ressembler le résultat stocké par arData ?

Dessinons une illustration pour le voir, c'est plus intuitif :

arData est un pointeur de type Bucket, utilisé pour stocker spécifiquement la clé et la valeur de chaque élément. Les données sont stockées dans l'ordre dans lequel les éléments sont. inséré, donc le tableau L'ordre est également garanti par cela.

Chaque élément du tableau arData, comme vous pouvez le voir sur l'image, le nombre négatif à gauche est la valeur après modulo la valeur de hachage, et l'index de l'arData à droite est stocké si -8 est en conflit, le L’élément head de la liste chaînée est stocké.

arData[0] : key='hello', h=xx (une valeur spécifique), val = 'haha'

arData[1] : val est le zval de type=IS_UNDEF (pas immédiatement après avoir été désactivé) a été supprimé et défini sur IS_UNDEF à la place)

arData[2] : key='world', h=xx (une valeur spécifique), val = 'world'

arData[3] : key=NULL, h=2 (un conflit de valeurs de hachage peut survenir), val = 2

….

L'exemple ci-dessus explique en détail la signification de nNumUsed, nNumOfElements, arData.

3. L'ordre des tableaux PHP

L'ordre de chaque élément du tableau est cohérent avec l'ordre d'insertion.

Afin d'assurer l'ordre des tableaux PHP, la table de hachage sous-jacente de PHP ajoute une table de mappage entre la fonction de hachage et le tableau d'éléments. Cette table de mappage est également un tableau, de la même taille que le tableau qui stocke les éléments. . Le type est un entier, utilisé pour enregistrer l'indice de l'élément dans le tableau ordonné stocké réel - les éléments sont insérés dans le tableau stocké réel dans l'ordre, puis l'indice du tableau est stocké dans le nouvel emplacement en fonction de la position hachée. par la fonction de hachage. Dans la table de mappage ajoutée :

De cette façon, l'ordre des données finales stockées peut être complété.

Cette table de mappage intermédiaire n'est pas explicitement identifiée dans la structure sous-jacente du tableau PHP, mais est placée avec arData Lorsque le tableau est initialisé, non seulement la mémoire utilisée pour stocker le Bucket est allouée, mais également le même nombre de. Les tailles uint32_t sont allouées. L'espace, ces deux espaces sont alloués ensemble, puis arData est décalé vers l'emplacement où le tableau d'éléments est stocké, et cette table de mappage intermédiaire est accessible via arData.

Résumé

La caractéristique des tableaux en PHP est de mapper les valeurs au type de clés. Contrairement à d'autres langages, les clés des tableaux en PHP peuvent être des chaînes et les valeurs peuvent être de n'importe quel type.

En plus des ajouts, suppressions, modifications et recherches réguliers, les tableaux comportent également de nombreuses autres opérations, telles que la copie, la fusion, la destruction, la réinitialisation, etc. Les codes correspondant à ces opérations se trouvent dans zend_hash.c. en apprendre davantage.

Apprentissage recommandé : "Tutoriel vidéo PHP"