一。前言
HashTable是PHP的靈魂,因為在Zend引擎中大量的使用了HashTable,如變數表,常量表,函數表等,這些都是適應HashTable保存的,另外,PHP的陣列也是透過使用HashTble實現的,所以,了解PHP的HashTable才能真正了解PHP。
#為了方便閱讀,這裡列舉HashTable實作中出現的基本概念。 哈希表是一種透過雜湊函數,將特定的鍵映射到特定值的一種資料結構,它維護鍵和值之間一一對應關係。
鍵(key):用於操作資料的標示,例如PHP陣列中的索引,或字串鍵等等。
插槽(slot/bucket):雜湊表中用來保存資料的一個單元,也就是資料真正存放的容器。
雜湊函數(hash function):將key映射(map)到資料應該存放的slot所在位置的函數。
雜湊衝突(hash collision):雜湊函數將兩個不同的key對應到同一個索引的情況。
PHP中的雜湊表實作在Zend/zend_hash.h中,先看看PHP實作中的資料結構, PHP使用以下兩個資料結構來實作雜湊表, HashTable結構體用於保存整個雜湊表所需的基本訊息, 而Bucket結構體用於保存具體的資料內容,(具體源碼見最後)
二。舉例
那麼,以創建一個變數為例,在底層到底發生了什麼事?
建立變數的步驟: $str = "hello";
1:建立zval結構,並設定其類型IS_STRING
2:設定其值為hello
3:將其加入符號表
{ zval *fooval; MAKE_STD_ZVAL(fooval); ZVAL_STRING(fooval, "hello", 1); ZEND_SET_SYMBOL( EG(active_symbol_table) , "foo" , fooval); }
#前兩步驟在上一篇的變數結構中有提到過,詳見PHP核心的儲存機制(分離/改變)
符號表是什麼?
答案:符號表是一張哈希表,裡面存儲了變數名稱->變數的zval結構體的位址
// zend/zend_globals.h 161行符號表
struct _zend_executor_globals { ... ... HashTable *active_symbol_table; /*活动符号表*/ HashTable symbol_table; /* 全局符号表 */ HashTable included_files; /* files already included */ ... }
#當執行到函數時,會產生函數的"執行環境結構體",包含函數名,參數,執行步驟,所在的類別(如果是方法),以及為這個函數產生一個符號表.符號表統一放在堆疊上.並且把active_symbol_table指向剛產生的符號表
#Zend/zend_compiles.h 384行,執行環境結構體:
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; };
上面這個,是目前函數執行時的符號表。
透過下邊例子,來描述下函數在執行中,PHP對各個儲存空間的分配,以及解釋了為什麼PHP的靜態變數可以共享。
當執行到函數時,會產生函數的"執行環境結構體",包含函數名稱,參數,執行步驟,所在的類別(如果是方法),以及為這個函數生成一個符號表.符號表統一放在棧上.並把active_symbol_table指向剛產生的符號表
##
解释:
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]; };
以上是PHP核心-簡單講解PHP靈魂HashTble的詳細內容。更多資訊請關注PHP中文網其他相關文章!