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函数的实现，下次再来个分析（二）吧。

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