• 从哈希结构看foreach的遍历顺序

    创建顺序,而非索引值顺序
    服务器君一共花费 16.718 ms 进行了 3 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    上一篇我们比较了了PHP数组遍历的3种方法(foreach、for、array_walk())的性能,并且知道了 foreach 的效率很高,比 for 要快一倍左右。那么我们这一篇开始了解一下 foreach ,看看它的一些细节性的知识。

    foreach 的遍历顺序

    • PHP的数组,如果用foreach来访问,遍历的顺序是固定的么?以什么顺序遍历呢? 下面我们写个小程序就知道了。
    $arr['nowamagic'] = '01';
    $arr['google']    = '02';
    $arr['zmazon']    = '03';
    foreach ($arr as $key => $val) {
    	//结果是什么?
    	echo $val.'<br />';
    }
    

    程序的运行结果:

    01
    02
    03
    

    这样的结果貌似大家都猜得到,那么下面再来一个例子:

    $arr[2] = 'nowamagic';
    $arr[1] = 'google';
    $arr[0] = 'amazon';
    foreach ($arr as $key => $val) {
    	//现在结果又是什么?
    	echo $val.'<br />';
    }
    

    这个程序的运行结果是什么呢?如果 foreach 从数组索引 0 开始遍历,那么会是下面这样的结果:

    amazon
    google
    nowamagic
    

    可事实上,不是这样的结果。真正的结果是:

    nowamagic
    google
    amazon
    

    从数组的哈希结构看 foreach 的遍历顺序

    数组的存储单元位于哈希表里的桶,桶的数据结构是下面这样的,前面提到很多次了。

    typedef struct bucket {
    	ulong h;             		/* 数字索引/hash值 */
    	uint nKeyLength;       		/* 字符索引的长度 */
    	void *pData;           		/* 数据 */
    	void *pDataPtr;          	/* 数据指针 */
    	struct bucket *pListNext;  	/* 下一个元素, 用于线性遍历 */
    	struct bucket *pListLast; 	/* 上一个元素, 用于线性遍历 */
    	struct bucket *pNext;   	/* 处于同一个拉链中的下一个元素 */
    	struct bucket *pLast; 		/* 处于同一拉链中的上一个元素 */
    	char arKey[1]; 	/* 节省内存,方便初始化的技巧 */
    } Bucket;
    

    那么这个数据结构与数组的构成有什么关系呢?我们一一说来。

    我们都知道,PHP的数组有两种。一种是索引数组,比如 array[0],另一种是关联数组,比如 array['nowamagic']。

    注意到成员 uint nKeyLength,如果 nKeyLength = 0,那么这个数组就是索引数组,h 就是索引值。

    那关联数组呢?关联数组的索引值会保存在arKey中,索引的长度保存在nKeyLength中。注意到成员 char arKey[1]; 这个是柔性数组成员。如果有兴趣,可以看看下面这些资料:

    再注意到成员 void *pData, 这是一个指针,它指向数组元素存储的内存块中。具体数组元素要存在哪个内存块,这个是系统分配的。

    如果Bucket保存的数据是一个指针时,HashTable将不会另外请求系统分配空间来保存这个指针,而是直接将该指针保存到pDataPtr中,然后再将pData指向本结构成员的地址。这样可以提高效率,减少内存碎片。

    我们假设一个数组,$arr = array( 3, 6, 1, 7, 5, 2 ),哈希表有 4 个桶,我们模取 3 来存储这个数组,那么哈希表大概就成下面这个样子。

    HashTable的pListHead指向线性列表形式下的第一个元素,上图中是元素3,pListTail指向的是最后一个元素2,而对于每一个元素pListNext就是红色线条画出的线性结构的下一个元素,而pListLast是上一个元素。

    pInternalPointer指向当前的内部指针的位置,在对数组进行顺序遍历的时候,这个指针指明了当前的元素。

    当在线性(顺序)遍历的时候,就会从pListHead开始,顺着Bucket中的pListNext/pListLast,根据移动pInternalPointer,来实现对所有元素的线性遍历。

    • 简单地说,当创建数组元素的时候,它们就在哈希表开辟了自己的位置,并且元素之间会有指针相互指向,类似双向链表一样。foreach 会严格遵守这个链表顺序,逐个遍历。再看前面的例子,虽然元素 $arr[2] = 'nowamagic' 索引比 $arr[1] = 'google' 后,但是它早创建,就是说它的哈希表队列位置比 google 前,所以遍历的话 nowamagic 先出来。

    对于foreach,如果我们查看它生成的opcode序列,我们可以发现,在foreach之前,会首先有个FE_RESET来重置数组的内部指针,也就是pInternalPointer,然后通过每次FE_FETCH来递增pInternalPointer,从而实现顺序遍历。

    tips1:PHP 数组是通过哈希表(HashTable)表实现的,因此 foreach 遍历数组时是依据元素添加的先后顺序来进行的。如果想按照索引大小遍历,应该使用 for() 循环遍历。

    tips2:用 list() 和 each() 结合来遍历数组,但测试发现效率不如 foreach()。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [C语言程序设计] C语言里的全局变量 2 个条目
  2. [移动开发] Content Provider内容提供者 3 个条目
  3. [移动开发] ListView 使用相关问题集 1 个条目
  4. [Python程序设计] Django架构流程分析 7 个条目
  5. [移动开发] Activity 初步知识 2 个条目
  6. [移动开发] Android里的ContentValues 2 个条目
  7. [移动开发] Android属性系统Property 9 个条目
  8. [PHP程序设计] httpd.conf设置相关 3 个条目
  9. [Python程序设计] Python语言概述 6 个条目
  10. [PHP程序设计] PHP与Stream流 5 个条目
  11. [智力开发与知识管理] 整体性学习步骤 9 个条目
  12. [Python程序设计] Tornado表单处理 3 个条目
窗口 -- [资讯]