It is never too late to learn。
PHP数组是一个神奇而强大的数据结构。以前听人说，都说语言的面向对象，PHP变成可以说是面向数组。
PHP 中的数组实际上是一个有序映射。映射是一种把 values 关联到 keys 的类型
于 PHP 数组的强大特性，我们可以轻易实现更加复杂的数据结构，比如栈、队列、列表、集合、字典等。PHP 数组功能之所以如此强大，得益于底层基于散列表Hashtable实现。
key: 键，通过它可以快速检索到对应的value。一般为数字或字符串。
value : 值，目标数据。可以是复杂的数据结构。
bucket： 桶，HashTable中存储数据的单元。用来存储key和value以及辅助信息的容器。
slot: 槽，HashTable有多个槽，一个bucket必须从属于具体的某一个slot，一个slot下可以有多个bucket。
哈希函数： 需要自己实现，在存储的时候，会对key应用哈希函数确定所在slot。
哈希冲突：当多个key经过哈希计算后，得出的slot的位置是同一个，那么就叫作哈希冲突。一般解决冲突的方法是链地址法和开放地址法。
PHP采用链地址法，将同一个slot中的bucket通过链表链接起来。
在具体实现中，PHP基于上述基本概念对bucket以及哈希函数进行了一些补充，增加了hash1函数以生成h值，然后通过hash2函数散列到不同的slot。
PHP5的数组源码
typedef struct bucket {
ulong h; /* 4字节 对char *key进行hash后的值，或者是用户指定的数字索引值 Used for numeric indexing */
uint nKeyLength; /* 4字节 字符串索引长度，如果是数字索引，则值为0 */
void *pData; /* 4字节 实际数据的存储地址，指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr,这里又是个指针，zval存放在别的地方*/
void *pDataPtr; /* 4字节 引用数据的存储地址，如果是指针数据，此值会指向真正的value，同时上面pData会指向此值 */
struct bucket *pListNext; /* 4字节 整个哈希表的该元素的下一个元素*/
struct bucket *pListLast; /* 4字节 整个哈希表的该元素的上一个元素*/
struct bucket *pNext; /* 4字节 同一个槽，双向链表的下一个元素的地址 */
struct bucket *pLast; /* 4字节 同一个槽，双向链表的上一个元素的地址*/
char arKey[1]; /* 1字节 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体*/
} Bucket;
typedef struct _hashtable {
uint nTableSize; /*4 哈希表中Bucket的槽的数量，初始值为8，每次resize时以2倍速度增长*/
uint nTableMask; /*4 nTableSize-1 ，索引取值的优化 */
uint nNumOfElements; /*4 哈希表中Bucket中当前存在的元素个数，count()函数会直接返回此值*/
ulong nNextFreeElement; /*4 下一个数字索引的位置 */
Bucket *pInternalPointer; /*4 当前遍历的指针（foreach比for快的原因之一） 用于元素遍历*/
Bucket *pListHead; /*4 存储数组头元素指针 */
Bucket *pListTail; /*4 存储数组尾元素指针 */
Bucket **arBuckets; /*4 指针数组,数组中每个元素都是指针,存储hash数组 */
dtor_func_t pDestructor; /*4 在删除元素时执行的回调函数，用于资源的释放 /*
persistent 指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。*/
zend_bool persistent; /*1 */
unsigned char nApplyCount; /*1 标记当前hash Bucket被递归访问的次数（防止多次递归）*/
zend_bool bApplyProtection;/*1 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次 */
#if ZEND_DEBUG
int inconsistent; /*4 */
#endif
} HashTable;
bucket里面有pListLast、pListNext、pLast、pNext这4个指针，维护两种双向链表。一种是全局链表，按插入顺序将所有bucket全部串联起来，整个HashTable只有一个全局链表。
另一个是局部链表，为了解决哈希冲突，每个slot 维护着一个链表，将所有哈希冲突的bucket串联起来。也就是，每一个bucket都处在一个双向链表上。pLast和pNext分别指向局部链表的前一个和后一个bucket，pListLast和pListTNext则指向全局链表的前一个和后一个。
bucket的h是通过key映射的哈希值，让不同的key均匀分配到哈希表的各个位置，PHP选用的time33算法。
nKeyLength（字符的个数）如果使用的是关联索引，那么此处nKeyLength就是字符的个数，比如说$arr['key']='value' ，那么这个值就为3，如果是索引数组，此字段就不会用上。
pNext和pLast （记录该bucket的前后bucket）
因为每一个bucket都需要分配一次内存。
key—value中的value都是zval。这种情况下，每个bucket需要维护指向zval的指针pDataPtr以及指向pDataPtr的指针pData。
每一个bucket需要维护4个指向bucket的指针
基于此PHP7重写了数组的相关代码
PHP7数组源码
typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
typedef struct _zend_array HashTable; /*typedef为C语言的关键字，作用是为一种数据类型定义一个新名字*/
struct _zend_array {
zend_refcounted_h gc;
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar _unused,
zend_uchar nIteratorsCount,
zend_uchar _unused2)
}v;
uint32_t flags;
} u;
uint32_t nTableMask; /* 掩码,用于根据hash值计算存储位置,永远等于nTableSize-1 */
Bucket *arData; /*存放实际数据*/
uint32_t nNumUsed; /* arData数组已经使用的数量 */
uint32_t nNumOfElements; /* hash表中元素个数 */
uint32_t nTableSize; /* hash表的大小 HashTable的大小，始终为2的指数（8,16,32,64...）。最小为8，最大值根据机器不同而不同*/
uint32_t nInternalPointer;/* 用于HashTable遍历 */
zend_long nNextFreeElement;/* 下一个空闲可用位置的数字索引 */
dtor_func_t pDestructor; /* 析构函数 */
};
数组的有序性
我们知道 PHP 数组是基于哈希表实现的，而与一般哈希表不同的是 PHP 的数组还实现了元素的有序性，就是插入的元素从内存上来看是连续的而不是乱序的，为了实现这个有序性 PHP 采用了「映射表」技术。下面就通过图例说明我们是如何访问 PHP 数组的元素
映射表和数组元素在同一片连续的内存中，映射表是一个长度与存储元素相同的整型数组，它默认值为 -1 ，有效值为 Bucket 数组的下标。而 HashTable->arData 指向的是这片内存中 Bucket 数组的第一个元素。
举个例子 $a['key'] 访问数组 $a 中键名为 key 的成员，流程介绍：首先通过 Time 33 算法计算出 key 的哈希值，然后通过散列算法计算出该哈希值对应的映射表下标，因为映射表中保存的值就是 Bucket 数组中的下标值，所以就能获取到 Bucket 数组中对应的元素。
现在我们来聊一下散列算法，就是通过键名的哈希值映射到「映射表」的下标的算法。其实很简单就一行代码：
nIndex = h | ht->nTableMask; 复制代码
将哈希值和 nTableMask 进行或运算即可得出映射表的下标，其中 nTableMask 数值为 nTableSize 的负数。并且由于 nTableSize 的值为 2 的幂次方，所以 h | ht->nTableMask 的取值范围在 [-nTableSize, -1] 之间，正好在映射表的下标范围内。至于为何不用简单的「取余」运算而是费尽周折的采用「按位或」运算？因为「按位或」运算的速度要比「取余」运算要快很多，我觉得对于这种频繁使用的操作来说，复杂一点的实现带来的时间上的优化是值得的
散列冲突
同键名的哈希值通过散列计算得到的「映射表」下标有可能相同，此时便发生了散列冲突。对于这种情况 PHP 使用了「链地址法」解决。下图是访问发生散列冲突的元素的情况：
我们同样访问 $a['key'] 的过程多了一些步骤。首先通过散列运算得出映射表下标为 -2 ，然后访问映射表发现其内容指向 arData 数组下标为 1 的元素。此时我们将该元素的 key 和要访问的键名相比较，发现两者并不相等，则该元素并非我们所想访问的元素，而元素的 val.u2.next 保存的值正是下一个具有相同散列值的元素对应 arData 数组的下标，所以我们可以不断通过 next 的值遍历直到找到键名相同的元素或查找失败
数组的扩容
数组的长度是定长的，那么如果空间已满还需继续插入的时候怎么办呢？PHP 的数组在底层实现了自动扩容机制，当插入一个元素且没有空闲空间时，就会触发自动扩容机制，扩容后再执行插入。
需要提出的一点是，当删除某一个数组元素时，会先使用标志位对该元素进行逻辑删除，而不会立即删除该元素所在的 Bucket，因为后者在每次删除时进行一次排列操作，从而造成不必要的性能开销。
扩容的过程为：
- 如果已删除元素所占比例达到阈值，则会移除已被逻辑删除的 Bucket，然后将后面的 Bucket 向前补上空缺的 Bucket，因为 Bucket 的下标发生了变动，所以还需要更改每个元素在中间映射表中储存的实际下标值。
- 如果未达到阈值，PHP 则会申请一个大小是原数组两倍的新数组，并将旧数组中的数据复制到新数组中，因为数组长度发生了改变，所以 key-value 的映射关系需要重新计算，这个步骤为重建索引。
注：因为在重建索引时需要重新计算映射关系，所以将旧数组复制到新数组中时，中间映射表的数据是无需复制的
参考链接：
