Qu'est-ce que PHP HashTable ?

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!