PHP Core - une brève explication de PHP Soul HashTble

Un. Préface

HashTable est l'âme de PHP, car HashTable est largement utilisé dans le moteur Zend, comme la table de variables, la table de constantes, la table de fonctions, etc., qui sont adaptées au stockage HashTable. De plus, le tableau de PHP est également implémenté à l'aide de HashTble, donc ce n'est qu'en comprenant le HashTable de PHP que vous pourrez vraiment comprendre PHP.

Pour faciliter la lecture, voici les concepts de base qui apparaissent dans l'implémentation de HashTable . Une table de hachage est une structure de données qui mappe des clés spécifiques à des valeurs spécifiques via une fonction de hachage. Elle maintient une correspondance biunivoque entre les clés et les valeurs.

• Clé : Un indicateur utilisé pour manipuler des données, comme un index dans un tableau PHP, ou une clé de chaîne, etc.

• Slot/bucket : une unité dans la table de hachage utilisée pour stocker les données, qui est le conteneur dans lequel les données sont réellement stockées.

• Fonction de hachage : une fonction qui mappe la clé à l'emplacement de l'emplacement où les données doivent être stockées.

• Collision de hachage : situation dans laquelle une fonction de hachage mappe deux clés différentes au même index.

La table de hachage en PHP est implémentée dans Zend/zend_hash.h. Examinons d'abord la structure des données dans l'implémentation de PHP. PHP utilise les deux structures de données suivantes pour implémenter la table de hachage. La structure HashTable est utilisée pour enregistrer les informations de base nécessaires à l'ensemble de la table de hachage, tandis que la structure Bucket est utilisée pour enregistrer le contenu des données spécifiques, (voir la fin pour le code source spécifique)

Deux. Exemple

Alors, en prenant la création d'une variable comme exemple, que se passe-t-il exactement sous le capot ?

Étapes pour créer des variables : $str = "hello";

1 : Créez une structure zval et définissez son type IS_STRING

2 : Définissez sa valeur sur hello

3 : Ajoutez-le à la table des symboles

{    
zval *fooval;     
MAKE_STD_ZVAL(fooval);    
ZVAL_STRING(fooval, "hello", 1);    
ZEND_SET_SYMBOL( EG(active_symbol_table) ,  "foo" , fooval);
}

Les deux premières étapes ont été mentionnées dans la structure des variables de l'article précédent, Pour plus de détails, voir Mécanisme de stockage du noyau PHP (séparation/changement)

Qu'est-ce que la table des symboles ?

Réponse : La table des symboles est une table de hachage . Le nom de la variable y est stocké -> L'adresse de la structure zval de la variable

// zend/zend_globals.h 161 lignes de table de symboles

struct _zend_executor_globals { 
      ...   
      ...	
HashTable *active_symbol_table; /*活动符号表*/	
HashTable symbol_table;		/* 全局符号表 */	
HashTable included_files;	/* files already included */
     ...
}

Lorsqu'une fonction est exécutée, la "structure d'environnement d'exécution" de la fonction sera générée, y compris le nom de la fonction, les paramètres, les étapes d'exécution, la classe (s'il s'agit d'une méthode), et une table de symboles générée pour cette fonction. La table de symboles est uniformément placée sur la pile et active_symbol_table pointe vers la table de symboles nouvellement générée

Zend/zend_compiles. .h ligne 384, structure de l'environnement d'exécution :

struct _zend_execute_data {
	struct _zend_op *opline;
	zend_function_state function_state;
	zend_op_array *op_array;//函数编译后的执行逻辑，编译后的opcode二进制代码，称为op_array
	zval *object;
	HashTable *symbol_table;//此函数的符号表地址
	struct _zend_execute_data *prev_execute_data;
	zval *old_error_reporting;
	zend_bool nested;
	zval **original_return_value;
	zend_class_entry *current_scope;
	zend_class_entry *current_called_scope;
	zval *current_this;  
	struct _zend_op *fast_ret; /* used by FAST_CALL/FAST_RET (finally keyword) */
	call_slot *call_slots;
	call_slot *call;
};

Ce qui précède est la table des symboles lorsque la fonction actuelle est exécutée.

À l'aide de l'exemple suivant, nous décrirons l'allocation par PHP de divers espaces de stockage lors de l'exécution de la fonction et expliquerons pourquoi les variables statiques de PHP peuvent être partagées.

Lorsqu'une fonction est exécutée, la "structure d'environnement d'exécution" de la fonction sera générée, y compris le nom de la fonction, les paramètres, les étapes d'exécution et la classe (si elle est une méthode), Et générez une table de symboles pour cette fonction. La table de symboles est placée sur la pile. Et pointez active_symbol_table vers la table de symboles nouvellement générée

解释：

1.执行t1时，形成t1的环境结构体，t1调入到执行栈，t1也有自己的符号表，符号表里边存储的变量对应这个t1环境(局部变量嘛)

2.执行t1到第三行，执行了t2，形成t2的环境结构体，t2入栈，t2也有自己的变量自己的符号表，与t1互不影响。

3.假使t1函数内部出现了递归调用t1，此时会生成第二个t1环境结构体，和【1】中是两个结构体，互不影响

函数执行时的栈变化

当函数调用时,为此函数生成了一个”执行环境变量”的结构体,里面存储了当前函数的名称,参数,对应的类....等等信息.称为_zend_execute_data {}结构体

struct _zend_execute_data {
	struct _zend_op *opline;
	zend_function_state function_state;
	zend_op_array *op_array;//函数编译后的执行逻辑，编译后的opcode二进制代码，称为op_array
	zval *object;
	HashTable *symbol_table;//此函数的符号表地址
	struct _zend_execute_data *prev_execute_data;
	zval *old_error_reporting;
	zend_bool nested;
	zval **original_return_value;
	zend_class_entry *current_scope;
	zend_class_entry *current_called_scope;
	zval *current_this;  
	struct _zend_op *fast_ret; /* used by FAST_CALL/FAST_RET (finally keyword) */
	call_slot *call_slots;
	call_slot *call;
};

这个结构体中,有2个重要的信息需要注意！:

{

*op_array ------>是函数的执行步骤，公用（静态变量字段存储于此！所以改一次依赖于此逻辑的函数全修改！）

*hash_table---->symbol_table 这个函数对应的符号表

}

 

思考一下: 1个函数,递归调用自己3次, 如t1

问：在栈上,肯定要有3个 execute_data生成.但是,这3个execute_data--->对应几个*op_array;

答:函数编译完了,生成一份*op_array,因为函数的执行逻辑是固定的.

 

问：生成了几个 symbol_table?

答：生成3个符号表.

结论：

1.每一个函数调用是都会生成自己的环境栈和符号表栈，不同的环境栈对应了自己的符号表栈，所以每个函数中的变量常量等，他们是有对应函数内的作用域限制

2.虽然每次会生成不同的环境栈与作用域，但是如果调用的是同一个函数，其 *op_array;是公用1份的，换句话说，t1递归调用自己，每次都会开辟一个环境栈区分独立，但是他们是同一个函数逻辑，所以op_array是一样的，而

三。其他

通过一个哈希算法，它总有碰撞的时候吧。PHP中的哈希表是使用拉链法来解决冲突 (具体点讲就是使用链表来存储哈希到同一个槽位的数据,Zend为了保存数据之间的关系使用了双向链表来链接元素)。

对于HashTable的初始化_zend_hash_init，

插入_zend_hash_add_or_update，

元素访问_zend_hash_add_or_find等操作，源码中有就不再这里叙述。

这样回头一想，变量表，常量表，函数表等，他们在PHP中都是靠HashTable来实现的，如[二]中叙述，hashtable是不是很强大呢？

Zend引擎哈希表结构和关系：

Zend/zend_hash.h 55行

typedef struct bucket {
	ulong h;						/* Used for numeric indexing */
	uint nKeyLength;
	void *pData;
	void *pDataPtr;
	struct bucket *pListNext;
	struct bucket *pListLast;
	struct bucket *pNext;
	struct bucket *pLast;
	const char *arKey;
} Bucket;

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，最小为8，以2x增长。
    uint nTableMask;        // nTableSize-1 ， 索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值 
    ulong nNextFreeElement; // 下一个数字索引的位置
    Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
    Bucket *pListHead;          // 存储数组头元素指针
    Bucket *pListTail;          // 存储数组尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;    // 在删除元素时执行的回调函数，用于资源的释放
    zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

Zend/zend_compiles.h 261行,op_array结构代码

struct _zend_op_array {
	/* Common elements */
	zend_uchar type;
	const char *function_name;		
	zend_class_entry *scope;
	zend_uint fn_flags;
	union _zend_function *prototype;
	zend_uint num_args;
	zend_uint required_num_args;
	zend_arg_info *arg_info;
	/* END of common elements */

	zend_uint *refcount;

	zend_op *opcodes;
	zend_uint last;

	zend_compiled_variable *vars;
	int last_var;

	zend_uint T;

	zend_uint nested_calls;
	zend_uint used_stack;

	zend_brk_cont_element *brk_cont_array;
	int last_brk_cont;

	zend_try_catch_element *try_catch_array;
	int last_try_catch;
	zend_bool has_finally_block;

	/* static variables support */
	HashTable *static_variables;

	zend_uint this_var;

	const char *filename;
	zend_uint line_start;
	zend_uint line_end;
	const char *doc_comment;
	zend_uint doc_comment_len;
	zend_uint early_binding; /* the linked list of delayed declarations */

	zend_literal *literals;
	int last_literal;

	void **run_time_cache;
	int  last_cache_slot;

	void *reserved[ZEND_MAX_RESERVED_RESOURCES];
};

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!