PHP数组的底层实现原理浅析
管理员 发布于 3年前 844
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;请勿发布不友善或者负能量的内容。与人为善，比聪明更重要！
该博客于2020-12-7日，后端基于go语言的beego框架开发
前端页面使用Bootstrap可视化布局系统自动生成
是我仿的原来我的TP5框架写的博客，比较粗糙，底下是入口
侯体宗的博客
文章标签
- test 三种扣减库存方案 Hyperf2.1启动报错端口占用 上外网神器Ghelper 上外网神器集装箱 laravel中HMVC模式 Hyperf框架验证器 Hyperf自定义函数编写 Hyperf对象转成数组 PHP2021面试题集 centos7系统上挂载 Hyperf框架 秒杀系统的设计 Laravel Octane PHP数组底层实现原理 php7垃圾回收机制 Laravel中类型转换 mysql事务特征及隔离级别 Linux-awk命令 mysql编码 JWT源码实现 Laravel内核分析 Laravel中的用法 centos7+go环境+beego框架 go+beego框架开发博客 go+beego开发博客首页 go+beego自定义公共函数 beego注册_登录_查询 beego控制器创建 Beego框架安装 go语言环境安装 laravel+Elasticsearc laravel运行原理 windows7搭建Vuejs环境 Laravel分块 laravel去重(distinct() laravel集合 laravel+mysql读写分离 laravel5+复杂原生sql laravel+MissMyCat/al lnmp sessio laravel自定义数组分页 laravel中.env配置 laravel8队列发邮件 码云仓库常用操作 laravel8配置163SMTP laravel8配置全局函数 laravel/jetstream之认证 laravel/jetstream
友情链接
