PHP 中的数组实际上是一个有序映射。映射是一种把 values 关联到 keys 的类型。--PHP手册
数组是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可能打算得到相同的哈希值(数值索引的哈希值直接便是数值本身)，但是这些值又须要插入同一个哈希表。
涌现哈希碰撞之后，又如何办理呢？一样平常有如下几种方法：
链表法：为每个 Hash 值建立一个单链表，当发生冲突时，将记录插入到链表中。开放寻址法：开放地司法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1),基本思想：当发生地址冲突时，按照某种方法连续探测哈希表中的其他存储单元，直到找到旷地位为止。再哈希法：当发生冲突时，利用第二个、第三个哈希函数打算地址，直到无冲突时。扩容哈希表可存储的value数是固定的，当空间不足用时就要进行扩容了。
PHP哈希表的大小为2^n，插入时如果容量不足则首先检讨已删除元素所占比例，如果达到阈值时，则将已删除元素移除，重修索引；如果未到阈值则进行扩容操作，扩大为当前大小的2倍，将当前Bucket数组复制到新的空间，然后重修索引。
重修哈希表
当删除元素达到一定数量或扩容后就须要重修哈希表，由于value在Bucket位置移动了或哈希数组nTableSize变革了导致key与value的映射关系改变。
重修过程实际便是遍历Bucket数组中的value，然后重新打算映射值更新到哈希表。
此外，还有一个主要的处理：移除已删除的value，开始的时候我们说过，删除value时只是将value的type设置为IS_UNDEF，并没有实际从Bucket数组中删除，如果这些value一贯存在那么将摧残浪费蹂躏很多空间，以是这里会把它们移除，操作的办法也比较大略：将后面未删除的value依次前移。
以上，先容了数组的哈希构造，如有遗漏和不敷欢迎大家连续补充。
