php5和php7中数组实现方式有何区别?
这篇文章给大家介绍的是php5和php7中数组实现方式的区别，从 PHP 5 到 PHP 7 ，PHP 通过对 hashtable 数据结构和实现方式的修改，使得数组在内存占用和性能上有了很大的提升，下面我们就来详细的了解看看。
⒈ 数据结构
// PHP 5 中 hashtable 的数据结构定义
typedef struct bucket {
ulong h;
/*对于索引数组，存储 key 的原始值；对于关联数组，存储 key 的 hash 之后的值*/
uint nKeyLength;
/*关联数组时存储 key 的长度，索引数组此值为 0*/
void *pData;
/*指向数组 value 的地址*/
void *pDataPtr;
/*如果 value 为指针，则由 pDataPtr 记录 vlaue，pData 则指向 pDataPtr*/
// PHP 5 中数组元素的顺序是固定的，无论什么时候遍历，数组元素总是与插入时的顺序一致
// PHP 5 中使用双向链表来保证数组元素的顺序，pListNext 和 pListLast 分别按照
// 元素插入顺序记录当前 bucket 的下一个和上一个 bucket
struct bucket *pListNext;
struct bucket *pListLast;
// PHP 5 使用拉链法解决 hash 碰撞，pNext 和 pLast 分别存储当前 bucket
// 在冲突的双向链表中的下一个和上一个相邻的 bucket
struct bucket *pNext;
struct bucket *pLast;
const char *arKey;
/*关联数组是存储 key 的原始值*/
}
Bucket;
typedef struct _hashtable {
uint nTableSize;
/*当前 ht 所分配的 bucket 的总数，2^n*/
uint nTableMask;
/*nTableSize - 1，用于计算索引*/
uint nNumOfElements;
/*实际存储的元素的数量*/
ulong nNextFreeElement;
/*下一个可以被使用的整数 key*/
Bucket *pInternalPointer;
/*数组遍历时，记录当前 bucket 的地址*/
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets;
/*记录 bucket 的 C 语言数组*/
dtor_func_t pDestructor;
/*删除数组元素时内部调用的函数*/
zend_bool persistent;
/*标识 ht 是否永久有效*/
unsigned char nApplyCount;
/*ht 允许的最大递归深度*/
zend_bool bApplyProtection;
/*是否启用递归保护*/
#if ZEND_DEBUG
int inconsistent;
#endif
}
HashTable;
// PHP 7 中 hashtable 的数据结构
// PHP 7 中个子版本以及阶段版本中对 hashtable 的数据结构的定义会有微小的差别，这里使用的是 PHP 7.4.0 中的定义
struct _zend_string {
zend_refcounted_h gc;
zend_ulong h;
/*字符串 key 的 hash 值*/
size_t len;
/*字符串 key 的长度*/
char val[1];
/*存储字符串的值，利用了 struct hack*/
}
;
typedef struct _Bucket {
zval val;
/*内嵌 zval 结构，存储数组的 value 值*/
zend_ulong h;
/* hash value (or numeric index) */
zend_string *key;
/* string key or NULL for numerics */
}
Bucket;
typedef struct _zend_array HashTable;
struct _zend_array {
zend_refcounted_h gc;
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar _unused,
zend_uchar nIteratorsCount,
zend_uchar _unused2)
}
v;
uint32_t flags;
}
u;
uint32_t nTableMask;
/*作用与 PHP 5 中 hashtable 中 nTableMask 作用相同，但实现逻辑稍有变化*/
Bucket *arData;
/*存储 bucket 相关的信息*/
uint32_t nNumUsed;
/*ht 中已经使用的 bucket 的数量，在 nNumOfElements 的基础上加上删除的 key*/
uint32_t nNumOfElements;
uint32_t nTableSize;
uint32_t nInternalPointer;
zend_long nNextFreeElement;
dtor_func_t pDestructor;
}
;
不考虑其他开销，单从 Bucket 所占用的空间来看：在 PHP 5 中，考虑到内存对齐，一个 Bucket 占用的空间为 72 字节；在 PHP 7 中，一个 zend_value 占 8 字节，一个 zval 占 16 字节，一个 Bucket 占 32 字节。相比之下，PHP 7 中 Bucket 的内存空间消耗比 PHP 5 低了一半以上。
具体 PHP 5 数组的内存消耗情况，之前的文章已有讲解，这里不再赘述
现在来谈谈 Bucket 的存储：在 PHP 5 中，arBucket 是一个 C 语言数组，长度为 nTableSize，存储的是指向 Bucket 的指针，发生 hash 碰撞的 Bucket 以双向链表的方式连接。
在 PHP 7 中，Bucket 按照数组元素写入的顺序依次存储，其索引值为 idx，该值存储在 *arData 左侧的映射区域中。idx 在映射区域中的索引为 nIndex，nIndex 值为负数，由数组 key 的 hash 值与 nTableMask 进行或运算得到。
// nTableMask 为 -2 倍的 nTableSize 的无符号表示
#define HT_SIZE_TO_MASK(nTableSize) \
((uint32_t)(-((nTableSize) + (nTableSize))))
// 在通过 idx 查找 Bucket 时，data 默认为 Bucket 类型，加 idx 表示向右偏移 idx 个 Bucket 位置
# define HT_HASH_TO_BUCKET_EX(data, idx) \
((data) + (idx))
// 在通过 nIndex 查找 idx 时，
// (uint32_t*)(data) 首先将 data 转换成了 uint32_t* 类型的数组
// 然后将 nIndex 转换成有符号数（负数），然后以数组的方式查找 idx 的值
#define HT_HASH_EX(data, idx) \
((uint32_t*)(data))[(int32_t)(idx)]
nIndex = h | ht->
nTableMask;
idx = HT_HASH_EX(arData, nIndex);
p = HT_HASH_TO_BUCKET_EX(arData, idx);
这里需要指出，nTableMask 之所以设置为 nTableSize 的两倍，是这样在计算 nIndex 时可以减小 hash 碰撞的概率。
⒉ 添加/修改元素
PHP 5
先来谈谈 PHP 5 中数组元素的添加和修改，由于 PHP 5 中数组元素的插入顺序以及 hash 碰撞都是通过双向链表的方式来维护，所以虽然实现起来有些复杂，但理解起来相对容易一些。
// hash 碰撞双向链表的维护
#define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
(element)->
pNext = (list_head);
\
(element)->
pLast = NULL;
\
if ((element)->
pNext) {
\
(element)->
pNext->
pLast = (element);
\
}
#define CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, last, next)\
(element)->
pListLast = (last);
\
(element)->
pListNext = (next);
\
if ((last) != NULL) {
\
(last)->
pListNext = (element);
\
}
else {
\
(ht)->
pListHead = (element);
\
}
\
if ((next) != NULL) {
\
(next)->
pListLast = (element);
\
}
else {
\
(ht)->
pListTail = (element);
\
}
\
// 数组元素插入顺序双向链表的维护
#define CONNECT_TO_GLOBAL_DLLIST(element, ht) \
CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, (ht)->
pListTail, (Bucket *) NULL);
\
if ((ht)->
pInternalPointer == NULL) {
\
(ht)->
pInternalPointer = (element);
\
}
// 数组元素的更新
#define UPDATE_DATA(ht, p, pData, nDataSize) \
if (nDataSize == sizeof(void*)) {
\
// 值为指针类型的元素的更新 \
if ((p)->
pData != &
(p)->
pDataPtr) {
\
pefree_rel((p)->
pData, (ht)->
persistent);
\
}
\
// pDataPtr 存储元素值的地址，pData 存储 pDataPtr 的地址 \
memcpy(&
(p)->
pDataPtr, pData, sizeof(void *));
\
(p)->
pData = &
(p)->
pDataPtr;
\
}
else {
\
// 如果数组元素为值类型，则存入 pData，此时 pDataPtr 为 Null \
if ((p)->
pData == &
(p)->
pDataPtr) {
\
(p)->
pData = (void *) pemalloc_rel(nDataSize, (ht)->
persistent);
\
(p)->
pDataPtr=NULL;
\
}
else {
\
(p)->
pData = (void *) perealloc_rel((p)->
pData, nDataSize, (ht)->
persistent);
\
/* (p)->
pDataPtr is already NULL so no need to initialize it */ \
}
\
memcpy((p)->
pData, pData, nDataSize);
\
}
// 数组元素的初始化
#define INIT_DATA(ht, p, _pData, nDataSize);
\
if (nDataSize == sizeof(void*)) {
\
// 指针类型元素的初始化 \
memcpy(&
(p)->
pDataPtr, (_pData), sizeof(void *));
\
(p)->
pData = &
(p)->
pDataPtr;
\
}
else {
\
// 值类型元素的初始化 \
(p)->
pData = (void *) pemalloc_rel(nDataSize, (ht)->
persistent);
\
memcpy((p)->
pData, (_pData), nDataSize);
\
(p)->
pDataPtr=NULL;
\
}
// hashtable 初始化校验，如果没有初始化，则初始化 hashtable
#define CHECK_INIT(ht) do {
\
if (UNEXPECTED((ht)->
nTableMask == 0)) {
\
(ht)->
arBuckets = (Bucket **) pecalloc((ht)->
nTableSize, sizeof(Bucket *), (ht)->
persistent);
\
(ht)->
nTableMask = (ht)->
nTableSize - 1;
\
}
\
}
while (0)
// 数组元素的新增或更新（精简掉了一些宏调用和代码片段)
ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
ulong h;
uint nIndex;
Bucket *p;
CHECK_INIT(ht);
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h &
ht->
nTableMask;
p = ht->
arBuckets[nIndex];
while (p != NULL) {
if (p->
arKey == arKey ||
((p->
h == h) &
&
(p->
nKeyLength == nKeyLength) &
&
!memcmp(p->
arKey, arKey, nKeyLength))) {
// 数组元素更新逻辑
if (flag &
HASH_ADD) {
return FAILURE;
}
ZEND_ASSERT(p->
pData != pData);
if (ht->
pDestructor) {
ht->
pDestructor(p->
pData);
}
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p->
pData;
}
return SUCCESS;
}
p = p->
pNext;
}
// 数组元素新增逻辑
if (IS_INTERNED(arKey)) {
p = (Bucket *) pemalloc(sizeof(Bucket), ht->
persistent);
p->
arKey = arKey;
}
else {
p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->
persistent);
p->
arKey = (const char*)(p + 1);
memcpy((char*)p->
arKey, arKey, nKeyLength);
}
p->
nKeyLength = nKeyLength;
INIT_DATA(ht, p, pData, nDataSize);
p->
h = h;
// hash 碰撞链表维护
CONNECT_TO_BUCKET_DLLIST(p, ht->
arBuckets[nIndex]);
if (pDest) {
*pDest = p->
pData;
}
// 数组元素写入顺序维护
CONNECT_TO_GLOBAL_DLLIST(p, ht);
ht->
arBuckets[nIndex] = p;
ht->
nNumOfElements++;
ZEND_HASH_IF_FULL_DO_RESIZE(ht);
/* If the Hash table is full, resize it */
return SUCCESS;
}
PHP 5 中的数组在新增或修改元素时，首先会根据给定的 key 计算得到相应的 hash 值，然后据此得到 arBuckets 的索引 nIndex，最终得到链表中第一个 Bucket（ hash 碰撞链表的表头），即p。
如果是更新数组中已有的项，那么会从 p 开始遍历 hash 碰撞链表，直到找到 arkey 与给定的 key 相同的 Bucket，然后更新 pData。
如果是向数组中新增项，首先会判断给定的 key 是否为 interned string 类型，如果是，那么只需要为 Bucket 申请内存，然后将 p-> arKey 指向给定的 key 的地址即可，否则在为新的 Bucket 申请内存的同时还需要为给定的 key 申请内存，然后将 p-> arKey 指向为 key 申请的内存的地址。之后会对新申请的 Bucket 进行初始化，最后要做的两件事：维护 hash 碰撞链表和数组元素写入顺序链表。在维护 hash 碰撞的链表时，新增的 Bucket 是放在链表头的位置；维护数组元素写入顺序的链表时，新增的 Bucket 是放在链表的末尾，同时将 hashtable 的 pListTail 指向新增的 Bucket。
关于 PHP 中的 interned string，之前在讲解 PHP 7 对字符串处理逻辑优化的时候已经说明，这里不再赘述
PHP 7
PHP 7 在 hashtable 的数据结构上做了比较大的改动，同时放弃了使用双向链表的方式来维护 hash 碰撞和数组元素的写入顺序，在内存管理以及性能上得到了提升，但理解起来却不如 PHP 5 中的实现方式直观。
#define Z_NEXT(zval) (zval).u2.next
#define HT_HASH_EX(data, idx) \
((uint32_t*)(data))[(int32_t)(idx)]
# define HT_IDX_TO_HASH(idx) \
((idx) * sizeof(Bucket))
// PHP 7 中数组添加/修改元素（精简了部分代码）
static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag)
{
zend_ulong h;
uint32_t nIndex;
uint32_t idx;
Bucket *p, *arData;
/*... ...*/
ZEND_HASH_IF_FULL_DO_RESIZE(ht);
/* If the Hash table is full, resize it */
add_to_hash:
idx = ht->
nNumUsed++;
ht->
nNumOfElements++;
arData = ht->
arData;
p = arData + idx;
p->
key = key;
p->
h = h = ZSTR_H(key);
nIndex = h | ht->
nTableMask;
Z_NEXT(p->
val) = HT_HASH_EX(arData, nIndex);
HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);
ZVAL_COPY_VALUE(&
p->
val, pData);
return &
p->
val;
}
这里需要先说明一下 nNumUsed 和 nNumOfElements 的区别：
按图中示例，此时 nNumUsed 的值应该为 5，但 nNumOfElements 的值则应该为 3。在 PHP 7 中，数组元素按照写入顺序依次存储，而 nNumUsed 正好可以用来充当数组元素存储位置索引的功能。
另外就是 p = arData + idx ，前面已经讲过 arData 为 Bucket 类型，这里 +idx 意为指针从 arData 的位置开始向右偏移 idx 个 Bucket 的位置。宏调用 HT_HASH_EX 也是同样的道理。
最后就是 Z_NEXT(p-> val)，PHP 7 中的 Bucket 结构都内嵌了一个 zval，zval 中的联合体 u2 中有一项 next 用来记录hash 碰撞的信息。nIndex 用来标识 idx 在映射表中的位置，在往 hashtable 中新增元素时，如果根据给定的 key 计算得到的 nIndex 的位置已经有值（即发生了 hash 碰撞），那么此时需要将 nIndex 所指向的位置的原值记录到新增的元素所对应的 Bucket 下的 val.u2.next 中。宏调用 HT_IDX_TO_HASH 的作用是根据 idx 计算得到 Bucket 的以字节为单位的偏移量。
⒊ 删除元素
PHP 5
在 PHP 5 中，数组元素的删除过程中的主要工作是维护 hash 碰撞链表和数组元素写入顺序的链表。
// 删除 Bucket 的代码（精简了部分代码片段）
static zend_always_inline void i_zend_hash_bucket_delete(HashTable *ht, Bucket *p)
{
if (p->
pLast) {
p->
pLast->
pNext = p->
pNext;
}
else {
ht->
arBuckets[p->
h &
ht->
nTableMask] = p->
pNext;
}
if (p->
pNext) {
p->
pNext->
pLast = p->
pLast;
}
if (p->
pListLast != NULL) {
p->
pListLast->
pListNext = p->
pListNext;
}
else {
/* Deleting the head of the list */
ht->
pListHead = p->
pListNext;
}
if (p->
pListNext != NULL) {
p->
pListNext->
pListLast = p->
pListLast;
}
else {
/* Deleting the tail of the list */
ht->
pListTail = p->
pListLast;
}
if (ht->
pInternalPointer == p) {
ht->
pInternalPointer = p->
pListNext;
}
ht->
nNumOfElements--;
if (ht->
pDestructor) {
ht->
pDestructor(p->
pData);
}
if (p->
pData != &
p->
pDataPtr) {
pefree(p->
pData, ht->
persistent);
}
pefree(p, ht->
persistent);
}
// 元素删除
ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
{
uint nIndex;
Bucket *p;
if (flag == HASH_DEL_KEY) {
h = zend_inline_hash_func(arKey, nKeyLength);
}
nIndex = h &
ht->
nTableMask;
p = ht->
arBuckets[nIndex];
while (p != NULL) {
if ((p->
h == h)
&
&
(p->
nKeyLength == nKeyLength)
&
&
((p->
nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */
|| !memcmp(p->
arKey, arKey, nKeyLength))) {
/* String index */
i_zend_hash_bucket_delete(ht, p);
return SUCCESS;
}
p = p->
pNext;
}
return FAILURE;
}
PHP 5 中数组在删除元素时，仍然是先根据给定的 key 计算 hash，然后找到 arBucket 的 nIndex，最终找到需要删除的 Bucket 所在的 hash 碰撞的链表，通过遍历链表，找到最终需要删除的 Bucket。
在实际删除 Bucket 的过程中，主要做的就是维护两个链表：hash 碰撞链表和数组元素写入顺序链表。再就是释放内存。
PHP 7
由于 PHP 7 记录 hash 碰撞信息的方式发生了变化，所以在删除元素时处理 hash 碰撞链表的逻辑也会有所不同。另外，在删除元素时，还有可能会遇到空间回收的情况。
#define IS_UNDEF 0
#define Z_TYPE_INFO(zval) (zval).u1.type_info
#define Z_TYPE_INFO_P(zval_p) Z_TYPE_INFO(*(zval_p))
#define ZVAL_UNDEF(z) do {
\
Z_TYPE_INFO_P(z) = IS_UNDEF;
\
}
while (0)
static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)
{
// 从 hash 碰撞链表中删除指定的 Bucket
if (!(HT_FLAGS(ht) &
HASH_FLAG_PACKED)) {
if (prev) {
Z_NEXT(prev->
val) = Z_NEXT(p->
val);
}
else {
HT_HASH(ht, p->
h | ht->
nTableMask) = Z_NEXT(p->
val);
}
}
idx = HT_HASH_TO_IDX(idx);
ht->
nNumOfElements--;
if (ht->
nInternalPointer == idx || UNEXPECTED(HT_HAS_ITERATORS(ht))) {
// 如果当前 hashtable 的内部指针指向了要删除的 Bucket 或当前 hashtable 有遍历
// 操作，那么需要避开当前正在被删除的 Bucket
uint32_t new_idx;
new_idx = idx;
while (1) {
new_idx++;
if (new_idx >
= ht->
nNumUsed) {
break;
}
else if (Z_TYPE(ht->
arData[new_idx].val) != IS_UNDEF) {
break;
}
}
if (ht->
nInternalPointer == idx) {
ht->
nInternalPointer = new_idx;
}
zend_hash_iterators_update(ht, idx, new_idx);
}
if (ht->
nNumUsed - 1 == idx) {
//如果被删除的 Bucket 在数组的末尾，则同时回收与 Bucket 相邻的已经被删除的 Bucket 的空间
do {
ht->
nNumUsed--;
}
while (ht->
nNumUsed >
0 &
&
(UNEXPECTED(Z_TYPE(ht->
arData[ht->
nNumUsed-1].val) == IS_UNDEF)));
ht->
nInternalPointer = MIN(ht->
nInternalPointer, ht->
nNumUsed);
}
if (p->
key) {
// 删除 string 类型的索引
zend_string_release(p->
key);
}
// 删除 Bucket
if (ht->
pDestructor) {
zval tmp;
ZVAL_COPY_VALUE(&
tmp, &
p->
val);
ZVAL_UNDEF(&
p->
val);
ht->
pDestructor(&
tmp);
}
else {
ZVAL_UNDEF(&
p->
val);
}
}
static zend_always_inline void _zend_hash_del_el(HashTable *ht, uint32_t idx, Bucket *p)
{
Bucket *prev = NULL;
if (!(HT_FLAGS(ht) &
HASH_FLAG_PACKED)) {
// 如果被删除的 Bucket 存在 hash 碰撞的情况，那么需要找出其在 hash 碰撞链表中的位置
uint32_t nIndex = p->
h | ht->
nTableMask;
uint32_t i = HT_HASH(ht, nIndex);
if (i != idx) {
prev = HT_HASH_TO_BUCKET(ht, i);
while (Z_NEXT(prev->
val) != idx) {
i = Z_NEXT(prev->
val);
prev = HT_HASH_TO_BUCKET(ht, i);
}
}
}
_zend_hash_del_el_ex(ht, idx, p, prev);
}
ZEND_API void ZEND_FASTCALL zend_hash_del_bucket(HashTable *ht, Bucket *p)
{
IS_CONSISTENT(ht);
HT_ASSERT_RC1(ht);
_zend_hash_del_el(ht, HT_IDX_TO_HASH(p - ht->
arData), p);
}
PHP 7 中数组元素的删除，其最终目的是删除指定的 Bucket。在删除 Bucket 时还需要处理好 hash 碰撞链表维护的问题。由于 PHP 7 中 hash 碰撞只维护了一个单向链表（通过 Bucket.val.u2.next 来维护），所以在删除 Bucket 时还需要找出 hash 碰撞链表中的前一项 prev。最后，在删除 Bucket 时如果当前的 hashtable 的内部指针（nInternalPointer）正好指向了要删除的 Bucket 或存在遍历操作，那么需要改变内部指针的指向，同时在遍历时跳过要删除的 Bucket。另外需要指出的是，并不是每一次删除 Bucket 的操作都会回收相应的内存空间，通常删除 Bucket 只是将其中 val 的类型标记为 IS_UNDEF，只有在扩容或要删除的 Bucket 为最后一项并且相邻的 Bucket 为 IS_UNDEF 时才会回收其内存空间。
⒋ 数组遍历
PHP 5
由于 PHP 5 中有专门用来记录数组元素写入顺序的双向链表，所以数组的遍历逻辑相对比较简单。
// 数组的正向遍历
ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
{
HashPosition *current = pos ? pos : &
ht->
pInternalPointer;
IS_CONSISTENT(ht);
if (*current) {
*current = (*current)->
pListNext;
return SUCCESS;
}
else
return FAILURE;
}
// 数组的反向遍历
ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
{
HashPosition *current = pos ? pos : &
ht->
pInternalPointer;
IS_CONSISTENT(ht);
if (*current) {
*current = (*current)->
pListLast;
return SUCCESS;
}
else
return FAILURE;
}
& emsp； PHP 5 中 hashtable 的数据结构中有三个字段：pInternalPointer 用来记录数组遍历过程中指针指向的当前 Bucket 的地址；pListHead 用来记录保存数组元素写入顺序的双向链表的表头；pListTail 用来记录保存数组元素写入顺序的双向链表的表尾。数组的正向遍历从 pListHead 的位置开始，通过不断更新 pInternalPointer 来实现；反向遍历从 pListTail 开始，通过不断更新 pInternalPointer 来实现。
PHP 7
由于 PHP 7 中数组的元素是按照写入的顺序存储，所以遍历的逻辑相对简单，只是在遍历过程中需要跳过被标记为 IS_UNDEF 的项。
⒌ hash 碰撞
PHP 5
前面在谈论数组元素添加/修改的时候已有提及，每次在数组新增元素时，都会检查并处理 hash 碰撞，即 CONNECT_TO_BUCKET_DLLIST，代码如下
CONNECT_TO_BUCKET_DLLIST(p, ht->
arBuckets[nIndex]);
#define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
(element)->
pNext = (list_head);
\
(element)->
pLast = NULL;
\
if ((element)->
pNext) {
\
(element)->
pNext->
pLast = (element);
\
}
在新增元素时，如果当前 arBuckets 的位置没有其他元素，那么只需要直接写入新增的 Bucket 即可，否则新增的 Bucket 会被写入 hash 碰撞双向链表的表头位置。
PHP 7
前面已经讲过，PHP 7 中的 hashtable 是通过 Bucket 中的 val.u2.next 项来维护 hash 碰撞的单向链表的。所以，在往 hashtable 中添加新的元素时，最后需要先将 nIndex 位置的值写入新增的 Bucket 的 val.u2.next 中。而在删除 Bucket 时，需要同时找出要删除的 Bucket 所在的 hash 碰撞链表中的前一项，以便后续的 hash 碰撞链表的维护。
⒍ 扩容
PHP 5
在数组元素新增/修改的 API 中的最后有一行代码 ZEND_HASH_IF_FULL_DO_RESIZE(ht) 来判断当前 hashtable 是否需要扩容，如果需要则对其进行扩容。
// 判断当前 hashtable 是否需要扩容
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
if ((ht)->
nNumOfElements >
(ht)->
nTableSize) {
\
zend_hash_do_resize(ht);
\
}
// hashtable 扩容（精简部分代码）
ZEND_API int zend_hash_do_resize(HashTable *ht)
{
Bucket **t;
if ((ht->
nTableSize 1) >
0) {
/* Let's double the table size */
t = (Bucket **) perealloc(ht->
arBuckets, (ht->
nTableSize 1) * sizeof(Bucket *), ht->
persistent);
ht->
arBuckets = t;
ht->
nTableSize = (ht->
nTableSize 1);
ht->
nTableMask = ht->
nTableSize - 1;
zend_hash_rehash(ht);
}
}
// 扩容后对 hashtable 中的元素进行 rehash（精简部分代码）
ZEND_API int zend_hash_rehash(HashTable *ht)
{
Bucket *p;
uint nIndex;
if (UNEXPECTED(ht->
nNumOfElements == 0)) {
return SUCCESS;
}
memset(ht->
arBuckets, 0, ht->
nTableSize * sizeof(Bucket *));
for (p = ht->
pListHead;
p != NULL;
p = p->
pListNext) {
nIndex = p->
h &
ht->
nTableMask;
CONNECT_TO_BUCKET_DLLIST(p, ht->
arBuckets[nIndex]);
ht->
arBuckets[nIndex] = p;
}
return SUCCESS;
}
首先，PHP 5 hashtable 扩容的前提条件：数组中元素的数量超过 hashtable 的 nTableSize 的值。之后，hashtable 的 nTableSize 会翻倍，然后重新为 arBuckets 分配内存空间并且更新 nTableMask 的值。最后，由于 nTableMask 发生变化，需要根据数组元素的索引重新计算 nIndex，然后将之前的 Bucket 关联到新分配的 arBuckets 中新的位置。
PHP 7
在 PHP 7 的新增/修改 hashtable 的 API 中也有判断是否需要扩容的代码 ZEND_HASH_IF_FULL_DO_RESIZE(ht)，当满足条件时则会执行扩容操作。
#define HT_SIZE_TO_MASK(nTableSize) \
((uint32_t)(-((nTableSize) + (nTableSize))))
#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_SET_DATA_ADDR(ht, ptr) do {
\
(ht)->
arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->
nTableMask));
\
}
while (0)
#define HT_GET_DATA_ADDR(ht) \
((char*)((ht)->
arData) - HT_HASH_SIZE((ht)->
nTableMask))
// 当 hashtable 的 nNumUsed 大于或等于 nTableSize 时则执行扩容操作
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
if ((ht)->
nNumUsed >
= (ht)->
nTableSize) {
\
zend_hash_do_resize(ht);
\
}
# define HT_HASH_RESET(ht) \
memset(&
HT_HASH(ht, (ht)->
nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->
nTableMask))
#define HT_IS_WITHOUT_HOLES(ht) \
((ht)->
nNumUsed == (ht)->
nNumOfElements)
// 扩容（精简部分代码）
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
if (ht->
nNumUsed >
ht->
nNumOfElements + (ht->
nNumOfElements >
>
5)) {
/* additional term is there to amortize the cost of compaction */
zend_hash_rehash(ht);
}
else if (ht->
nTableSize HT_MAX_SIZE) {
/* Let's double the table size */
void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
uint32_t nSize = ht->
nTableSize + ht->
nTableSize;
Bucket *old_buckets = ht->
arData;
ht->
nTableSize = nSize;
new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) &
IS_ARRAY_PERSISTENT);
ht->
nTableMask = HT_SIZE_TO_MASK(ht->
nTableSize);
HT_SET_DATA_ADDR(ht, new_data);
memcpy(ht->
arData, old_buckets, sizeof(Bucket) * ht->
nNumUsed);
pefree(old_data, GC_FLAGS(ht) &
IS_ARRAY_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));
}
}
// rehash（精简部分代码）
ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
Bucket *p;
uint32_t nIndex, i;
if (UNEXPECTED(ht->
nNumOfElements == 0)) {
if (!(HT_FLAGS(ht) &
HASH_FLAG_UNINITIALIZED)) {
ht->
nNumUsed = 0;
HT_HASH_RESET(ht);
}
return SUCCESS;
}
HT_HASH_RESET(ht);
i = 0;
p = ht->
arData;
if (HT_IS_WITHOUT_HOLES(ht)) {
// Bucket 中没有被标记为 IS_UNDEF 的项
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 {
// Bucket 中有被标记为 IS_UNDEF 的项
uint32_t old_num_used = ht->
nNumUsed;
do {
if (UNEXPECTED(Z_TYPE(p->
val) == IS_UNDEF)) {
// Bucket 中第一项被标记为 IS_UNDEF
uint32_t j = i;
Bucket *q = p;
if (EXPECTED(!HT_HAS_ITERATORS(ht))) {
// hashtable 没有遍历操作
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 {
// hashtable 存在遍历操作
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)) {
do {
zend_hash_iterators_update(ht, iter_pos, j);
iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1);
}
while (iter_pos i);
}
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);
/* Migrate pointer to one past the end of the array to the new one past the end, so that
* newly inserted elements are picked up correctly. */
if (UNEXPECTED(HT_HAS_ITERATORS(ht))) {
_zend_hash_iterators_update(ht, old_num_used, ht->
nNumUsed);
}
}
return SUCCESS;
}
PHP 7 中 hashtable 在扩容时也是将 nTableSize 翻倍，然后进行 rehash。在进行 rehash 操作时，如果 Bucket 中没有标记为删除的项（IS_UNDEF），那么 rehash 操作之后 Bucket 的存储顺序不会发生任何变化，只是 idx 索引存储的位置会因为 nTableMask 的变化而变化，最终导致 hash 碰撞链表的变化。如果 Bucket 中存在被标记为删除的项，那么在 rehash 的过程中会跳过这些 Bucket 项，只保留那些没有被删除的项。同时，由于这样会导致 Bucket 的索引相较于原来发生变化，所以在 rehash 的过程中需要同时更新 hashtable 内部指针的信息以及与遍历操作相关的信息。
⒎ PHP 7 中的 packed hashtable
在 PHP 7 中，如果一个数组为索引数组，并且数组中的索引为升序排列，那么此时由于 hashtable 中 Bucket 按照写入顺序排列，而数组索引也是升序的，所以映射表已经没有必要。PHP 7 针对这种特殊的情况对 hashtable 做了一些优化 packed hashtable。
#define HT_MIN_MASK ((uint32_t) -2)
#define HT_MIN_SIZE 8
#define HT_HASH_RESET_PACKED(ht) do {
\
HT_HASH(ht, -2) = HT_INVALID_IDX;
\
HT_HASH(ht, -1) = HT_INVALID_IDX;
\
}
while (0)
static zend_always_inline void zend_hash_real_init_packed_ex(HashTable *ht)
{
void *data;
if (UNEXPECTED(GC_FLAGS(ht) &
IS_ARRAY_PERSISTENT)) {
data = pemalloc(HT_SIZE_EX(ht->
nTableSize, HT_MIN_MASK), 1);
}
else if (EXPECTED(ht->
nTableSize == HT_MIN_SIZE)) {
data = emalloc(HT_SIZE_EX(HT_MIN_SIZE, HT_MIN_MASK));
}
else {
data = emalloc(HT_SIZE_EX(ht->
nTableSize, HT_MIN_MASK));
}
HT_SET_DATA_ADDR(ht, data);
/* Don't overwrite iterator count. */
ht->
u.v.flags = HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS;
HT_HASH_RESET_PACKED(ht);
}
packed hashtable 在初始化时，nTableMask 的值默认为 -2，同时在 hashtable 的 flags 中会进行相应的标记。如果此时 packed hashtable 中没有任何元素，那么 nTableSize 会设为 0。
static void ZEND_FASTCALL zend_hash_packed_grow(HashTable *ht)
{
HT_ASSERT_RC1(ht);
if (ht->
nTableSize >
= HT_MAX_SIZE) {
zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->
nTableSize * 2, sizeof(Bucket), sizeof(Bucket));
}
ht->
nTableSize += ht->
nTableSize;
HT_SET_DATA_ADDR(ht, perealloc2(HT_GET_DATA_ADDR(ht), HT_SIZE_EX(ht->
nTableSize, HT_MIN_MASK), HT_USED_SIZE(ht), GC_FLAGS(ht) &
IS_ARRAY_PERSISTENT));
}
另外，packed hashtable 在扩容时，只需要将 nTableSize 翻倍，同时由于索引是升序排列的，所以 Bucket 的顺序不需要做任何调整，只需要重新分配内存空间即可。
需要强调的是，packed hashtable 只适用于索引为升序排列的索引数组（索引不一定要连续，中间可以有间隔）。如果索引数组的索引顺序被破坏，或索引中加入了字符串索引，那么此时 packed hashtable 会被转换为普通的 hashtable。
总结
现在大家对于php5和php7中数组实现方式的区别应该都有所了解了，本文对大家学习和了解php5和php7的区别以及数组的实现都有一定的帮助，有需要的朋友可以参考学习。最后，想要了解更多大家可以关注网络其它相关文章。
文本转载自脚本之家
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： php5和php7中数组实现方式有何区别?
本文地址： https://pptw.com/jishu/653358.html