剖析PHP底层数组是如何实现的

PHP是一门入门容易,使用范围广泛的语言,以其灵活性以及web后端开发被很多人熟知,也被很多人戏称“PHP是世界上最好的语言”。本人是一名“忠实”的PHPer,相信用过PHP的程序员都会体会到PHP数组的灵活性,相对传统的C语言,使用起来很是方便,拥有关联数组(key值可以是字符串),不需要预定义数组空间大小,关联数组,不需要指定key的快速索引赋值等等便利方法,这段时间研究了一下PHP数组的底层结构,并总结分析,里面含有一些我自己的猜想,如有错误请指出。

1.PHP的数组底层结构

哈希结构是一种非常重要的数据结构,他是一种通过key映射到value的结构,由于其特性,可以在大部分的情况下让查找和插入的效率达到O(1),在很多语言或者系统里面都有显性得体现出来,具体的实现思路有很多种。详细的介绍可以看我的博客数据结构之哈希结构

  PHP的数组是用链地址法的哈希结构去实现的,链表是双向链表,这样既可以动态分配数组空间,也可以通过key值去计算hash值去访问对应的元素,是一种非常高效的数据结构。

  下面是PHP  Bucket的结构,Bucket是一个基本结点的结构,Bucket是以存放基本元素的容器,可以简单理解为数组元素的房子。

剖析PHP底层数组是如何实现的

下面是PHP  HashTable结构,HashTable是用以存储Bucket数组和Bucket信息的哈希表结构,采用双向链表的拉链法结构。

剖析PHP底层数组是如何实现的

  可能首次去看数据结构可能会觉得有点难受,密密麻麻的一堆东西,下面我会一个个分析数据字段。

2.Bucket结构体

1.h(哈希值)

  通过key映射的哈希值(未经过纠正)h,为了让不同key值均匀分配到哈希表的各个位置,必须要有一个好的哈希函数,而PHP选用的是time33算法,也就是下面的算法(简化版)。

剖析PHP底层数组是如何实现的

  当然啦在PHP的具体实现细节又会有点不同,但是原理是差不多的。

2.nKeyLength(字符的个数)

  如果使用的是关联索引,那么此处nKeyLength就是字符的个数,比如说$arr[‘key’]=’value’ ,那么这个值就为3,如果是索引数组,此字段就不会用上。

3.pNext pLast (记录该桶的前后桶)

继续引用百度的图,类似于下面的哈希表,拿元素337来说,他的pNext指向353的位置,pLast指向1的位置,只不过下面是单向链表,没有看到当前元素指向前一个元素。

剖析PHP底层数组是如何实现的

4.pListNext(记录该桶在数据上的后元素)

这个字段从命名意思就可以看出,是链表的指向后继元素的指针。比如说作如下赋值。guangdong的pListNext指向beijing,beijing的pListNext指向shanghai…..

剖析PHP底层数组是如何实现的

所以你如果用foreach去遍历数组,会发现一个很有趣的现象。输出的结果如下,居然不是按照数组下标1,2,3,4顺序去输出,其实只要你理解了PHP的存储数组的数据结构你就很明白了。

剖析PHP底层数组是如何实现的

他的数据结构如下图显示,第一个元素是guangdong,然后来个元素beijing,于是guangdong的pListLast指向beijing,后面的元素同理。而foreach遍历会从第一个元素(也就是pListHead指向的Bucket,详看下文HashTable的介绍)去输出,然后再指向下一个元素,因此输出的顺序不是按照下标来的,而是按照赋值顺序来的,这也是为什么foreach遍历数组要比for遍历要快的原因,因为for每次查找元素都要去做一次哈希映射查找对应下标的Bucket,而foreach只需要遍历Bucket链表就好了。pListLast与pListNext同理,只是指向前一个数组元素。

剖析PHP底层数组是如何实现的

5.arKey(用以存储key值)

    这是一个c99柔性成员,如果需要深究可以百度查查c的柔性成员,如果这一个关联数组,这个arKey就是存储对应的key值。$arr[‘abc’]=’value’;那么arKey存储的就是abc。

3.HashTable结构体

1.nTableSize(哈希表的大小)

  这是哈希表的分配Bucket空间的大小,默认会分配8个Bucket空间,当存储元素个数大于8个就会存储16个,如此下去,存储的个数为2x大小,即8,16,32,64…

2.nTableMask(纠正掩码)

  用以纠正过长的哈希值,值为nTableSize-1,比如说一个我有一个字符经过哈希函数得出值为9,但是nTableSize为8,那该怎么办呢,存放到第1个位置吧,计算方法就是9   mod 8,但是在计算机里面下标是从0开始,因此我们会使用&运算得出结果,9&7=1。

3.nNumOfElements(数组元素个数)

  用以统计数组元素的个数,PHP的count()元素其实就是获取这个值。

4.NextFreeElement(下一个空闲的元素)

  用以存储下一个空闲的元素的值。当你的数组是索引数组,用到$arr[]=value赋值就会用到,如果你上次赋值的元素下标是100,那么NextFreeELement就为101了。无关你的元素个数。

5.pListHead(链表的头部元素)

  这个Bucket指针从名字就可以看出来,用以指向链表的头部元素,例如你给一个数组第一次附上一个值$arr[]=value1,那么这个指针就是指向value1。

6.pListTail(链表的尾部元素)

  原理同上,只是指向尾部元素,每次来一个新的数组元素,pListTail就会指向它。

7.nInternalPointer(用以指向内部指向的元素)

  如果我们用foreach遍历数组,这个指针就会指向当前遍历的元素,用以保存当前指向记录。用到此项的还有current(),next(),prev()函数。

8.arBuckets(用以存储Bucket在C的内部数组)

  此项为指针的指针,可以用于操作Bucket数组。

下面列出一副图来说明PHP的数组结构(为版面清晰忽略了两种指向前一个Bucket的指针:pListLast,pLast)。

剖析PHP底层数组是如何实现的

   最后我大概猜想一下foreach函数的执行过程,首先是将nInternalPointer指向HashTable的第一个Buckets,也就是pListHead,如果不为空则输出该元素,然后nInternaPointer指向该Bucket的下一个元素,也就是pListNext,如此循环下去。

剖析PHP底层数组是如何实现的

未经允许不得转载:PHP100中文网 - 中国第一档PHP资源分享门户 » 剖析PHP底层数组是如何实现的

赞 (0) 打赏

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏