PHP 数组

tracy 发布于2019-07-01 10:50 / 3039人阅读

摘要：以下为数组的基础结构，插入，查找和过程。再存放其，如果根据其下标计算取模得到的中已经有值，那么说明出现了哈希碰撞，这个时候把当前中的值取出来保存到当前，把保存的索引保存在当前，以此类推。

以下为 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，之后再插入元素的时候就从这个位置开始插入，以前的元素直接被覆盖就是了。

云服务器 GPU云服务器 php一维数组转二维数组 php三维数组转一维数组 php二维数组变成一维数组 php二维数组转一维数组

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/29545.html

foreach遍历过程中的奇怪现象（PHP5）

摘要：中基础中的三大坑，遍历，引用机制，数组。今天我们在讲讲中的一些奇怪现象。本文适合有一定基础的。运行流程共用一个结构体开始遍历数组，进行判断，拷贝数组是一个新的结构体，操作的是新的结构体。那么遍历数组时，全程与原数组无关。 PHP中基础中的三大坑，foreach遍历，引用机制&，数组。今天我们在讲讲foreach中的一些奇怪现象。在讲解之前，可以先看看我其他相关的文章，属于同一个大的...

kgbook 2019-07-01 12:15 评论0 收藏0
php数组原理遍历原理揭秘

摘要：数组原理遍历原理揭秘数组原理遍历原理揭秘可见，数组其实已经改变了，但是遍历出来的并没有增加的哪一项。此时，我们也可以输出一下当前指针位置数组原理遍历原理揭秘数组原理遍历原理揭秘数组指针停留在了位置上。 php中的中的数组跟js里面数组是不大一样的。php中数组的下标可以整数也可以是字符串，而且数组中元素的顺序不是由下标决定的，而是由添加元素的顺序。数组基础 $arr1 = array(...

wanghui 2019-06-27 15:35 评论0 收藏0
不要认为学PHP就不需要学C语言

摘要：之所以这样说不要认为学就不需要学语言，是因为一味的只学而没有语言等这些基础语言的支撑，是很难深入理解的很多东西的。之所以这样说不要认为学PHP就不需要学C语言，是因为一味的只学PHP而没有C语言等这些基础语言的支撑，是很难深入理解PHP的很多东西的。这样的例子其实很多，这里我就举这个例子吧：PHP的数组和C语言的数组的区别和联系。学过C语言的朋友当然知道C语言里有数组； PHP里...

KoreyLee 2019-06-27 16:27 评论0 收藏0
PHP： array数组常用API

摘要：语法数组删除数组的最后一项语法数组在数组的最末添加一项语法数组删除数组的首项语法数组在数组的首部添加一项案例分析 1:数组的指针操作：语法：current(数组) 当前指针指向的单元值（默认是第零个）语法 next(数组) 当前指针往下移动一帧语法 prev(数组) 当前指针往前移动一个指针语法 end(array) 将当前指针移动到最后一项语法 ...

Cheriselalala 2019-07-01 12:24 评论0 收藏0
php学习笔记（一）基础部分

摘要：学习至今一年有余，笔记积累挺多的，也挺杂的，写篇文章整理一下吧。基础部分输出文本的基础指令和。函数内部声明的变量拥有作用域，只能在函数内部进行访问。布尔型要指定一个布尔值，使用关键字或。 php学习至今一年有余，笔记积累挺多的，也挺杂的，写篇文章整理一下吧。 php基础部分 showImg(http://segmentfault.com/img/bVcWhR); PHP 输出文本...

wapeyang 2019-06-27 10:51 评论0 收藏0
[译] 理解数组在 PHP 内部的实现（给PHP开发者的PHP源码-第四部分）

摘要：为了防止你错过了之前的文章，以下是链接第一部分给开发者的源码源码结构第二部分理解内部函数的定义第三部分的变量实现所有的东西都是哈希表基本上，里面的所有东西都是哈希表。哈希后的结果可以被作为正常的数组的键值又名为内存块。表示哈希表的容量。文章来自：http://www.hoohack.me/2016/02/15/understanding-phps-internal-array-im...

solocoder 2019-06-27 11:58 评论0 收藏0