關(guān)于PHP5和PHP7中數(shù)組實(shí)現(xiàn)方式的比較總結(jié)

第關(guān)于PHP5和PHP7中數(shù)組實(shí)現(xiàn)方式的比較總結(jié)typedefstructbucket{

ulongh;/*對(duì)于索引數(shù)組，存儲(chǔ)key的原始值；對(duì)于關(guān)聯(lián)數(shù)組，存儲(chǔ)key的hash之后的值*/

uintnKeyLength;/*關(guān)聯(lián)數(shù)組時(shí)存儲(chǔ)key的長(zhǎng)度，索引數(shù)組此值為0*/

void*pData;/*指向數(shù)組value的地址*/

void*pDataPtr;/*如果value為指針，則由pDataPtr記錄vlaue，pData則指向pDataPtr*/

//PHP5中數(shù)組元素的順序是固定的，無(wú)論什么時(shí)候遍歷，數(shù)組元素總是與插入時(shí)的順序一致

//PHP5中使用雙向鏈表來(lái)保證數(shù)組元素的順序，pListNext和pListLast分別按照

//元素插入順序記錄當(dāng)前bucket的下一個(gè)和上一個(gè)bucket

structbucket*pListNext;

structbucket*pListLast;

//PHP5使用拉鏈法解決hash碰撞，pNext和pLast分別存儲(chǔ)當(dāng)前bucket

//在沖突的雙向鏈表中的下一個(gè)和上一個(gè)相鄰的bucket

structbucket*pNext;

structbucket*pLast;

constchar*arKey;/*關(guān)聯(lián)數(shù)組是存儲(chǔ)key的原始值*/

}Bucket;

typedefstruct_hashtable{

uintnTableSize;/*當(dāng)前ht所分配的bucket的總數(shù)，2^n*/

uintnTableMask;/*nTableSize-1，用于計(jì)算索引*/

uintnNumOfElements;/*實(shí)際存儲(chǔ)的元素的數(shù)量*/

ulongnNextFreeElement;/*下一個(gè)可以被使用的整數(shù)key*/

Bucket*pInternalPointer;/*數(shù)組遍歷時(shí)，記錄當(dāng)前bucket的地址*/

Bucket*pListHead;

Bucket*pListTail;

Bucket**arBuckets;/*記錄bucket的C語(yǔ)言數(shù)組*/

dtor_func_tpDestructor;/*刪除數(shù)組元素時(shí)內(nèi)部調(diào)用的函數(shù)*/

zend_boolpersistent;/*標(biāo)識(shí)ht是否永久有效*/

unsignedcharnApplyCount;/*ht允許的最大遞歸深度*/

zend_boolbApplyProtection;/*是否啟用遞歸保護(hù)*/

#ifZEND_DEBUG

intinconsistent;

#endif

}HashTable;

//PHP7中hashtable的數(shù)據(jù)結(jié)構(gòu)

//PHP7中個(gè)子版本以及階段版本中對(duì)hashtable的數(shù)據(jù)結(jié)構(gòu)的定義會(huì)有微小的差別，這里使用的是PHP7.4.0中的定義

struct_zend_string{

zend_refcounted_hgc;

zend_ulongh;/*字符串key的hash值*/

size_tlen;/*字符串key的長(zhǎng)度*/

charval[1];/*存儲(chǔ)字符串的值，利用了structhack*/

typedefstruct_Bucket{

zvalval;/*內(nèi)嵌zval結(jié)構(gòu)，存儲(chǔ)數(shù)組的value值*/

zend_ulongh;/*hashvalue(ornumericindex)*/

zend_string*key;/*stringkeyorNULLfornumerics*/

}Bucket;

typedefstruct_zend_arrayHashTable;

struct_zend_array{

zend_refcounted_hgc;

union{

struct{

ZEND_ENDIAN_LOHI_4(

zend_ucharflags,

zend_uchar_unused,

zend_ucharnIteratorsCount,

zend_uchar_unused2)

}v;

uint32_tflags;

}u;

uint32_tnTableMask;/*作用與PHP5中hashtable中nTableMask作用相同，但實(shí)現(xiàn)邏輯稍有變化*/

Bucket*arData;/*存儲(chǔ)bucket相關(guān)的信息*/

uint32_tnNumUsed;/*ht中已經(jīng)使用的bucket的數(shù)量，在nNumOfElements的基礎(chǔ)上加上刪除的key*/

uint32_tnNumOfElements;

uint32_tnTableSize;

uint32_tnInternalPointer;

zend_longnNextFreeElement;

dtor_func_tpDestructor;

不考慮其他開(kāi)銷(xiāo)，單從Bucket所占用的空間來(lái)看：在PHP5中，考慮到內(nèi)存對(duì)齊，一個(gè)Bucket占用的空間為72字節(jié)；在PHP7中，一個(gè)zend_value占8字節(jié)，一個(gè)zval占16字節(jié)，一個(gè)Bucket占32字節(jié)。相比之下，PHP7中Bucket的內(nèi)存空間消耗比PHP5低了一半以上。

具體PHP5數(shù)組的內(nèi)存消耗情況，之前的文章已有講解，這里不再贅述

現(xiàn)在來(lái)談?wù)凚ucket的存儲(chǔ)：在PHP5中，arBucket是一個(gè)C語(yǔ)言數(shù)組，長(zhǎng)度為nTableSize，存儲(chǔ)的是指向Bucket的指針，發(fā)生hash碰撞的Bucket以雙向鏈表的方式連接。

在PHP7中，Bucket按照數(shù)組元素寫(xiě)入的順序依次存儲(chǔ)，其索引值為idx，該值存儲(chǔ)在*arData左側(cè)的映射區(qū)域中。idx在映射區(qū)域中的索引為nIndex，nIndex值為負(fù)數(shù)，由數(shù)組key的hash值與nTableMask進(jìn)行或運(yùn)算得到。

//nTableMask為-2倍的nTableSize的無(wú)符號(hào)表示

#defineHT_SIZE_TO_MASK(nTableSize)\

((uint32_t)(-((nTableSize)+(nTableSize))))

//在通過(guò)idx查找Bucket時(shí)，data默認(rèn)為Bucket類(lèi)型，加idx表示向右偏移idx個(gè)Bucket位置

#defineHT_HASH_TO_BUCKET_EX(data,idx)\

((data)+(idx))

//在通過(guò)nIndex查找idx時(shí)，

//(uint32_t*)(data)首先將data轉(zhuǎn)換成了uint32_t*類(lèi)型的數(shù)組

//然后將nIndex轉(zhuǎn)換成有符號(hào)數(shù)（負(fù)數(shù)），然后以數(shù)組的方式查找idx的值

#defineHT_HASH_EX(data,idx)\

((uint32_t*)(data))[(int32_t)(idx)]

nIndex=h|ht-nTableMask;

idx=HT_HASH_EX(arData,nIndex);

p=HT_HASH_TO_BUCKET_EX(arData,idx);

這里需要指出，nTableMask之所以設(shè)置為nTableSize的兩倍，是這樣在計(jì)算nIndex時(shí)可以減小hash碰撞的概率。

⒉添加/修改元素

PHP5

先來(lái)談?wù)凱HP5中數(shù)組元素的添加和修改，由于PHP5中數(shù)組元素的插入順序以及hash碰撞都是通過(guò)雙向鏈表的方式來(lái)維護(hù)，所以雖然實(shí)現(xiàn)起來(lái)有些復(fù)雜，但理解起來(lái)相對(duì)容易一些。

//hash碰撞雙向鏈表的維護(hù)

#defineCONNECT_TO_BUCKET_DLLIST(element,list_head)\

(element)-pNext=(list_head);\

(element)-pLast=NULL;\

if((element)-pNext){\

(element)-pNext-pLast=(element);\

#defineCONNECT_TO_GLOBAL_DLLIST_EX(element,ht,last,next)\

(element)-pListLast=(last);\

(element)-pListNext=(next);\

if((last)!=NULL){\

(last)-pListNext=(element);\

}else{\

(ht)-pListHead=(element);\

if((next)!=NULL){\

(next)-pListLast=(element);\

}else{\

(ht)-pListTail=(element);\

//數(shù)組元素插入順序雙向鏈表的維護(hù)

#defineCONNECT_TO_GLOBAL_DLLIST(element,ht)\

CONNECT_TO_GLOBAL_DLLIST_EX(element,ht,(ht)-pListTail,(Bucket*)NULL);\

if((ht)-pInternalPointer==NULL){\

(ht)-pInternalPointer=(element);\

//數(shù)組元素的更新

#defineUPDATE_DATA(ht,p,pData,nDataSize)\

if(nDataSize==sizeof(void*)){\

//值為指針類(lèi)型的元素的更新\

if((p)-pData!=(p)-pDataPtr){\

pefree_rel((p)-pData,(ht)-persistent);\

//pDataPtr存儲(chǔ)元素值的地址，pData存儲(chǔ)pDataPtr的地址\

memcpy((p)-pDataPtr,pData,sizeof(void*));\

(p)-pData=(p)-pDataPtr;\

}else{\

//如果數(shù)組元素為值類(lèi)型，則存入pData，此時(shí)pDataPtr為Null\

if((p)-pData==(p)-pDataPtr){\

(p)-pData=(void*)pemalloc_rel(nDataSize,(ht)-persistent);\

(p)-pDataPtr=NULL;\

}else{\

(p)-pData=(void*)perealloc_rel((p)-pData,nDataSize,(ht)-persistent);\

/*(p)-pDataPtrisalreadyNULLsononeedtoinitializeit*/\

memcpy((p)-pData,pData,nDataSize);\

//數(shù)組元素的初始化

#defineINIT_DATA(ht,p,_pData,nDataSize);\

if(nDataSize==sizeof(void*)){\

//指針類(lèi)型元素的初始化\

memcpy((p)-pDataPtr,(_pData),sizeof(void*));\

(p)-pData=(p)-pDataPtr;\

}else{\

//值類(lèi)型元素的初始化\

(p)-pData=(void*)pemalloc_rel(nDataSize,(ht)-persistent);\

memcpy((p)-pData,(_pData),nDataSize);\

(p)-pDataPtr=NULL;\

//hashtable初始化校驗(yàn)，如果沒(méi)有初始化，則初始化hashtable

#defineCHECK_INIT(ht)do{\

if(UNEXPECTED((ht)-nTableMask==0)){\

(ht)-arBuckets=(Bucket**)pecalloc((ht)-nTableSize,sizeof(Bucket*),(ht)-persistent);\

(ht)-nTableMask=(ht)-nTableSize-1;\

}while(0)

//數(shù)組元素的新增或更新（精簡(jiǎn)掉了一些宏調(diào)用和代碼片段)

ZEND_APIint_zend_hash_add_or_update(HashTable*ht,constchar*arKey,uintnKeyLength,void*pData,uintnDataSize,void**pDest,intflagZEND_FILE_LINE_DC)

ulongh;

uintnIndex;

Bucket*p;

CHECK_INIT(ht);

h=zend_inline_hash_func(arKey,nKeyLength);

nIndex=hht-nTableMask;

p=ht-arBuckets[nIndex];

while(p!=NULL){

if(p-arKey==arKey||

((p-h==h)(p-nKeyLength==nKeyLength)!memcmp(p-arKey,arKey,nKeyLength))){

//數(shù)組元素更新邏輯

if(flagHASH_ADD){

returnFAILURE;

ZEND_ASSERT(p-pData!=pData);

if(ht-pDestructor){

ht-pDestructor(p-pData);

UPDATE_DATA(ht,p,pData,nDataSize);

if(pDest){

*pDest=p-pData;

returnSUCCESS;

p=p-pNext;

//數(shù)組元素新增邏輯

if(IS_INTERNED(arKey)){

p=(Bucket*)pemalloc(sizeof(Bucket),ht-persistent);

p-arKey=arKey;

}else{

p=(Bucket*)pemalloc(sizeof(Bucket)+nKeyLength,ht-persistent);

p-arKey=(constchar*)(p+1);

memcpy((char*)p-arKey,arKey,nKeyLength);

p-nKeyLength=nKeyLength;

INIT_DATA(ht,p,pData,nDataSize);

p-h=h;

//hash碰撞鏈表維護(hù)

CONNECT_TO_BUCKET_DLLIST(p,ht-arBuckets[nIndex]);

if(pDest){

*pDest=p-pData;

//數(shù)組元素寫(xiě)入順序維護(hù)

CONNECT_TO_GLOBAL_DLLIST(p,ht);

ht-arBuckets[nIndex]=p;

ht-nNumOfElements++;

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

returnSUCCESS;

PHP5中的數(shù)組在新增或修改元素時(shí)，首先會(huì)根據(jù)給定的key計(jì)算得到相應(yīng)的hash值，然后據(jù)此得到arBuckets的索引nIndex，最終得到鏈表中第一個(gè)Bucket（hash碰撞鏈表的表頭），即p。

如果是更新數(shù)組中已有的項(xiàng)，那么會(huì)從p開(kāi)始遍歷hash碰撞鏈表，直到找到arkey與給定的key相同的Bucket，然后更新pData。

如果是向數(shù)組中新增項(xiàng)，首先會(huì)判斷給定的key是否為internedstring類(lèi)型，如果是，那么只需要為Bucket申請(qǐng)內(nèi)存，然后將p-arKey指向給定的key的地址即可，否則在為新的Bucket申請(qǐng)內(nèi)存的同時(shí)還需要為給定的key申請(qǐng)內(nèi)存，然后將p-arKey指向?yàn)閗ey申請(qǐng)的內(nèi)存的地址。之后會(huì)對(duì)新申請(qǐng)的Bucket進(jìn)行初始化，最后要做的兩件事：維護(hù)hash碰撞鏈表和數(shù)組元素寫(xiě)入順序鏈表。在維護(hù)hash碰撞的鏈表時(shí)，新增的Bucket是放在鏈表頭的位置；維護(hù)數(shù)組元素寫(xiě)入順序的鏈表時(shí)，新增的Bucket是放在鏈表的末尾，同時(shí)將hashtable的pListTail指向新增的Bucket。

關(guān)于PHP中的internedstring，之前在講解PHP7對(duì)字符串處理邏輯優(yōu)化的時(shí)候已經(jīng)說(shuō)明，這里不再贅述

PHP7

PHP7在hashtable的數(shù)據(jù)結(jié)構(gòu)上做了比較大的改動(dòng)，同時(shí)放棄了使用雙向鏈表的方式來(lái)維護(hù)hash碰撞和數(shù)組元素的寫(xiě)入順序，在內(nèi)存管理以及性能上得到了提升，但理解起來(lái)卻不如PHP5中的實(shí)現(xiàn)方式直觀。

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

#defineHT_HASH_EX(data,idx)\

((uint32_t*)(data))[(int32_t)(idx)]

#defineHT_IDX_TO_HASH(idx)\

((idx)*sizeof(Bucket))

//PHP7中數(shù)組添加/修改元素（精簡(jiǎn)了部分代碼）

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

zend_ulongh;

uint32_tnIndex;

uint32_tidx;

Bucket*p,*arData;

/*......*/

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

add_to_hash:

idx=ht-nNumUsed++;

ht-nNumOfElements++;

arData=ht-arData;

p=arData+idx;

p-key=key;

p-h=h=ZSTR_H(key);

nIndex=h|ht-nTableMask;

Z_NEXT(p-val)=HT_HASH_EX(arData,nIndex);

HT_HASH_EX(arData,nIndex)=HT_IDX_TO_HASH(idx);

ZVAL_COPY_VALUE(p-val,pData);

returnp-

這里需要先說(shuō)明一下nNumUsed和nNumOfElements的區(qū)別：

按圖中示例，此時(shí)nNumUsed的值應(yīng)該為5，但nNumOfElements的值則應(yīng)該為3。在PHP7中，數(shù)組元素按照寫(xiě)入順序依次存儲(chǔ)，而nNumUsed正好可以用來(lái)充當(dāng)數(shù)組元素存儲(chǔ)位置索引的功能。

另外就是p=arData+idx，前面已經(jīng)講過(guò)arData為Bucket類(lèi)型，這里+idx意為指針從arData的位置開(kāi)始向右偏移idx個(gè)Bucket的位置。宏調(diào)用HT_HASH_EX也是同樣的道理。

最后就是Z_NEXT(p-val)，PHP7中的Bucket結(jié)構(gòu)都內(nèi)嵌了一個(gè)zval，zval中的聯(lián)合體u2中有一項(xiàng)next用來(lái)記錄hash碰撞的信息。nIndex用來(lái)標(biāo)識(shí)idx在映射表中的位置，在往hashtable中新增元素時(shí)，如果根據(jù)給定的key計(jì)算得到的nIndex的位置已經(jīng)有值（即發(fā)生了hash碰撞），那么此時(shí)需要將nIndex所指向的位置的原值記錄到新增的元素所對(duì)應(yīng)的Bucket下的val.u2.next中。宏調(diào)用HT_IDX_TO_HASH的作用是根據(jù)idx計(jì)算得到Bucket的以字節(jié)為單位的偏移量。

⒊刪除元素

PHP5

在PHP5中，數(shù)組元素的刪除過(guò)程中的主要工作是維護(hù)hash碰撞鏈表和數(shù)組元素寫(xiě)入順序的鏈表。

//刪除Bucket的代碼（精簡(jiǎn)了部分代碼片段）

staticzend_always_inlinevoidi_zend_hash_bucket_delete(HashTable*ht,Bucket*p)

if(p-pLast){

p-pLast-pNext=p-pNext;

}else{

ht-arBuckets[p-hht-nTableMask]=p-pNext;

if(p-pNext){

p-pNext-pLast=p-pLast;

if(p-pListLast!=NULL){

p-pListLast-pListNext=p-pListNext;

}else{

/*Deletingtheheadofthelist*/

ht-pListHead=p-pListNext;

if(p-pListNext!=NULL){

p-pListNext-pListLast=p-pListLast;

}else{

/*Deletingthetailofthelist*/

ht-pListTail=p-pListLast;

if(ht-pInternalPointer==p){

ht-pInternalPointer=p-pListNext;

ht-nNumOfElements--;

if(ht-pDestructor){

ht-pDestructor(p-pData);

if(p-pData!=p-pDataPtr){

pefree(p-pData,ht-persistent);

pefree(p,ht-persistent);

//元素刪除

ZEND_APIintzend_hash_del_key_or_index(HashTable*ht,constchar*arKey,uintnKeyLength,ulongh,intflag)

uintnIndex;

Bucket*p;

if(flag==HASH_DEL_KEY){

h=zend_inline_hash_func(arKey,nKeyLength);

nIndex=hht-nTableMask;

p=ht-arBuckets[nIndex];

while(p!=NULL){

if((p-h==h)

(p-nKeyLength==nKeyLength)

((p-nKeyLength==0)/*Numericindex(shortcircuitsthememcmp()check)*/

||!memcmp(p-arKey,arKey,nKeyLength))){/*Stringindex*/

i_zend_hash_bucket_delete(ht,p);

returnSUCCESS;

p=p-pNext;

returnFAILURE;

PHP5中數(shù)組在刪除元素時(shí)，仍然是先根據(jù)給定的key計(jì)算hash，然后找到arBucket的nIndex，最終找到需要?jiǎng)h除的Bucket所在的hash碰撞的鏈表，通過(guò)遍歷鏈表，找到最終需要?jiǎng)h除的Bucket。

在實(shí)際刪除Bucket的過(guò)程中，主要做的就是維護(hù)兩個(gè)鏈表：hash碰撞鏈表和數(shù)組元素寫(xiě)入順序鏈表。再就是釋放內(nèi)存。

PHP7

由于PHP7記錄hash碰撞信息的方式發(fā)生了變化，所以在刪除元素時(shí)處理hash碰撞鏈表的邏輯也會(huì)有所不同。另外，在刪除元素時(shí)，還有可能會(huì)遇到空間回收的情況。

#defineIS_UNDEF0

#defineZ_TYPE_INFO(zval)(zval).u1.type_info

#defineZ_TYPE_INFO_P(zval_p)Z_TYPE_INFO(*(zval_p))

#defineZVAL_UNDEF(z)do{\

Z_TYPE_INFO_P(z)=IS_UNDEF;\

}while(0)

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

//從hash碰撞鏈表中刪除指定的Bucket

if(!(HT_FLAGS(ht)HASH_FLAG_PACKED)){

if(prev){

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

}else{

HT_HASH(ht,p-h|ht-nTableMask)=Z_NEXT(p-val);

idx=HT_HASH_TO_IDX(idx);

ht-nNumOfElements--;

if(ht-nInternalPointer==idx||UNEXPECTED(HT_HAS_ITERATORS(ht))){

//如果當(dāng)前hashtable的內(nèi)部指針指向了要?jiǎng)h除的Bucket或當(dāng)前hashtable有遍歷

//操作，那么需要避開(kāi)當(dāng)前正在被刪除的Bucket

uint32_tnew_idx;

new_idx=idx;

while(1){

new_idx++;

if(new_idx=ht-nNumUsed){

break;

}elseif(Z_TYPE(ht-arData[new_idx].val)!=IS_UNDEF){

break;

if(ht-nInternalPointer==idx){

ht-nInternalPointer=new_idx;

zend_hash_iterators_update(ht,idx,new_idx);

if(ht-nNumUsed-1==idx){

//如果被刪除的Bucket在數(shù)組的末尾，則同時(shí)回收與Bucket相鄰的已經(jīng)被刪除的Bucket的空間

do{

ht-nNumUsed--;

}while(ht-nNumUsed0(UNEXPECTED(Z_TYPE(ht-arData[ht-nNumUsed-1].val)==IS_UNDEF)));

ht-nInternalPointer=MIN(ht-nInternalPointer,ht-nNumUsed);

if(p-key){

//刪除string類(lèi)型的索引

zend_string_release(p-key);

//刪除Bucket

if(ht-pDestructor){

zvaltmp;

ZVAL_COPY_VALUE(tmp,p-val);

ZVAL_UNDEF(p-val);

ht-pDestructor(tmp);

}else{

ZVAL_UNDEF(p-val);

staticzend_always_inlinevoid_zend_hash_del_el(HashTable*ht,uint32_tidx,Bucket*p)

Bucket*prev=NULL;

if(!(HT_FLAGS(ht)HASH_FLAG_PACKED)){

//如果被刪除的Bucket存在hash碰撞的情況，那么需要找出其在hash碰撞鏈表中的位置

uint32_tnIndex=p-h|ht-nTableMask;

uint32_ti=HT_HASH(ht,nIndex);

if(i!=idx){

prev=HT_HASH_TO_BUCKET(ht,i);

while(Z_NEXT(prev-val)!=idx){

i=Z_NEXT(prev-val);

prev=HT_HASH_TO_BUCKET(ht,i);

_zend_hash_del_el_ex(ht,idx,p,prev);

ZEND_APIvoidZEND_FASTCALLzend_hash_del_bucket(HashTable*ht,Bucket*p)

IS_CONSISTENT(ht);

HT_ASSERT_RC1(ht);

_zend_hash_del_el(ht,HT_IDX_TO_HASH(p-ht-arData),p);

PHP7中數(shù)組元素的刪除，其最終目的是刪除指定的Bucket。在刪除Bucket時(shí)還需要處理好hash碰撞鏈表維護(hù)的問(wèn)題。由于PHP7中hash碰撞只維護(hù)了一個(gè)單向鏈表（通過(guò)Bucket.val.u2.next來(lái)維護(hù)），所以在刪除Bucket時(shí)還需要找出hash碰撞鏈表中的前一項(xiàng)prev。最后，在刪除Bucket時(shí)如果當(dāng)前的hashtable的內(nèi)部指針（nInternalPointer）正好指向了要?jiǎng)h除的Bucket或存在遍歷操作，那么需要改變內(nèi)部指針的指向，同時(shí)在遍歷時(shí)跳過(guò)要?jiǎng)h除的Bucket。另外需要指出的是，并不是每一次刪除Bucket的操作都會(huì)回收相應(yīng)的內(nèi)存空間，通常刪除Bucket只是將其中val的類(lèi)型標(biāo)記為IS_UNDEF，只有在擴(kuò)容或要?jiǎng)h除的Bucket為最后一項(xiàng)并且相鄰的Bucket為IS_UNDEF時(shí)才會(huì)回收其內(nèi)存空間。

⒋數(shù)組遍歷

PHP5

由于PHP5中有專(zhuān)門(mén)用來(lái)記錄數(shù)組元素寫(xiě)入順序的雙向鏈表，所以數(shù)組的遍歷邏輯相對(duì)比較簡(jiǎn)單。

//數(shù)組的正向遍歷

ZEND_APIintzend_hash_move_forward_ex(HashTable*ht,HashPosition*pos)

HashPosition*current=pospos:ht-pInternalPointer;

IS_CONSISTENT(ht);

if(*current){

*current=(*current)-pListNext;

returnSUCCESS;

}else

returnFAILURE;

//數(shù)組的反向遍歷

ZEND_APIintzend_hash_move_backwards_ex(HashTable*ht,HashPosition*pos)

HashPosition*current=pospos:ht-pInternalPointer;

IS_CONSISTENT(ht);

if(*current){

*current=(*current)-pListLast;

returnSUCCESS;

}else

returnFAILURE;

emsp；PHP5中hashtable的數(shù)據(jù)結(jié)構(gòu)中有三個(gè)字段：pInternalPointer用來(lái)記錄數(shù)組遍歷過(guò)程中指針指向的當(dāng)前Bucket的地址；pListHead用來(lái)記錄保存數(shù)組元素寫(xiě)入順序的雙向鏈表的表頭；pListTail用來(lái)記錄保存數(shù)組元素寫(xiě)入順序的雙向鏈表的表尾。數(shù)組的正向遍歷從pListHead的位置開(kāi)始，通過(guò)不斷更新pInternalPointer來(lái)實(shí)現(xiàn)；反向遍歷從pListTail開(kāi)始，通過(guò)不斷更新pInternalPointer來(lái)實(shí)現(xiàn)。

PHP7

由于PHP7中數(shù)組的元素是按照寫(xiě)入的順序存儲(chǔ)，所以遍歷的邏輯相對(duì)簡(jiǎn)單，只是在遍歷過(guò)程中需要跳過(guò)被標(biāo)記為IS_UNDEF的項(xiàng)。

⒌hash碰撞

PHP5

前面在談?wù)摂?shù)組元素添加/修改的時(shí)候已有提及，每次在數(shù)組新增元素時(shí)，都會(huì)檢查并處理hash碰撞，即CONNECT_TO_BUCKET_DLLIST，代碼如下

CONNECT_TO_BUCKET_DLLIST(p,ht-arBuckets[nIndex]);

#defineCONNECT_TO_BUCKET_DLLIST(element,list_head)\

(element)-pNext=(list_head);\

(element)-pLast=NULL;\

if((element)-pNext){\

(element)-pNext-pLast=(element);\

在新增元素時(shí)，如果當(dāng)前arBuckets的位置沒(méi)有其他元素，那么只需要直接寫(xiě)入新增的Bucket即可，否則新增的Bucket會(huì)被寫(xiě)入hash碰撞雙向鏈表的表頭位置。

PHP7

前面已經(jīng)講過(guò)，PHP7中的hashtable是通過(guò)Bucket中的val.u2.next項(xiàng)來(lái)維護(hù)hash碰撞的單向鏈表的。所以，在往hashtable中添加新的元素時(shí)，最后需要先將nIndex位置的值寫(xiě)入新增的Bucket的val.u2.next中。而在刪除Bucket時(shí)，需要同時(shí)找出要?jiǎng)h除的Bucket所在的hash碰撞鏈表中的前一項(xiàng)，以便后續(xù)的hash碰撞鏈表的維護(hù)。

⒍擴(kuò)容

PHP5

在數(shù)組元素新增/修改的API中的最后有一行代碼ZEND_HASH_IF_FULL_DO_RESIZE(ht)來(lái)判斷當(dāng)前hashtable是否需要擴(kuò)容，如果需要?jiǎng)t對(duì)其進(jìn)行擴(kuò)容。

//判斷當(dāng)前hashtable是否需要擴(kuò)容

#defineZEND_HASH_IF_FULL_DO_RESIZE(ht)\

if((ht)-nNumOfElements(ht)-nTableSize){\

zend_hash_do_resize(ht);\

//hashtable擴(kuò)容（精簡(jiǎn)部分代碼）

ZEND_APIintzend_hash_do_resize(HashTable*ht)

Bucket**t;

if((ht-nTableSize1)0){/*Let'sdoublethetablesize*/

t=(Bucket**)perealloc(ht-arBuckets,(ht-nTableSize1)*sizeof(Bucket*),ht-persistent);

ht-arBuckets=t;

ht-nTableSize=(ht-nTableSize1);

ht-nTableMask=ht-nTableSize-1;

zend_hash_rehash(ht);

//擴(kuò)容后對(duì)hashtable中的元素進(jìn)行rehash（精簡(jiǎn)部分代碼）

ZEND_APIintzend_hash_rehash(HashTable*ht)

Bucket*p;

uintnIndex;

if(UNEXPECTED(ht-nNumOfElements==0)){

returnSUCCESS;

memset(ht-arBuckets,0,ht-nTableSize*sizeof(Bucket*));

for(p=ht-pListHead;p!=NULL;p=p-pListNext){

nIndex=p-hht-nTableMask;

CONNECT_TO_BUCKET_DLLIST(p,ht-arBuckets[nIndex]);

ht-arBuckets[nIndex]=p;

returnSUCCESS;

首先，PHP5hashtable擴(kuò)容的前提條件：數(shù)組中元素的數(shù)量超過(guò)hashtable的nTableSize的值。之后，hashtable的nTableSize會(huì)翻倍，然后重新為arBuckets分配內(nèi)存空間并且更新nTableMask的值。最后，由于nTableMask發(fā)生變化，需要根據(jù)數(shù)組元素的索引重新計(jì)算nIndex，然后將之前的Bucket關(guān)聯(lián)到新分配的arBuckets中新的位置。

PHP7

在PHP7的新增/修改hashtable的API中也有判斷是否需要擴(kuò)容的代碼ZEND_HASH_IF_FULL_DO_RESIZE(ht)，當(dāng)滿足條件時(shí)則會(huì)執(zhí)行擴(kuò)容操作。

#defineHT_SIZE_TO_MASK(nTableSize)\

((uint32_t)(-((nTableSize)+(nTableSize))))

#defineHT_HASH_SIZE(nTableMask)\

(((size_t)(uint32_t)-(int32_t)(nTableMask))*sizeof(uint32_t))

#defineHT_DATA_SIZE(nTableSize)\

((size_t)(nTableSize)*sizeof(Bucket))

#defineHT_SIZE_EX(nTableSize,nTableMask)\

(HT_DATA_SIZE((nTableSize))+HT_HASH_SIZE((nTableMask)))

#defineHT_SET_DATA_ADDR(ht,ptr)do{\

(ht)-arData=(Bucket*)(((char*)(ptr))+HT_HASH_SIZE((ht)-nTableMask));\

}while(0)

#defineHT_GET_DATA_ADDR(ht)\

((char*)((ht)-arData)-HT_HASH_SIZE((ht)-nTableMask))

//當(dāng)hashtable的nNumUsed大于或等于nTableSize時(shí)則執(zhí)行擴(kuò)容操作

#defineZEND_HASH_IF_FULL_DO_RESIZE(ht)\

if((ht)-nNumUsed=(ht)-nTableSize){\

zend_hash_do_resize(ht);\

#defineHT_HASH_RESET(ht)\

memset(HT_HASH(ht,(ht)-nTableMask),HT_INVALID_IDX,HT_HASH_SIZE((ht)-nTableMask))

#defineHT_IS_WITHOUT_HOLES(ht)\

((ht)-nNumUsed==(ht)-nNumOfElements)

//擴(kuò)容（精簡(jiǎn)部分代碼）

staticvoidZEND_FASTCALLzend_hash_do_resize(HashTable*ht)

if(ht-nNumUsedht-nNumOfElements+(ht-nNumOfElements5)){/*additionaltermistheretoamortizethecostofcompaction*/

zend_hash_rehash(ht);

}elseif(ht-nTableSizeHT_MAX_SIZE){/*Let'sdoublethetablesize*/

void*new_data,*old_data=HT_GET_DATA_ADDR(ht);

uint32_tnSize=ht-nTableSize+ht-nTableSize;

Bucket*old_buckets=ht-arData;

ht-nTableSize=nSize;

new_data=pemalloc(HT_SIZE_EX(nSize,HT_SIZE_TO_MASK(nSize)),GC_FLAGS(ht)IS_ARRAY_PERSISTENT);

ht-nTableMask=HT_SIZE_TO_MASK(ht-nTableSize);

HT_SET_DATA_ADDR(ht,new_data);

memcpy(ht-arData,old_buckets,sizeof(Bucket)*ht-nNumUsed);

pefree(old_data,GC_FLAGS(ht)IS_ARRAY_PERSISTENT);

zend_hash_rehash(ht);

}else{

zend_error_noreturn(E_ERROR,"Possibleintegeroverflowinmemoryallocation(%u*%zu+%zu)",ht-nTableSize*2,sizeof(Bucket)+sizeof(uint32_t),sizeof(Bucket));

//rehash（精簡(jiǎn)部分代碼）

ZEND_APIintZEND_FASTCALLzend_hash_rehash(HashTable*ht)

Bucket*p;

uint32_tnIndex,i;

if(UNEXPECTED(ht-nNumOfElements==0)){

if(!(HT_FLAGS(ht)HASH_FLAG_UNINITIALIZED)){

ht-nNumUsed=0;

HT_HASH_RESET(ht);

returnSUCCESS;

HT_HASH_RESET(ht);

i=0;

p=ht-arData;

if(HT_IS_WITHOUT_HOLES(ht)){

//Bucket中沒(méi)有被標(biāo)記為IS_UNDEF的項(xiàng)

do{

nIndex=p-h|ht-nTableMask;

Z_NEXT(p-val)=HT_HASH(ht,nIndex);

HT_HASH(ht,nIndex)=HT_IDX_TO_HASH(i);

p++;

}while(++iht-nNumUsed);

}else{

//Bucket中有被標(biāo)記為IS_UNDEF的項(xiàng)

uint32_told_num_used=ht-nNumUsed;

do{

if(UNEXPECTED(Z_TYPE(p-val)==IS_UNDEF)){

//Bucket中第一項(xiàng)被標(biāo)記為IS_UNDEF

uint32_tj=i;

Bucket*q=p;

if(EXPECTED(!HT_HAS_ITERATORS(ht))){

//hashtable沒(méi)有遍歷操作

while(++i