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

数组结构

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数组中取出元素。

比如：

对应的HashTable如下图所示：

哈希碰撞

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

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

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

扩容

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

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

重建哈希表

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

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

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

以上，介绍了数组的哈希结构，如有遗漏和不足欢迎大家继续补充。