原创PHP7内核之HashTabl_php发展_php应用

PHP7内核之HashTable实现

作者：wj（电商技术）

php开发的主干已经切换到大版本7了，这个版本Zend引擎改变很大，可以说是一个全新的版本，因此新的Zend引擎被命名为NG。在这个大版本中变量以及hash表变动也很大。所以在这里把自己的学习过程和成果记录下来，毕竟好记性不如烂笔头啊。

数据结构

HashTable的结构定义在Zend/zend_types.h，之前的php版本中被定义在Zend/Zend_hash.h文件中。HashTable中的每一个元素都被保存在一个Bucket结构中，新的结构定义如下：

typedefstruct_Bucket{

zvalval;

zend_ulongh;/*hashvalue(ornumericindex)*/

zend_string*key;/*stringkeyorNULLfornumerics*/

}Bucket;

新的Bucket的结构已经相当简洁了，不像原来的里面还有链表指针什么的。HashTable的结构定义如下：

typedefstruct_HashTable{

union{

struct{

ZEND_ENDIAN_LOHI_3(

zend_ucharflags,

zend_ucharnApplyCount,/*循环遍历保护*/

uint16_treserve)

}v;

uint32_tflags;

}u;

uint32_tnTableSize;/*hash表的大小*/

uint32_tnTableMask;/*掩码,用于根据hash值计算存储位置,永远等于nTableSize-1*/

uint32_tnNumUsed;/*arData数组已经使用的数量*/

uint32_tnNumOfElements;/*hash表中元素个数*/

uint32_tnInternalPointer;/*用于HashTable遍历*/

zend_longnNextFreeElement;/*下一个空闲可用位置的数字索引*/

Bucket*arData;/*存放实际数据*/

uint32_t*arHash;/*Hash表*/

dtor_func_tpDestructor;/*析构函数*/

}HashTable;

创建HashTable

创建一个HashTable有很多途径，但是最终调用的都是_zend_hash_init函数，下面是这个函数的实现,我们省掉windows的实现部分

ZEND_APIvoid_zend_hash_init(HashTable*ht,uint32_tnSize,dtor_func_tpDestructor,zend_boolpersistentZEND_FILE_LINE_DC)

{

...

/*sizeshouldbebetween8and0x*/

nSize=(nSize=8?8:(nSize=0x?0x:nSize));

#ifdefined(__GNUC__)

ht-nTableSize=0x2(__builtin_clz(nSize-1)^0x1f);

#else

nSize-=1;

nSize

=(nSize1);

nSize

=(nSize2);

nSize

=(nSize4);

nSize

=(nSize8);

nSize

=(nSize16);

ht-nTableSize=nSize+1;

#endif

ht-nTableMask=0;

ht-nNumUsed=0;

ht-nNumOfElements=0;

ht-nNextFreeElement=0;

ht-arData=NULL;

ht-arHash=(uint32_t*)uninitialized_bucket;

ht-pDestructor=pDestructor;

ht-nInternalPointer=INVALID_IDX;

ht-u.flags=(persistent?HASH_FLAG_PERSISTENT:0)

HASH_FLAG_APPLY_PROTECTION;

}

pDestructor是HashTable元素的析构指针，在更新/销毁HashTable中的元素时候会使用。上面的一系列得nSize的计算只是为了得到一个大于等于原始nSize的2的整数次幂的最小值,在这里并没有初始化arData，它会在使用HashTable的时候来创建。

操作HashTable

添加更新元素

在新的实现中，将以前的最底层添加和更新元素的api_zend_hash_add_or_update变成了现在的_zend_hash_add_or_update_i，其他的对HashTable的新增和更新的操作全部是基于_zend_hash_add_or_update_i实现的宏。下面是_zend_hash_add_or_update_i的实现：

staticzend_always_inlinezval*_zend_hash_add_or_update_i(HashTable*ht,zend_string*key,zval*pData,uint32_tflagZEND_FILE_LINE_DC)

{

zend_ulongh;

uint32_tnIndex;

uint32_tidx;

Bucket*p;

IS_CONSISTENT(ht);

if(UNEXPECTED(!(ht-u.flagsHASH_FLAG_INITIALIZED))){/*检查hashtable是否初始化*/

CHECK_INIT(ht,0);

gotoadd_to_hash;

}elseif(ht-u.flagsHASH_FLAG_PACKED){/*?*/

zend_hash_packed_to_hash(ht);

}elseif((flagHASH_ADD_NEW)==0){/*新增*/

p=zend_hash_find_bucket(ht,key);/*根据key查是否已经存在*/

if(p){/*当前的key已经存在*/

zval*data;

if(flagHASH_ADD){/*key已经存在产生添加冲突，退出*/

returnNULL;

}

ZEND_ASSERT(p-val!=pData);/*key存在的情况下，值不一样做更新操作*/

data=p-val;

if((flagHASH_UPDATE_INDIRECT)Z_TYPE_P(data)==IS_INDIRECT){

data=Z_INDIRECT_P(data);

}

HANDLE_BLOCK_INTERRUPTIONS();

if(ht-pDestructor){

ht-pDestructor(data);/*释放掉原来的data*/

}

ZVAL_COPY_VALUE(data,pData);/*将新的pData值复制给原来的data*/

HANDLE_UNBLOCK_INTERRUPTIONS();

returndata;

}

ZEND_HASH_IF_FULL_DO_RESIZE(ht);/*IftheHashtableisfull,resizeit*/

add_to_hash:

HANDLE_BLOCK_INTERRUPTIONS();

idx=ht-nNumUsed++;/*已使用计数+1，并且用老的位置来做为索引*/

ht-nNumOfElements++;/*元素个数加1*/

if(ht-nInternalPointer==INVALID_IDX){

ht-nInternalPointer=idx;

}

p=ht-arData+idx;/*指针加法移位*/

p-h=h=zend_string_hash_val(key);/*计算key的hash值*/

p-key=key;

zend_string_addref(key);

ZVAL_COPY_VALUE(p-val,pData);

nIndex=hht-nTableMask;/*与tablemask进行计算得出hash索引*/

Z_NEXT(p-val)=ht-arHash[nIndex];/*新的元素的hash冲突链表的next指向当前冲突链表的首部元素*/

ht-arHash[nIndex]=idx;/*新的元素放到当前hash冲突链表的头部*/

HANDLE_UNBLOCK_INTERRUPTIONS();

returnp-val;

}

#defineZ_NEXT(zval)(zval).u2.next

从上面的api_zend_hash_add_or_update_i可以看出，其实更新操作很简单的，验证key是否存在，key存在的情况下如果值相等的话不做任何的操作，值不相同做更新操作。

这里比较重要的是hash表的新增，这里会涉及hash索引以及hash冲突链表。上面代码中的add_to_hash部分的代码主要就是在做这部分的做操。从上面的代码中可以看出，ht-arData其实就是一个不定长的Bucket数组，它利用ht-nNumUsed来计算这个数组下一个空闲位置,然后将新的Bucket放到这个位置上。计算得到传入的key的hash值，然后与ht-nTableMask进行按位与得出新的bucket对应的ht-arHash上的位置,这里就完成了hash表的构造。

但是还有个非常重要的地方，就是hash冲突的解决。hash冲突一直都是以一个链表来解决的，当出现hash冲突时候会将相同hash值的bucket连接成一个链表，然后进行查找时候是一个个的遍历，一个个的对比key值是否相同。和NG之前不同的是，现在的hash冲突链表被放到了__zval_struct结构中，而不是以前的Bucket里面。下面先是新老结构的对比

OldBucket

typedefstructbucket{

ulongh;/*Usedfornumericindexing*/

uintnKeyLength;

void*pData;

void*pDataPtr;

structbucket*pListNext;/*指向哈希链表中下一个元素*/

structbucket*pListLast;/*指向哈希链表中的前一个元素*/

structbucket*pNext;/*相同哈希值的下一个元素（哈希冲突用）*/

structbucket*pLast;/*相同哈希值的上一个元素（哈希冲突用）*/

constchar*arKey;

}Bucket;

NewBucket

typedefstruct_Bucket{

zvalval;

zend_ulongh;/*hashvalue(ornumericindex)*/

zend_string*key;/*stringkeyorNULLfornumerics*/

}Bucket;

从上面结构的对比可以看出，新的_Bucket只是一个单纯存储key以及value的结构了，而不承担以前的hash链表以及hash冲突链表的构建工作了。新的HashTable中，hash链表的构建工作由HashTable-arHash来承担，而解决hash冲突的链表则被放到了_zval_struct了。在新的实现当中，HashTable-arHash[]会指向冲突链表的头，然后利用_zval_struct.u2.next来指向冲突链表中的下一个Bucket对应的arHash的位置。这样，现在的冲突链表俨然由原来的双向链表变成了现在的单向链表了。当新的冲突产生的时候，会将新的Bucket放入这个冲突链表的头部，然后让这个链表所对应的arHash的位置重新指向它，然后它的_zval_struct.u2.next指向原来的冲突链表头元素。就这样就构建好了一个冲突链表。

删除元素

Zend提供了一系列删除HashTable中元素的API，，定义如下：

ZEND_APIintzend_hash_del(HashTable*ht,zend_string*key);

ZEND_APIintzend_hash_del_ind(HashTable*ht,zend_string*key);

ZEND_APIintzend_hash_str_del(HashTable*ht,constchar*key,size_tlen);

ZEND_APIintzend_hash_str_del_ind(HashTable*ht,constchar*key,size_tlen);

ZEND_APIintzend_hash_index_del(HashTable*ht,zend_ulongh);

接下来看看zend_hash_del的代码：

ZEND_APIintzend_hash_del(HashTable*ht,zend_string*key)

{

zend_ulongh;

uint32_tnIndex;

uint32_tidx;

Bucket*p;

Bucket*prev=NULL;

IS_CONSISTENT(ht);

h=zend_string_hash_val(key);/*根据key计算出hash值*/

nIndex=hht-nTableMask;/*与nTableMask按位与计算出在hashtable中的位置*/

idx=ht-arHash[nIndex];

while(idx!=INVALID_IDX){

p=ht-arData+idx;/*指针移位*/

if((p-key==key)

/*比较key值*/

(p-h==h

p-key

p-key-len==key-len

memcmp(p-key-val,key-val,key-len)==0)){

_zend_hash_del_el_ex(ht,idx,p,prev);/*做实际删除动作的函数*/

returnSUCCESS;

}

prev=p;

idx=Z_NEXT(p-val);/*遍历hash冲突链表*/

}

returnFAILURE;

}

上面的函数函数非常简单，就是进行hash查找，然后比较key值，最后调用函数_zend_hash_del_el_ex进行实际的删除动作，我们接下来看看_zend_hash_del_el_exd的代码实现：

staticzend_always_inlinevoid_zend_hash_del_el_ex(HashTable*ht,uint32_tidx,Bucket*p,Bucket*prev)

{

HANDLE_BLOCK_INTERRUPTIONS();

if(!(ht-u.flagsHASH_FLAG_PACKED)){/*非自然key序数组*/

if(prev){/*找到的元素不在hash冲突链表的首位，将它的前一个的next指针指向它的下一个元素*/

Z_NEXT(prev-val)=Z_NEXT(p-val);

}else{/*找到的元素位于hash冲突链表的首位，将arHash对应的位置指向它的下一个元素*/

ht-arHash[p-hht-nTableMask]=Z_NEXT(p-val);

}

if(ht-nNumUsed-1==idx){/*元素位于arData数组的尾部*/

do{

ht-nNumUsed--;

}while(ht-nNumUsed0(Z_TYPE(ht-arData[ht-nNumUsed-1].val)==IS_UNDEF));/*循环自减，去掉删除当前元素后遗留的尾部的UNDEF元素*/

}

ht-nNumOfElements--;/*hash表中元素个数减1*/

if(ht-nInternalPointer==idx){

while(1){

idx++;

if(idx=ht-nNumUsed){/*当idx指向的元素位于hash表最后一个元素时候，重置hash遍历指针为无效指针*/

ht-nInternalPointer=INVALID_IDX;

break;

}elseif(Z_TYPE(ht-arData[idx].val)!=IS_UNDEF){/*当前元素不在hash表最后，并且指向的元素是非UNDEF的，将hash遍历指针指向它*/

ht-nInternalPointer=idx;

break;

}

if(p-key){/*释放key*/

zend_string_release(p-key);

}

if(ht-pDestructor){/*调用析构函数释放value的值*/

zvaltmp;

ZVAL_COPY_VALUE(tmp,p-val);

ZVAL_UNDEF(p-val);

ht-pDestructor(tmp);

}else{

ZVAL_UNDEF(p-val);

}

HANDLE_UNBLOCK_INTERRUPTIONS();

}

有一个注意的就是上面出现了一个宏HASH_FLAG_PACKED。根据鸟哥原话的解释：

表示一个自然key序的数组，就是可以随机访问的数组，就好比是C语言的数

array(1,2,3,4)，那么$arr[2]就是ht-arData[2]

array(1,2,3,4)packed/array(1=2,3=2,2=1)非packed

个人理解就是自然排序(packed)就是Zend引擎自己生成的一个key，而不是程序员指定的。

清空HashTable

Zend提供了一个api来清空整个HashTablezend_hash_clean，下面是它的实现代码：

ZEND_APIvoidzend_hash_clean(HashTable*ht)

{

Bucket*p,*end;

IS_CONSISTENT(ht);

if(ht-nNumUsed){/*非空HashTable*/

p=ht-arData;/*数组头*/

end=p+ht-nNumUsed;/*数组尾*/

if(ht-pDestructor){

if(ht-u.flagsHASH_FLAG_PACKED){/*自然key序数组*/

do{

if(EXPECTED(Z_TYPE(p-val)!=IS_UNDEF)){

ht-pDestructor(p-val);

}

}while(++p!=end);/*循环遍历，挨个调用析构函数进行销毁*/

}else{

do{

if(EXPECTED(Z_TYPE(p-val)!=IS_UNDEF)){

ht-pDestructor(p-val);/*调用析构函数进行数据销毁*/

if(EXPECTED(p-key)){/*存在key，销毁key并释放内存*/

zend_string_release(p-key);

}

}while(++p!=end);/*循环遍历进行销毁*/

}

}else{

if(!(ht-u.flagsHASH_FLAG_PACKED)){/*非自然key序数组*/

do{

if(EXPECTED(Z_TYPE(p-val)!=IS_UNDEF)){

if(EXPECTED(p-key)){

zend_string_release(p-key);

}

}while(++p!=end);/*循环遍历，挨个销毁key*/

}

if(!(ht-u.flagsHASH_FLAG_PACKED)){/*非自然key序数组，重置arHash*/

memset(ht-arHash,INVALID_IDX,ht-nTableSize*sizeof(uint32_t));

}

ht-nNumUsed=0;/*arData计数置为0*/

ht-nNumOfElements=0;/*hash表中元素个数置为0*/

ht-nNextFreeElement=0;/*下一个空闲可用位置的数字索引置为0*/

ht-nInternalPointer=INVALID_IDX;/*Hash遍历指针置为不可用*/

}

销毁HashTable

HashTable的销毁是由zend_hash_destroy来负责的，实现如下：

ZEND_APIvoidzend_hash_destroy(HashTable*ht)

{

Bucket*p,*end;

IS_CONSISTENT(ht);

if(ht-nNumUsed){

p=ht-arData;

end=p+ht-nNumUsed;

if(ht-pDestructor){

SET_INCONSISTENT(HT_IS_DESTROYING);

if(ht-u.flagsHASH_FLAG_PACKED){

do{

if(EXPECTED(Z_TYPE(p-val)!=IS_UNDEF)){

ht-pDestructor(p-val);

}

}while(++p!=end);

}else{

do{

if(EXPECTED(Z_TYPE(p-val)!=IS_UNDEF)){

ht-pDestructor(p-val);

if(EXPECTED(p-key)){

zend_string_release(p-key);

}

}while(++p!=end);

}

SET_INCONSISTENT(HT_DESTROYED);

}else{

if(!(ht-u.flagsHASH_FLAG_PACKED)){

do{

if(EXPECTED(Z_TYPE(p-val)!=IS_UNDEF)){

if(EXPECTED(p-key)){

zend_string_release(p-key);

}

}while(++p!=end);

}

}elseif(EXPECTED(!(ht-u.flagsHASH_FLAG_INITIALIZED))){

return;

}

pefree(ht-arData,ht-u.flagsHASH_FLAG_PERSISTENT);/*释放arData的内存*/

}

其实zend_hash_destroy和zend_hash_clean的实现很相近，释放元素的过程几乎一样，唯一的区别就是最后的工作，zend_hash_destroy最后是将arData彻底释放了。

结尾

HashTable在PHP的内核中的地位非常重要，数组、作用域等都是靠HashTable来实现的，PHP数组设计的操作肯定不止这点，更多的操作还包括排序、rehash等。不过这些都是最普遍的增删改查。更多的实现请自行阅读PHP源码zend_hash.czend_hash.h

-------------------------------------------------------------------------------------

黑夜路人，一个

白癜风有治疗好的吗
 有治好白癜风的患者吗

转载请注明原文网址：http://www.coolofsoul.com/phptx/12259.html