课程咨询 :13623629309

太原PHP培训 > 达内新闻 > 浅析PHP数组的实现
  • 浅析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高级开发名企定制班(剩2个名额)

php高级开发名企定制班(剩2个名额)

开班日期:12-29

php高级开发周末班(剩5个名额)

php高级开发周末班(剩5个名额)

开班日期:12-29

php高级开发免费试听(剩5个名额)

php高级开发免费试听(剩5个名额)

开班日期:12-29

更多高级开发工程师精品班

更多高级开发工程师精品班

开班日期:12-29

  • 地址:山西省太原市小店区学府街长治路高新国际A座24层
  • 课程培训电话:13623629309     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56