PHP 数组的底层实现使用了 HashTable 这种数据结构，PHP 7.0 相比于旧版本 PHP 数组做了很多的修改，本文主要记录 PHP7.0 相对于旧版本修改了那些东西。
介绍 PHP7 HashTable
HasahTable 又叫做散列表，具有如下特点（具体可参考《数据结构与算法分析》第五章散列）
- 可以以 O(1) 的效率执行数据插入、删除和查找操作
- 通过散列函数维护 K-V 之间的映射关系，可能会产生哈希冲突现象等
- 数据是 K-V 形式存储，元素间是无顺序的结构，不能对数据进行排序
PHP7 优化介绍
PHP 5 到 PHP 7.0 HashTable 主要做了如下修改
- 优化 HashTable 的数据结构：一个 PHP 数组 zend_array 的内存占用从PHP5点72个字节，降低到了56个字节
- 使用内存缓存局部性的特点，优化 PHP 数组效率
- PHP 5 的 Bucket ，包括 zval 都是独立分配（在内存中是离散的）
- PHP 7 中使用一块连续的空间存储 Bucket，并且一个 Bucket 中包含一个 zval 数据，即 Bucket 和 zval 在内存中都是连续存储的
- 其他一些细节优化
- 指针访问速度
- 优化 Empty Array
- .......
PHP 5 HashTable 的数据结构
typedef struct _hashtable { uint nTableSize; /* 散列表大小, Hash值的区间 */ uint nTableMask; /* 等于nTableSize -1, 用于快速定位 */ uint nNumOfElements; /* HashTable中实际元素的个数 */ ulong nNextFreeElement; /* 下个空闲可用位置的数字索引 */ Bucket *pInternalPointer; /* 内部位置指针, 会被reset, current这些遍历函数使用 */ Bucket *pListHead; /* 头元素, 用于线性遍历 */ Bucket *pListTail; /* 尾元素, 用于线性遍历 */ Bucket **arBuckets; /* 实际的存储容器 */ dtor_func_t pDestructor;/* 元素的析构函数(指针) */ zend_bool persistent; unsigned char nApplyCount; /* 循环遍历保护 */ zend_bool bApplyProtection; #if ZEND_DEBUG int inconsistent; #endif } HashTable; typedef struct bucket { ulong h; /* 数字索引/hash值 */ uint nKeyLength; /* 字符索引的长度 */ void *pData; /* 数据 */ void *pDataPtr; /* 数据指针 */ struct bucket *pListNext; /* 下一个元素, 用于线性遍历 */ struct bucket *pListLast; /* 上一个元素, 用于线性遍历 */ struct bucket *pNext; /* 处于同一个拉链中的下一个元素 */ struct bucket *pLast; /* 处于同一拉链中的上一个元素 */ char arKey[1]; /* 节省内存,方便初始化的技巧 */ } Bucket;
从数据结构和下图可以看出，PHP5 的 HashTable 使用了双向链表实现可以顺序遍历的结构。并使用拉链法解决 Hash 冲突
其中需要介绍的字段有：
- arBuckets 中的 pListHead、pListTail 双向链表的头和尾指针
- Bucket 中的 pListNext、pListLast 双向链表的上一个和下一个节点
- Bucket 中的 pNext、pLast ，拉链法解决 Hash 冲突的上一个和下一个这指针
- 其中 Bucket 代表 HashTable 中的一个键值，Bucket->pData 为 zval 存储值的数据结构
PHP7 Hashtable 的数据结构
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; Bucket *arData; uint32_t nNumUsed; uint32_t nNumOfElements; uint32_t nTableSize; uint32_t nInternalPointer; zend_long nNextFreeElement; dtor_func_t pDestructor; }; typedef struct _Bucket { zval val; zend_ulong h; /* hash value (or numeric index) */ zend_string *key; /* string key or NULL for numerics */ } Bucket
从数据结构和下图可以看出，arData 和 Bucket 的数据结构都更加的简洁了。罗列下大概做了如下修改
- 冲突拉链被bauck.zval->u2.next替代， 于是bucket->pNext, bucket->pLast可以去掉了
- zend_array->arData是一个数组，所以也就不再需要pListNext, pListLast来保持顺序了, 他们也可以去掉了。 现在数组中元素的先后顺序，完全根据它在arData中的index顺序决定，先加入的元素在低的index中
- PHP7中的Bucket现在直接保存一个zval, 取代了PHP5时代bucket中的pData和pDataPtr
- PHP7中现在使用zend_string作为数组的字符串key，取代了PHP5时代bucket的*key, nKeylength
还要介绍一个东西：arData 通过数据的 index 保证了数据的有序性，数据 K-V 关系是使用了 arHash 来存储，其中 arHash 可以通过 arData 取负的索引访问到，介绍如下图
PHP7 HashTable 的其他特点请阅读 Laruence 深入理解PHP7内核之HashTable
我的博客即将搬运同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=13ews1h77n5l4