php内核-数据类型之数组-蒲公英云

php内核-数据类型之数组

php数组的底层实现为散列表（HashTable）

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
了解更多：https://zh.wikipedia.org/wiki/哈希表

HashTable的数据结构：

typedef struct _zend_array      zend_array;
typedef struct _zend_array HashTable;
typedef struct _Bucket {
    zval              val;              /* 存储的具体的值 */
    zend_ulong        h;                /* key的hash code */
    zend_string      *key;              /* 存储元素的key */
} Bucket;
struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    _unused,
                zend_uchar    nIteratorsCount,
                zend_uchar    _unused2)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;      /* 用于散列函数映射存储元素在arData数组中的下标 */
    Bucket           *arData;          /* 存储元素数组，每个元素结构统一为Bucket, arData指向第一个Bucket */ 
    uint32_t          nNumUsed;        /* 已用的Bucket个数 */
    uint32_t          nNumOfElements;  /* 数组中实际存储的元素个数*/
    uint32_t          nTableSize;      /* 数组总容量*/
    uint32_t          nInternalPointer;/* 内部指针 */
    zend_long         nNextFreeElement;/* 下一个可用的数值索引，注意是数值索引，即无key时的索引 */
    dtor_func_t       pDestructor;
};

arData：散列表中保存存储元素的数组，内存联系，arData指向数组首地址
nTableSize：数组的总容量，即可以容纳的元素数。它的大小始终是2的幂次方，最小为8，依次为8、16、32、64等等
nTableMask：散列函数根据key的hash code映射元素的存储位置是用到，实际值是nTableSize的相反数，即nTableMask = -nTableSize，位运算表示则为nTableMask = ~nTableSize + 1
nNumUsed & nNumOfElements： nNumUsed是指数组当前使用的Bucket数，但这些Bucket中存储的不一定都是有效的数据，因为当数组删除掉一个元舒适，并不会马上将其从数组中移除，而是先将其标记为IS_UNDEF，只有在数组容量超限扩容时，才会真正的删除。nNumOfElements则是数组中有效元素的数量。
nNextFreeElement：这个是自动确定数值索引使用的，从0开始。一定是数值索引。
pDestructor：当删除或覆盖数组中的某个元素是，如果提供了这个函数句柄，则删除或覆盖后调用次函数，对旧元素进行清理。
u：这个结构主要用于一些辅助作用。