深入理解PHP之数组(遍历顺序) Laruence原创

经常会有人问我, PHP的数组, 如果用foreach来访问, 遍历的顺序是固定的么? 以什么顺序遍历呢?
比如:


代码如下:

<?php
$arr['laruence'] = 'huixinchen';
$arr['yahoo'] = 2007;
$arr['baidu'] = 2008;
foreach ($arr as $key => $val) {
//结果是什么?
}

又比如:


代码如下:

<?php
$arr[2] = 'huixinchen';
$arr[1] = 2007;
$arr[0] = 2008;
foreach ($arr as $key => $val) {
//现在结果又是什么?
}

要完全了解清楚这个问题, 我想首先应该要大家了解PHP数组的内部实现结构………

PHP的数组
在PHP中, 数组是用一种HASH结构(HashTable)来实现的, PHP使用了一些机制, 使得可以在O(1)的时间复杂度下实现数组的增删, 并同时支持线性遍历和随机访问.

之前的文章中也讨论过, PHP的HASH算法, 基于此, 我们做进一步的延伸.

认识HashTable之前, 首先让我们看看HashTable的结构定义, 我加了注释方便大家理解:


代码如下:

typedef struct _hashtable {
uint nTableSize; /* 散列表大小, Hash值的区间 */
uint nTableMask; /* 等于nTableSize -1, 用于快速定位 */
uint nNumOfElements; /* HashTable中实际元素的个数 */
ulong nNextFreeElement; /* 下个空闲可用位置的数字索引 */
Bucket *pInternalPointer; /* 内部位置指针, 会被reset, current这些遍历函数使用 */
Bucket *pListHead; /* 头元素, 用于线性遍历 */
Bucket *pListTail; /* 尾元素, 用于线性遍历 */
Bucket **arBuckets; /* 实际的存储容器 */
dtor_func_t pDestructor;/* 元素的析构函数(指针) */
zend_bool persistent;
unsigned char nApplyCount; /* 循环遍历保护 */
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

关于nApplyCount的意义, 我们可以通过一个例子来了解:


代码如下:

<?php
$arr = array(1,2,3,4,5,);
$arr[] = &$arr;

var_export($arr); //Fatal error: Nesting level too deep - recursive dependency?

这个字段就是为了防治循环引用导致的无限循环而设立的.

查看上面的结构, 可以看出, 对于HashTable, 关键元素就是arBuckets了, 这个是实际存储的容器, 让我们来看看它的结构定义:


代码如下:

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;

我们注意到, 最后一个元素, 这个是flexible array技巧, 可以节省内存,和方便初始化的一种做法, 有兴趣的朋友可以google flexible array.
h是元素的Hash值,对于数字索引的元素,h为直接索引值(通过nKeyLength=0来表示是数字索引).而对于字符串索引来说, 索引值保存在arKey中, 索引的长度保存在nKeyLength中.
在Bucket中,实际的数据是保存在pData指针指向的内存块中,通常这个内存块是系统另外分配的。但有一种情况例外,就是当Bucket保存 的数据是一个指针时,HashTable将不会另外请求系统分配空间来保存这个指针,而是直接将该指针保存到pDataPtr中,然后再将pData指向本结构成员的地址。这样可以提高效率,减少内存碎片。由此我们可以看到PHP HashTable设计的精妙之处。如果Bucket中的数据不是一个指针,pDataPtr为NULL(本段来自Altair的”Zend HashTable详解”)
结合上面的HashTable结构, 我们来说明下HashTable的总结构图:

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

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

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

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

类似的, 当我们使用, each/next系列函数来遍历的时候, 也是通过移动数组的内部指针而实现了顺序遍历, 这里有一个问题, 比如:


代码如下:

<?php
$arr = array(1,2,3,4,5);
foreach ($arr as $v) {
//可以获取
}

while (list($key, $v) = each($arr)) {
//获取不到
}
?>

了解到我刚才介绍的知识, 那么这个问题也就很明朗了, 因为foreach会自动reset, 而while这块不会reset, 所以在foreach结束以后, pInternalPointer指向数组最末端, while语句块当然访问不到了, 解决的办法就是在each之前, 先reset数组的内部指针.

而在随机访问的时候, 就会通过hash值确定在hash数组中的头指针位置, 然后通过pNext/pLast来找到特点元素.

增加元素的时候, 元素会插在相同Hash元素链的头部和线性列表的尾部. 也就是说, 元素在线性遍历的时候是根据插入的先后顺序来遍历的, 这个特殊的设计使得在PHP中,当使用数字索引时, 元素的先后顺序是由添加的顺序决定的,而不是索引顺序.

也就是说, PHP中遍历数组的顺序, 是和元素的添加先后相关的, 那么, 现在我们就很清楚的知道, 文章开头的问题的输出是:


代码如下:

huixinchen
2007
2008

所以, 如果你想在数字索引的数组中按照索引大小遍历, 那么你就应该使用for, 而不是foreach


代码如下:

for($i=0,$l=count($arr); $i<$l; $i++) {
//这个时候,不能认为是顺序遍历(线性遍历)
}

原文:http://www.laruence.com/2009/08/23/1065.html

(0)

相关推荐

  • PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解

    数据结构很重要,算法+数据结构+文档=程序使用PHP描述冒泡排序算法,对象可以是一个数组 复制代码 代码如下: //冒泡排序(数组排序)function bubble_sort($array) {$count = count($array);if ($count <= 0)return false;for($i=0; $i<$count; $i++){for($j=$count-1; $j>$i; $j–){if ($array[$j] < $array[$j-1]){$tmp =

  • php实现插入数组但不影响原有顺序的方法

    本文实例讲述了php实现插入数组但不影响原有顺序的方法.分享给大家供大家参考.具体实现方法如下: function array_intsort($array,$num) { $array_right = $array_left = array(); $length = count($array); if ($num < $array[0]) { array_unshift($array,$num); return $array; } else { for($i=0; $i < $length;

  • ThinkPHP写数组插入与获取最新插入数据ID实例

    本文实例讲述了thinkphp写数组插入与获取最新插入数据ID的实现方法.分享给大家供大家参考.具体方法分析如下: 该实例讲述了thinkphp怎么自己写数组插入,此处是以注册用户为例. 具体实现代码如下: 复制代码 代码如下: public function insert2(){  header("Content-Type:text/html; charset=utf-8");  $Dao = M("User"); // 构建写入的数据数组  $data[&quo

  • 逆序二维数组插入一元素的php代码

    复制代码 代码如下: <?php /** * 逆序二维数组插入一元素 * * @author WadeYu * @date 2012-05-30 */ $aSorted = array( array(1, 100), array(2, 90), array(3, 80), array(4, 70), array(5, 60), array(6, 50), array(7, 40), array(8, 40), array(9, 40), array(10, 20), ); $aInsert =

  • PHP 数组遍历顺序理解

    比如: <?php$arr['laruence'] = 'huixinchen';$arr['yahoo']    = 2007;$arr['baidu']    = 2008;foreach ($arr as $key => $val) {//结果是什么?} 又比如: <?php$arr[2] = 'huixinchen';$arr[1]  = 2007;$arr[0]  = 2008;foreach ($arr as $key => $val) {//现在结果又是什么?} 要完

  • php数组函数序列之array_unshift() 在数组开头插入一个或多个元素

    array_unshift()定义和用法 array_unshift() 函数在数组开头插入一个或多个元素. 被加上的元素作为一个整体添加,这些元素在数组中的顺序和在参数中的顺序一样. 该函数会返回数组中元素的个数. 语法 array_unshift(array,value1,value2,value3...)参数 描述 array 必需.规定输入的数组. value1 必需.规定插入的值. value2 可选.规定插入的值. value3 可选.规定插入的值. 提示和注释 注释:所有的数值键名

  • php数组函数序列之array_splice() - 在数组任意位置插入元素

    array_splice定义和用法 array_splice() 函数与 array_slice() 函数类似,选择数组中的一系列元素,但不返回,而是删除它们并用其它值代替. 如果提供了第四个参数,则之前选中的那些元素将被第四个参数指定的数组取代. 最后生成的数组将会返回. 语法 array_splice(array,offset,length,array)参数 描述 array 必需.规定数组. offset 必需.数值.如果 offset 为正,则从输入数组中该值指定的偏移量开始移除.如果

  • php插入排序法实现数组排序实例

    本文实例讲述了php插入排序法实现数组排序的方法.分享给大家供大家参考.具体分析如下: 插入排序法的基本思路:同样以案例来说明,还是以$arr = array(2,6,3,9),由大到小排序. 实现原理:假设(并不实际创建)有一个有序数组$arr = array(2),用$arr[1]=6来与它进行比较,如果6>2,由把$arr[0]后移到$arr[1]位置,而6插入到$arr[0]位置.接着,$arr[2]=3与$arr[1]=2比较,3>2,则$arr[1]=2继续后移到$arr[2]位置

  • 深入理解PHP之数组(遍历顺序) Laruence原创

    经常会有人问我, PHP的数组, 如果用foreach来访问, 遍历的顺序是固定的么? 以什么顺序遍历呢? 比如: 复制代码 代码如下: <?php $arr['laruence'] = 'huixinchen'; $arr['yahoo'] = 2007; $arr['baidu'] = 2008; foreach ($arr as $key => $val) { //结果是什么? } 又比如: 复制代码 代码如下: <?php $arr[2] = 'huixinchen'; $arr

  • PHP 数组遍历foreach语法结构及实例

    foreach() PHP foreach() 语法结构用于遍历操作或输出数组,foreach() 仅能用于遍历数组或对象,当试图将其用于其它数据类型或者一个未初始化的变量时会产生错误. 语法: foreach (array as $value) statement // 或者: foreach (array as $key => $value) statement 上述语法中,每次循环将当前单元的值赋给 $value 并且数组内部的指针向前移一步.在第二种语法格式中还将当前单元的键名也会在每次

  • C++实现基于静态数组的顺序表

    本文实例为大家分享了C++实现基于静态数组的顺序表,供大家参考,具体内容如下 实现的基本操作有: 1. 初始化 2. 尾插 3. 尾删 4. 头插 5. 头删 6.查找任意元素 7. 读任意位置元素 8. 修改任意位置元素 9. 查找指定元素值的下标 10. 在任意位置插入元素 11.删除指定位置的元素 12.删除任意元素 13.打印数据 头文件seqlist.h: #pragma once #include<stdio.h> #include<stdlib.h> #include

  • JS数组遍历中for,for in,for of,map,forEach各自的使用方法与优缺点

    JS数组遍历普通函数 优点:支持流程控制(break.continue.return) for const arr = ["A", "B", "C"] for(let i = 0; i<arr.length; i++){ console.log(arr[i]) } 优点:能够对索引精确控制缺点:语法较为繁琐 for in const arr = ["A","B","C"] arr[

  • JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍

    •原理: •高级浏览器支持forEach方法 语法:forEach和map都支持2个参数:一个是回调函数(item,index,list)和上下文: •forEach:用来遍历数组中的每一项:这个方法执行是没有返回值的,对原来数组也没有影响: •数组中有几项,那么传递进去的匿名回调函数就需要执行几次: •每一次执行匿名函数的时候,还给其传递了三个参数值:数组中的当前项item,当前项的索引index,原始数组input: •理论上这个方法是没有返回值的,仅仅是遍历数组中的每一项,不对原来数组进行

  • java数组遍历 删除remove(示例代码)

    废话不多说,直接上代码 复制代码 代码如下: package com.b; import java.util.ArrayList; //数组遍历删除,添加 public class Core2 {     private String name;     private int num;     private String color; public Core2() {     } public Core2(String a, int b, String c) {         name =

  • IE8对JS通过属性和数组遍历解析不一样的地方探讨

    以文谨记在此被浏览器版本差异的坑. 复制代码 代码如下: Array.prototype.Contains = function (str) { if (!str) return false; for (var i = 0; i < this.length; i++) { if (this[i] == str) { return true; } } return false; } var tmp = new Array(); tmp.push("1"); tmp.push(&qu

  • PHP多维数组遍历方法(2种实现方法)

    本文实例讲述了PHP多维数组遍历方法.分享给大家供大家参考,具体如下: 方法一: $a=array('fruits'=>array('a'=>'orange', 'b'=>'grape',c=>'apple'), 'numbers'=>array(1,2,3,4,5,6), 'holes'=>array('first',5=>'second','third') ); foreach($a as $list=>$things){ if(is_array($th

  • PHP数组遍历知识汇总(包含遍历方法、数组指针操作函数、数组遍历测速)

    一.数组遍历的3个方法介绍 1. foreach() foreach()是一个用来遍历数组中数据的最简单有效的方法. #example1: 复制代码 代码如下: <?php $colors= array('red','blue','green','yellow'); foreach ($colorsas$color){ echo "Do you like $color? <br />"; } ?> 显示结果: Do you like red? Do you li

随机推荐