浅析PHP数组的实现

蜀风

一. PHP数组特点介绍       php数组可谓是php的核心，其key=>value的存储结构，让我们处理数据可以游刃有余，并且在一般情况下增删查改都是O(1)的时间复杂度，并表现出一些特点让我们对其内部的结构充满了好奇。
「数组内存申请不需要自己控制」：数组的内存申请和释放是内部控制的，不需要人为的去干预。
「兼容关联数组和索引数组」：数组可以以数字为下标进行操作，也可以以字符串为下标进行操作，其实他俩本质上都是key=>value的格式。
「可以无key值存储」：像a[] = 10; 这样去存储一个value值，事实上他也是有key值的。
「不会出现数组越界的问题」：不会像我们操作C/C++等语言一样，要注意数组的边界，一定不能正向或者逆向越界。在php中不会有这些问题的存在。
「value值无严格的定义和统一」：这里就是php内部自己实现了一个范型。
「foreach遍历数组与插入顺序有关」：插入顺序和遍历输出一致。
二. PHP数组结构的演变这个地方主要讲PHP5.6=>PHP7.0=>PHP7.1的演变过程

​
PHP5.6的数组结构
我们可以看到，数组本质就是一个hashtable结构，左侧的0~nTablemask便是hash下标，而后面有一个双向链表，便是我们通常所说的hash冲突的链地址法。
而绿色的双向链表，则是foreach遍历用的，这个地方用双向链表，主要是为了逆序访问来用的，遍历的时候，就是从pListHead开始不断的next便可以遍历所有的元素。这样要比下标遍历hashtable快得多。
但是这个结构有很明显的缺点：
①. 每次插入/删除元素都要申请/释放内存，这样会严重的导致内存碎片化，降低内存的使用率。
②. 再者，每次插入元素的时候都要去申请内存，会有一次寻址的过程，时间效率低。
③. 指针结构很复杂，有大量的指针操作。

​
PHP7.0的数组结构
针对上面5.6所有的问题，提出了如上的结构。arData结构便是我们插入数据的结构，是一段连续的内存，在初始化/数组扩充时一次性内存申请好，这样内存便不会产生碎片化问题，并且我们看，hash冲突的时候是单链表，并且没有插入元素时候的双向链表，因为我们可以直接扫描数组便可以顺序/逆序访问插入的数据。

​
PHP7.1的数组结构
如上是最新的数据结构，最主要的区别是把7.0的两段内存转化为一段内存，算是在内存上的继续优化。他的内存申请是从下标-8位置申请的，然后移动指针到key1位置。
三. PHP7.0数组源码实现3.1 PHP7.0数组的主要数据结构
​
Bucket结构
Bucket结构便是我们所说的保存插入数据的结构。主要包括：key(字符串，如果是数字下标，转化位字符串), value, h(只会计算一次，如果是数组下标，直接把key作为h)。

​
PHP数组的结构
这便是PHP7.0的数组结构，我后面讲全部是用7.0结构讲，比较清晰。nNextFreeElement是无key值存储时使用的数据，用来分配key值。
3.2 PHP数组的hash方法
​
PHP hash源码
如上是php的hash源码，看一眼容易把人瞎蒙，然而把它简化一下便是：

​
PHP 源码转化
简单讲一下。其中源码中把 hash*33 转化为 (hash<<5) + hash
在一个就是，使用了循环展开策略，减少不必要的循环判断，在一个是连续的执行相同的指令，提高指令的cache命中率。可以看着：https://en.wikipedia.org/wiki/Loop_unrolling
那么计算出hash值来之后，并不是我们想要的下标，因为很有可能超过了hashmask值，所以需要一步计算来得到index。
•7.0：
hashmask = tablesize – 1;   //tablesize一定是2的指数倍，和申请内存有关系，后面讲
h = hashcode & hashmask;  //计算index
hashmask=7(10)=111(2)       //十进制下的7转为二进制下的111
0<=h<8                                 //所有值 & hashmask 一定在0~7之间
•7.1：
hashmask = -tablesize;
h = hashcode | hashmask;
hashmask=-8(10)=11111000(2补码)
-8<=h<=-1
7.1的结构因为是hash负下标，所以用的另一种计算策略，大同小异。
3.3 PHP数组插入数据
​
PHP插入数据的流程图
大致流程如上，看一下就好。讲一下插入数据的结构变化。

​
插入数据结构变化
在我们插入key6这个key值之后，在arData数据往后排，我们假设他与key1的hash冲突，所以使用链地址法，直接插入到链表首部。
3.4 PHP数组删除数据在上面的结构，假如我们删除key1，会有两种考虑。
①. 删除该元素之后，我们是否要保证空间的利用率，把后面的数据移动，覆盖当前位置。
②. 删除元素之后，直接把该位置空出。
其实第一种策略是不可接受，因为这样会导致时间复杂度退化为O(n)，而第二种策略，我们控制当前位置之后，我们可以在内存扩充时，把这些空位置给删除掉即可。
​
PHP数组删除数据
3.4 PHP数组内存申请及rehash假设我们要在如下结构中插入key9
​
PHP 数组结构
发现当前arData已经满了，所以我们申请新内存(初始大小位2，以2的倍数不断扩充)，把所有数据以内存的形式copy过去，然后扫描数组，把无用的数据给删除掉(用移动后面元素的策略)。因为nTableMask数值改变了然后进行rehash。
这里有一个点值得提一下：把原数据copy过去的时候，我们可以选择遍历原先的数组，把有用的数据copy过去，也可以先把原内存的数据复制到新内存的位置，然后去遍历数组去移动数据。PHP实现选择了第二种，这样考虑应该是我们删除元素的次数比较少，直接以内存的形式copy数据要比遍历copy的速度快，在权衡之下选择了第二种。

​
插入数据之后
结构变化如上图。
四. PHP数组的可优化点4.1 PHP数组的退化案例本案例参考的鸟哥的博客。

​
攻击代码
大概测了一下
​
运行结果
我们可以看到，时间效率差别很大。我们来分析一下为什么会这样。
•插入元素:key=0,1*65536,2*65536,….,65535*65536
•插入元素特点:h=key&65535=0,生成绝对的hash冲突导致退化1*****00000000&0****011111111=0
•大致的插入计算次数：1+2+3+4+5+…+65536(每次插入都会冲突，从而会去查询是否有相同的key值，所以会有扫描的次数总和如此)
•导致插入元素时间复杂度退化为O(n*(1+n)/2)=O(n^2)
那么65536^2在计算机1s处理10^8运算的情况下，大概36s以上，所以运行结果算是可预期的。

​
hash冲突的结构
4.2 可进行优化的策略我们参考Java中hashtable的实现来使用红黑树解决这个问题。
•①.设定链表冲突长度的阀值
•②.当链表长度超过阀值的时候，以key值为键值进行红黑树的转化，key全是字符串，所以我们可以以key的字典序进行排序
•③.Hashtable的指针指向树根
•④.增删查改，不断对红黑树结构进行调整
•⑤.使增删查改时间复杂度达到最差为O(logn)
我们来看下结构的变化为：

​
加入红黑树后的结构变化
如果不了解红黑树，可以去参考一下《算法导论》中的详解
五. PHP数组的总结「数组内存申请不需自己控制」
hashtable内存大小与arData大小相同，并且一定为2的指数倍不断扩展
「兼容关联数组和索引数组」
索引是hash值同时也是key值，转化为关联数组，关联数组用hashtable实现
「可以无索引(key值)存储」
无索引存储时，会自动为其分配最后一个没有被使用过的下标来作为key和hash值进行存储
「不会出现数组越界的情况」
索引即hash值，用无符号长整形存储，不会出现负向越界
索引的大小与内存的大小没有绝对的关系，不会出现正向越界
「value值无严格的定义或统一」
php对value值进行了范型处理
「foreach遍历数组与插入顺序有关」
foreach是对arData遍历，而arData是顺序存储的
用foreach比用for进行下标访问永远要快

巴亮

谢谢楼主

雒汕帼

非常好，谢谢分析。

q9yy

楼主你太好了.........

阚霞

谢谢楼主~~~~~~~