c语言结构体里使用动态数组_PHP 语法六数组使用及内部结构

约定不等于承诺〃 2023-01-10 10:15 93阅读 0赞

## 说明 ##

这里基于 php7.2.5 进行测试，php7 之后内部结构变化应该不是太大，但与 php5.X 有差别。我们今天学习 PHP 中的数组语法，数组在 PHP 中堪称万能结构，什么都能存什么都能放，非常灵活，因为 PHP 没有其他语言的如 map、list 等结构，PHParray 就够了。

们前面说变量的存储结构为 zval, 值呢放在 zend\_value 中，忘了的看这里

### 如何声明 ###

$arr  = [];
    $arr[1] = "hello";
    $arr1 = ['name' => '愤怒的鸟'];

## 如何实现 ##

数组的底层结构为 zend\_array 也叫 HashTable，也就是通过对数组的 key 进行 hash 计算之后能直接获取 value 的地址，时间复杂度为 O (1) 那是很快的。

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; // 已使用的bucket数量，可能包含已删除的元素
        uint32_t          nNumOfElements; // 数组中有效元素的数量
        uint32_t          nTableSize; // 数组的总容量
        uint32_t          nInternalPointer;
        zend_long         nNextFreeElement;// 数值索引的值
        dtor_func_t       pDestructor;
    };
    
    typedef struct _Bucket {
        zval              val; // 元素的值 实际是一个zval
        zend_ulong        h;  /* 数组key 经过hash计算得出的值 */              /* hash value (or numeric index)   */
        zend_string      *key;   /*元素的key*/           /* string key or NULL for numerics */
    } Bucket;

我们知道数组的 key 可以是数字或者字符串，但是 PHP 中的数组是有序的，也就是跟插入顺序是保持一致的，那么是如何做到的。

## 结论： ##

key 在存入 bucket 之前先通过一个中间映射表保存 key 的位置，先对 key 进行 hash 计算然后与数组大小值进行取模运算得出这个 key 在中间表的位置，然后在中间表的位置存储这个 key 在 bucket 中的位置。如图

![0e2c2117b9a14f7affb3edf56c764aff.png][]

这里在 key 是字符串的时候需要进行 hash 计算，如果是数值就直接拿来用就行了。

### 插入元素 ###

这个操作比较明晰了，先计算中间表的位置，再存储到 bucket

add_to_hash:
        // nMumUsed  Bucket的数量 ++
        idx = ht->nNumUsed++;
    // 有效元素的数量 ++
        ht->nNumOfElements++;
        if (ht->nInternalPointer == HT_INVALID_IDX) {
            ht->nInternalPointer = idx;
        }
        zend_hash_iterators_update(ht, HT_INVALID_IDX, idx);
    // arData的内存位置 给当前元素用
        p = ht->arData + idx;
    // 设置bucket的key
        p->key = key;
        if (!ZSTR_IS_INTERNED(key)) {
            zend_string_addref(key);
            ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
            zend_string_hash_val(key);
        }
    // 设置bucket的h值 ，这里其实是zend_string中的h 
        p->h = h = ZSTR_H(key);
    // 设置bucket的val, 
        ZVAL_COPY_VALUE(&p->val, pData);
    // 在bucket中的位置
        nIndex = h | ht->nTableMask;
        Z_NEXT(p->val) = HT_HASH(ht, nIndex);
        HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
    
        return &p->val;

### 查找元素 ###

先自己思考一下我们在获取数组的值 $a \[‘name’\], 是如何获取的，先用 key 计算 hash 值，拿到中间表的位置，再拿到 bucket 的位置，就能取到值了

// 拿到key的hash值
    h = zend_string_hash_val(key);
        arData = ht->arData;
    // 拿到中间表的位置
        nIndex = h | ht->nTableMask;
    // 拿到bucket的位置
        idx = HT_HASH_EX(arData, nIndex);
    // 这里先不看
        while (EXPECTED(idx != HT_INVALID_IDX)) {
            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;
            }
            idx = Z_NEXT(p->val);
        }

hash 冲突

hash 计算不可避免的在数据量大的时候有冲突的几率，一般一个常用方法是拉链法，也就是冲突元素串成链表，当 keyhash 冲突后遍历这个位置的链表，最终拿到匹配的 key, 也就是上面的查找元素中 while 那一段，来看下 PHP hashTable 是如何处理的，我们还是分析上面那一段代码

### 上图 ###

![46ec095c63d4b67303156e0212aebc14.png][]

### 扩容 ###

PHP 数组在初始化时不需要指定容量大小，也就是它是自动扩容的，如何实现呢。

### 结论： ###

如果插入元素时发现容量不够了，如果已删除的元素达到一定比例就重建索引，如果没有达到就会进行原大小 2 倍的扩容，然后复制元素到新数组。

IS_CONSISTENT(ht);
        HT_ASSERT_RC1(ht);
    
    // 是否达到了这个值
        if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */
            zend_hash_rehash(ht);
        } else if (ht->nTableSize < HT_MAX_SIZE) {    /* Let's double the table size */
        // 这里会扩容2倍
            void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
        // 2倍
            uint32_t nSize = ht->nTableSize + ht->nTableSize;
            Bucket *old_buckets = ht->arData;
    // 申请内存
            new_data = pemalloc(HT_SIZE_EX(nSize, -nSize), ht->u.flags & HASH_FLAG_PERSISTENT);
        // 设置一些属性
            ht->nTableSize = nSize;
            ht->nTableMask = -ht->nTableSize;
            HT_SET_DATA_ADDR(ht, new_data);
        // 复制buckets
            memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
        // 删除老bucket
            pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT);
            zend_hash_rehash(ht);
        } else {
            zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
        }

## 总结 ##

PHP 数组底层是 hashTable, 通过一个中间映射表实现顺序性，自动扩容，value 可以任何类型，key 可以是 int 也可以是 string

更多学习内容请访问：

八重樱：腾讯T3-T4标准精品PHP架构师教程目录大全，只要你看完保证薪资上升一个台阶（持续更新）zhuanlan.zhihu.com

![3cd08a9b18af2cdf67c7a9c306f4fcef.png][]

**以上内容希望帮助到大家，**很多PHPer在进阶的时候总会遇到一些问题和瓶颈，业务代码写多了没有方向感，不知道该从那里入手去提升，对此我整理了一些资料，包括但不限于：分布式架构、高可扩展、高性能、高并发、服务器性能调优、TP6，laravel，YII2，Redis，Swoole、Swoft、Kafka、Mysql优化、shell脚本、Docker、微服务、Nginx等多个知识点高级进阶干货需要的可以免费分享给大家**，需要的可以加入**我的官方群点击此处。

[0e2c2117b9a14f7affb3edf56c764aff.png]: /images/20221119/4977b1d3723241cea9d4b2ed59274ea6.png
[46ec095c63d4b67303156e0212aebc14.png]: https://img-blog.csdnimg.cn/img_convert/46ec095c63d4b67303156e0212aebc14.png
[3cd08a9b18af2cdf67c7a9c306f4fcef.png]: https://img-blog.csdnimg.cn/img_convert/3cd08a9b18af2cdf67c7a9c306f4fcef.png