PHP数组的内存布局
Posted Updated programming4 minutes read (About 596 words)

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
 *                 |                             |
 *                 |                             |
 *                 +=============================+
 */
#

Like this article? Support the author with

Comments

Your browser is out-of-date!

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

×

×