Analyse du code source du noyau sous-jacent PHP8 - tableau (3)

Ce qui précède a entièrement analysé l'implémentation de la structure de base des tableaux en PHP et le principe de composition des index

S'appuyant sur les deux structures _Bucket et _zend_array

La complexité de o(1) est réalisée grâce à la fonction de hachage

Mais il y a un tableau d'index avant le bucket I. comprenais ce tableau d'index au moment où j'ai traversé de nombreux pièges

L'image ci-dessous est $c =array('x'=>1,'y'=>2,' z'=>3,'a '=>0); La structure de compartiment du tableau c

As mentionné ci-dessus, s'il s'agit d'un pack_array Le tableau d'index est toujours 2 et ne fonctionnera pas

Parce que s'il est compressé, la clé est directement nulle Il n'est pas nécessaire de calculer la valeur de hachage . Ce tableau d'index est uniquement utilisé pour localiser rapidement la valeur h

<.>

typedef struct _Bucket {
zval              val;   //数组的值 ( 复习下 zval只有16个字节)
zend_ulong         h;     // key的 h  值
zend_string      *key;      //当数组为 hash_array时候 会用到 也就是 key的值  
} Bucket;

Copier après la connexion

devrait être emballé

array Ne laissez pas val affecter vos idées d'apprentissage pour le moment. La valeur h est égale à l'indice de la position du tableau (les tableaux commencent tous à 0, donc l'indice. commence également à 0). Par exemple, $b =array(1=>'a',3=>'b',5=>'c'); Le tableau b est également un pack_array et a ce qui suit. structure

Parce que le tableau b ne définit pas la valeur du 0ème tableau, il n'est pas valide. [1] est 'a' Ici, j'ai directement marqué val=a(zval) sur l'image. En fait, c'est le zend_string de type string dans le zval de 16 octets. Ici, le gc que j'ai appris auparavant est utilisé. de nombreuses poupées gigognes infinies dans tous les codes sources du noyau PHP Vous passez en revue le passé et apprenez le nouveau.

Retournez en parler $c =array('x'=>1,'y'=>2,'z'=>3,'a'=>0);

La structure est la suivante

Cette valeur h est très grande. calculée en utilisant la clé à travers le temps33 Pourquoi est-ce appelé une valeur de hachage Je pense que c'est la valeur h calculée à travers le temps33 puis transformée en une table de hachage

Une table de hachage est principalement composée de deux parties : un tableau d'éléments de stockage et une fonction de hachage. Une simple fonction de hachage peut utiliser la méthode du reste. Par exemple, si la taille de la table de hachage est de 8, alors lorsque la table de hachage initialise le tableau, allouez un espace de 8 éléments. Suivez le code de hachage de la clé et divisez-le. par 8. La valeur obtenue est celle-ci L'index de l'élément dans le tableau. De cette façon, la clé peut être mappée à un emplacement spécifique dans la baie de stockage

Cependant, il y a un problème avec directement. implémentant le tableau de la manière ci-dessus : la position des éléments dans le tableau est aléatoire et elle n'est pas ordonnée

Le tableau en PHP est ordonné, il ajoute donc une table d'index entre la fonction de hachage et le tableau d'éléments. Cette table d'index est également un tableau. La taille est la même que celle du tableau dans lequel les éléments sont stockés. Cependant, le type d'élément qu'il stocke est toujours un entier, qui est utilisé pour enregistrer l'indice du tableau d'éléments dans le tableau stocké réel : les éléments sont insérés dans l'ordre stocké réel, puis l'indice du tableau est calculé en fonction de la fonction de hachage. La position est stockée dans l'index nouvellement ajouté.

La première étape consiste à calculer 4 puis à trouver -4 dans la table d'index. Parce que c'est le 0ème tableau, mettez-le. dans la table d'index La valeur du -4ème tableau est définie sur 0. Ensuite, le 0ème élément de la table du tableau réel est défini sur la clé des différents éléments de la table de hachage zval

réelle attribuée. la valeur de hachage calculée est La même chose est qu'un conflit de hachage se produira lors du pointage vers un indice dans la même table d'index. Étant donné que la table d'index ne peut stocker qu'un seul élément, PHP utilise la méthode zipper pour générer un conflit de hachage, qui consiste à extraire la valeur dans une liste chaînée. Vous pouvez vous référer à l'image ci-dessous "Analyse du noyau PHP7 - Qin Peng"

Situation normaleval.u2.next La valeur est -1, ce qui signifie qu'une fois qu'un conflit de hachage se produit avec la valeur initiale, la valeur ici pointera vers la vraie position du tableau avant le conflit.

▏Cet article a été publié sur le site Web PHP chinois avec le consentement de l'auteur original PHP Cui Xuefeng L'adresse originale : https://zhuanlan.zhihu.com/p/360952022.