Qu'est-ce que PHP HashTable ?
PHP HashTable fait référence à une table de hachage, qui est une structure de données à laquelle on accède directement en fonction de la valeur clé, c'est-à-dire qu'elle peut accéder aux enregistrements en mappant la valeur clé à un emplacement dans la table. , afin qu'il puisse Pour accélérer la recherche, le tableau stockant les enregistrements est une table de hachage.
La nouvelle version de HashTable
Par rapport à l'ancienne version de hashtable, les changements sont assez importants
Les éléments de l'ancienne version Le stockage est décentralisé. Bucket **arBuckets stocke l'adresse du pointeur pointant vers le bucket Le stockage des éléments de la nouvelle version est continu Bucket *arData
Là. Il y a 4 buckets dans l'ancienne version. Pointeurs Il n'y a qu'un seul pointeur dans le bucket dans la nouvelle version, et il n'est utilisé qu'en cas de collision de hachage
Il y a trois pointeurs de moins. un aperçu de la façon de suivre la nouvelle version de hashtable Traversée de l'ordre d'insertion et résolution des conflits de hachage
Regardez la définition de hashtable
typedef struct _zend_array HashTable; struct _zend_array { zend_refcounted_h gc; // 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; // hash表的掩码 用来确定hsh Bucket *arData; // bucket数组 uint32_t *arHash; // hashtable 查找 大小为nTableMask 存放指向bucket的指针(疑问在源码定义中未看到) uint32_t nNumUsed; // 元素个数 包含已删除的元素 uint32_t nNumOfElements; // 有效的元素个数 uint32_t nTableSize; // hash表的大小 uint32_t nInternalPointer; zend_long nNextFreeElement; dtor_func_t pDestructor; };
La définition du bucket
typedef struct _Bucket { zval val; zend_ulong h; //存的hash 值 用来寻找对比key zend_string *key; // 如果key是string 则存放key 如果是数字 则为空 } Bucket; typedef struct _zval_struct zval; struct _zval_struct { zend_value value; // value 真正的结构 union { struct { ZEND_ENDIAN_LOHI_4( zend_uchar type, /* active type */ zend_uchar type_flags, zend_uchar const_flags, zend_uchar reserved) /* call info for EX(This) */ } v; uint32_t type_info; } u1; union { uint32_t next; // 重点关注这个 存放hash 冲突下一个元素的位置 uint32_t cache_slot; /* literal cache slot */ uint32_t lineno; /* line number (for ast nodes) */ uint32_t num_args; /* arguments number for EX(This) */ uint32_t fe_pos; /* foreach position */ uint32_t fe_iter_idx; /* foreach iterator index */ uint32_t access_flags; /* class constant access flags */ uint32_t property_guard; /* single property guard */ uint32_t extra; /* not further specified */ } u2;
Schéma structurel
Tutoriel recommandé : "PHP"
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!