从PHP数组实现原理看线性表数据结构

线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线串起来，再存储到物理空间中”。最简单的线性表就是数组了。虽然PHP的数组本身不是由基础的数据结构构成，但是其内部实现方式应用到了大部分的线性表数据结构。今天，借着学习线性表数据结构的机会，重新回顾PHP数组的内部实现原理。

PHP数组的内部实现

数组是PHP中很强大且非常重要的数据类型。它既支持单纯的数字索引数组又支持键值对数组，其中键值对数组类似于 java的 HashMap。由于采用了哈希表实现能够保证基本查找时间复杂度为 O(1)，而且还能够保证数据遍历的顺序。

首先看看PHP在内核C语言的数据结构长什么样

看一下在php代码中，给数组插入一个元素会发生什么

$arr = ['name'=>'admin'];

1.内核首先会创建一个_zend_array数据对象。初始化数组的大小为HT_MIN_SIZE，PHP中定义了HT_MIN_SIZE为8;所以当数组元素小于8的时候，插入数据并不会进行数组扩容。

2.使用Times 33hash算法，将 name转换成一个长整形的数。

3.在arData[nNumUsed++]中保存 Bucket 数据中 key是数组的键名，h中保存key的hash之后的整数（负数），val的u2.next 保存 arData[h]的地址。将转换表存储以 arData 起始指针为起点做镜面映射存储。这样，我们不需要额外的空间存储，在分配 arData 空间的同时也分配了转换表。

查找数组的时候，根据键名直接hash之后，可以直接定位到实际保存键值的Bucket，遍历的时候，因为arData本身是有序的C数组，遍历数组之后可以获取到保存键值的Bucket。因此PHP的数组既能够以O(1)的复杂度查询到数组，又能够顺序的遍历数组元素。

对应源码实现逻辑的主要核心代码如下：

上面的过程省略了hash冲突的情况。但是即使是从上面简单的版本中也可以发现PHP数组的实现运用了很多的数据结构知识。

Bucket *arData;是一个C语言数组，对应数据结构中的有序表。Bucket之间，通过val的u2.next又构成了一个链表结构。

同时，PHP在处理hash冲突情况的时候，是将所有的冲突的键名数据退化成一个链表。而这种处理方式，是绝大部分hash处理的方式。

顺序表

顺序表的定义如下:

所谓顺序表就是顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构。

上面PHP核心代码中 arData就是一个顺序表。

序表的特点：

1. 在线性表中逻辑上相邻的数据元素，在物理存储上也是相邻的。

2. 存储密度高，但要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费。

3. 便于随机存储。只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

4. 不便于插入和删除操作，这是因为在顺序表上进行的插入和删除操作会引起大量数据元素的移动。

顺序表存在的问题:

1. 物理上相邻存储，不便于内存利用。例如一个容量为10的数组，需要内存为10字节，但是目前没有连续10个字节空余的内存空间，但是有很多不连续的小于10字节的内存空间，这样也没办法分配；

2. 顺序表的容量很难确定。对于C语言而言，定义一个数组是需要指定数组大小的。这个大小就是为了方便底层用于申请连续内存空间。PHP源码中在初始化一个空数组的时候，也会先创建一个长度为16的arData数组，在需要扩容的时候在进行数组扩容。

3. 插入元素不方便，需要移动整个顺序表元素

链表

链表的数据结构，是针对顺序表的问题而提出的。链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。在PHP的数组的源码中，每个Bucket就是链表中的一个节点。通过Bucket.u2.next指向下一个节点(虽然本身是为了实现hash查找)。

根据链表的链接方式，分为单链表，双链表。

单链表的每一个节点中只有指向下一个结点的指针，不能进行回溯，适用于节点的增加和删除。

双链表的每一个节点中既有指向下一个结点的指针，也有指向上一个结点的指针，可以快速的找到当前节点的前一个节点，适用于需要双向查找节点值的情况

链表的优点：

插入和删除的效率高，只需要改变指针的指向就可以进行插入和删除。

内存利用率高，不会浪费内存，可以使用内存中细小的不连续的空间，只有在需要的时候才去创建空间。大小不固定，拓展很灵活。

总结

本文以PHP7.4的源码为基础，介绍了PHP内部是如何实现数组的有序同时保证键值查找的O(1)的查询速度。从PHP数组的实现出发，介绍了线性表中有序表，链表的基本内容以及各自的特点。皮毛内容，希望对大家有所帮助。

[1] PHP7 哈希表实现原理 : http://www.sohu.com/a/119748257_464029 [2] 链表: https://blog.csdn.net/Shuffle_Ts/article/details/95055467 [3] 数据结构(C语言版)系列一 线性表: https://www.cnblogs.com/wwf828/p/9503821.html