PHP源码解析-array分析

在PHP中,数组是使用频率非常高的数据结构,相对于java,c++,php的数组简直是太好用了,不用区分是数字key,还是字符串key,为开发带来了极大的便利。

但是你曾经想一探php实现数组的奥秘吗?

相信大家都知道,PHP的数组结构,其内部是使用hashTable结构来实现的,所以我们在php的源码中没有看到zend_array文件,而是zend_hash.h和zend_hash.c两个入口文件。

在讲PHP的数组实现前,我们先来简单说说HashTable吧!

HashTable有称散列表,是通过key-value的方式来高效的访问数据的一种结构。哈希表是数组和链表的一种合并,集成了数组的寻址快,链表的插入快的特点于一身。

HashTable主要分为两个环节:

1. 哈希函数:哈希函数将要查找的值转换成数字索引,通过数字索引可以快速的找到值存在的位置。

2. 哈希碰撞:理想情况下,不同的值通过哈希函数后,出来的结果是不一样的;如果不一样的值,哈希后出来一样的数字,我们称之为哈希碰撞;因此HashTable必须要解决哈希碰撞,主要有两种:链表法,开放寻址法。

简单介绍下链表法和开放寻址法:

链表法:当遇到hash的key有冲突的时候,就在对应的数组元素后,挂一个链表,如上图。

开发寻址法:当遇到hash的key有冲突的时候,会去寻找下一个数组元素,如果下一个元素是空的,则占用;如果被占用,则继续寻找下一个元素,直到找到空闲的元素。如下图(网上截图):

正餐开始啦!

在讲php的实现前,先了解一下数组的数据结构,在zend_type.h文件中,可以找到如下的定义(如图,具体的注释已写入图中):

上面依次是zend_array,Bucket,zval类型的结构。

图一的 gc: 引用计数,垃圾回收使用。

图一中的nTableMask的解释写错了,nTableMask是哈希值计算掩码,这个值是负的,为什么是负值,在下面的介绍会讲到。

注意zval结构中的next,这个是为hash结构预留的一个字段,hash碰撞时产生的链表是使用这个字段连起来的。

了解了zend_array的数据结构,接着看看数组的初始化吧:

注意:nTableMask=-2,二进制(8位的二进制)1111 1110,可以看到实际在初始化的时候,赋了个很大的负值。

为了更好的理解整个hash结构,我们来举个例子说明一下这个结构:

$mapData = array(

‘hello’ => ‘haha’,

1 => ‘me to’

‘world’ => ‘world’,

2 => 2,

);

unset($mapData[1]);

上面的hash结构应该是什么样的呢?arData存储的结果应该是什么样呢?如图:

图中下面每个arData数组的元素,从图中可以看到,左边负数是哈希值取模后的值,存储的是右边arData的索引;如-8冲突了,则存储了链表的头元素。

arData[0]: key=‘hello’,h=xx(具体某个值),val = ‘haha’

arData[1]: val是 type=IS_UNDEF的zval(被unset后,不是立即被删除,而是置成IS_UNDEF)

arData[2]: key=‘world’,h=xx(具体某个值),val = ‘world’

arData[3]: key=NULL,h=2(可能会哈希值冲突),val = 2

….

上面那个例子很具体的解释了nNumUsed,nNumOfElements,arData的意义。

从图中arData是Bucket类型的指针,用来具体存储每个元素的key,value。

同时发现,arData是按照插入元素的顺序存储数据的,所以数组的顺序也是靠这个来保证。

对于IS_UNDEF,源码中随处可见对IS_UNDEF类型的判断。

奥,忘记说了,数组初始化图中说到的漏洞,具体可以在知乎搜索php执行漏洞。

HT_FLAGS(ht) :指得是zend_array里面的u.flags字段,这个字段包含有:HASH_FLAG_STATIC_KEYS(静态),HASH_FLAG_INITIALIZED(初始化),HASH_FLAG_PACKED(压缩)等。这个标志在操作数组时会用到。

对于增加或者更新数组,都是经过哪些逻辑呢?

不多说了,见图吧。

太多了逻辑,写不下去了,看源码还真是挺费劲的,还想看看hash函数的实现,下次再来个分析(二)吧。

以上笔者根据源码和网上的一些见解,自己领悟的,如有错误,还请下方留言,大家一起交流!!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190129G1B94Y00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券