关于php:PHP每天都在用的数组你足够了解吗

PHP 用的最多的数据类型就是数组了。然而你晓得他的实现原理吗？PHP 数组，相似于咱们 C 语言中学到的索引数组，又相似于咱们学的数据结构哈希表 / 字典；他底层是基于什么数据结构实现的呢？

在解说之前咱们先看这么一个小试验：

<?php

$count = 1000000;

$first = memory_get_usage();
for($i = 0; $i < $count; $i ++) {$packed_array[] = $i;
}
$second = memory_get_usage();
$use1 = $second - $first;
echo "1. memory use: $use1\r\n";


for($i = 0; $i < $count; $i ++) {$hash_array[$count - 1 - $i] = $i;
}
$third = memory_get_usage();
$use2 = $third - $second;
echo "2. memory use: $use2\r\n";

echo "more memory:" . ($use2 - $use1) . "\r\n";

// 试验后果
//1. memory use: 33558608
//2. memory use: 37748848
//more memory: 4190240

两种数组赋值形式，第二个数组占用内存多了 4190240，数组元素数目为 1000000，相当于每个元素多消耗 4 字节。

同样是存储 1000000 个数组元素，两种数组占用内存空间不一样，阐明两种数组的底层实现形式可能也是有差异的。

其实，第一个数组就是咱们所说的索引数组，也称之为 packed array；第二个数组就是咱们所说的关联数组，也称之为 hash array。本文将具体介绍两种数组的实现原理。

PHP 数组的 foreach 遍历，是有序性的；即，遍历的程序和写入的程序是完全一致的。如上面事例所示：

<?php

$arr['a'] = 'a';
$arr['b'] = 'b';
$arr['c'] = 'c';
$arr['d'] = 'd';

foreach ($arr as $val){echo $val;}

思考一下，该个性如何实现呢：1）能够存取 key-val，不就是一个哈希表么，最罕用的就是数组 + 链表实现形式；2）遍历程序与写入程序统一，如同有点难办，如果每个节点再加一个指针呢？依照写入程序再保护一个链表构造呢？如下图所示：

PHP5 就是通过这种形式实现数组 foreach 遍历的有序性。性能是满足了，然而多个指针，就相当于每存储一个元素，就须要额定的 8 字节。PHP7 数组实现形式进行了优化。

PHP 数组能够分为索引数组和关联数组两大类；接下来咱们逐渐剖析两类数组的实现原理：

1）索引数组，即只通过 $array[] = $val 形式复制，这时候数组的索引是主动递增的；数组的 key 也即数组的索引。遍历的有序性呢？依照索引从小到大即可。这和一般数组没有较大区别。

Bucket 构造即为 key-val 实体：

typedef struct _Bucket {
    zval              val;
    zend_ulong        h;                /* hash value (or numeric index)   */
    zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

再扩大思考下，如果咱们这么对数组赋值呢？

$arr[1] =1;
$arr[3] =3;
$arr[5] =5;
$arr[6] =6;

索引不是程序递增，而是跳跃的；这时候还能应用下面的简略存储形式呢？其实也很简略，Bucket 的存储也跟着一起跳跃呗，只是这时候 Bucket 数组中存在一些空洞，这些空洞就有些节约了。

当然，并不是所有的跳跃索引，都能这么存储的，比如说：

$arr[1] =1;
$arr[1000] =1000;

难道说 Bucket 数组的长度至多须要 1001？而外面只存储 2 个元素，其余 999 都是空洞节约？这显然是不适合的。这时候 PHP 数组构造须要适当调整下了。

能够看到，索引跳跃度过高的数组，下面的存储构造就不太适合了；另外，对于关联数组，还有数组的 key，并不等于数组索引，还须要反对依照 key 查找 value 的性能。

这时候你可能会说，应用哈希表呗，那不又回到 PHP5 的实现形式了，额定的指针造成链表。还有没有其余形式呢？比如说参照索引数组的实现，略微改变下？

1）有序性遍历：数组元素还是依照索引数组形式，程序写入；

2）依照 key 查找 value：每一个数组元素的 Bucket 索引是确定的（写入程序决定）；那么能够额定提供数组（长度等于 Bucket 数组长度），存储 key-Bucket 索引的映射关系。key 计算 hash 值，依照 Bucket 数组长度取模计算索引，在该地位存储 Bucket 索引的值；

3）hash 抵触解决：Bucket 的值构造为 zval，而 zval 自身就有一个额定字段
next，通过该字段多个 Bucket 能够造成一个隐式的链表。

struct _zval_struct {
    zend_value        value;            /* value */
    union {
        ……
        uint32_t type_info;
    } u1;
    union {
        uint32_t     next;                 /* hash collision chain */
        ……
    } u2;
};

这样说是不是还有点含糊，请看上面的示意图：

依照 key=a,b,c,d,e,f 程序写入。能够看到，下面的数组存储的是 Bucket 索引值，通过该值能够在 Bucket 数组中找到对应的 key-value 对。另外，key=a/c/e，产生了 hash 抵触，最终存储的是 key= e 对应的 Bucket 索引；通过 e.next 能够查找到 key=c；通过 c.next 能够查找到 key=a。

如果咱们通过 unset 回收数组元素呢？比方：

$arr[0] =0;
$arr[1] =1;
$arr[2] =2;
$arr[3] =3;

unset($arr[1])

unset 之后，Bucket 数组两头存在了一个空洞；显然咱们能够通过平移来从新利用这个空洞（空洞前面元素全副向前平移一个地位）。然而想想，有必要这么做吗？复杂度是不是有点高呀，没有必要为了这么一个空洞地位引入这么高的工夫复杂度吧？

那我要是始终 unset，Bucket 数组中的空洞越来越多，内存空间节约越来越重大，这时候就值得回收利用这些空洞了，就义一点工夫复杂度也是值得的。

上面率领大家学习一下 PHP7 数组的次要实现源码。

PHP7 的数组由构造体_zend_array 示意，定义如下：

typedef struct _zend_array HashTable;

struct _zend_array {
    ……
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
};

nTableMask：掩码，通常等于 -nTableSize；为什么是正数呢？因为存储索引的数组和 Bucket 数组是一起调配的，Bucket 数组从 arData 地址处，向高地址增长；存储索引的数组从 arData 地址处，向低地址增长，相当于存储索引的数组拜访下标都是正数；
arData：Bucket 数组；
nTableSize：Bucket 数组长度；
nNumUsed：Bucket 数组已应用数目（包含元素被 unset 造成的空洞），下一个元素写入的地位默认为 nNumUsed+1；
nNumOfElements：元素数目，不包含 unset 的元素；
nInternalPointer：游标，迭代时应用；
nNextFreeElement：用于生成自增的索引，$array[]=$val 赋值形式应用；

上一节咱们提到 nTableMask 是掩码，且等于 -nTableSize；因为，存储索引的数组和 Bucket 数组是一起调配的，Bucket 数组从 arData 地址处，向高地址增长；存储索引的数组从 arData 地址处，向低地址增长，相当于存储索引的数组拜访下标都是正数。

为了不便形容，咱们将存储索引的数组成为索引数组，存储真正数据内容的成为 Bucket 数组。

PHP 数组的初始化函数为 zend_hash_real_init_ex，实现如下：

static zend_always_inline void zend_hash_real_init_ex(HashTable *ht, int packed)
{(ht)->nTableMask = -(ht)->nTableSize;
    
    //pemalloc 分配内存（索引数组 +Bucket 数组）//HT_SET_DATA_ADDR 将 arData 指向首地址偏移（-nTableMask）* sizeof(uint32_t) 地位
    HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT));
    
    // 索引数组全副初始化为 -1
    HT_HASH_RESET(ht);

}

//arData 指向索引数组与 Bucket 数组临界点
#define HT_SET_DATA_ADDR(ht, ptr) do { \
        (ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); \
    } while (0)
    
// 索引数组大小
#define HT_HASH_SIZE(nTableMask) \
    (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t))

#define HT_HASH_RESET(ht) \
    memset(&HT_HASH(ht, (ht)->nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->nTableMask))
    
#define HT_HASH(ht, idx) \
    HT_HASH_EX((ht)->arData, idx)

PHP 内核代码里有十分多的宏定义，这点须要习惯。能够看到，一次性分配内存空间包含 hash 数组和 Bucket 数组；而 arData 指向的是两个数组的临界点；并且 hash 数组是从高地址到低地址，所以索引只能是正数。

当往数组增加一个元素时，怎么依据掩码计算索引数组索引值呢？其实很简略，就一行代码：nIndex = h | ht->nTableMask；其中 h 为哈希值。

咱们以 nTableSize= 8 为例，nTableMask=-8；内存中二进制掩码（不理解的能够去学习下原码，反码，补码的概念）为：

11111111 11111111 11111111 11111000

任何整数与其进行或运算后，后果正好满足 [nTableMask, -1]：

11111111 11111111 11111111 11111000 //-8
……
11111111 11111111 11111111 11111111 //-1

数组元素的增加或者更新须要留神 packed_array 和 hash_array 的区别，packed_array 并没有后面的索引数组，只有一个 Bucket 数组，且数组元素的键都是整数。

packed_array 更新逻辑由函数_zend_hash_index_add_or_update_i 实现，其实就是存储数据到下一个 Bucket 数组即可。这里不做过多介绍。

hash_array 更新逻辑由函数_zend_hash_add_or_update_i 实现；增加元素之前，首先须要校验数组中是否曾经存在以后 key：

static zend_always_inline Bucket *zend_hash_find_bucket(const HashTable *ht, zend_string *key)
{h = zend_string_hash_val(key);
        arData = ht->arData;
        nIndex = h | ht->nTableMask;
        
        // 从索引数组中获取 Bucket 的下标
        idx = HT_HASH_EX(arData, nIndex);

        // 值不等于 -1，阐明对应 Bucket 存储有数据
        while (EXPECTED(idx != HT_INVALID_IDX)) {
                //Bucket 数组获取元素
                p = HT_HASH_TO_BUCKET_EX(arData, idx);
                if (EXPECTED(p->key == key)) { /* check for the same interned string */
                        return p;
                } else if (EXPECTED(p->h == h) &&
                     EXPECTED(p->key) &&
                     EXPECTED(ZSTR_LEN(p->key) == ZSTR_LEN(key)) &&
                     EXPECTED(memcmp(ZSTR_VAL(p->key), ZSTR_VAL(key), ZSTR_LEN(key)) == 0)) {return p;}

                // 获取下一个 Bucket 索引，zval.u2.next
                idx = Z_NEXT(p->val);
        }
        return NULL;
}

如果查找到 key，则须要更新对应的值；否则新增加 key-value 对；新增加逻辑如下：

idx = ht->nNumUsed++;
ht->nNumOfElements++;

// 间接顺序存储再下一个地位
p = ht->arData + idx;
p->key = key;
p->h = h = ZSTR_H(key);
ZVAL_COPY_VALUE(&p->val, pData);

// 索引数组以后 nIndex 处可能曾经有值
nIndex = h | ht->nTableMask;
// 通过 zval.u2.next 造成链表
Z_NEXT(p->val) = HT_HASH(ht, nIndex);

// 设置索引数组以后 nIndex 处值为 idx 地位
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

关于php:PHP每天都在用的数组你足够了解吗

问题引入

谈谈 foreach

PHP7 数组实现

索引数组（packed_array）

关联数组（hash_array）

unset

源码实现

根本构造

负掩码

增加 / 更新元素

Just My Socks（注册教程内含优惠码）

关于php:PHP每天都在用的数组你足够了解吗

问题引入

谈谈 foreach

PHP7 数组实现

索引数组（packed_array）

关联数组（hash_array）

unset

源码实现

根本构造

负掩码

增加 / 更新元素

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）