PHP数组的特点PHP数组是一种非常强大和灵活的数据类型。在说它的底层实现之前，我们先来看看PHP数组的特点。可以使用数字或字符串作为数组键值$arr=[1=>'ok','one'=>'hello'];可以顺序读取数组foreach($arras$key=>$value){echo$arr[$key];}随机读取数组中的元素$arr=[1=>'ok','one'=>'你好','a'=>'世界'];echo$arr['一个'];回声当前（$arr）；数组的长度是可变的$arr=[1,2,3];$arr[]=4;array_push($arr,5);基于这些特性，我们可以在PHP中使用数组来轻松实现集合、栈、列表、字典等各种数据结构。那么这些特性在底层是如何实现的呢？这得从数据结构说起。数据结构PHP中的数组实际上是一个有序映射。映射是一种将值与键相关联的类型。PHP数组的底层实现是一个哈希表（也叫hashTable）。哈希表是一种根据键（Key）直接访问内存存储位置的数据结构。它的key和value之间有一个映射函数，可以根据key通过映射函数得到。索引的hash值直接索引到对应的value值，不需要关键字比较。理想情况下，不考虑哈希冲突，哈希表的查找效率非常高，时间复杂度为O(1)。从源代码中我们可以看到zend_array的结构如下：typedefstruct_zend_arrayzend_array;typedefstruct_zend_arrayhashTable;struct_zend_array{zend_refcounted_hgc;union{struct{ZEND_ENDIAN_LOHI_4(zend_ucharflags,zend_ucharnApplyCount,zend_ucharnIteratorsCount,zend_ucharreserve)}v;uint32_t标志；}你;uint32_tnTableMask；//Hash值计算掩码，等于nTableSize的负值(nTableMask=-nTableSize)Bucket*arData;//存储元素数组，指向第一个Bucketuint32_tnNumUsed;//使用的桶数（包括无效桶）uint32_tnNumOfElements;//哈希表有效元素个数uint32_tnTableSize;//哈希表总大小，2的n次方（包括无效元素）uint32_tnInternalPointer;//内部指针，用于遍历zend_longnNextFreeElement;//下一个可用的数值索引，如：arr[]=1;arr[“a”]=2；arr[]=3;然后nNextFreeElement=2;dtor_func_tpDestructor;};structure中的Bucket是存储元素个数group，arData指向数组的起始位置，使用映射函数映射key值后可以得到偏移值，通过内存起始位置+偏移量在哈希表中进行寻址操作价值。Bucket的数据结构如下：typedefstruct_Bucket{zvalval;//存储的具体值，这里是一个zval，不是指针zend_ulongh;//数字键或字符串键的哈希值。用于搜索zend_string*key时进行key比较；//当key值为字符串时，指向该字符串对应的zend_string（使用数字索引时该值为NULL），用于搜索时进行key比较}Bucket;to这里有个问题：哈希表中存储的元素是乱序的，PHP数组怎么才能按顺序读取呢？答案是中间映射表。为了实现哈希表的有序化，PHP为其添加了一个中间映射表。这个表是一个和Bucket一样大的数组。数组存储整数数据，用于保存元素的实际存储。Bucekt中值的下标。Bucekt中的数据是有序的，而中间映射表中的数据是无序的。但是映射函数映射的哈希值必须在中间映射表的区间内，这就对映射函数提出了要求。PHP7数组映射函数使用的映射方式：nIndex=h|ht->nTableMask;映射表的下标可以由key通过time33算法生成的哈希值h与nTableMask进行OR运算得到，其中nTableMask的值为nTableSize负数。而由于nTableSize的值是2的幂，所以nTableMask右边的二进制位全部为0，保证了h|的取值范围ht->nTableMask会在[-nTableSize,-1]之间，正好在映射表的下标范围内。此外，按位或运算的方法比取余法等其他方法更快。这个映射函数可以说是设计得很巧妙了。哈希（hash）冲突映射函数针对不同键名计算出的哈希值可能相同，这时就会发生哈希冲突。哈希冲突常用的方法有四种：1.将哈希值放在最近的相邻地址2.更改哈希函数重新计算哈希值3.将冲突的哈希值放在另一个地方4.构造单向链接list在冲突位置，将hash值相同的元素放入同槽对应的链表中。这种方法称为链地址法，PHP数组就是用这种方法来解决散列冲突问题的。具体实现是：将冲突的Buckets串成一个链表，使得中间映射表映射的不是某个元素，而是一个Bucket链表。通过hash函数定位到对应的Bucket链表时，需要遍历链表，逐一比较。键值，然后找到目标元素。每个Bucket之间的链接是将原值的下标保存到新值的zval.u2.next中，并将新值放在当前位置，这样就形成了一个单向链表。例如：当我们访问$arr['key']时，假设先通过hash运算映射表的下标为-2，然后访问映射表，发现其内容指向下标为1的元素arData数组的。这时我们将元素的key和要访问的key名进行比较，发现两者不相等，则该元素不是我们要访问的元素，而元素的zval.u2中存储的值.next是另外一个hash值相同的元素对应arData数组的下标，所以我们可以一直遍历zval.u2.next的值，直到找到一个键名相同的元素。扩容PHP数组在底层实现了自动扩容机制。当插入一个元素，没有空闲空间时，会触发自动扩容机制，扩容后再进行插入。扩容过程如下：如果删除元素的比例达到阈值，逻辑删除的Bucket将被移除，然后向前填充后续的Bucket，以填充空出的Bucket。因为Bucket的下标发生了变化，所以仍然需要改变每个元素在中间映射表中存储的实际下标值。如果没有达到阈值，PHP会申请一个比原数组大一倍的新数组，并将旧数组中的数据复制到新数组中，因为数组的长度发生了变化，所以键值映射关系需要重新计算，这一步就是重建索引。重建哈希表时，删除数组元素时，会先使用标志位逻辑删除元素，即删除值时，只设置值的类型为IS_UNDEF，并不会立即删除元素所在的Bucket，因为如果每次删除一个元素都立即删除Bucket，那么每次都需要进行一次排列操作，会造成不必要的性能开销。因此，当删除的元素达到一定数量或扩容后，需要重建哈希表，即删除标记为已删除的值。因为值在Bucket中移动或者hash数组nTableSize发生变化，导致key和value的映射关系发生变化。重构过程就是遍历Bucket数组中的值，然后重新计算映射值，更新到哈希表中。这是对PHP7的数组底层实现的总结，因为水平有限，无法深入研究。有什么问题或者不足之处欢迎追问~~参考资料《PHP7 的底层设计与源码实现》php7-internal更多好文章，关注公众号获取
