太原PHP培训
达内太原php培训中心

0351-5608878

热门课程

浅析PHP数组的实现

  • 时间:2016-10-21
  • 发布:简书
  • 来源:简书

浅析PHP数组的实现

在任何编程中都会涉及到数组的问题,太原php培训机构讨论一下php的数组问题。

. PHP数组特点介绍

php数组可谓是php的核心,其key=>value的存储结构,让我们处理数据可以游刃有余,并且在一般情况下增删查改都是O(1)的时间复杂度,并表现出一些特点让我们对其内部的结构充满了好奇。

「数组内存申请不需要自己控制」:数组的内存申请和释放是内部控制的,不需要人为的去干预。

「兼容关联数组和索引数组」:数组可以以数字为下标进行操作,也可以以字符串为下标进行操作,其实他俩本质上都是key=>value的格式。

「可以无key值存储」:像a[] = 10; 这样去存储一个value值,事实上他也是有key值的。

「不会出现数组越界的问题」:不会像我们操作C/C++等语言一样,要注意数组的边界,一定不能正向或者逆向越界。在php中不会有这些问题的存在。

value值无严格的定义和统一」:这里就是php内部自己实现了一个范型。

foreach遍历数组与插入顺序有关」:插入顺序和遍历输出一致。

. PHP数组结构的演变

这个地方主要讲PHP5.6=>PHP7.0=>PHP7.1的演变过程

PHP5.6的数组结构

我们可以看到,数组本质就是一个hashtable结构,左侧的0~nTablemask便是hash下标,而后面有一个双向链表,便是我们通常所说的hash冲突的链地址法。

而绿色的双向链表,则是foreach遍历用的,这个地方用双向链表,主要是为了逆序访问来用的,遍历的时候,就是从pListHead开始不断的next便可以遍历所有的元素。这样要比下标遍历hashtable快得多。

但是这个结构有很明显的缺点:

①. 每次插入/删除元素都要申请/释放内存,这样会严重的导致内存碎片化,降低内存的使用率。

②. 再者,每次插入元素的时候都要去申请内存,会有一次寻址的过程,时间效率低。

③. 指针结构很复杂,有大量的指针操作。

PHP7.0的数组结构

针对上面5.6所有的问题,提出了如上的结构。arData结构便是我们插入数据的结构,是一段连续的内存,在初始化/数组扩充时一次性内存申请好,这样内存便不会产生碎片化问题,并且我们看,hash冲突的时候是单链表,并且没有插入元素时候的双向链表,因为我们可以直接扫描数组便可以顺序/逆序访问插入的数据。

PHP7.1的数组结构

如上是最新的数据结构,最主要的区别是把7.0的两段内存转化为一段内存,算是在内存上的继续优化。他的内存申请是从下标-8位置申请的,然后移动指针到key1位置。

. PHP7.0数组源码实现

3.1 PHP7.0数组的主要数据结构

Bucket结构

Bucket结构便是我们所说的保存插入数据的结构。主要包括:key(字符串,如果是数字下标,转化位字符串), value, h(只会计算一次,如果是数组下标,直接把key作为h)

PHP数组的结构

这便是PHP7.0的数组结构,我后面讲全部是用7.0结构讲,比较清晰。nNextFreeElement是无key值存储时使用的数据,用来分配key值。

3.2 PHP数组的hash方法

PHP hash源码

如上是phphash源码,看一眼容易把人瞎蒙,然而把它简化一下

PHP 源码转化

简单讲一下。其中源码中把 hash*33 转化为 (hash<<5) + hash

在一个就是,使用了循环展开策略,减少不必要的循环判断,在一个是连续的执行相同的指令,提高指令的cache命中率。可以看着:https://en.wikipedia.org/wiki/Loop_unrolling

那么计算出hash值来之后,并不是我们想要的下标,因为很有可能超过了hashmask值,所以需要一步计算来得到index

•7.0

hashmask = tablesize – 1; //tablesize一定是2的指数倍,和申请内存有关系,后面讲

h = hashcode & hashmask; //计算index

hashmask=7(10)=111(2) //十进制下的7转为二进制下的111

0<=h<8 //所有值 & hashmask 一定在0~7之间

•7.1

hashmask = -tablesize;

h = hashcode | hashmask;

hashmask=-8(10)=11111000(2补码)

-8<=h<=-1

7.1的结构因为是hash负下标,所以用的另一种计算策略,大同小异。

3.3 PHP数组插入数据

PHP插入数据的流程图

大致流程如上,看一下就好。讲一下插入数据的结构变化。

插入数据结构变化

在我们插入key6这个key值之后,在arData数据往后排,我们假设他与key1hash冲突,所以使用链地址法,直接插入到链表首部。

3.4 PHP数组删除数据

在上面的结构,假如我们删除key1,会有两种考虑。

①. 删除该元素之后,我们是否要保证空间的利用率,把后面的数据移动,覆盖当前位置。

②. 删除元素之后,直接把该位置空出。

其实第一种策略是不可接受,因为这样会导致时间复杂度退化为O(n),而第二种策略,我们控制当前位置之后,我们可以在内存扩充时,把这些空位置给删除掉即可。

PHP数组删除数据

3.4 PHP数组内存申请及rehash

假设我们要在如下结构中插入key9

PHP 数组结构

发现当前arData已经满了,所以我们申请新内存(初始大小位2,以2的倍数不断扩充),把所有数据以内存的形式copy过去,然后扫描数组,把无用的数据给删除掉(用移动后面元素的策略)。因为nTableMask数值改变了然后进行rehash

这里有一个点值得提一下:把原数据copy过去的时候,我们可以选择遍历原先的数组,把有用的数据copy过去,也可以先把原内存的数据复制到新内存的位置,然后去遍历数组去移动数据。PHP实现选择了第二种,这样考虑应该是我们删除元素的次数比较少,直接以内存的形式copy数据要比遍历copy的速度快,在权衡之下选择了第二种。

插入数据之后

结构变化如上图。

. PHP数组的可优化点

4.1 PHP数组的退化案例

本案例参考的鸟哥的博客。

攻击代码

大概测了一下

运行结果

我们可以看到,时间效率差别很大。我们来分析一下为什么会这样。

插入元素:key=0,1*65536,2*65536,….,65535*65536

插入元素特点:h=key&65535=0,生成绝对的hash冲突导致退化1*****00000000&0****011111111=0

大致的插入计算次数:1+2+3+4+5+…+65536(每次插入都会冲突,从而会去查询是否有相同的key值,所以会有扫描的次数总和如此)

导致插入元素时间复杂度退化为O(n*(1+n)/2)=O(n^2)

那么65536^2在计算机1s处理10^8运算的情况下,大概36s以上,所以运行结果算是可预期的。

hash冲突的结构

4.2 可进行优化的策略

我们参考Javahashtable的实现来使用红黑树解决这个问题。

•①.设定链表冲突长度的阀值

•②.当链表长度超过阀值的时候,以key值为键值进行红黑树的转化,key全是字符串,所以我们可以以key的字典序进行排序

•③.Hashtable的指针指向树根

•④.增删查改,不断对红黑树结构进行调整

•⑤.使增删查改时间复杂度达到最差为O(logn)

我们来看下结构的变化

加入红黑树后的结构变化

如果不了解红黑树,可以去参考一下《算法导论》中的详解

. PHP数组的总结

「数组内存申请不需自己控制」

hashtable内存大小与arData大小相同,并且一定为2的指数倍不断扩展

「兼容关联数组和索引数组」

索引是hash值同时也是key值,转化为关联数组,关联数组用hashtable实现

「可以无索引(key)存储」

无索引存储时,会自动为其分配最后一个没有被使用过的下标来作为keyhash值进行存储

「不会出现数组越界的情况」

索引即hash值,用无符号长整形存储,不会出现负向越界

索引的大小与内存的大小没有绝对的关系,不会出现正向越界

value值无严格的定义或统一」

phpvalue值进行了范型处理

foreach遍历数组与插入顺序有关」

foreach是对arData遍历,而arData是顺序存储的

foreach比用for进行下标访问永远要快

好了,今天就给大家讲这么多吧,喜欢我的内容可以关注或者分享(微信公众平台:tytedu)选择太原达内培训,不再孤军奋战,轻轻松松做IT高薪白领。太原达内培训带领有明确目标的学子迈向成功之路!

上一篇:Yii 2.0.10 发布,高性能 PHP 框架
下一篇:揭秘PHP匿名函数

PHP中十六个魔术方法详解(三)

JavaScript 与 Java、PHP 的比较

太原php培训资源站

太原PHP编程开发并发编程槽与坑

选择城市和中心
贵州省

广西省

海南省