php数组的基础结构介绍-5G云源码分享网

如果下载的源码需要作者授权,请更换源码。

本站免费分享资源不会增加授权

本篇文章给大家带来的内容是关于组的基础结构介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

以下为PHP数组的基础结构,插入,查找和rehash过程。

基础结构:

struct_zend_array{zend_refcounted_hgc;union{struct{ZEND_ENDIAN_LOHI_4(zend_ucharflags,zend_ucharnApplyCount,zend_ucharnIteratorsCount,zend_ucharconsistency)}v;uint32_tflags;}u;uint32_tnTableMask;//哈希值计算掩码,等于nTableSize的负值(nTableMask=-nTableSize)Bucket*arData;//存储元素数组,指向第一个Bucketuint32_tnNumUsed;//已用Bucket数uint32_tnNumOfElements;//哈希表有效元素数=nNumUsed-num(is_undef)uint32_tnTableSize;//哈希表总大小,为2的n次方,最小为8uint32_tnInternalPointer;//怀疑是内部指针zend_longnNextFreeElement;//下一个可用的数值索引arr[]=1;arr[a]=2;arr[]=3;则nNextFreeElement=2;dtor_func_tpDestructor;};typedefstruct_Bucket{zvalval;//存储的具体valuezend_ulongh;//hashvalue(ornumericindex)zend_string*key;//stringkeyorNULLfornumerics}Bucket;

说明:

数组存放的时候先按照顺序保存value,再保存value的位置。

存放记录的数组称做散列表,这个数组用来存储value,而value按顺序保存,其存储位置会保存在由key计算hash取模nTableMask得到的idx中。

数组初始化的时候最小大小为8,以此为16,32,64。

数组初始化的时候边做的idx区会全部初始化为-1,rehash的时候也会初始化为-1。

数组中删除一个元素的时候,是把该删除的元素的type标记为is_undef,并且nNumOfEmelment1,如果该元素为最后一个元素,那么nNumUsed1。

插入:

以$arr=[a=1,b=2]为例:

首先把1放到数组中,其val。

u2。

next=-1,根据其下标a计算hash,然后hash取模nTableMask得到一个idx,在该idx的位置保存前边保存1的索引nindex。

再存放2,其val。

u2。

next=-1,如果根据其下标b计算hash取模nTableMask得到的idx中已经有值,那么说明出现了哈希碰撞,这个时候把当前idx中的值取出来保存到当前val。

u2。

next,把保存2的索引nindex保存在当前idx,以此类推。

查找:

根据下标a计算hash取模nTableMask得到一个idx,拿到该idx中的值nindex去arData中查找,如果找到的位置中的key!

=a,那么找不到;如果找到的位置中的key==a,那么检查其u2。

next,如果为-1,那么找到了;如果不为-1,说明插入的过程中出现了哈希冲突,那么根据u2。

next继续在arData中查找,直到找到为止。

rehash:

rehash的时候,首先把nindex区的所有记录全部重置为-1,然后从第一个元素开始挪动指针*p,如果元素没有被标记为is_undef,那么重新计算该元素的keyhash并放到nindex,然后循环,p++。

如果元素被标记为is_undef,那么继续挪动指针p++,并设置一个新的指针j指向该位置,继续循环,把后边不为is_undef的元素一个一个挪到前边来,p每次移动,j遇到is_undef就不移动,直到被赋值。

一直挪动到最后的nNunUsed,那么把j赋值给nNunUsed,之后再插入元素的时候就从这个位置开始插入,以前的元素直接被覆盖就是了。

AD:【5G云技术交流群】入群打赏4。

8,打赏备注QQ号,核对后进群

0个人已赞赞一个收藏(0)打赏

入群打赏请备注QQ,购买打赏请备注邮箱


Leave Your Comments