PHP7之数组

前言

本文主要简单介绍一下PHP7数组的数据结构哈希表，阅读本文前，您需要掌握基础的C/C++的知识以及对哈希表的定义有简单的了解。

概念

哈希表是根据键(Key)而直接访问在内存存储位置的数据结构，就像数组的索引的一样。我们可以先想象一下这个数据结构：

首先需要一个字段来存储具体的数据。
其次需要根据key可以直接访问到这个具体的值，可想而知能够直接访问内存的无外乎内存地址了，那我们要做的就是key和内存地址的映射。内存地址的的访问分两种，一种是开始地址+偏移量得到目标数据的地址，还有一种就是直接得到目标数据的地址。后者从理论上是不可行的，前者很方便，但是只在连续的内存空间内可行。
开始地址是不变的，我们要做的是key和偏移量之间的映射，这样就可以访问到不同内存地址，他们之间可以用hash算法实现
虽然我们会选择更唯一，更均匀的hash算法，但还是会存在冲突，所以我们还需要一个解决冲突的方法

如果满足了上面4条，一个哈希表基本就实现了。

PHP中的HashTable

先贴上php源码中哈希表的数据结构

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; //nTableSize的负值
    Bucket           *arData; //存取具体值的桶
    uint32_t          nNumUsed; //已经使用的Bucket数量
    uint32_t          nNumOfElements; //有具体值的Bucket数量
    uint32_t          nTableSize; //总的Bucket数量
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

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

其中重要的字段后面我都加了注释。接下来，我们根据上面说的4条，来分析一下这个结构体：

存取数据的字段就是Bucket，zval是php的核心，是所有数据类型的抽象表示，类似于go里面的interface，h是key的hash值。
在php中，索引数组["a", "b"]和关联数组["a" => "b"]都是用这个结构来实现的，索引数组可以直接用索引当做是偏移量；关联数组的key是字符串，偏移量的算法可以用h % nTableSize取模，按照这样我们大概可以画出一个内存结构图：

1.jpg

如果h % nTableSize的模为2，则我们就把数据存储到下标为2的bucket上

哈希冲突。当多个key的hash值对nTableSize的模相等时，就出现了冲突，两个数据就落在了同一个bucket里面。解决的方法也很多，链表法最常用，也最简单，就是把冲突的元素用一个单向链表串联起来，看图：

2.jpg

当我们根据key去查找元素的时候，从定位的bucket开始，沿着单向链表一直匹配，如果key和某个bucket的key相等，我们认为这就是我们想要的数据。至于链表的长度，就要看哈希函数的唯一性了。

我们知道，php中不管是索引数组还是关联数组都是插入有序的，也就是说先插入的肯定先遍历出来，索引数组当然没有问题，但是关联数组很可能不是我们想要的结果，从上面的内存图中，如果我们从开始地址遍历这个数组，我们得到的结果很可能是无序的，因为第一个元素key对应bucket很可能不在索引为0的bucket，解决的方法就是按插入的顺序用一个可以顺序访问结构存起来，比如redis的有序集合用的就是跳跃表(skiptable)。php做法也是类似，但是稍有不同，它用后面的bucket内存来充当顺序结构，再用一块内存也就是前面的idx来做地址映射，idx的最小索引为nTableMask, 如下：

3.jpg

遍历的时候只要按顺序遍历bucket就行了。随机访问，比如关联数组的key经过hash运算之后的值-3，则先找到索引为-3的idx,再通过idx找到对应的bucket。

首先要给大家普及两个c语言的知识：

任何数据在内存里面都是没有数据类型之分的，都是按字节存储
如果你的p指针指向数组中的任意一个元素，则p[1]是访问当前元素的下一个元素，p[-1]就是前一个元素

有人可能会问了，那bucket充当顺序结构，那冲突链去哪了呢？在idx上？其实，PHP并没有用一个活生生的链表去解决冲突。先来看下PHP的核心zval这个结构体：

struct _zval_struct {
    zend_value        value;            /* value */
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    type,         /* active type */
                zend_uchar    type_flags,
                zend_uchar    const_flags,
                zend_uchar    reserved)     /* call info for EX(This) */
        } v;
        uint32_t type_info;
    } u1;
    union {
        uint32_t     next;                 /* hash collision chain */
        uint32_t     cache_slot;           /* literal cache slot */
        uint32_t     lineno;               /* line number (for ast nodes) */
        uint32_t     num_args;             /* arguments number for EX(This) */
        uint32_t     fe_pos;               /* foreach position */
        uint32_t     fe_iter_idx;          /* foreach iterator index */
        uint32_t     access_flags;         /* class constant access flags */
        uint32_t     property_guard;       /* single property guard */
        uint32_t     extra;                /* not further specified */
    } u2;
};

u2联合体里面的next字段就是用来解决hash冲突的，这个字段存储的并不是下一个冲突元素地址，而是下一个冲突元素距离bucket开始地址的字节偏移量，然后把首个元素的字节偏移量存储到对应的idx里面。如下图：

4.jpg

也就是说我们每次新增元素的时候都是先把next指向原来idx存放的字节偏移量，然后用新元素的字节偏移量去覆盖idx.

需要注意的是：

idx和bucket是一整块连续内存，并不是单独的内存块，不同的是idx用的是unsign int类型来访问，后面的则用bucket类型来访问。
idx的索引是负数，那如何对负数取模呢？对负数取模运算结果是正的，不符合我们的要求，但是要保证idx在[nTableMask, -1]区间内，php用的不是取模运算，而是h | nTabeMask, 至于为什么这里就不详细说了，你们多举几个例子就明白了。

到这为止php中哈希表的模型已经解释完了，下一篇我们跟着源码去更详细的看下哈希表的新增，删除，查找，扩容以及一些标志位的作用来进一步了解哈希表，然后分析一下在什么情况下会出现一些性能问题。