问题引入

  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。本文将具体介绍两种数组的实现原理。

谈谈 foreach

  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数组实现形式进行了优化。

PHP7数组实现

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

索引数组（packed_array）

  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数组构造须要适当调整下了。

关联数组（hash_array）

  能够看到，索引跳跃度过高的数组，下面的存储构造就不太适合了；另外，对于关联数组，还有数组的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

  如果咱们通过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);