关于后端:PHP7内核实现原理数组的实现

PHP 的数组是基于 HashTable 实现的，并且在其上减少了程序拜访的个性。这里分 PHP 5 和 PHP 7 两个版本看数组的演进。

PHP 5.6.31 源码：https://github.com/php/php-src/blob/php-5.6.31/Zend/zend_hash.h#L67

PHP 7.2.1 源码：https://github.com/php/php-src/blob/php-7.2.1/Zend/zend_types.h#L234

PHP 中的数组有两个最突出的特点，也即 PHP 数组满足两个语义：

PHP 数组是一个字典，反对 key value 拜访，key 反对整型或字符串。
PHP 数组是有序的，即遍历数组时会依照增加程序遍历，不像传统意义上的字典是无序的。

一个传统的 HashTable 大抵构造如下：

首先一个 key 通过哈希函数计算，得出属于哪个 slot。key 值和 value 值应用 bucket 构造体保留，放在对应的 slot 下。如果不同 key 通过哈希计算后失去雷同 slot 值，即产生哈希抵触时，应用链表法接在 slot 的 bucket 链前面。这里提一句有的语言解决哈希抵触会应用红黑树。

PHP 中的 HashTable 在此基础上做了一些调整，减少了一个哈希函数，以及这个新增哈希函数对应的哈希值 h：

其中 key 通过 hash1 函数失去 h 值，h 值是一个无符号整型（ulong），之后 h 值再通过 hash2 函数计算失去 slot，调配时与之前一样。另外 bucket 中也减少了对 h 值的保留。

为什么的要减少这个 h 值，作用是什么？

PHP 要反对数字和字符串两种 key，当应用字符串 key 时，h 值就是其对应的数字值。而 应用数字 key 时，h 间接就等于这个 key 值。相当于将数字和字符串两种 key 归一为数字类型，对立放到 h 字段中。
在比拟两个字符串 key 的 value 是否相等时，能够先通过判断对应的 h 值是否相等，且绝大部分状况下，字符串哈希抵触的概率也比拟小，所以如果不相等间接返回，放慢判断的速度。

先看源码：

https://github.com/php/php-src/blob/php-5.6.31/Zend/zend_hash.h#L67

PHP 5 的 bucket：

bucket 代码：

struct _hashtable;

typedef struct bucket {
    ulong h; /* Used for numeric indexing */
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    const char *arKey;
} Bucket;

bucket 图示：

各字段含意：

h：就是后面提到的 h 值
arKey：是以后 bucket 的 key 值
pListLast、pListNext、pLast、pNext：四个指针
nKeyLength：是 arKey 的长度，当这个值为 0 时，示意以后 key 是数字类型。
pDataPtr 和 pData：指向具体的 value。这里有个优化，如果 value 的大小等于一个指针，则将 value 间接存储在 pDataPtr 上，缩小内存占用

bucket 中为什么有 4 个指针？

因为要满足数组有序的语义，PHP 5 应用 pListNext 和 pListLast 别离示意 全局链表 上的下一个节点和上一个节点。在前面 HashTable 的实现中别离也有两个指针，指向全局链表的头部和尾部，实现正序和倒序拜访。

而 pNext 和 pLast 别离示意产生哈希抵触时的 部分链表。

PHP 5 的 HashTable 的构造：

HashTable 源码：

typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;    /* Used for element traversal */
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

arBuckets：是一个指针，指向一段间断的数组内存，数组中每个元素指向一个 slot。通过这个指针就能够找到所有 slot 及 slot 下的 bucket。即 slot 的数组。
nTableSize：是 arBuckets 所指向的数组的大小，即 slot 的数量。取值始终是 2 的 n 次方。最小值 8，最大 2 的 31 次方。这个值的意义在于，当 bucket 的数量大于这个值时，示意曾经呈现了哈希抵触，当抵触重大时 PHP 会发动 rehash，从新平衡 slot 的散布。
nTableMask：掩码。始终等于 nTableSize – 1，所以他的每一位都是 1。HashTable 要通过两层 hash 函数，第二个 hash 函数就是 slot = h & nTableMask 以此来计算出 slot。相当于 取余操作。这里在 PHP 7 中会发生变化。
nNumOfElements：bucket 元素的个数。
pListHead 和 pListTail：为实现 HashTable 有序而保护的双向链表。这两个指针别离指向第一个 bucket 和最初一个 bucket。
pInternalPointer：指向 以后元素的指针，foreach 遍历时就是应用这个指针遍历的，这也是为什么 PHP 5 中 foreach 遍历数组比用索引遍历快的起因。

bucket 和 HashTable 联动图示：

按程序插入四个 key a、b、c、d，假如 a 被映射到了 slot1，而 b、c、d 被映射到了 slot0 中：

其中 HashTable 上的 pListHead 作为全局链表头指向了第一个 bucket a，pListTail 作为全局链表尾指向最初一个 bucket d。通过 pListHead 和 pListTail 就可实现数组的正序和倒序遍历。

可见 PHP 的数组有序指的是插入的程序，例如鸟哥的博客也讲到这一点，提了一个问题：

https://www.laruence.com/2009/08/23/1065.html

$arr['laruence'] = 'huixinchen';
$arr['yahoo']    = 2007;
$arr['baidu']    = 2008;
foreach ($arr as $key => $val) {// 后果是什么?}

$arr[2] = 'huixinchen';
$arr[1]  = 2007;
$arr[0]  = 2008;
foreach ($arr as $key => $val) {// 当初后果又是什么?}

答案是一样的，即插入的程序。

PHP 5 数组的有余

整体来说，有两处能够优化：

应用的字段是比拟多的，而且每个 bucket 都要有四个指针，占用空间大。
其次 bucket 的调配地位是随机的，不间断的，导致无奈利用到 CPU 的局部性原理，无奈利用 cache。

PHP 7 次要针对下面提到的两个不足之处做了改良。首先精简了字段，且不再应用指针保护节点间的程序，改为了间断内存。这样既缩小了空间占用，又应用程序读写利用了 CPU 的局部性原理，进步了数据读取速度。

PHP 7 数组的源码：https://github.com/php/php-src/blob/php-7.2.1/Zend/zend_types.h#L234

bucket 构造：

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

首先因为不再应用指针保护程序，bucket 的构造精简了很多。

val：指向具体的变量，zval 构造体
h：跟以前一样的 h 值，无符号数字类型
key：字符串 key，不再应用 char *，而是间接用了 zend_string 构造体

之后 bucket 引入了状态的概念，分为：未应用、无效、有效。无效和有效 bucket 始终排列在未应用 bucket 后面：

状态机：

HashTable 构造：

typedef struct _zend_array HashTable;

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    consistency)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

图示：

各字段含意：

gc：援用计数
arData：一块间断的内存空间，寄存 bucket 数组。
nTableSize：arData 指向的 bucket 数组的大小，即所有 bucket 的数量。该字段取值始终是 2 的 n 次方，最小值是 8
nNumUsed：指所有 已应用 bucket 的数量，包含无效 bucket 和有效 bucket。
nNumOfElements：无效 bucket 的数量。该值总是小于或等于 nNumUsed。
nTableSize、nNumUsed、nNumOfElements 三者的关系：
nTableMask：掩码。个别为 -nTableSize。
nInternalPointer：游标指针，因为当初 bucket 都是间断存储的，所以不再应用指针而改用无符号整数存储索引值即可。
nNextFreeElement：下一个天然索引值，默认是 0。即如果应用 $arr[] = 1 的形式插入元素，相当于插入到索引 0 的地位。

基于以上前提，如何实现 key 对应到 slot 再到 bucket 链表呢？

这里就谈到为什么 nTableMask 是负值的起因了。实际上在调配 bucket 数组内存的时候，即 arData，在这个数组最后面额定多申请了一些内存，这段内存的作用是充当索引，也叫索引表或 arHash。索引表外面的每个元素代表一个 slot，其值为其下第一个 bucket 在 arData 中的下标。如果以后 slot 没有任何 bucket 元素，那么其值为 -1。到此就实现了 key 到 slot 再到 bucket 的映射。

从而 PHP 7 中的第二个哈希函数，即应用 h 值获得 slot 值，变成了：slot = h | nTableMask。

如，当 nTableSize=8，则 nTableMask=-8，二进制即：11111111111111111111111111111000。那么任何数与之做或运算，只能是 000 – 111 这 8 种值，即 -1 到 -8，这 8 个 slot 在别离存一个具体的 bucket 索引值。就实现了 key → h → slot → bucket 的查找了。

对于 -8 的二进制示意，须要回顾下计算机组成原理二进制示意：

正数 = 其正值的补码 -8 正值就是 8

8 的原码示意为 00001000

8 的反码示意为 11110111，即按位取反

8 的补码示意为 11111000，即反码 + 1

这样一来扩大到 32 位时就可知 -8 的二进制为 11111111111111111111111111111000

参考：https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/compute…

PHP 7 数组几种初始化过程：

packed array 和 hash array

留神后面提到 nTableMask = – nTableSize，但这个不相对，当数组是 packed array 类型时其实是用不到索引表的，所以个别初始化数组时，在未确定数组类型时，nTableSize 个别只调配 2 个。

初始化数组时，数组的内存调配状态：

什么是 packed array 和 hash array

$a = array(1,2,3); // packed array
$b = array('a' => 1, 'b' => 2, 'c' => 3); // hash array

当 HashTable 的 u.v.flags 的 HASH_FLAG_PACKED 位 > 0 时示意 packed array，否则是 hash array。

packed array 具备以下束缚和个性。

key 全是数字类型的。
key 按插入顺序排列，依然是递增的。
每一个 key-value 对的存储地位都是确定的，都存储在 bucket 数组的第 key 个元素上。
packed array 不须要索引数组。

packed array 不须要索引表，间接用 key 作为 arData 的索引，节俭了后面一段索引表的空间。

packed array 示意图：

hash array 示意图：

如：

其中最初一个非凡，也是数字 key，也是递增，为什么不是 packed array？因为用 1 和 8 做索引，数组太过于稠密，利用率不高，在工夫效率和空间效率的均衡下，应用了 hash array。

来自鸟哥博客的一段代码，这段代码展现了从 packed array 切换到 hash array 的内存占用状况：

echo "Packed array:\n";
$begin = memory_get_usage();
$array = range(0, 10000);
echo "Memory:", memory_get_usage() - $begin, "bytes\n";
$begin = memory_get_usage();

// 这里新增一个元素
$array[10001] = 1;
// 内存简直无变动
echo "Memory Increased:", memory_get_usage() - $begin, "bytes\n";
 
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {$array[$i];
}
echo "Time:", (microtime(true) - $start) * 1000 , "ms\n";
 
unset($array);
 
echo "\nMixed array:\n";
$begin = memory_get_usage();
$array = range(0, 10000);
echo "Memory:", memory_get_usage() - $begin, "bytes\n";
$begin = memory_get_usage();

// 这里插入一个字符串 key，使数组变成了 hash array
$array["foo"] = 1;
// 内存占用变动显著
echo "Memory Increased:", memory_get_usage() - $begin, "bytes\n";
 
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {$array[$i];
}
echo "Time:", (microtime(true) - $start) * 1000 ,"ms\n";

打印后果：

Packed array:
Memory: 528440 bytes
Memory Increased: 0 bytes
Time: 0.19598007202148 ms

Mixed array:
Memory: 528440 bytes
Memory Increased: 126976 bytes
Time: 0.18215179443359 ms

鸟哥代码地址：https://www.laruence.com/2020/02/25/3182.html

packed array 转换成 hash array

从 packed array 到 hash array 转换须要调用 zend_hash_packed_to_hash 函数。首先将 u.flags 中设置标记位 HASH_FLAG_PACKED，之后新生成一个 arData，再调用 memcpy 拷贝过来，最初开释掉老的 arData。

PHP 7 数组的 CRUD

根本步骤：

先查找 key 存不存在
插入时分为字符串 key 插入，数字 key 插入，nextIndex 插入

如何解决哈希抵触

发生冲突时，把新的元素放在 nextFreeIndex 处，而后新 zval 的 next 指针指向老元素在 arData 中的索引，之后在 arHash 索引表中，指向新元素的地位。即索引表永远指向新元素，新元素的 next 再指向老元素，串起来。

扩容 resize 和重建索引 rehash

扩容 resize 看书：zend_hash_do_resize

重建索引 rehash 函数：zend_hash_rehash，因为扩容导致数组容量变动，须要重新分配索引

在插入元素时判断是否要 resize 和 rehash，根本步骤是：

判断数组空间是否够用
不够用时，看是不是有效 bucket 太多
- 太多就真删除一波，之后 rehash
- 不是很多，阐明真的没中央了，那就先扩容 resize，再真删除，再 rehash

精简了 bucket 的字段
应用 bucket.zval.u2.next 取代旧的部分抵触链表
将 bucket 存储在间断的 arData 数组中，勾销了全局链表。并且因为内存间断，利用局部性原理，进步读取性能。
packed array 节俭了索引表 arHash 的空间。

本文由 mdnice 多平台公布

关于后端:PHP7内核实现原理数组的实现

PHP 数组特点

传统 HashTable

PHP 中的 HashTable

PHP 5 的数组实现

PHP 7 的数组实现

比拟 PHP 5 和 PHP 7 的数组实现：