欢迎大家来到IT世界,在知识的湖畔探索吧!

hello，大家好，我是张张，「架构精进之路」公号作者。

在PHP中，数组数据结构的应用处理是使用频率非常高的，相对于Java、C++ 这种强类型语言来说，PHP的数组简直可以说是太好用了，可以存储各种类型的数据（如：数字、字符串甚至对象等），为开发带来了极大的便利。

基于 PHP 数组的强大特性，我们可以轻易实现更加复杂的数据结构，比如栈、队列、列表、集合、字典等。

你是否迫不及待的想要一探究竟：PHP到底是如何实现数组的呢？

1、PHP数组底层数据结构

PHP 数组其内部是使用 HashTable 结构来实现的，那就先来简单说说HashTable吧！

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

HashTable主要分为两个环节：

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

2. 哈希碰撞：理想情况下，不同的值通过哈希函数后，出来的结果是不一样的；如果不一样的值，哈希后出来一样的数字，我们称之为哈希碰撞。

因此应用 HashTable 就必须要面临解决哈希碰撞的问题，主要的解法有两种：链表法，开放寻址法。

在zend_type.h文件中，可以找到 HashTable 的主要结构定义如下：

zend_数组 类型

挑选几个重点成员介绍一下：

• gc: 引用计数，垃圾回收使用。
• arData：散列表中保存存储元素的数组，其内存是连续的，arData指向数组的起始位置；
• nTableSize：数组的总容量，即可以容纳的元素数，arData 的内存大小就是根据这个值确定的，它的大小的是2的幂次方，最小为8，然后按照 8、16、32…依次递增；

Bucket 类型

Bucket 的结构比较简单，主要用来保存元素的 key 和 value，以及一个整型的 h（散列值，或者叫哈希值）。

• 如果元素是数值索引，则其值就是数值索引的值；
• 如果是字符串索引，那么其值就是 key 通过 Time33 算法计算得到的散列值。

h 的值用来最终映射元素的存储位置。

2、PHP 数组的基本实现

上面部分我们了解了 zend_数组 的数据结构，那接着看看数组的初始化吧：

数组的初始化主要是针对 HashTable 成员的设置，初始化时并不会立即分配 arData 的内存，插入第一个元素之后才会分配 arData 的内存。

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

$data = array(
    'hello' => 'haha',
    1       => 'me to'
    'world' => 'world',
    2       => 2,
);
unset($data[1]);

欢迎大家来到IT世界,在知识的湖畔探索吧!

那上面的hash结构应该是什么样的呢？arData存储的结果应该是什么样呢？

画个图例来看看吧，更直观一些：

arData是Bucket类型的指针，用来具体存储每个元素的key，value，按照插入元素的顺序存储数据的，所以数组的顺序也是靠这个来保证。

每个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的意义。

3、PHP 数组的有序性

数组中各元素的顺序和插入顺序一致，这个是怎么实现的呢？

为了实现 PHP 数组的有序性，PHP 底层的散列表在散列函数与元素数组之间加了一层映射表，这个映射表也是一个数组，大小和存储元素的数组相同，存储元素的类型为整型，用于保存元素在实际存储的有序数组中的下标 —— 元素按照先后顺序依次插入实际存储数组，然后将其数组下标按照散列函数散列出来的位置存储在新加的映射表中：

这样，就可以完成最终存储数据的有序性了。

PHP 数组底层结构中并没有显式标识这个中间映射表，而是与 arData 放到了一起，在数组初始化的时候并不仅仅分配用于存储 Bucket 的内存，还会分配相同数量的 uint32_t 大小的空间，这两块空间是一起分配的，然后将 arData 偏移到存储元素数组的位置，而这个中间映射表就可以通过 arData 向前访问到。

总结

PHP中的数组其特点就是将 values 映射到 keys 的类型。与其他语言不同的是，PHP中数组的 key 可以是字符串，而values可以是任意类型。

除常规增删改查之外，数组还有很多其他操作，比如复制、合并、销毁、重置等，这些操作对应的代码都位于 zend_hash.c 中，感兴趣的同学可以去了解一下。

·END·

希望今天的讲解对大家有所帮助，谢谢！

Thanks for reading!

作者：张张，十年研发风雨路，大厂架构师，「架构精进之路」专注架构技术沉淀学习及分享，职业与认知升级，坚持分享接地气儿的干货文章，期待与你一起成长。

关注并私信我回复“01”，送你一份程序员成长进阶大礼包，欢迎勾搭。