PHP数组的内存布局

PHP数组的内存布局

内存布局

它的内存结构,目前的实现方案是分配一块连续的内存区间,用来存储hash元数据和具体数据。
连续的内存,上面部分是存储hash值到值地址的映射,而下面部分就是值的存储区域,如下图(摘自php-src/Zend/zend_types.h):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* HashTable Data Layout
* =====================
*
* +=============================+
* | HT_HASH(ht, ht->nTableMask) |
* | ... |
* | HT_HASH(ht, -1) |
* +-----------------------------+
* ht->arData ---> | Bucket[0] |
* | ... |
* | Bucket[ht->nTableSize-1] |
* +=============================+
*/

新建数组

初始化一块内存,大小为HT_SIZE(ht) = HT_HASH_SIZE(ht) + HT_DATA_SIZE(ht),如果你查看zend_types.h,能看到这三个宏定义:

1
2
3
4
5
6
7
8
#define HT_SIZE(ht) \
(HT_HASH_SIZE(ht) + HT_DATA_SIZE(ht))

#define HT_DATA_SIZE(ht) \
((size_t)(ht)->nTableSize * sizeof(Bucket))

#define HT_HASH_SIZE(ht) \
(((size_t)(uint32_t)-(int32_t)(ht)->nTableMask) * sizeof(uint32_t))

这里要知道nTableMask是什么,从字面意思是掩码,它的类型是uint32_t,值是(uint32_t)(-nTableSize),nTableSize最小为2,那么此时nTableMask为4294967294,表示成二进制,11111111 11111111 11111111 11111110,这个值在之后计算对应hash所在的下标值会用到。
下面就是这块内存最开始的状态,假设数组大小为2,nNumUsed即已有元素为0,则下面是初始状态:

1
2
3
4
5
6
7
8
9
10
11
12
/*
* HashTable Data Layout
* =====================
* ht->nNumUsed = 0
* +=============================+
* 0 | |
* 1 | |
* +-----------------------------+
* ht->arData ---> | |
* | |
* +=============================+
*/

插入key的hash值为12345678的元素E

事实上对于这块内存,我们仅仅是根据arData这个指针去使用,而它是Bucket* 类型,上半部分的类型是uint32_t* ,怎么在不超出上半部分边界的情况下进行索引,这里用到了刚才提到的nTableMask,下标为(int32_t)(HASH | nTableMask),计算出为-2,那么((uint32_t)arData)[-2]所指向的就是下标为0处的内存地址,通过nTableMask保证不会越界。
E元素首先根据nNumUsed找到存储自身的位置,即ht->arData[ht->nNumUsed],并且修改hash元数据部分,*
0**位置的值指向存储区域,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
/*
* HashTable Data Layout
* =====================
* ht->nNumUsed = 1
* +=============================+
* 0 | 0 |
* 1 | |
* +-----------------------------+
* ht->arData ---> | E | next->HT_INVALID_IDX
* | |
* +=============================+
*/

插入key的hash值为12345678的元素F

使用链表法解决冲突。

1
2
3
4
5
6
7
8
9
10
11
12
/*
* HashTable Data Layout
* =====================
* ht->nNumUsed = 2
* +=============================+
* 0 | 1*sizeof(Bucket) |
* 1 | |
* +-----------------------------+
* ht->arData ---> | E | next->HT_INVALID_IDX
* | F | next->0
* +=============================+
*/

哈希拓容,rehash

扩大数组大小,将数据转存到新数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* HashTable Data Layout
* =====================
* ht->nNumUsed = 2
* +=============================+
* 0 | 1*sizeof(Bucket) |
* 1 | |
* 2 | |
* 3 | |
* +-----------------------------+
* ht->arData ---> | E | next->HT_INVALID_IDX
* | F | next->0
* | |
* | |
* +=============================+
*/

Comments

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×