侯体宗的博客 PHP数组的底层实现原理浅析

石可破,丹可磨
  • 首页
  • laravel8仿版
  • beego仿版
  • go_聊天
  • 人生
  • 技术
  • php
  • 架构
  • 数据库
  • 更多
    • 文件下载
    • 匿名群聊
    • 群聊(进来吹会!)
    • 留言
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册
    • 设置栏目
    • 更多设置
    • 分割线

PHP数组的底层实现原理浅析

php  /  管理员 发布于 2021-03-02 16:48:20   92

PHP数组的底层实现原理是:

1、哈希表,将不同的关键字映射到不同单元的一种数据结构;

2、链表,就是由不同的链表节点组成的一种数据结构;

3、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;


上一条:php7垃圾回收变量的GC机制详解

下一条:PHP程序员2021年最新面试题集-持续更新中...

昵称:

邮箱:

0条评论
最新最热
  • 分类目录
  • 人生 (119)
  • 技术 (49)
  • linux (25)
  • blog从零开始 (9)
  • php (48)
  • 架构 (15)
  • 前端 (22)
  • TP(3/5) (14)
  • 数据库 (29)
  • 微信 (2)
  • Laravel (58)
  • Redis (3)
  • Docker (2)
  • Go (8)
  • swoole (7)
  • 相关文章
  • PHP程序员2021年最新面试题集-持续更新中...(0个评论)
  • PHP数组的底层实现原理浅析(0个评论)
  • php7垃圾回收变量的GC机制详解(0个评论)
  • php基础知识switch结构详解,及刚在论坛上看到的一道面试题做分析(0个评论)
  • lnmp1.6正式版一键安装包php5+升级到php7+操作流程步骤及升级报错处理(0个评论)
  • 近期文章
  • 国内用什么翻墙使用谷歌?上外网神器佛跳墙VPN(永久免费)使用流程步骤(0个评论)
  • 在Linux系统中Shell编程的基本语法详解(0个评论)
  • Linux系统中常用的、基本的操作命令使用说明详解(0个评论)
  • Hyperf2.1框架基于session的登录注册退出等个人中心功能的开发流程步骤(0个评论)
  • 下单减库存与付款减库存的三种扣减库存方案优缺点及其使用场景探讨(0个评论)
  • Hyperf2.1启动报错:failed to listen server port[0.0.0.0:9501], Error: Address already(0个评论)
  • 国内用什么翻墙使用谷歌?上外网神器集装箱chrome扩展插件详解(0个评论)
  • 如何才能使一个良好的结构在Laravel框架项目中呢?介绍一下HMVC模式跟nwidart/laravel modules这个包(0个评论)
  • Hyperf2.1框架中验证器的使用流程步骤(0个评论)
  • Hyperf2.1版本自定义函数的编写流程步骤及使用(0个评论)
  • 近期评论
  • 博主 在

    nginx中500,501,502,503,504,505状态码的详解及出现的原因/区别中评论 有错误可以指正吧 没必要搞人心态 老铁 信不信我删库跑路..
  • 博主 在

    国内用什么翻墙使用谷歌?上外网神器Ghelper插件详解中评论 @白马  最近是很不稳定,后面我会找找其它更稳定的方式,发表一篇博文..
  • 白马 在

    国内用什么翻墙使用谷歌?上外网神器Ghelper插件详解中评论 显示:暂停注册。。这注册不了啊,该怎么办呢?..
  • 博主 在

    国内用什么翻墙使用谷歌?上外网神器Ghelper插件详解中评论 @请教  小图标没有出现 重复检查步骤5,进去看看右下角是否开启..
  • 请教 在

    国内用什么翻墙使用谷歌?上外网神器Ghelper插件详解中评论 你好,我也遇到了安装完右上角没有显示图标,也不能打开相关网页的问题,用的是谷歌浏..
  • 文章归档
  • 2016-10 (4)
  • 2016-11 (2)
  • 2017-06 (3)
  • 2017-07 (4)
  • 2017-09 (2)
  • 2017-11 (1)
  • 2017-12 (1)
  • 2018-01 (2)
  • 2018-03 (1)
  • 2020-04 (9)
  • 2020-05 (3)
  • 2020-06 (8)
  • 2020-07 (4)
  • 2020-09 (1)
  • 2021-02 (1)
  • 2021-03 (2)
Top
  • 友情链接
  • 技术博客集
  • 澜溪博客
  • 心中hope
  • 陈大剩博客
  • 赵波的博客
  • 佘春晓的博客
  • Liao-博客
  • 友链交换留言

Auther ·HouTiZong© 2009-2020 zongscan.com 版权所有ICP证: 粤ICP备20027696号 PHP交流群 也可以扫右边的二维码

侯体宗的博客