PHP7-数组底层解析

PHP 中的数组实际上是一个有序映射。映射是一种把 values 关联到 keys 的类型。--PHP手册

数组是PHP中非常强大、灵活的一种数据类型，它的底层实现为HashTable（哈希表)，除了我们熟悉的PHP用户空间的Array类型之外，内核中也随处用到哈希表，比如函数、类、常量、include文件的索引表、全局符号表等都用的HashTable存储。
1、数组结构

PHP中HashTable的数据结构如下：

//Bucket：散列表中存储的元素
typedef struct _Bucket {
 zval val; //存储的具体value，这里嵌入了一个zval，而不是一个指针
 zend_ulong h; //key根据times 33计算得到的哈希值，或者是数值索引编号
 zend_string *key; //存储元素的key
} Bucket;
//HashTable结构
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数
 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;
};

注意：nNumUsed：已用bucket数 nNumOfElements：哈希表有效元素数

两者有不同的含义，当将一个元素从哈希表删除时并不会将对应的Bucket移除，而是将Bucket存储的zval修改为IS_UNDEF，只有扩容时发现nNumOfElements与nNumUsed相差达到一定数量时才会将已删除的元素全部移除，重新构建哈希表，所以 nNumUsed >= nNumOfElements。

HashTable中另外一个非常重要的值arData，这个值指向存储元素数组的第一个Bucket，插入元素时按顺序依次插入数组，比如第一个元素在arData[0]、第二个在arData[1] ... arData[nNumUsed]。PHP数组的有序性正是通过arData保证的。

所以，HashTable主要依赖arData实现元素的存储、索引。插入一个元素时先将元素按先后顺序插入Bucket数组，位置是idx，再根据key的哈希值映射到散列表中的某个位置nIndex，将idx存入这个位置；查找时先在哈希表中映射到nIndex，得到value在Bucket数组的位置idx，再从Bucket数组中取出元素。

2、哈希碰撞

哈希碰撞是指不同的key可能计算得到相同的哈希值(数值索引的哈希值直接就是数值本身)，但是这些值又需要插入同一个哈希表。

出现哈希碰撞之后，又如何解决呢？一般有如下几种方法：

链表法：为每个 Hash 值建立一个单链表，当发生冲突时，将记录插入到链表中。
开放寻址法：有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1),基本思想：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
再哈希法：当发生冲突时，使用第二个、第三个哈希函数计算地址，直到无冲突时。

3、扩容

哈希表可存储的value数是固定的，当空间不够用时就要进行扩容了。

PHP哈希表的大小为2^n，插入时如果容量不够则首先检查已删除元素所占比例，如果达到阈值时，则将已删除元素移除，重建索引；如果未到阈值则进行扩容操作，扩大为当前大小的2倍，将当前Bucket数组复制到新的空间，然后重建索引。

4、重建散列表

当删除元素达到一定数量或扩容后就需要重建哈希表，因为value在Bucket位置移动了或哈希数组nTableSize变化了导致key与value的映射关系改变。

重建过程实际就是遍历Bucket数组中的value，然后重新计算映射值更新到哈希表。

此外，还有一个重要的处理：移除已删除的value，开始的时候我们说过，删除value时只是将value的type设置为IS_UNDEF，并没有实际从Bucket数组中删除，如果这些value一直存在那么将浪费很多空间，所以这里会把它们移除，操作的方式也比较简单：将后面未删除的value依次前移。