从源码看 PHP 7 数组的实现 (4)

zend_types.h

#if SIZEOF_SIZE_T == 4 # define HT_MAX_SIZE 0x04000000 /* small enough to avoid overflow checks */ /* 省略代码 */ #elif SIZEOF_SIZE_T == 8 # define HT_MAX_SIZE 0x80000000 /* 省略代码 */ #else # error "Unknown SIZEOF_SIZE_T" #endif

根据 sizeof(size_t) 的执行结果判断应该设置为 67108864 还是 2147483648 。

0x04000000 转为二进制是: 00000100000000000000000000000000
0x80000000 转为二进制是: 10000000000000000000000000000000

当 nNumUsed 大于等于 nTableSize 时,会触发 Resize 操作,以此获取更多可使用的 Bucket 。

Resize 策略

Resize 的定义是:

zend_hash.c:

static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)

Resize 有两种策略:

rehash

双倍扩容 + rehash

之所以有不用双倍扩容的选择,是因为 PHP 在删除元素时,只是将对应 Data 区的 Bucket 的值设置为 undefined,并没有移动后面的元素。

选择的条件主要涉及 HashTable 的三个成员:

struct _zend_array { // ...省略 uint32_t nNumUsed; // Data 区最后一个有效 Bucket 的下标 + 1。 uint32_t nNumOfElements; // 存在多少个有效 Bucket。删除数组元素时,会使其减一。 uint32_t nTableSize; // 总共有多少空间。 // ...省略 } 什么情况下只需要 rehash ?

源码是:

ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)

这里做一个转换,方便理解:

ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)

也就是被设置为 undefined 的 Bucket 数量大于当前元素个数除以 32 向下取整的值。

例如:

当 nNumUsed 为 2048 , nNumOfElements 为 2000 的时候,得到 2048 - 2000 < 62 ,因此执行扩容。

当 nNumUsed 为 2048 , nNumOfElements 为 1900 的时候,得到 2048 - 1900 > 59 ,因此执行 rehash。

rehash 做以下操作:

清空 Hash 区;

取两个指针,一个指向当前扫描的位置(叫做 p),一个指向迁移后的位置(叫做 q),遍历直到 p 到达 nNumUsed ;
p 在碰到无效 Bucket 时,会继续往前走一步,不做其他事。
p 在碰到有效 Bucket 时,会把 Bucket 的值复制到 q 指向的 Bucket 的值,并且 p 和 q 一起往前走一步。
这种做法的效率会比每次移动有效 Bucket 都把后面的数据一起往前移动来得高。

重新创建冲突链;

更新内部指针,使其指向更新位置后的 Bucket;

更新 nNumUsed,使其等于 nNumOfElements 。

什么情况下双倍扩容 + rehash ?

满足只 rehash 的条件就只做 rehash,如果不满足条件并且 nTableSize 小于数组可拥有的最大容量(HT_MAX_SIZE),则双倍扩容。

由于 HT_MAX_SIZE 是 0x04000000 或者 0x80000000,并且 nTableSize 始终是 2 的次方,所以最后一次双倍扩容后的容量刚好是 HT_MAX_SIZE 。

0x04000000 转为二进制是: 00000100000000000000000000000000
0x80000000 转为二进制是: 10000000000000000000000000000000

双倍扩容时,做以下操作:

nTableSize 变为原先的两倍;

重新申请一次 Hash 区和 Data 区的内存,然后把原先 Data 区的数据以内存拷贝的方式复制到新的 Data 区;

重新计算 nTableMask;

释放掉原先 Data 区的内存;

做 rehash 。主要是为了重建 Hash 区。

负载因子(Load Factor)

负载因子会影响 hash 碰撞的概率从而影响到耗时,也会影响 Hash 区的大小来影响内存消耗。

在 PHP 中,用 nTableMask 和 nTableSize 的关系来体现:

负载因子 = |nTableMask / nTableSize|

负载因子为 1 的时候(PHP 5),nTableMask == - (nTableSize) 。

负载因子为 0.5 的时候(PHP 7), nTableMask == - (nTableSize + nTableSize) 。

上一次修改负载因子的提交是:
https://github.com/php/php-src/commit/34ed8e53fea63903f85326ea1d5bd91ece86b7ae

为什么负载因子会影响时间消耗和内存消耗?

负载因子越大, nTableMask 绝对值就越小(nTableMask 本身受到 nTableSize 的影响),从而导致 Hash 区变小。

Hash 区一旦变小,更容易产生碰撞。也就使得冲突链更长,执行的操作会在冲突链的时间消耗变得更长。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzxggy.html