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

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

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

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

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

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

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

//元素插入順序記錄當前bucket的下一個和上一個bucket

structbucket*pListNext;

structbucket*pListLast;

//PHP5使用拉鏈法解決hash碰撞，pNext和pLast分別存儲當前bucket

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

structbucket*pNext;

structbucket*pLast;

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

}Bucket;

typedefstruct_hashtable{

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

uintnTableMask;/*nTableSize-1，用于計算索引*/

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

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

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

Bucket*pListHead;

Bucket*pListTail;

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

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

zend_boolpersistent;/*標識ht是否永久有效*/

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

zend_boolbApplyProtection;/*是否啟用遞歸保護*/

#ifZEND_DEBUG

intinconsistent;

#endif

}HashTable;

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

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

struct_zend_string{

zend_refcounted_hgc;

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

size_tlen;/*字符串key的長度*/

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

typedefstruct_Bucket{

zvalval;/*內(nèi)嵌zval結(jié)構(gòu)，存儲數(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作用相同，但實現(xiàn)邏輯稍有變化*/

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

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

uint32_tnNumOfElements;

uint32_tnTableSize;

uint32_tnInternalPointer;

zend_longnNextFreeElement;

dtor_func_tpDestructor;

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

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

現(xiàn)在來談談Bucket的存儲：在PHP5中，arBucket是一個C語言數(shù)組，長度為nTableSize，存儲的是指向Bucket的指針，發(fā)生hash碰撞的Bucket以雙向鏈表的方式連接。

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

//nTableMask為-2倍的nTableSize的無符號表示

#defineHT_SIZE_TO_MASK(nTableSize)\

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

//在通過idx查找Bucket時，data默認為Bucket類型，加idx表示向右偏移idx個Bucket位置

#defineHT_HASH_TO_BUCKET_EX(data,idx)\

((data)+(idx))

//在通過nIndex查找idx時，

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

//然后將nIndex轉(zhuǎn)換成有符號數(shù)（負數(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之所以設置為nTableSize的兩倍，是這樣在計算nIndex時可以減小hash碰撞的概率。

⒉添加/修改元素

PHP5

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

//hash碰撞雙向鏈表的維護

#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ù)組元素插入順序雙向鏈表的維護

#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*)){\

//值為指針類型的元素的更新\

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

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

//pDataPtr存儲元素值的地址，pData存儲pDataPtr的地址\

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

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

}else{\

//如果數(shù)組元素為值類型，則存入pData，此時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*)){\

//指針類型元素的初始化\

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

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

}else{\

//值類型元素的初始化\

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

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

(p)-pDataPtr=NULL;\

//hashtable初始化校驗，如果沒有初始化，則初始化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ù)組元素的新增或更新（精簡掉了一些宏調(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碰撞鏈表維護

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

if(pDest){

*pDest=p-pData;

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

CONNECT_TO_GLOBAL_DLLIST(p,ht);

ht-arBuckets[nIndex]=p;

ht-nNumOfElements++;

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

returnSUCCESS;

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

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

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

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

PHP7

PHP7在hashtable的數(shù)據(jù)結(jié)構(gòu)上做了比較大的改動，同時放棄了使用雙向鏈表的方式來維護hash碰撞和數(shù)組元素的寫入順序，在內(nèi)存管理以及性能上得到了提升，但理解起來卻不如PHP5中的實現(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ù)組添加/修改元素（精簡了部分代碼）

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-

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

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

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

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

⒊刪除元素

PHP5

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

//刪除Bucket的代碼（精簡了部分代碼片段）

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ù)組在刪除元素時，仍然是先根據(jù)給定的key計算hash，然后找到arBucket的nIndex，最終找到需要刪除的Bucket所在的hash碰撞的鏈表，通過遍歷鏈表，找到最終需要刪除的Bucket。

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

PHP7

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

#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))){

//如果當前hashtable的內(nèi)部指針指向了要刪除的Bucket或當前hashtable有遍歷

//操作，那么需要避開當前正在被刪除的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ù)組的末尾，則同時回收與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類型的索引

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時還需要處理好hash碰撞鏈表維護的問題。由于PHP7中hash碰撞只維護了一個單向鏈表（通過Bucket.val.u2.next來維護），所以在刪除Bucket時還需要找出hash碰撞鏈表中的前一項prev。最后，在刪除Bucket時如果當前的hashtable的內(nèi)部指針（nInternalPointer）正好指向了要刪除的Bucket或存在遍歷操作，那么需要改變內(nèi)部指針的指向，同時在遍歷時跳過要刪除的Bucket。另外需要指出的是，并不是每一次刪除Bucket的操作都會回收相應的內(nèi)存空間，通常刪除Bucket只是將其中val的類型標記為IS_UNDEF，只有在擴容或要刪除的Bucket為最后一項并且相鄰的Bucket為IS_UNDEF時才會回收其內(nèi)存空間。

⒋數(shù)組遍歷

PHP5

由于PHP5中有專門用來記錄數(shù)組元素寫入順序的雙向鏈表，所以數(shù)組的遍歷邏輯相對比較簡單。

//數(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)中有三個字段：pInternalPointer用來記錄數(shù)組遍歷過程中指針指向的當前Bucket的地址；pListHead用來記錄保存數(shù)組元素寫入順序的雙向鏈表的表頭；pListTail用來記錄保存數(shù)組元素寫入順序的雙向鏈表的表尾。數(shù)組的正向遍歷從pListHead的位置開始，通過不斷更新pInternalPointer來實現(xiàn)；反向遍歷從pListTail開始，通過不斷更新pInternalPointer來實現(xiàn)。

PHP7

由于PHP7中數(shù)組的元素是按照寫入的順序存儲，所以遍歷的邏輯相對簡單，只是在遍歷過程中需要跳過被標記為IS_UNDEF的項。

⒌hash碰撞

PHP5

前面在談論數(shù)組元素添加/修改的時候已有提及，每次在數(shù)組新增元素時，都會檢查并處理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);\

在新增元素時，如果當前arBuckets的位置沒有其他元素，那么只需要直接寫入新增的Bucket即可，否則新增的Bucket會被寫入hash碰撞雙向鏈表的表頭位置。

PHP7

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

⒍擴容

PHP5

在數(shù)組元素新增/修改的API中的最后有一行代碼ZEND_HASH_IF_FULL_DO_RESIZE(ht)來判斷當前hashtable是否需要擴容，如果需要則對其進行擴容。

//判斷當前hashtable是否需要擴容

#defineZEND_HASH_IF_FULL_DO_RESIZE(ht)\

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

zend_hash_do_resize(ht);\

//hashtable擴容（精簡部分代碼）

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);

//擴容后對hashtable中的元素進行rehash（精簡部分代碼）

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

PHP7

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

#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))

//當hashtable的nNumUsed大于或等于nTableSize時則執(zhí)行擴容操作

#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)

//擴容（精簡部分代碼）

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（精簡部分代碼）

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中沒有被標記為IS_UNDEF的項

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中有被標記為IS_UNDEF的項

uint32_told_num_used=ht-nNumUsed;

do{

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

//Bucket中第一項被標記為IS_UNDEF

uint32_tj=i;

Bucket*q=p;

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

//hashtable沒有遍歷操作

while(++i