php底层原理之数组实现

HackerShell 发布于2019-07-01 12:38 / 3472人阅读

摘要：数组是最常用的数据类型，同时容易上手也得益于其强大的数组，但是数组在中是如何实现的呢首先，我们还是先了解下相关的数据结构，为下面的内容打好基础哈希表哈希表，顾名思义，即将不同的关键字映射到不同单元的一种数据结构。

数组是PHPer最常用的数据类型，同时php容易上手也得益于其强大的数组，但是数组在php中是如何实现的呢？

首先，我们还是先了解下相关的数据结构，为下面的内容打好基础

哈希表

哈希表，顾名思义，即将不同的关键字映射到不同单元的一种数据结构。而将不同关键字映射到不同单元的方法就叫做哈希函数

理想情况下，经过哈希函数处理，关键字和单元是会进行一一对应的；但是如果关键字值足够多的情况下，就容易出现多个关键字映射到同一单元的情况，即出现哈希冲突

哈希冲突的解决方案，要么使用链接法，要么使用开放寻址法

链接法
即当不同的关键字映射到同一单元时，在同一单元内使用链表来保存这些关键字

开放寻址法
即当插入数据时，如果发现关键字被映射到的单元存在数据了，说明发生了冲突，就继续寻找下一个单元，直到找到可用单元为止

而因为开放寻址法方案属于占用其他关键字映射单元的位置，所以后续的关键字更容易出现哈希冲突，因此容易出现性能下降

链表

既然上面提到了链表，这里我们简单聊一下链表的基础知识。链表分为很多种类型，常用的数据结构包括：队列，栈，双向链表等

链表，就是由不同的链表节点组成的一种数据结构。链表节点一般由元素+指向下一节点的指针组成。而双向链表，顾名思义，则是由指向上一节点的指针+元素+指向下一节点的指针组成

对于数据结构的内容，我们不过多展开，我们之后会有专门的内容去详细介绍数据结构

php数组

php解决哈希冲突的方式是使用了链接法，所以php数组是由哈希表+链表实现，准确来说，是由哈希表+双向链表实现

内部结构-哈希表

HashTable结构体主要用来存放哈希表的基本信息

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，即哈希表的容量，最小为8，以2x增长。
    uint nTableMask;        // nTableSize-1 ， 索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值 
    ulong nNextFreeElement; // 下一个可使用的数字键值
    Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
    Bucket *pListHead;          // 存储整个哈希表的头元素指针
    Bucket *pListTail;          // 存储整个哈希表的尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;    // 在删除元素时执行的回调函数，用于资源的释放
    zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

Bucket结构体则用于保存数据的具体内容

typedef struct bucket {
    ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值
    uint nKeyLength;    // hash关键字的长度，如果数组索引为数字，此值为0
    void *pData;        // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
    void *pDataPtr;     // 如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
    struct bucket *pListNext;   // 指向整个哈希表的该单元的下一个元素
    struct bucket *pListLast;   // 指向整个哈希表的该单元的上一个元素
    struct bucket *pNext;       // 指向由于哈希冲突导致存放在同一个单元的链表中的下一个元素
    struct bucket *pLast;       // 指向由于哈希冲突导致存放在同一个单元的链表中的上一个元素
    // 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
    char arKey[1];              
} Bucket;

其中Bucket结构体内有指向用户数据的pData元素，其实是指向了之前我们介绍的变量zval结构体，这也是为什么当创建数组时，会出现数组元素+1的变量容器。不了解变量底层相关知识的，请查看我之前的文章：

php底层原理之变量（一）
php底层原理之变量（二）

哈希表内部结构关系图

注：图片来源于网络

从上图我们可以看出，Bucket在存放数据的时候，如果存在哈希冲突，则将多个关键字映射到链表中，由此组成了双向链表

总结

今天，我们以数组作为切入点，简单了解了下基本的数据结构：哈希表和链表；并且了解了数组的底层实现，即哈希表+双向链表。其实哈希表作为php中最重要的数据结构，用处很广。变量的符号表，函数列表等都是用哈希表来存储的，感兴趣的同学可以看我之前的文章来了解相关知识

GPU云服务器云服务器 php的数组底层实现 php数组的原理 ECS底层原理 php 数组实现if

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

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

php底层原理之变量（一）

摘要：对于来说，变量有全局变量和局部变量之分那么，他们都是存储到一个哈希表内了么其实不是的，变量存储也有作用域的概念。上次跟大家讲了垃圾回收机制后，有些小伙伴对底层原理比较感兴趣，私信问我了一些关于变量的相关知识，既然大家对变量比较感兴趣，那么这次我们来系统的讲一下变量的底层原理变量结构首先，我们还是先摆上我们的zval结构体，即php所有变量都会以zval结构体的形式实现 struc...

curlyCheng 2019-07-01 12:35 评论0 收藏0
php底层原理之垃圾回收机制

摘要：总结垃圾回收机制以的引用计数机制为基础以前只有该机制同时使用根缓冲区机制，当发现有存在循环引用的时，就会把其投入到根缓冲区，当根缓冲区达到配置文件中的指定数量后，就会进行垃圾回收，以此解决循环引用导致的内存泄漏问题开始引入该机制 php垃圾回收机制，对于PHPer来说是一个不陌生但是又不是很熟悉的内容。那么php是怎么实现对不需要的内存进行回收的呢？ php变量的内部存储结构首先还是...

light 2019-07-01 12:32 评论0 收藏0
PHP小知识点

摘要：那些琐碎的知识点作者记录的的很奇特很难记的知识点。易错知识点整理注意和的区别中和都是输出的作用，但是两者之间还是有细微的差别。今天手头不忙，总结一下，分享过程中掌握的知识点。深入理解 PHP 之：Nginx 与 FPM 的工作机制这篇文章从 Nginx 与 FPM 的工作机制出发，探讨配置背后的原理，让我们真正理解 Nginx 与 PHP 是如何协同工作的。 PHP 那些琐碎的知识...

hover_lew 2019-06-28 14:35 评论0 收藏0
php底层原理之变量（二）

摘要：但是对于结构体中的和字段我们一直都没有详细介绍过，而这两个字段其实是和变量之间赋值的原理有着密切的关系的。上周我们从底层的角度介绍了php变量从生成->常量赋值->销毁的完整生命周期（不了解的同学可以翻看一下前面的文章php底层原理之变量（一）），但是我们留了一个思考，不知道大家有答案了没，变量之间的赋值在底层又是如何实现的呢？变量之间赋值 php变量的zval结构，我们已经介绍了...

bladefury 2019-07-01 12:36 评论0 收藏0
foreach遍历过程中的奇怪现象（PHP5）

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

kgbook 2019-07-01 12:15 评论0 收藏0