争怎路由网/网站教程/内容

php数组的基础结构介绍

网站教程2024-04-05 阅读
网页的本质就是超级文本标记语言,通过结合使用其他的Web技术(如:脚本语言、公共网关接口、组件等),可以创造出功能强大的网页。因而,超级文本标记语言是万维网(Web)编程的基础,也就是说万维网是建立在超文本基础之上的。超级文本标记语言之所以称为超文本标记语言,是因为文本中包含了所谓“超级链接”点。
本篇文章给大家带来的内容是关于组的基础结构介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

以下为 PHP 数组的基础结构,插入,查找和 rehash 过程。

基础结构:

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的负值(nTableMask = -nTableSize)
    Bucket            *arData;     // 存储元素数组,指向第一个Bucket
    uint32_t          nNumUsed;   // 已用Bucket数
    uint32_t          nNumOfElements; // 哈希表有效元素数 = nNumUsed - num(is_undef)
    uint32_t          nTableSize;   // 哈希表总大小,为2的n次方, 最小为8
    uint32_t          nInternalPointer;  // 怀疑是内部指针
    zend_long         nNextFreeElement; // 下一个可用的数值索引 arr[] = 1;arr["a"] = 2;arr[] = 3;  则nNextFreeElement = 2;
    dtor_func_t       pDestructor;
};

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

说明:

数组存放的时候先按照顺序保存 value,再保存 value 的位置。

存放记录的数组称做散列表,这个数组用来存储 value,而 value 按顺序保存,其存储位置会保存在由 key 计算 hash 取模 nTableMask 得到的 idx 中。

数组初始化的时候最小大小为 8,以此为16,32,64。。。

数组初始化的时候边做的 idx 区会全部初始化为 -1,rehash 的时候也会初始化为 -1。

数组中删除一个元素的时候,是把该删除的元素的 type 标记为 is_undef, 并且 nNumOfEmelment - 1,如果该元素为最后一个元素,那么 nNumUsed - 1。

插入:

以 $arr = ['a'=>1, 'b'=>2] 为例:

首先把 1 放到数组中,其 val.u2.next = -1, 根据其下标 a 计算 hash, 然后 hash 取模 nTableMask 得到一个 idx, 在该 idx 的位置保存前边保存 1 的索引 nindex。

再存放 2, 其 val.u2.next = -1, 如果根据其下标 b 计算hash 取模 nTableMask 得到的 idx 中已经有值,那么说明出现了哈希碰撞,这个时候把当前 idx 中的值取出来保存到当前 val.u2.next,把保存 2 的索引 nindex 保存在当前 idx,以此类推。

查找:

根据下标 a 计算 hash 取模 nTableMask 得到一个 idx ,拿到该 idx 中的值 nindex 去 arData 中查找,如果找到的位置中的 key != a, 那么找不到;如果找到的位置中的 key == a,那么检查其 u2.next, 如果为 -1, 那么找到了;如果不为-1,说明插入的过程中出现了哈希冲突,那么根据 u2.next 继续在 arData 中查找,直到找到为止。

rehash:

rehash 的时候,首先把 nindex 区的所有记录全部重置为 -1,然后从第一个元素开始挪动指针 *p,如果元素没有被标记为 is_undef,那么重新计算该元素的 key hash 并放到 nindex,然后循环, p++。如果元素被标记为 is_undef, 那么继续挪动指针 p++,并设置一个新的指针 j 指向该位置,继续循环,把后边不为 is_undef 的元素一个一个挪到前边来,p 每次移动,j 遇到 is_undef 就不移动,直到被赋值。一直挪动到最后的 nNunUsed ,那么把 j 赋值给 nNunUsed,之后再插入元素的时候就从这个位置开始插入,以前的元素直接被覆盖就是了。

以上就是php数组的基础结构介绍的详细内容,更多请关注php中文网其它相关文章!

  • 微信

  • 网站建设是一个广义的术语,涵盖了许多不同的技能和学科中所使用的生产和维护的网站。



    ……

    标签:php数组的基础结构介绍
    相关阅读