引入数组
大家都知道,在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的示意图如下:
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,示意图如下:
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
数据结构到此为止,到这里,对比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。示意图如下:
而Hash Array正好相反,它要依赖索引数组来维护每一个slot链表中首元素在bucket数组中的下标,且b的key为字符串,所以b是Hash Array。示意图如下:
问题:
观察下面三个是 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).扩容并重建完成后,如果有足够的空间则再执行插入操作。
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/