本质上PHP数组是一个有序字典,它必须同时满足以下2个条件:
PHP的数组zend_array对应的是HashTable。HashTable(哈希表)是一种通过某种哈希函数将特定的键映射到特定值的一种数据结构,它维护着键和值的一一对应关系,并且可以快速地根据键检索到值,查找效率为O(1)。HashTable的示意如图下:
说明:
在具体实现过程中,PHP基于上述基本概念,对bucket以及哈希函数进行了一些补充,增加了hash1函数以生成h值,然后通过hash2函数散列到不同的slot, 示意图如下:
说明:
这个h值的作用是什么呢?
php7中h的计算(即1.2节中所说的hash1)采用了DJB hash function,俗称“Times33”算法。很多流行的hash map都使用了这种计算方法,它的思想十分简单:
h(0) = 任意初始值
h(i) = 33 * h(i-1) + str[i]
一个简单的c版本实现如下:
unsigned int DJBHash(char* str, unsigned int len)
{
//初始值
unsigned int hash = 5381;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
//左移5相当于*32,再加一个自身的值就相当于*33,用位移替代乘法,以提高速度
hash = ((hash << 5) + hash) + (*str);
}
return hash;
}
php7中源码如下,函数上方还有一大段注释,讲述了一些time33算法的内容,有兴趣可以查看。
//php-7.0.14/Zend/zend_string.h
static zend_always_inline zend_ulong zend_inline_hash_func(const char *str, size_t len){
//hash初始值
register zend_ulong hash = Z_UL(5381);
/* variant with the hash unrolled eight times */
//8个一组计算,减少循环次数
for (; len >= 8; len -= 8) {
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
hash = ((hash << 5) + hash) + *str++;
}
//累加字串余下部分(一定小于8)的值
switch (len) {
case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
case 1: hash = ((hash << 5) + hash) + *str++; break;
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
/* Hash value can't be zero, so we always set the high bit */
#if SIZEOF_ZEND_LONG == 8
return hash | Z_UL(0x8000000000000000);
#elif SIZEOF_ZEND_LONG == 4
return hash | Z_UL(0x80000000);
#else
# error "Unknown SIZEOF_ZEND_LONG"
#endif
}
PHP7通过链地址法来解决哈希冲突,只不过PHP5的链表是真实物理存在的链表,链表中bucket间的上下游是通过真实存在的指针来维护,而PHP7的链表其实是一种逻辑上的链表,所有的bucket都分配在一段连续的数组内存中,且不再通过指针维护上下游关系,每一个bucket只维护一个bucket在数组中的索引(由于内存是连续的,通过索引可以快速定位到bucket),即可完成链表上的bucket遍历。
在PHP 7中,数组的核心结构是struct _zend_array和bucket,并且为struct_zend_array起了两个别名:HashTable和zend_array。
zend_array定义如下:
//php-7.0.14/Zend/zend_types.h
typedef struct _zend_array zend_array;
typedef struct _zend_array HashTable;
typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
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;
} 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;
};
由于不再依赖于物理指针,整个bucket变得清爽了很多,只有val、h、key3个字段。
bucket从使用角度可以分为3种:未使用bucket、有效bucket、无效bucket。
在内存分布上,有效bucket和无效bucket会交替分布,但都在未使用bucket的前面。插入的时候永远在未使用bucket上进行。当由于删除等操作,导致无效bucket非常多,而有效bucket很少时,会对整个bucket数组进行rehash操作。这样,稀疏的有效bucket就会变得连续而紧密,部分无效bucket会被重新利用而变为有效bucket。还有一部分有效bucket和无效bucket会被释放出来,重新变为未使用bucket。
接下来看看HashTable。
nTableSize、nNumUsed、nNumOfElements三者关系如下:
//php-7.0.14/Zend/zend_hash.h
#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
PHP 7在分配bucket数组内存时,在bucket数组的前面额外多申请了一些内存,这段内存是一个索引数组(也叫索引表),数组里面的每个元素代表一个slot,存放着每个slot链表的第一个bucket在bucket数组中的下标。如果当前slot没有任何bucket元素,那么索引值为-1。而为了实现逻辑链表,由于bucket元素的val是zval, PHP 7通过bucket.val.u2.next表达链表中下一个元素在数组中的下标,如下图(n等于nTableSize)所示。
这里一个非常巧妙的设计是索引数组仍然通过HashTable.arData来引用。由于索引数组和bucket数组是连续的内存,因此arData[0…n-1]表示bucket数组元素,((uint32_t*) (arData))[-1…-n]表示索引数组元素。因此在计算bucket属于哪个slot时,要做的就是确定它在索引数组中的下标,而这个下标是从-n~-1的负数,分别代表slot1到slotN。
为了得到介于[-n, -1]之间的负数的下标,PHP7的HashTable设计中的hash2函数(根据h值取得slot值)是这样的(其中nIndex就是slot值):
nIndex = h | ht->nTableMask;
以nTableSize=8为例,nTableMask=-8,二进制表示是:
11111111111111111111111111111000
任何整数和它进行按位或之后的结果只有以下8种,这恰好满足[-n, -1]的取值范围:
11111111111111111111111111111000 //-8
11111111111111111111111111111001 //-7
11111111111111111111111111111010 //-6
11111111111111111111111111111011 //-5
11111111111111111111111111111100 //-4
11111111111111111111111111111101 //-3
11111111111111111111111111111110 //-2
11111111111111111111111111111111 //-1
PHP数组有两种用法:
例如:
$a = [1, 2, 3]; //纯数组
$b = ["a" => 1, "b" => 2, "c" => 3]; //map
对于上面的两种用法,PHP7引申出了 Packed Array 和 Hash Array的概念。当HashTable的u.v.flags & HASH_FALG_PACKED > 0时,表示当前数组是Packed Array,否则是Hash Array。
packed array和hash array的区别在哪里呢?先看下面两段代码:
//array1.php
$start = memory_get_usage();
$test = [];
for($i=0; $i<=200000; $i++){
$test[$i] = $i;
}
$end = memory_get_usage();
echo $end - $start, "\n"
//array2.php
$start = memory_get_usage();
$test = [];
for($i=200000; $i>=0; $i--){
$test[$i] = $i;
}
$end = memory_get_usage();
echo $end - $start, "\n";
运行结果如下:
php array1.php
8392840
php array2.php
9437320
array2.php比array1.php多使用了1M左右内存,这是为什么呢?原因就在于这两种写法,test数组的内存结构是有区别的,一种是packed array,另一种是hash array。
packed array具有以下约束和特性。
它实际上利用了bucket数组的连续性特点,对于某些只有数字key的场景进行的优化。由于不再需要索引数组,从内存空间上节省了(nTableSize-2 )*sizeof(uint32_t) 个字节。另外,由于存取bucket是直接操作bucket数组,在性能上也有所提升。
接下来我们看下本小节开头举的例子,array1.php中test的key都是数字key,且key插入顺序为0,1,2,满足递增的特性,所以它是Packed Array。示意图如下:
说明:
hash array依赖索引数组来维护每一个slot链表中首元素在bucket数组中的下标。对array2.php,$test的key不是递增的,因此它不是packed array,而是hash array。示意图如下:
说明:
下面以$test[199999]为例,说明hash方式如何寻找其值。
$a = [1=>'a', 3=>'b', 5=>'c']; //packed array
$b = [1=>'a', 5=>'c', 3=>'b']; //hash array
$c = [1=>'a', 8=>'b']; //hash array
说明:
bucket数组中下标为2~7的6个bucket为了保持packed array特性,无法再插入元素,成为浪费的空间。因此,PHP 7会在packed array的空间效率以及时间效率优化与空间浪费之间做一个平衡,当空间浪费比较多的时候,PHP 7会将packed array转化为hash array,变成下面的样子:
数据在插入HashTable时,不同的key经过哈希函数得到的值可能相同,导致插入索引数组冲突,理论上需要在索引数组外再加一个链表把所有冲突的value以双链表的形式关联起来,然后读取的时候去遍历这个双链表中的数据,比较对应的key。
PHP7的hash array的做法是,不单独维护一个双链表,而是把每个冲突的idx存储在bucket的zval.u2.next中,插入的时候把老的value存储的地址(idx)放到新value的next中,再把新value的存储地址更新到索引数组中。
举个例子,假如顺次插入的第1、2、3元素, 它们的h|nTableMask相同,均为-6, 发生哈希冲突,那么解决方法如下图所示:
在hash array中unset一个key的时候并不会真正触发删除,是只做一个标记,删除是在扩容和rehash(重建索引)的时候才会触发。插入时触发扩容及rehash的整体流程如下图所示:
说明:
ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)
则将已删除元素从HashTable中移除,并重建索引(rehash)。如果未到阈值,则要进行扩容操作,新的容量扩大到当前大小的2倍(即2*nTableSize),将当前bucket数组复制到新的空间,然后重建索引。
相关源码如下:
//php-7.0.14/Zend/zend_hash.c
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 */
HANDLE_BLOCK_INTERRUPTIONS();
//触发条件,重建索引,以便释放空间
zend_hash_rehash(ht);
HANDLE_UNBLOCK_INTERRUPTIONS();
}
//将现有空间翻倍
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,加法比*2快
uint32_t nSize = ht->nTableSize + ht->nTableSize;
Bucket *old_buckets = ht->arData;
HANDLE_BLOCK_INTERRUPTIONS();
//申请新的数组内存大小
new_data = pemalloc(HT_SIZE_EX(nSize, -nSize), ht->u.flags & HASH_FLAG_PERSISTENT);
//设置新的table大小
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);
HANDLE_UNBLOCK_INTERRUPTIONS();
} else {
//内存不够,报错
zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%zu * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
}
}
下面我们对rehash作更详细的说明:
下面来看源码
//php-7.0.14/Zend/zend_hash.c
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_INVALID_IDX(-1)
HT_HASH_RESET(ht);
}
return SUCCESS;
}
HT_HASH_RESET(ht);
i = 0;
p = ht->arData;
/*
* 数组里没有删除的元素
* 重新计算索引数组即可
*/
if (ht->nNumUsed == ht->nNumOfElements) {
do {
nIndex = p->h | ht->nTableMask;
//zval.u2.next记录开链(有hash冲突的情况)
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
//在索引区(nIndex处)记录当前元素位置
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
p++;
} while (++i < ht->nNumUsed);
}
else{
do{
/*此时表明有已删除元素
*则将后面的value依次前移,压实Bucket数组
*/
if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
//j记录了当前实际有效元素的个数
uint32_t j = i;
//q记录下第一个被删除元素的位置
Bucket *q = p;
... ...
while (++i < ht->nNumUsed) {
p++;
//p碰到非IS_UNDEF元素时,将其复制到q所指的位置
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向前移动
q++;
//有效元素增加一个
j++;
}
}
... ...
//数据被压实了,所以ht->nNumUsed即为当前有效元素的个数
ht->nNumUsed = j;
break;
}
//未碰到IS_UNDEF元素前走此逻辑,只需要重算索引
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;
}
来看一个例子:
//生成hash array
for($i=7; $i>=0; $i--){
$arr[$i] = $i * 10;
}
//产生空洞
unset($arr[3]);
unset($arr[4]);
unset($arr[5]);
/*
* ht->nNumUsed = 8
* ht->nNumOfElements = 5
* 插入新元素满足ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)
* 所以触发rehash
*/
$arr[11] = 110;
rehash之前
rehash之后
值得注意的是,rehash后,bucket数组中第6,7两个位置存储的值依然在,只是索引中找不到他们的位置。另外使用gdb可看到nNumUsed = 6,也表明6,7两个位置是未使用的。
转换代码如下:
//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位置
Bucket *old_buckets = ht->arData;
HT_ASSERT(GC_REFCOUNT(ht) == 1);
HANDLE_BLOCK_INTERRUPTIONS();
//去掉packed array标记
ht->u.flags &= ~HASH_FLAG_PACKED;
//为新hash array申请bucket数组空间
new_data = pemalloc(HT_SIZE_EX(ht->nTableSize, -ht->nTableSize), (ht)->u.flags & HASH_FLAG_PERSISTENT);
//重新设置ht->nTableMask(packed array的nTableMask为-2,所以要重设)
ht->nTableMask = -ht->nTableSize;
//ht->arData指向新地址
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);
HANDLE_UNBLOCK_INTERRUPTIONS();
}
下面我们结合gdb看一个转换的例子,php代码如下:
//hash.php
$arr[] = 'foo';
echo "packed array\n";
var_dump($arr);
$arr['a'] = 'bar';
echo "hash array\n";
var_dump($arr);
在命令行下执行gdb php, 进入gdb调试。
/*在var_dump处设置断点,查看数组变化*/
b php_var_dump
Breakpoint 1 at 0x597040: file /usr/local/src/php-7.0.14/ext/standard/var.c, line 79.
(gdb) run hash.php
packed array
Breakpoint 1, php_var_dump (struc=0x7ffff7813160, level=1) at /usr/local/src/php-7.0.14/ext/standard/var.c:79
79 {
//struc即是$arr
(gdb) p struc
$1 = (zval *) 0x7ffff7813160
(gdb) p *struc.value.arr
$3 = {gc = {refcount = 2, u = {v = {type = 7 '\a', flags = 0 '\000', gc_info = 0}, type_info = 7}}, u = {v = {
flags = 30 '\036', nApplyCount = 0 '\000', nIteratorsCount = 0 '\000', reserve = 0 '\000'}, flags = 30},
nTableMask = 4294967294, arData = 0x7ffff785c788, nNumUsed = 1, nNumOfElements = 1, nTableSize = 8, nInternalPointer = 0,
nNextFreeElement = 1, pDestructor = 0x62faa0 <_zval_ptr_dtor>}
//查看第0个元素内容为foo,符合预期
(gdb) p *struc.value.arr.arData[0].val.value.str.val@3
$3 = "foo"
接下来查看变成hash的arr
(gdb) c
Continuing.
array(1) {
[0]=>
Breakpoint 1, php_var_dump (struc=0x7ffff785c788, level=3) at /usr/local/src/php-7.0.14/ext/standard/var.c:79
79 {
(gdb) c
Continuing.
string(3) "foo"
}
//输出hash array后,说明是插入a=bar的$arr了
hash array
Breakpoint 1, php_var_dump (struc=0x7ffff7813160, level=1) at /usr/local/src/php-7.0.14/ext/standard/var.c:79
79 {
(gdb) p *struc.value.arr
$7 = {gc = {refcount = 2, u = {v = {type = 7 '\a', flags = 0 '\000', gc_info = 0}, type_info = 7}}, u = {v = {
flags = 26 '\032', nApplyCount = 0 '\000', nIteratorsCount = 0 '\000', reserve = 0 '\000'}, flags = 26},
nTableMask = 4294967288, arData = 0x7ffff785c8e0, nNumUsed = 2, nNumOfElements = 2, nTableSize = 8, nInternalPointer = 0,
nNextFreeElement = 1, pDestructor = 0x62faa0 <_zval_ptr_dtor>}
(gdb) p struc.value.arr.arData[0]
//第0个元素h=0
$11 = {val = {value = {lval = 140737345758432, dval = 6.9533487626122526e-310, counted = 0x7ffff78024e0,
str = 0x7ffff78024e0, arr = 0x7ffff78024e0, obj = 0x7ffff78024e0, res = 0x7ffff78024e0, ref = 0x7ffff78024e0,
ast = 0x7ffff78024e0, zv = 0x7ffff78024e0, ptr = 0x7ffff78024e0, ce = 0x7ffff78024e0, func = 0x7ffff78024e0, ww = {
w1 = 4152370400, w2 = 32767}}, u1 = {v = {type = 6 '\006', type_flags = 0 '\000', const_flags = 0 '\000',
reserved = 0 '\000'}, type_info = 6}, u2 = {var_flags = 4294967295, next = 4294967295, cache_slot = 4294967295,
lineno = 4294967295, num_args = 4294967295, fe_pos = 4294967295, fe_iter_idx = 4294967295}}, h = 0, key = 0x0}
//第0个元素内容foo
(gdb) p *struc.value.arr.arData[0].val.value.str.val@3
$12 = "foo"
//第1个元素h=9223372036854953478
(gdb) p struc.value.arr.arData[1]
$13 = {val = {value = {lval = 140737345758560, dval = 6.9533487626185766e-310, counted = 0x7ffff7802560,
str = 0x7ffff7802560, arr = 0x7ffff7802560, obj = 0x7ffff7802560, res = 0x7ffff7802560, ref = 0x7ffff7802560,
ast = 0x7ffff7802560, zv = 0x7ffff7802560, ptr = 0x7ffff7802560, ce = 0x7ffff7802560, func = 0x7ffff7802560, ww = {
w1 = 4152370528, w2 = 32767}}, u1 = {v = {type = 6 '\006', type_flags = 0 '\000', const_flags = 0 '\000',
reserved = 0 '\000'}, type_info = 6}, u2 = {var_flags = 4294967295, next = 4294967295, cache_slot = 4294967295,
lineno = 4294967295, num_args = 4294967295, fe_pos = 4294967295, fe_iter_idx = 4294967295}}, h = 9223372036854953478,
key = 0x7ffff7802540}
//第一个元素内容为bar
(gdb) p *struc.value.arr.arData[1].val.value.str.val@3
$14 = "bar"
//第一个元素key为a
(gdb) p *struc.value.arr.arData[1].key
$16 = {gc = {refcount = 0, u = {v = {type = 6 '\006', flags = 2 '\002', gc_info = 0}, type_info = 518}},
h = 9223372036854953478, len = 1, val = "a"}
下面来看看索引区
/* 第0个元素, h=0,0|-8= -8, 所以index为-8
* 查看索引数组第8个位置,存储的索引为0
*/
(gdb) p ((uint32_t *)struc.value.arr.arData)[-8]
$17 = 0
/* 第1个元素, h=9223372036854953478, 9223372036854953478|-8 = -2, 所以index为-2
* 查看索引数组第2个位置,存储的索引为1
*/
(gdb) p ((uint32_t *)struc.value.arr.arData)[-2]
$18 = 1