Introduction à la structure de base des tableaux php

Cet article vous apporte une introduction à la structure de base du groupe. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'il vous sera utile.

Ce qui suit est la structure de base, le processus d'insertion, de recherche et de remaniement du tableau PHP.

Structure de base :

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    consistency)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask; // 哈希值计算掩码，等于nTableSize的负值(nTableMask = -nTableSize)
    Bucket            *arData;     // 存储元素数组，指向第一个Bucket
    uint32_t          nNumUsed;   // 已用Bucket数
    uint32_t          nNumOfElements; // 哈希表有效元素数 = nNumUsed - num(is_undef)
    uint32_t          nTableSize;   // 哈希表总大小，为2的n次方, 最小为8
    uint32_t          nInternalPointer;  // 怀疑是内部指针
    zend_long         nNextFreeElement; // 下一个可用的数值索引 arr[] = 1;arr["a"] = 2;arr[] = 3;  则nNextFreeElement = 2;
    dtor_func_t       pDestructor;
};

typedef struct _Bucket {
    zval              val;  // 存储的具体value
    zend_ulong        h;    // hash value (or numeric index)  
    zend_string      *key;  // string key or NULL for numerics
} Bucket;

Explication :

Lors du stockage du tableau, enregistrez d'abord la valeur dans l'ordre, puis enregistrez la position de la valeur.

Le tableau qui stocke les enregistrements est appelé table de hachage. Ce tableau est utilisé pour stocker les valeurs, et les valeurs sont enregistrées dans l'ordre. Leurs emplacements de stockage seront enregistrés dans l'idx obtenu en calculant le hachage du. clé modulo nTableMask.

Lorsque le tableau est initialisé, la taille minimale est de 8, soit 16, 32, 64. . .

La zone idx créée lors de l'initialisation du tableau sera toutes initialisée à -1, et sera également initialisée à -1 lors du rehachage.

Lorsqu'un élément est supprimé du tableau, le type de l'élément supprimé est marqué comme is_undef et nNumOfEmelment - 1. Si l'élément est le dernier élément, alors nNumUsed - 1.

Insérer :

Prenez $arr = ['a'=>1, 'b'=>2] comme exemple :

Mettez d'abord 1 dans le tableau, son val.u2.next = -1, calculez le hachage en fonction de son indice a, puis prenez le hachage modulo nTableMask pour obtenir un idx, et sauvegardez l'index nindex du 1 précédent à la position de l'idx.

Stockez à nouveau 2, son val.u2.next = -1 Si le hachage calculé en fonction de son indice b modulo nTableMask a déjà une valeur dans l'idx, alors cela signifie qu'une collision de hachage s'est produite. cette fois, la valeur dans l'idx actuel est extraite et enregistrée dans le val.u2.next actuel, et l'index nindex de 2 est enregistré dans l'idx actuel, et ainsi de suite.

Recherche :

Calculez le hachage en fonction de l'indice a, prenez le modulo nTableMask et obtenez un idx, récupérez la valeur nindex dans l'idx et recherchez-la dans arData . Si la position est trouvée La clé dans != a, alors elle ne peut pas être trouvée ; si la clé dans la position trouvée == a, alors vérifiez sa valeur u2.next. Si elle est -1, alors elle est trouvée ; n'est pas -1, cela signifie qu'il est en cours d'insertion. Si un conflit de hachage se produit, continuez la recherche dans arData selon u2.next jusqu'à ce qu'il soit trouvé.

rehash : lors de

rehash, réinitialisez d'abord tous les enregistrements de la zone nindex à -1, puis déplacez le pointeur *p à partir du premier élément si le. L'élément n'est pas marqué comme is_undef, puis recalculez le hachage de clé de l'élément et placez-le dans nindex, puis bouclez, p++. Si l'élément est marqué comme is_undef, continuez à déplacer le pointeur p++ et définissez un nouveau pointeur j pour pointer vers la position. Continuez la boucle et déplacez les éléments qui ne sont pas is_undef vers l'avant, un par un. , j rencontre is_undef. Il ne bougera pas tant qu'une valeur ne lui sera pas attribuée. Déplacez-vous jusqu'au dernier nNunUsed, puis attribuez j à nNunUsed, puis insérez des éléments à partir de cette position, et les éléments précédents seront directement écrasés.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!