引入数组
大家都知道，在PHP中，数组是一个非常重要且神奇强大的数据结构，且在实际开发中会大量的使用数组。数组既可以存储连续的数组，也可以存储KV映射的map结构。本文会讲解PHP5和PHP7数组的区别以及PHP7在设计上的巧妙，以及在时间效率和空间效率的如何提升！
基本概念
在了解PHP数组实现细节之前，我们有必要知道一下PHP数组的设计目标,那么什么是PHP的数组呢？它能提供什么能力呢？ 其实本质上，PHP数组就是一个有序的字典，它必须同时满足以下2个条件
1) 首先PHP数组是一个字典，存储着Key-Value对。通过Key可以快速地找到value，其中Key可以是
整型，也可以是字符串。
2) 其次PHP数组是有序的。（1）插入有序 （2）遍历有序
PHP的数组通过zend_array对应的是HashTable(哈希表/散列表)来实现。也是一种通过某种hash函数将特定的key映射到特定value的一种数据结构，它维护着键和值的一一对应关系，并且可以快速的根据键找到值(o(1)). 一般HashTable的示意图如下:
HashTable示意图
1) key: 通过key可以快速找到value。一般可以为数字或者字符串。
2) value: 值可以为复杂结构
3) bucket: 桶，HashTable存储数据的单元，用来存储key/value以及其他辅助信息的容器
4) slot:槽，HashTable有多少个槽，一个bucket必须属于具体的某一个slot，一个slot可以有多个
bucket
5) 哈希函数:一般都是自己实现（time33），在存储的时候，会将key通过hash函数确定所在的slot
6) 哈希冲突: 当多个key经过哈希计算后，得到的slot位置是同一个，那么就会冲突，一般这个时候会有
2种解决办法:链地址法和开放地址法。其中php采用的是链地址法，即将同一个slot中的bucket通过
链表连接起来
以上示意图是一个普通HashTable的结构图，那么PHP在此基础上，对Bucket以及哈希函数进行了补充，增加了hash1函数用来生成h值，然后通过hash2函数散列到不同过的slot，示意图如下:
带有h值的HashTable示意图
1) bucket里面增加了h字段
2) 哈希函数拆分成了hash1和hash2函数。hash1将key映射为h值，hash2函数将h值映射为slot的索引值
3) bucket里面的key字段为字符串key而不是数字key
其中多出来的h值是什么作用呢？
1) HashTable中的key可能是数字也可能是字符串，所以在设计bucket的key时，分为字符串key和数字
key，在上图中的bucket中，“h”代表数字key，“key”代表字符串key，对于数字key，hash1函数并没
有做任何事情，h值就是数字key
2) 每个字符串key，经过hash1函数都会计算一个h值。可以加快字符串之间的比较速度。如果要比较2个
字符串是否相等，首先比较这2个key的h值是否相等，如果相等再比对2个key的长度和内容。否则可以
判定不相等。这样可以提高HashTable插入，查找速度
PHP5数组实现
在学习PHP7数组实现之前，我们来了解一下PHP5的数组实现，以及了解为啥PHP7要对结构进行精简和优化
PHP5的bucket和HashTable结构
PHP-5.6.31/Zend/zend_hash.h
PHP-5.6.31/Zend/zend_hash.c
struct _hashtable;
typedef struct bucket {
//对应HashTable设计中的h，表示数字key或者字符串key的h值
ulong h; /* Used for numeric indexing */
//arKey的长度。当等于0时，表示数字key。比较字符串key是否相等时，先比较h值，如h值相等，则
//先比较字符串的长度是否相等再比较字符串内容，以提高比较速度
uint nKeyLength;
//一般value都存储在pData所指向的内存空间，pDataPtr是空指针。例外情况:如果value的大小等
//于一个指针的大小（大部分情况是指针），那么将不会额外申请内存空间来存储这个指针，而是直接
//存储在pDataPtr上，再让pData指向pDataPtr，可以减少内存碎片
void *pData; //对应HashTable设计中的value
void *pDataPtr; //对应HashTable设计中的value
//4个指向bucket的指针，php5中维护了两种双向链表：全局，局部链表，按插入顺序将所有的
//bucket全部串联起来，整个HashTable只有一个全局链表。局部链表是为了解决哈希冲突的，每个
//slot维护一个链表，将所有哈希冲突的bucket串联起来，即每一个bucket都处在2个双向链表上
struct bucket *pListNext; //全局链表的前一个bucket
struct bucket *pListLast;//全局链表的后一个bucket
struct bucket *pNext;//局部链表的前一个bucket
struct bucket *pLast;//局部链表的后一个bucket
const char *arKey; //对应HashTable设计中的key，表示字符串key
} Bucket;
typedef struct _hashtable {
//arBuckets指向的连续内存中指针的个数，即slot的数量，该字段始终是2的n次方，最小为8，
//最大为2^31 次方，当bucket大于slot时，会存在某个slot至少有2个bucket，随着slot下的
//bucket越来越多，HashTable会退化成链表，性能严重下降，此时就会进行rehash以达到bucket在
//slot中的平衡分布
uint nTableSize;
//掩码。总是等于nTableSize-1，即2^n-1，nTableMask每一位都是1.key经过hash1函数生成h值，
//h值通过hash2函数生成slot值，这里的hash2函数就是slot = h & nTableMask，通过
//arBuckets[slot]可以得到当前slot链表的头指针
uint nTableMask;
//bucket元素个数。php5中，删除某元素会将bucket从全局链表和局部链表中真正删除，并释放
//bucket本身以及value所占用的内存
uint nNumOfElements;
//HashTable的自然key，比如$a[] = 1,实际插入的key为0的bucket上，然后nNextFreeElement
//会变为1，代表下一个自然插入元素的key=1
ulong nNextFreeElement;
//HashTable的全局默认游标，维护正在遍历的bucket
Bucket *pInternalPointer; /* Used for element traversal */
//为了保证数组有序，HashTable维护了一个全局链表
Bucket *pListHead; //全局链表的表头
Bucket *pListTail;//全局链表的表尾
//二级指针，指向一段连续的数组内存，这段并没有存储bucket，而是存储着指向bucket的指针。每
//个指针代表一个slot，并指向slot局部链表的首元素，通过这个指针，可以遍历这个slot下的所有
//的bucket
Bucket **arBuckets;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
//h ,arKey,nKeyLength PHP数组中，有两类不同的索引，一类是数字索引，这与C中的数组非常类似
//(如$arr = array(1=>'count')), 另一类是字符串索引，也就是使用关键词作为数组项的索引
//（如$arr = array('index'=>'count');）.这两类索引在PHP底层是通过不同的机制来区分的：对于
//数字型索引，直接使用h作为hash值，同时，arKey=NULL 且nKeyLength=0, 而对于字符串索引，
//arKey保存字符串key, nKeyLength保存该key的长度，h则是该字符串通过hash函数计算后的hash值。
//这样，在PHP中，实际上通过h, arKey, nKeyLength来唯一确定数组中的一个元素的
typedef struct _zend_hash_key {
const char *arKey;
uint nKeyLength;
ulong h;
} zend_hash_key;
举例说明PHP5数组实现
将4个key/value对插入数组中，按插入顺序，key分别为：“a”,"b","c","d",值为“1”,"2","3","4" 并且假设“a”被映射到slot1，而“b”,"c","d"被映射到了slot0(哈希冲突示例)，最终这个数组有4个元素，它在内存中的分布图如下所示:
插入数组元素示例图
总结PHP5数组在时间/空间效率的问题
1) 其中每一个bucket都需要一次内存分配，由于PHP内核基于内存池实现，会提前准备好需要申请的内存
而不需要通过malloc函数直接申请系统内存，免去了系统调用在用户态和内核态切换以及malloc额外
消耗带来的空间浪费，但是内存申请的耗时还是存在且不可以忽略掉的
2）空间效率问题，对于大部分的场景，key/value中的value都是zval。所以每个bucket都需要维护指向
zval的指针pDataPtr以及指向pDataPtr的pData指针
3）为了保证数组快速查找以及有序，每一个bucket需要维护4个指向bucket的指针，在32/64位系统中，
每个bucket将为这4个指针付出16/32字节，那么对于有1024个bucket元素的HashTable，就需要额外
分配15/32KB的内存，且bucket分配是随机，导致CPU缓存命令率降低，遍历并没有提高性能
PHP7数组实现
上面说完PHP5数组的实现，也了解了PHP5数组实现的在空间和时间效率的问题，那么如何基于HashTable来实现优雅高效的数组呢？既然是HashTable，如果还是通过链地址法解决哈希冲突，那么链表是必须的，同时为了保证顺序，也的确需要维护一个全局链表来保证，那么PHP7是如何实现的呢？
其实，PHP7实现思路依然是链地址法来解决哈希冲突，只不过PHP5的链表是真实物理存在的链表，链表中bucket间的上下游是通过真实存在的指针来维护，而PHP7的链表其实是一种逻辑上的链表，所有的bucket都分配在一段连续的数组内存中，且不再通过指针维护上下游关系，每一个bucket只维护一个bucket在数组中的索引【由于内存是连续的，通过索引可以快速定位到bucket】，即可完成链表上的bucket遍历
PHP7数组基本结构
PHP7下面所有的数据结构定义：PHP-7.1.0/Zend/zend_types.h
PHP7数组：PHP-7.1.0/Zend/zend_hash.h
PHP7数组：PHP-7.1.0/Zend/zend_hash.c
/* regular data types */
#define IS_ARRAY 7 //数组类型
//zval 8字节
typedef union _zend_value {
zend_long lval; /*整型 */
double dval; /* 浮点型 */
zend_refcounted *counted; /* 引用计数 */
zend_string *str; /* 字符串 */
zend_array *arr; /* 数组 */
zend_object *obj; /* 对象 */
zend_resource *res; /* 资源 */
zend_reference *ref; /* 引用 */
zend_ast_ref *ast; /* 抽象语法树*/
zval *zv; /* zval类型 */
void *ptr; /* 指针类型 */
zend_class_entry *ce; /* class类型*/
zend_function *func; /* function类型 */
struct {
uint32_t w1;
uint32_t w2;
} ww;
} zend_value;
//整个zval占用16字节
struct _zval_struct {
zend_value value; //8字节
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar type, /* active type */
zend_uchar type_flags,
zend_uchar const_flags,
zend_uchar reserved) /* call info for EX(This) */
} v;
uint32_t type_info; //4字节
} u1;
union {
uint32_t next; /* 解决hash冲突 */
uint32_t cache_slot; /* 运行时缓存 */
uint32_t lineno; /* 对于zend_ast_zval存行号*/
uint32_t num_args; /* EX(This)参数个数 */
uint32_t fe_pos; /* foreach 的位置 */
uint32_t fe_iter_idx; /* foreach 游标标记 */
uint32_t access_flags; /* 类的常量访问标识 public protected private */
uint32_t property_guard; /* 单一属性保护 */
} u2;
};
//整块占用8字节
typedef struct _zend_refcounted_h {
uint32_t refcount; //4字节 32位长度引用计数的值存储
union {
struct {
ZEND_ENDIAN_LOHI_3(
zend_uchar type, //等同于zval的u1.v.type 当前元素数据类型
zend_uchar flags, //标记字符串或者对象
uint16_t gc_info) // 记录所在GC池中的位置和颜色
} v;
uint32_t type_info;
} u;
} zend_refcounted_h;
struct _zend_refcounted {
zend_refcounted_h gc;
};
struct _zend_string {
zend_refcounted_h gc; //8字节，内嵌的gc，引用计数以及字符串类别存储
zend_ulong h; // 字符串的哈希值 8字节
size_t len; //8字节 字符串的长度
char val[1]; //柔性数组，字符串值存储位置
};
typedef struct _Bucket {
//始终为zval，PHP7将zval嵌入到bucket中，每一个zval只有16字节，当zval是IS_PTR类型是，
//可以通过zval.value.ptr指向任何类型数据
zval val;
// h值，表示数字key或者字符串key的h值
zend_ulong h;
//字符串key,区别于PHP5，不再是char *类型的指针，而是一个指向zend_string的指针
//zend_string是带有字符串长度，h值，gc信息的字符串数组，可以大幅度提升性能和空间效率
zend_string *key;
} Bucket;
typedef struct _zend_array HashTable;
struct _zend_array {
//引用计数，引用计数不是zval的字段而是被设计在zval所在value字段所指向的结构体中
zend_refcounted_h gc;
//总共4字节 可以存储一个uint32_t类型的flags，也可以存储由4个unsigned char组成的结构体v
union {
struct {
//兼容不同操作系统的大小端
ZEND_ENDIAN_LOHI_4(
//用各个bit表达HashTable的各种标记，总共6中flag，对应flags的第1位到第6位
//在zend_hash.h文件中38~43行
//#define HASH_FLAG_PERSISTENT (1<<0) 是否使用持久化内存，不使用内存池
//#define HASH_FLAG_APPLY_PROTECTION (1<<1) 是否开启递归遍历保护
//#define HASH_FLAG_PACKED (1<<2) 是否是packed array
//#define HASH_FLAG_INITIALIZED (1<<3) 是否已经初始化
//#define HASH_FLAG_STATIC_KEYS (1<<4) 标记key为数字key或者字符串key
//#define HASH_FLAG_HAS_EMPTY_IND (1<<5) 是否存在空的间接val
zend_uchar flags,
//递归遍历数，为了解决循环引用导致死循环问题
zend_uchar nApplyCount,
//迭代器计数，php中每一个foreach语句都会在全局遍历EG中创建一个迭代器，
//包含正在遍历的HashTable和游标信息。该字段记录了当前runtime正在迭代当前
//HashTable的迭代器的数量
zend_uchar nIteratorsCount,
//调试目的用
//#define HT_OK 0x00 正常状态 各种数据完全一致
//#define HT_IS_DESTROYING 0x40 正在删除所有内容，包括arBuckets本身
//#define HT_DESTROYED 0x80 已删除，包括arBuckets本身
//#define HT_CLEANING 0xc0 正在清除所有的arBuckets指向的内容，但不包括arBuckets本身
zend_uchar consistency)
} v;
uint32_t flags;
} u;
//掩码。一般为-nTableSize，区别于PHP5,PHP7中的掩码始终为负数
uint32_t nTableMask;
//实际的存储容器，通过指针指向一段连续的内存，存储着bucket数组
Bucket *arData;
//所有已使用bucket的数量，包括有效bucket和无效bucket数量，在bucket数组中，下标从
//0~(nNumUsed-1)的bucket都属于已使用bucket，而下标从nNumUsed~(nTableSize-1)的bucket
//都属于未使用bucket
uint32_t nNumUsed;
//有效的bucket数量，总是<=nNumUsed
uint32_t nNumOfElements;
//HashTable的大小，表示arData所指向的bucket数组大小，即所有bucket数量，取值始终是2^n,
//最小是8，最大32位系统是（2^30）,64位系统(2^31)
uint32_t nTableSize;
//HashTable的全局默认游标，在PHP7中reset/key/current/next/prev/end等等函数都与该字段
//有关，是一个有符号整型，由于所有bucket内存是连续的，不需要再根据指针维护正在遍历的
//bucket，而是只维护正在遍历的bucket所在数组中的下标就可以
uint32_t nInternalPointer;
//HashTable的自然key，即数组插入元素无须指定key，key会以nNextFreeElement的值为准。
//该值初始化为0，比如$a[] = 1, 实际上插入到key等于0的bucket上，然后nNextFreeElement
//会变为1，代表下一个自然插入的元素的key为1
zend_long nNextFreeElement;
//析构函数，当bucket元素被更新或者删除时，会对bucket的value调用该函数，如果value是引用计数
//的类型，那么会对value引用计数-1，引发可能的GC
dtor_func_t pDestructor;
};
/*
* HashTable Data Layout
* =====================
*
* +=============================+
* | HT_HASH(ht, ht->nTableMask) |
* | ... |
* | HT_HASH(ht, -1) |
* +-----------------------------+
* ht->arData ---> | Bucket[0] |
* | ... |
* | Bucket[ht->nTableSize-1] |
* +=============================+
*/
#define HT_INVALID_IDX ((uint32_t) -1)
#define HT_MIN_MASK ((uint32_t) -2)
#define HT_MIN_SIZE 8
#if SIZEOF_SIZE_T == 4
# define HT_MAX_SIZE 0x04000000 /* small enough to avoid overflow checks */
# define HT_HASH_TO_BUCKET_EX(data, idx) \
((Bucket*)((char*)(data) + (idx)))
# define HT_IDX_TO_HASH(idx) \
((idx) * sizeof(Bucket))
# define HT_HASH_TO_IDX(idx) \
((idx) / sizeof(Bucket))
#elif SIZEOF_SIZE_T == 8
# define HT_MAX_SIZE 0x80000000
PHP7中HashTable各种计数示例
数据结构到此为止，到这里，对比PHP5的数组实现，大家有没有发现一个问题，HashTable的slot和链表上哪去了？arData指向的bucket数组，并没有像PHP5那样，指向的是bucket *指针数组，那么如何基于一个bucket的数组实现多个slot和链表呢？
1) PHP7在分配bucket数组的时候，在bucket数组的前面额外多申请了一些内存(索引数组/索引表)
2) 数组中的每个元素代表一个slot，存放着每个slot链表的第一个bucket在bucket数组中的下标。如
果当前slot没有任何bucket，那么索引值为-1。
3) 为了实现逻辑链表，bucket的元素的val都是zval，PHP7通过bucket。val.u2.next表示链表中下一
个元素在数组中的下标
这里面一个非常巧妙的设计是索引数组还是通过HashTable.arData来引用。由于索引数组和bucket数组是连续的内存，因此arData[0 ~ n-1]表示bucket数组元素，((uint32_t*)(arData))[-1 ~ -n]表示索引数组元素，因此计数bucket属于哪个slot时候，要做的就是确定它在索引数组中的下标，而整个下标是从-n~-1的，到这里是否已经理解了为什么HashTable的掩码是负数了吧？那是因为为了得到介于[-n,-1]之间的负数的下标，PHP7的HashTable设计中的hash2函数是如下计算方式：
nIndex = h | ht->nTableMask;
以nTableSize=8为例子，nTableMask=-8 对应的二进制为:
11111111 11111111 11111111 1111000
取模和按位取或计算示意图
Packed Array 和 Hash Array 的区别
PHP数组有两种用法:
1）纯数组
2）基于key-value的map
例如：
<?php
$a = [1, 2, 3]; //纯数组
$b = ["a" => 1, "b" => 2, "c" => 3]; //map
$c["foo"] = 1;
$c[] =2;
$c["s"] = 3;
$c["x"] = 4;
?>
对于上面的两种用法，PHP7引申出了 Packed Array 和 Hash Array的概念。当HashTable的u.v.flags & HASH_FALG_PACKED > 0时，表示当前数组是Packed Array，否则是Hash Array。
1. 内存的本质区别
//a.php
<?php
echo "PHP_VERSION:". PHP_VERSION. "\n";
$memory_start = memory_get_usage();
$test = [];
for ($i =0; $i <= 200000; $i++) {
$test[$i] = 1;
}
echo memory_get_usage() - $memory_start, " bytes\n";
?>
//b.php
<?php
echo "PHP_VERSION:". PHP_VERSION. "\n";
$memory_start = memory_get_usage();
$test = [];
for ($i =200000; $i >=0 ; $i--) {
$test[$i] = 1;
}
echo memory_get_usage() - $memory_start, " bytes\n";
?>
root@55e3f3b83dcf:/var/www/html/site1# php a.php
PHP_VERSION:7.2.8
8392784 bytes
root@55e3f3b83dcf:/var/www/html/site1# php b.php
PHP_VERSIONS:7.2.8
9437264 bytes
从执行结果看，两个脚本的使用内存是不一样的，b.php比a.php大概多使用了1M左右的内存，这是为什么呢？
原因就是 2个php中的test数组的内存结构是有区别的，一种是Packed Array，一种是Hash Array
(需要保存索引数组到bucket数组的索引关系)。
HashTable初始化源码如下:
static zend_always_inline void zend_hash_real_init_ex(HashTable *ht, int packed)
{
HT_ASSERT(GC_REFCOUNT(ht) == 1);
ZEND_ASSERT(!((ht)->u.flags & HASH_FLAG_INITIALIZED));
//如果时packed array 处理方式
if (packed) {
//为arData申请分配内存，并把arData的指针偏移指向bucket数组的首地址
HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT));
//修改flag为已经初始化并且为packed array
(ht)->u.flags |= HASH_FLAG_INITIALIZED | HASH_FLAG_PACKED;
//nIndex设置为无效标识-1 即arData[-1] = -1, arData[-2] = -1
HT_HASH_RESET_PACKED(ht);
} else {
//hash array处理方式
//hash array时候 nTableMask恒等于-nTableSize，因为nTableSize=2^n,所以nTableMask
//的二进制位右侧全部为0，所以可以保证nIndex落在数组索引的范围之内（|nIndex| <= nTableSize）
(ht)->nTableMask = -(ht)->nTableSize;
//为arData申请分配内存，并把arData的指针偏移指向bucket数组的首地址
HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT));
//修改flag为已经初始化 此时bucket数组还未初始化
(ht)->u.flags |= HASH_FLAG_INITIALIZED;
if (EXPECTED(ht->nTableMask == (uint32_t)-8)) {
Bucket *arData = ht->arData;
//设置nIndex设置为无效标识-1
HT_HASH_EX(arData, -8) = -1;
HT_HASH_EX(arData, -7) = -1;
HT_HASH_EX(arData, -6) = -1;
HT_HASH_EX(arData, -5) = -1;
HT_HASH_EX(arData, -4) = -1;
HT_HASH_EX(arData, -3) = -1;
HT_HASH_EX(arData, -2) = -1;
HT_HASH_EX(arData, -1) = -1;
} else {
HT_HASH_RESET(ht);
}
}
}
//nIndex设置为无效标识-1 即arData[-1] = -1, arData[-2] = -1
#define HT_HASH_RESET_PACKED(ht) do { \
HT_HASH(ht, -2) = HT_INVALID_IDX; \
HT_HASH(ht, -1) = HT_INVALID_IDX; \
} while (0)
//HT宏用来计算ht索引数组和bucket数组大小总和，索引数组大小为:-nTableMask*sizeof(uint32_t)),
//bucket数组大小为:nTableSize* sizeof(Bucket))
#define HT_MIN_MASK ((uint32_t) -2) //最小的nTableMask
#define HT_HASH_SIZE(nTableMask) \
(((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t))
#define HT_DATA_SIZE(nTableSize) \
((size_t)(nTableSize) * sizeof(Bucket))
#define HT_SIZE_EX(nTableSize, nTableMask) \
(HT_DATA_SIZE((nTableSize)) + HT_HASH_SIZE((nTableMask)))
#define HT_SIZE(ht) \
HT_SIZE_EX((ht)->nTableSize, (ht)->nTableMask)
#define HT_USED_SIZE(ht) \
(HT_HASH_SIZE((ht)->nTableMask) + ((size_t)(ht)->nNumUsed * sizeof(Bucket)))
#define HT_HASH_RESET(ht) \
//申请bucket相关内存时，会通过pemalloc一次性申请HT_SIZE大小的内存，并返回这段内存的指针ptr，
//当作HT_SET_DATA_ADDR宏的第二个参数。HT_SET_DATA_ADDR宏将ht->arData指向ptr这段内存中
//bucket数组的起始位置。从宏代码可以看到，就是将ptr之后-nTableMask * sizeof(uint32_t)个字节
//的位置指针赋值给ht->arData，即让arData指向bucket数组的起始位置
//申请bucket内存。如果是packed array，由于这时nTableMask等于-2，所以会通过pemalloc申请大小
//为2 *sizeof(uint32_t) + nTableSize * sizeof(Bucket）的内存。
//如果是hash array，会先将nTableMask置为-nTableSize，然后通过pemalloc申请大小为
//nTableSize * sizeof(uint32_t) + nTableSize * sizeof(Bucket)的内存
//设置数据arData地址位置
#define HT_SET_DATA_ADDR(ht, ptr) do { \
(ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); \
} while (0)
//获取数据arData地址位置
#define HT_GET_DATA_ADDR(ht) \
((char*)((ht)->arData) - HT_HASH_SIZE((ht)->nTableMask))
2. Packed Array
Packed Array 有以下约束和特性:
1） key全是数字key
2） key按插入顺序排列，必须是递增的
3）每个key-value对的存储位置都是确定的，都存储在bucket数组的第key个元素上
4）packed array 不需要索引数组。 其实就是利用了bucket数组连续性的特点，对于某些只有数字key
的场景进行优化，由于不再需要索引数组，从内存空间上节省了
(nTableSIze - 2) * sizeof(uint32_t)个字节
接下来我们看下本小节开头举的例子，a的key都是数字key，且key插入顺序为0，1，2,满足递增的特性，所以a为Packed Array。示意图如下:
packed array实现示意图
而Hash Array正好相反，它要依赖索引数组来维护每一个slot链表中首元素在bucket数组中的下标，且b的key为字符串，所以b是Hash Array。示意图如下:
hash array 实现示意图
带冲突的hash array实现示意图
带冲突的hash array实现示意图2
带冲突的hash array实现示意图3
带冲突的hash array实现示意图4
问题:
观察下面三个是 packed array 还是 hash array
$a = [1=>"a", 3=> "b", 5 => "c"]; //是
$b = [1 =>"a", 5=> "c", 3 => "b"]; //不是
$c = [1 =>"a", 8=> "b"]; //不是
扩容和Rehash操作
我们知道，Hash Array在重置一个key的时候并不会真正触发，而是只做一个标记，删除是在扩容和Rehash(重建索引)的时候才会触发，下面开始说明扩容和Rehash的实现过程。
1). Hash Array的容量是分配是固定的，初始化时每次申请是2^n的容量，最小为8，最大为0x80000000
2).当容量足够的时候直接执行插入操作。
3).当容量不够时(nNumUsed >= nTableSize),检查已删除元素所占的比例，假如达到阈值
(ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)),则将已删除元素从
HashTable中移除，并进行重建索引操作。如果未达到阈值，则进行扩容，新的容量扩大到当前的2倍
(2 * nTableSize),将当前Bucket数组复制到新的空间，并进行重建索引操作。
4).扩容并重建完成后，如果有足够的空间则再执行插入操作。
扩容和重建索引整体流程
重建索引Rehash示意图
1). Rehash 对应的源码中的 zend_hash_rehash(ht)方法
2). Rehash 的主要功能就是把HashTable bucket数组中标识为IS_UNDEF的数据删除，把有效的数据重
新聚合到bucket数组并更新插入索引表
3).整个Rehash不会重新申请内存，而是在原有结构上进行聚合调整
具体步骤如下:
(1). 重置所有nIndex数组为-1.
(2). 初始化2个bucket类型的指针p，q,循环遍历bucket数组
(3). 每次循环，p++，遇到第一个IS_UNDEF时，q=p；继续遍历
(4). 当再次遇到一个正常数据时，把正常数据拷贝到q指向的位置,q++
(5). 直到遍历完数组，更新nNumUsed等计数
//packed array 转hash array
ZEND_API void ZEND_FASTCALL zend_hash_packed_to_hash(HashTable *ht)
{
//获取新旧arData数据位置
void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
//先将ht->arData位置赋值给old_buckets
Bucket *old_buckets = ht->arData;
HT_ASSERT(GC_REFCOUNT(ht) == 1);
//ht->u.flags = 26 生成一个新的arData，调用memcpy拷贝过去，释放掉老的arData
ht->u.flags &= ~HASH_FLAG_PACKED;
//申请新的data数据大小
new_data = pemalloc(HT_SIZE_EX(ht->nTableSize, -ht->nTableSize), (ht)->u.flags & HASH_FLAG_PERSISTENT);
//转为hash array后 nTableMask 恒等于 -nTableSize
ht->nTableMask = -ht->nTableSize;
//设置新的arData地址指向bucket数组内存
HT_SET_DATA_ADDR(ht, new_data);
//拷贝旧数据到新的arData
memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
//释放老的arData空间
pefree(old_data, (ht)->u.flags & HASH_FLAG_PERSISTENT);
//重建索引
zend_hash_rehash(ht);
}
//hash array 转 packed array
ZEND_API void ZEND_FASTCALL zend_hash_to_packed(HashTable *ht)
{
//获取新旧arData数据位置
void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
//先将ht->arData位置赋值给old_buckets
Bucket *old_buckets = ht->arData;
HT_ASSERT(GC_REFCOUNT(ht) == 1);
//申请新的data数据大小
new_data = pemalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), (ht)->u.flags & HASH_FLAG_PERSISTENT);
ht->u.flags |= HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS;
//设置nTableMask 为HT_MIN_MASK(-2)
ht->nTableMask = HT_MIN_MASK;
//设置新的arData地址指向bucket数组内存
HT_SET_DATA_ADDR(ht, new_data);
//nIndex设置为无效标识-1 即arData[-1] = -1, arData[-2] = -1
HT_HASH_RESET_PACKED(ht);
//拷贝旧数据到新的arData
memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
//释放老的arData空间
pefree(old_data, (ht)->u.flags & HASH_FLAG_PERSISTENT);
}
//hash array 扩容
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
IS_CONSISTENT(ht);
HT_ASSERT(GC_REFCOUNT(ht) == 1);
if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */
//当nNumUsed大小超过阈值 重建hash
zend_hash_rehash(ht);
} else if (ht->nTableSize < HT_MAX_SIZE) { /* Let's double the table size */
//获取新旧arData位置
void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
//此时nsize为2*nTableSize
uint32_t nSize = ht->nTableSize + ht->nTableSize;
//先将arData地址指向旧的bucket数组内存
Bucket *old_buckets = ht->arData;
//申请新的数组内存大小
new_data = pemalloc(HT_SIZE_EX(nSize, -nSize), ht->u.flags & HASH_FLAG_PERSISTENT);
//总的HashTable大小为2*nTableSize
ht->nTableSize = nSize;
//hash array中，nTableMask 恒等于-nTableSize
ht->nTableMask = -ht->nTableSize;
//设置新的arData位置
HT_SET_DATA_ADDR(ht, new_data);
//拷贝旧的bucket数组数据到新的arData
memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
//释放旧的arData数据
pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT);
//重建索引
zend_hash_rehash(ht);
} else {
//报错
zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
}
}
//hash array 重建
ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
Bucket *p;
uint32_t nIndex, i;
IS_CONSISTENT(ht);
if (UNEXPECTED(ht->nNumOfElements == 0)) {
if (ht->u.flags & HASH_FLAG_INITIALIZED) {
ht->nNumUsed = 0;
HT_HASH_RESET(ht);
}
return SUCCESS;
}
HT_HASH_RESET(ht);
i = 0;
p = ht->arData;
if (HT_IS_WITHOUT_HOLES(ht)) {
do {
nIndex = p->h | ht->nTableMask;
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
p++;
} while (++i < ht->nNumUsed);
} else {
do {
if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
uint32_t j = i;
Bucket *q = p;
if (EXPECTED(ht->u.v.nIteratorsCount == 0)) {
while (++i < ht->nNumUsed) {
p++;
if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
ZVAL_COPY_VALUE(&q->val, &p->val);
q->h = p->h;
nIndex = q->h | ht->nTableMask;
q->key = p->key;
Z_NEXT(q->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
if (UNEXPECTED(ht->nInternalPointer == i)) {
ht->nInternalPointer = j;
}
q++;
j++;
}
}
} else {
uint32_t iter_pos = zend_hash_iterators_lower_pos(ht, 0);
while (++i < ht->nNumUsed) {
p++;
if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
ZVAL_COPY_VALUE(&q->val, &p->val);
q->h = p->h;
nIndex = q->h | ht->nTableMask;
q->key = p->key;
Z_NEXT(q->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
if (UNEXPECTED(ht->nInternalPointer == i)) {
ht->nInternalPointer = j;
}
if (UNEXPECTED(i == iter_pos)) {
zend_hash_iterators_update(ht, i, j);
iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1);
}
q++;
j++;
}
}
}
ht->nNumUsed = j;
break;
}
nIndex = p->h | ht->nTableMask;
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
p++;
} while (++i < ht->nNumUsed);
}
return SUCCESS;
}
至此PHP7的HashTable和bucket的数组结构已经分析完毕。
参考资料:
陈雷大佬的PHP7源码书籍
https://www.cnblogs.com/ohmygirl/p/internal-3.html
https://fivezh.github.io/2018/11/02/graceful-design-in-php7-src/
https://maxielj.github.io/2018/08/20/php%E6%95%B0%E7%BB%84%E5%AE%9E%E7%8E%B0/
