PHP 数组具有的特性
PHP 的数组是一种非常强大灵活的数据类型，在讲它的底层实现之前，先看一下 PHP 的数组都具有哪些特性。
可以使用数字或字符串作为数组健值
<p>4本文￥来源gao!%daima.com搞$代*!码$网9</p><pre>搞代gaodaima码
$arr = [1 => ‘ok’, ‘one’ => ‘hello’];
可按顺序读取数组
foreach($arr as $key => $value){
echo $arr[$key];
}
可随机读取数组中的元素
$arr = [1 => 'ok', 'one' => 'hello', 'a' => 'world']; echo $arr['one']; echo current($arr);
数组的长度是可变的
$arr = [1, 2, 3]; $arr[] = 4; array_push($arr, 5);
正是基于这些特性，我们可以使用 PHP 中的数组轻易的实现集合、栈、列表、字典等多种数据结构。那么这些特性在底层是如何实现的呢？ 这就得从数据结构说起了。
数据结构
PHP 中的数组实际上是一个有序映射。映射是一种把 values 关联到 keys 的类型。
PHP 数组的底层实现是散列表（也叫 hashTable )，散列表是根据键（Key）直接访问内存存储位置的数据结构，它的key – value 之间存在一个映射函数，可以根据 key 通过映射函数得到的散列值直接索引到对应的 value 值，无需通过关键字比较，在理想情况下，不考虑散列冲突，散列表的查找效率是非常高的，时间复杂度是 O(1)。
从源码中我们可以看到 zend_array 的结构如下：
typedef struct _zend_array zend_array;
typedef struct _zend_array hashTable;
struct _zend_array {
zend_refcounted_h gc;
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar nApplyCount,
zend_uchar nIteratorsCount,
zend_uchar reserve)
} v;
uint32_t flags;
} u;
uint32_t nTableMask; // 哈希值计算掩码，等于nTableSize的负值(nTableMask = -nTableSize)
Bucket *arData; // 存储元素数组，指向第一个Bucket
uint32_t nNumUsed; // 已用Bucket数（含失效的 Bucket）
uint32_t nNumOfElements; // 哈希表有效元素数
uint32_t nTableSize; // 哈希表总大小，为2的n次方（包括无效的元素）
uint32_t nInternalPointer; // 内部指针，用于遍历
zend_long nNextFreeElement; // 下一个可用的数值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 则nNextFreeElement = 2;
dtor_func_t pDestructor;
};
该结构中的 Bucket 即储存元素的数组，arData 指向数组的起始位置，使用映射函数对 key 值进行映射后可以得到偏移值，通过内存起始位置 + 偏移值即可在散列表中进行寻址操作。
Bucket 的数据结构如下：
typedef struct _Bucket {
zval val; // 存储的具体 value，这里是一个 zval，而不是一个指针
zend_ulong h; // 数字 key 或字符串 key 的哈希值。用于查找时 key 的比较
zend_string *key; // 当 key 值为字符串时，指向该字符串对应的 zend_string（使用数字索引时该值为 NULL），用于查找时 key 的比较
} Bucket;
到这里有个问题出现了：存储在散列表里的元素是无序的，PHP 数组如何做到按顺序读取的呢？
答案是中间映射表，为了实现散列表的有序性，PHP 为其增加了一张中间映射表，该表是一个大小与 Bucket 相同的数组，数组中储存整形数据，用于保存元素实际储存的 Value 在 Bucekt 中的下标。Bucekt 中的数据是有序的，而中间映射表中的数据是无序的。
转载请注明原文链接：PHP7数组的底层实现示例
