关于PHP5和PHP7中数组实现方式的比较总结

第关于PHP5和PHP7中数组实现方式的比较总结typedefstructbucket{

ulongh;/*对于索引数组，存储key的原始值；对于关联数组，存储key的hash之后的值*/

uintnKeyLength;/*关联数组时存储key的长度，索引数组此值为0*/

void*pData;/*指向数组value的地址*/

void*pDataPtr;/*如果value为指针，则由pDataPtr记录vlaue，pData则指向pDataPtr*/

//PHP5中数组元素的顺序是固定的，无论什么时候遍历，数组元素总是与插入时的顺序一致

//PHP5中使用双向链表来保证数组元素的顺序，pListNext和pListLast分别按照

//元素插入顺序记录当前bucket的下一个和上一个bucket

structbucket*pListNext;

structbucket*pListLast;

//PHP5使用拉链法解决hash碰撞，pNext和pLast分别存储当前bucket

//在冲突的双向链表中的下一个和上一个相邻的bucket

structbucket*pNext;

structbucket*pLast;

constchar*arKey;/*关联数组是存储key的原始值*/

}Bucket;

typedefstruct_hashtable{

uintnTableSize;/*当前ht所分配的bucket的总数，2^n*/

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

uintnNumOfElements;/*实际存储的元素的数量*/

ulongnNextFreeElement;/*下一个可以被使用的整数key*/

Bucket*pInternalPointer;/*数组遍历时，记录当前bucket的地址*/

Bucket*pListHead;

Bucket*pListTail;

Bucket**arBuckets;/*记录bucket的C语言数组*/

dtor_func_tpDestructor;/*删除数组元素时内部调用的函数*/

zend_boolpersistent;/*标识ht是否永久有效*/

unsignedcharnApplyCount;/*ht允许的最大递归深度*/

zend_boolbApplyProtection;/*是否启用递归保护*/

#ifZEND_DEBUG

intinconsistent;

#endif

}HashTable;

//PHP7中hashtable的数据结构

//PHP7中个子版本以及阶段版本中对hashtable的数据结构的定义会有微小的差别，这里使用的是PHP7.4.0中的定义

struct_zend_string{

zend_refcounted_hgc;

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

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

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

typedefstruct_Bucket{

zvalval;/*内嵌zval结构，存储数组的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作用相同，但实现逻辑稍有变化*/

Bucket*arData;/*存储bucket相关的信息*/

uint32_tnNumUsed;/*ht中已经使用的bucket的数量，在nNumOfElements的基础上加上删除的key*/

uint32_tnNumOfElements;

uint32_tnTableSize;

uint32_tnInternalPointer;

zend_longnNextFreeElement;

dtor_func_tpDestructor;

不考虑其他开销，单从Bucket所占用的空间来看：在PHP5中，考虑到内存对齐，一个Bucket占用的空间为72字节；在PHP7中，一个zend_value占8字节，一个zval占16字节，一个Bucket占32字节。相比之下，PHP7中Bucket的内存空间消耗比PHP5低了一半以上。

具体PHP5数组的内存消耗情况，之前的文章已有讲解，这里不再赘述

现在来谈谈Bucket的存储：在PHP5中，arBucket是一个C语言数组，长度为nTableSize，存储的是指向Bucket的指针，发生hash碰撞的Bucket以双向链表的方式连接。

在PHP7中，Bucket按照数组元素写入的顺序依次存储，其索引值为idx，该值存储在*arData左侧的映射区域中。idx在映射区域中的索引为nIndex，nIndex值为负数，由数组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转换成了uint32_t*类型的数组

//然后将nIndex转换成有符号数（负数），然后以数组的方式查找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中数组元素的添加和修改，由于PHP5中数组元素的插入顺序以及hash碰撞都是通过双向链表的方式来维护，所以虽然实现起来有些复杂，但理解起来相对容易一些。

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

//数组元素插入顺序双向链表的维护

#defineCONNECT_TO_GLOBAL_DLLIST(element,ht)\

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

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

(ht)-pInternalPointer=(element);\

//数组元素的更新

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

//如果数组元素为值类型，则存入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);\

//数组元素的初始化

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

//数组元素的新增或更新（精简掉了一些宏调用和代码片段)

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

//数组元素更新逻辑

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;

//数组元素新增逻辑

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;

//数组元素写入顺序维护

CONNECT_TO_GLOBAL_DLLIST(p,ht);

ht-arBuckets[nIndex]=p;

ht-nNumOfElements++;

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

returnSUCCESS;

PHP5中的数组在新增或修改元素时，首先会根据给定的key计算得到相应的hash值，然后据此得到arBuckets的索引nIndex，最终得到链表中第一个Bucket（hash碰撞链表的表头），即p。

如果是更新数组中已有的项，那么会从p开始遍历hash碰撞链表，直到找到arkey与给定的key相同的Bucket，然后更新pData。

如果是向数组中新增项，首先会判断给定的key是否为internedstring类型，如果是，那么只需要为Bucket申请内存，然后将p-arKey指向给定的key的地址即可，否则在为新的Bucket申请内存的同时还需要为给定的key申请内存，然后将p-arKey指向为key申请的内存的地址。之后会对新申请的Bucket进行初始化，最后要做的两件事：维护hash碰撞链表和数组元素写入顺序链表。在维护hash碰撞的链表时，新增的Bucket是放在链表头的位置；维护数组元素写入顺序的链表时，新增的Bucket是放在链表的末尾，同时将hashtable的pListTail指向新增的Bucket。

关于PHP中的internedstring，之前在讲解PHP7对字符串处理逻辑优化的时候已经说明，这里不再赘述

PHP7

PHP7在hashtable的数据结构上做了比较大的改动，同时放弃了使用双向链表的方式来维护hash碰撞和数组元素的写入顺序，在内存管理以及性能上得到了提升，但理解起来却不如PHP5中的实现方式直观。

#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中数组添加/修改元素（精简了部分代码）

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的区别：

按图中示例，此时nNumUsed的值应该为5，但nNumOfElements的值则应该为3。在PHP7中，数组元素按照写入顺序依次存储，而nNumUsed正好可以用来充当数组元素存储位置索引的功能。

另外就是p=arData+idx，前面已经讲过arData为Bucket类型，这里+idx意为指针从arData的位置开始向右偏移idx个Bucket的位置。宏调用HT_HASH_EX也是同样的道理。

最后就是Z_NEXT(p-val)，PHP7中的Bucket结构都内嵌了一个zval，zval中的联合体u2中有一项next用来记录hash碰撞的信息。nIndex用来标识idx在映射表中的位置，在往hashtable中新增元素时，如果根据给定的key计算得到的nIndex的位置已经有值（即发生了hash碰撞），那么此时需要将nIndex所指向的位置的原值记录到新增的元素所对应的Bucket下的val.u2.next中。宏调用HT_IDX_TO_HASH的作用是根据idx计算得到Bucket的以字节为单位的偏移量。

⒊删除元素

PHP5

在PHP5中，数组元素的删除过程中的主要工作是维护hash碰撞链表和数组元素写入顺序的链表。

//删除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中数组在删除元素时，仍然是先根据给定的key计算hash，然后找到arBucket的nIndex，最终找到需要删除的Bucket所在的hash碰撞的链表，通过遍历链表，找到最终需要删除的Bucket。

在实际删除Bucket的过程中，主要做的就是维护两个链表：hash碰撞链表和数组元素写入顺序链表。再就是释放内存。

PHP7

由于PHP7记录hash碰撞信息的方式发生了变化，所以在删除元素时处理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的内部指针指向了要删除的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在数组的末尾，则同时回收与Bucket相邻的已经被删除的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中数组元素的删除，其最终目的是删除指定的Bucket。在删除Bucket时还需要处理好hash碰撞链表维护的问题。由于PHP7中hash碰撞只维护了一个单向链表（通过Bucket.val.u2.next来维护），所以在删除Bucket时还需要找出hash碰撞链表中的前一项prev。最后，在删除Bucket时如果当前的hashtable的内部指针（nInternalPointer）正好指向了要删除的Bucket或存在遍历操作，那么需要改变内部指针的指向，同时在遍历时跳过要删除的Bucket。另外需要指出的是，并不是每一次删除Bucket的操作都会回收相应的内存空间，通常删除Bucket只是将其中val的类型标记为IS_UNDEF，只有在扩容或要删除的Bucket为最后一项并且相邻的Bucket为IS_UNDEF时才会回收其内存空间。

⒋数组遍历

PHP5

由于PHP5中有专门用来记录数组元素写入顺序的双向链表，所以数组的遍历逻辑相对比较简单。

//数组的正向遍历

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;

//数组的反向遍历

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的数据结构中有三个字段：pInternalPointer用来记录数组遍历过程中指针指向的当前Bucket的地址；pListHead用来记录保存数组元素写入顺序的双向链表的表头；pListTail用来记录保存数组元素写入顺序的双向链表的表尾。数组的正向遍历从pListHead的位置开始，通过不断更新pInternalPointer来实现；反向遍历从pListTail开始，通过不断更新pInternalPointer来实现。

PHP7

由于PHP7中数组的元素是按照写入的顺序存储，所以遍历的逻辑相对简单，只是在遍历过程中需要跳过被标记为IS_UNDEF的项。

⒌hash碰撞

PHP5

前面在谈论数组元素添加/修改的时候已有提及，每次在数组新增元素时，都会检查并处理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

前面已经讲过，PHP7中的hashtable是通过Bucket中的val.u2.next项来维护hash碰撞的单向链表的。所以，在往hashtable中添加新的元素时，最后需要先将nIndex位置的值写入新增的Bucket的val.u2.next中。而在删除Bucket时，需要同时找出要删除的Bucket所在的hash碰撞链表中的前一项，以便后续的hash碰撞链表的维护。

⒍扩容

PHP5

在数组元素新增/修改的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扩容的前提条件：数组中元素的数量超过hashtable的nTableSize的值。之后，hashtable的nTableSize会翻倍，然后重新为arBuckets分配内存空间并且更新nTableMask的值。最后，由于nTableMask发生变化，需要根据数组元素的索引重新计算nIndex，然后将之前的Bucket关联到新分配的arBuckets中新的位置。

PHP7

在PHP7的新增/修改hashtable的API中也有判断是否需要扩容的代码ZEND_HASH_IF_FULL_DO_RESIZE(ht)，当满足条件时则会执行扩容操作。

#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时则执行扩容操作

#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