PHP7系列：核心数组的优化（四）

PHP源码中的数组

PHP5的hashtable：

typedef struct _hashtable { uint nTableSize; uint nTableMask; uint nNumOfElements; ulong nNextFreeElement; Bucket *pInternalPointer; 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; /* Used for numeric indexing */ uint nKeyLength; void *pData; void *pDataPtr; struct bucket *pListNext; struct bucket *pListLast; struct bucket *pNext; struct bucket *pLast; const char *arKey; } Bucket;

Hashtable的核心是存储了一个个指向zval指针的指针, 也就是zval**； 是zval**, 而不是zval*: 如果在符号表中存的是zval*,就做不到对一处修改, 所有的持有方都有感知。

PHP7的Hashtable： 定义了一个结构体叫做zend_array，Alias为 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; /* 通过 32 个可用标识，设置散列表的属性 */ } u; uint32_t nTableMask; /* 哈希值计算掩码，等于nTableSize的负值(nTableMask = ~nTableSize + 1)，计算最终落在那个Bucket的值 */ Bucket *arData; /* 用来储存数据 Bucket里面存的是key-value对*/ uint32_t nNumUsed; /* arData 中的已用空间大小 */ uint32_t nNumOfElements; /* 哈希表已有元素数 */ uint32_t nTableSize; /* 哈希表总大小，为2的n次方 */ uint32_t nInternalPointer; /* 内部的指针，用于迭代（foreach） */ zend_long nNextFreeElement; /* 下一个可用的数值索引 如:arr[] = 1;arr["a"] = 2;arr[] = 3; 则nNextFreeElement = 2*/ dtor_func_t pDestructor; /* 数据析构函数（句柄） */ };

散列算法：通过key算出一个散列值，然后以tableMask进行或运算，然后就可以保证元素散列到我们指定的Bucket上 nIndex = key->h | nTableMask; 而数据会核心保存在arData中，arData是一个Bucket数组，Bucket定义:

typedef struct _Bucket { zval val; /* 值 */ zend_ulong h; /* 使用 time 33 算法对 key 进行计算后得到的哈希值（或为数字索引） */ zend_string *key; /* 当 key 值为字符串时，指向该字符串对应的 zend_string（使用数字索引时该值为 NULL） */ } Bucket;

zend_array的内存占用从PHP5的72个字节，降为56个字节，极大的节省内存占用。

PHP7数组都是有序存放：

哈希表实现的关键是有一个数组存储哈希值与Bucket的映射，但是HashTable中并没有这样一个索引数组。

实际上这个索引数组包含在arData中，索引数组与Bucket列表一起分配，arData指向了Bucket列表的起始位置，而索引数组可以通过arData指针向前移动访问到，即arData[-1]、arData[-2]、arData[-3]……索引数组的结构是uint32_t,它存储的是Bucket元素在arData中的位置。

整体来看HashTable主要依赖arData实现元素的存储、索引。插入一个元素时先将元素插入Bucket数组，位置是idx，再根据key的哈希值与nTableMask计算出索引数组的位置，将idx存入这个位置；查找时先根据key的哈希值与nTableMask计算出索引数组的位置，获得元素在Bucket数组的位置idx，再从Bucket数组中取出元素。

原来HashTable为什么要设计保存zval**， 那么PHP7因为_Bucket直接保存的是zval了，那怎么解决COW的时候一处修改多处可见的需求呢？ IS_INDIRECT类型其实可以理解为就是一个zval*的结构体。它被广泛应用在GLOBALS，Properties等多个需要俩个HashTable指向同于一个ZVAL的场景。

两者对比 现在的冲突拉链被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。