最近在温习PHP基础，搞的自己甚是烦躁，静下心，写一篇博客压压惊。
今天就聊聊PHP最核心的数组Array。
PHP数组具有的特性
以使用数字或字符串作为数组健值
$arr = [1 => 'ok', 'one' => 'hello'];可按顺序读取数组
foreach($arr as $key => $value){
echo $arr[$key];
}可随机读取数组中的元素
$arr = [1 => 'ok', 'one' => 'hello'];数组的长度是可变的
$arr = [1 => 'ok', 'one' => 'hello'];PHP 数组的数据结构
PHP 数组的底层实现是散列表（也叫 hashTable )，散列表是根据键（Key）直接访问内存存储位置的数据结构，它的 key - value 之间存在一个映射函数，可以根据 key 通过映射函数得到的散列值直接索引到对应的 value 值，无需通过关键字比较，在理想情况下，不考虑散列冲突，散列表的查找效率是非常高的，时间复杂度是 O (1)。
PHP 数组底层依赖的散列表数据结构定义如下（位于 Zend/zend_types.h）：
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;
};这个散列表中有很多成员，我们挑几个比较重要的来讲讲：
arData：散列表中保存存储元素的数组，其内存是连续的，arData指向数组的起始位置；
nTableSize：数组的总容量，即可以容纳的元素数，arData 的内存大小就是根据这个值确定的，它的大小的是2的幂次方，最小为8，然后按照 8、16、32...依次递增；
nTableMask：这个值在散列函数根据 key 的哈希值映射元素的时候用到，它的值实际就是 nTableSize 的负数，即 nTableMask = -nTableSize，用位运算来表示就是 nTableMask = ~nTableSize+1；
nNumUsed、nNumOfElements：nNumUsed 是指数组当前使用的 Bucket 数，但不是数组有效元素个数，因为某个数组元素被删除后并没有立即从数组中删除，而是将其标记为 IS_UNDEF，只有在数组需要扩容时才会真正删除，nNumOfElements 则表示数组中有效的元素数量，即调用 count 函数返回值，如果没有扩容，nNumUsed 一直递增，无论是否删除元素；
nNextFreeElement：这个是给自动确定数值索引使用的，默认从 0 开始，比如 $arr[] = 200，这个时nNextFreeElement 值会自动加 1；
pDestructor：当删除或覆盖数组中的某个元素时，如果提供了这个函数句柄，则在删除或覆盖时调用此函数，对旧元素进行清理；
Bucket 的结构比较简单，主要用来保存元素的 key 和 value，以及一个整型的 h（散列值，或者叫哈希值）：如果元素是数值索引，则其值就是数值索引的值；如果是字符串索引，那么其值就是 key 通过 Time33 算法计算得到的散列值，h 的值用来最终映射元素的存储位置。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 中的数组除了具备散列表的基本特点之外，还有一个特别的地方，那就是它是有序的（与Java中的HashMap的无序有所不同）：数组中各元素的顺序和插入顺序一致。这个是怎么实现的呢？
为了实现 PHP 数组的有序性，PHP 底层的散列表在散列函数与元素数组之间加了一层映射表，这个映射表也是一个数组，大小和存储元素的数组相同，存储元素的类型为整型，用于保存元素在实际存储的有序数组中的下标 —— 元素按照先后顺序依次插入实际存储数组，然后将其数组下标按照散列函数散列出来的位置存储在新加的映射表中：
这样，就可以完成最终存储数据的有序性了。
PHP 数组底层结构中并没有显式标识这个中间映射表，而是与 arData 放到了一起，在数组初始化的时候并不仅仅分配用于存储 Bucket 的内存，还会分配相同数量的 uint32_t 大小的空间，这两块空间是一起分配的，然后将 arData 偏移到存储元素数组的位置，而这个中间映射表就可以通过 arData 向前访问到。
映射函数
PHP7 数组采用的映射方式：
nIndex = h | ht->nTableMask;将 key 经过 time33 算法生成的哈希值 h 和 nTableMask 进行或运算即可得出映射表的下标，其中 nTableMask 数值为 nTableSize 的负数。并且由于 nTableSize 的值为 2 的幂次方，所以 nTableMask 二进制位右侧全部为 0，保证了 h | ht->nTableMask 的取值范围会在 [-nTableSize, -1] 之间，正好在映射表的下标范围内。另外，用按位或运算的方法和其他方法如取余的方法相比运算速度较高，这个映射函数可以说设计的非常巧妙了。
散列（哈希）冲突
不同键名的通过映射函数计算得到的散列值有可能相同，此时便发生了散列冲突。
对于散列冲突有以下 4 种常用方法：
- 将散列值放到相邻的最近地址里
- 换个散列函数重新计算散列值
- 将冲突的散列值统一放到另一个地方
- 在冲突位置构造一个单向链表，将散列值相同的元素放到相同槽位对应的链表中。这个方法叫链地址法，PHP 数组就是采用这个方法解决散列冲突的问题。
其具体实现是：将冲突的 Bucket 串成链表，这样中间映射表映射出的就不是某一个元素，而是一个 Bucket 链表，通过散列函数定位到对应的 Bucket 链表时，需要遍历链表，逐个对比 Key 值，继而找到目标元素。而每个 Bucket 之间的链接则是将原 value 的下标保存到新 value 的 zval.u2.next 里，新 value 放在当前位置上，从而形成一个单向链表。
举个例子：
当我们访问 $arr['key'] 的过程中，假设首先通过散列运算得出映射表下标为 -2 ，然后访问映射表发现其内容指向 arData 数组下标为 1 的元素。此时我们将该元素的 key 和要访问的键名相比较，发现两者并不相等，则该元素并非我们所想访问的元素，而元素的 zval.u2.next 保存的值正是另一个具有相同散列值的元素对应 arData 数组的下标，所以我们可以不断通过 zval.u2.next 的值遍历直到找到键名相同的元素。
数组的初始化
数组的初始化主要是针对 HashTable 成员的设置，初始化时并不会立即分配 arData 的内存，插入第一个元素之后才会分配 arData 的内存。初始化操作可以通过 zend_hash_init 宏完成，最后由 _zend_hash_init_int 函数处理（该函数定义在 Zend/zend_hash.c 文件中）。
此时的 HashTable 只是设置了散列表的大小及其他成员的初始值，还无法用来存储元素。
插入数据
插入时会检查数组是否已经分配存储空间，因为初始化并没有实际分配 arData 的内存，在第一次插入时才会根据 nTableSize 的大小分配，分配以后会把 HashTable->u.flags 打上 HASH_FLAG_INITIALIZED 掩码，这样，下次插入时发现已经分配了就不会重复操作，这段检查逻辑_zend_hash_add_or_update_i 函数中：
如果 arData 还没有分配，则最终由 zend_hash_real_init_mixed_ex 完成内存分配：
分配完 arData 的内存后就可以进行插入操作了，插入时先将元素按照顺序插入 arData，然后将其在 arData 数组中的位置存储到根据 key 的散列nTableMask 计算得到的中间映射表中的对应位置：
上述只是最基本的插入处理，不涉及已存在数据的覆盖和清理。
数组查找
清楚了 HashTable 的实现和哈希冲突的解决方式之后，查找的过程就比较简单了：首先根据 key 计算出的散列值与 nTableMask 计算得到最终散列nIndex，然后根据散列值从中间映射表中得到存储元素在有序存储数组中的位置 idx，接着根据 idx 从有序存储数组（即 arData）中取出 Bucket，遍历该 Bucket，判断 Bucket 的 key 是否是要查找的 key，如果是则终止遍历，否则继续根据 zval.u2.next 遍历比较。
删除数据
关于数组数据删除前面我们在介绍散列表中的 nNumUsed 和 nNumOfElements 字段时已经提及过，从数组中删除元素时，并没有真正移除，并重rehash，而是当 arData 满了之后，才会移除无用的数据，从而提高性能。即数组在需要扩容的情况下才会真正删除元素：首先检查数组中已删除元素所占比例，如果比例达到阈值则触发重新构建索引的操作，这个过程会把已删除的 Bucket 移除，然后把后面的 Bucket 往前移动补上空位，如果还没有达到阈值则会分配一个原数组大小 2 倍的新数组，然后把原数组的元素复制到新数组上，最后重建索引，重建索引会将已删除的 Bucket 移除。