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 区一旦变小,更容易产生碰撞。也就使得冲突链更长,执行的操作会在冲突链的时间消耗变得更长。