深入理解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

时间: 2012-06-10

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

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

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

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

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

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

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实现插入数组但不影响原有顺序的方法

本文实例讲述了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;

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 /** * 逆序二维数组插入一元素 * * @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 = 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选择排序法实现数组排序实例分析

本文实例分析了php选择排序法实现数组排序的方法.分享给大家供大家参考.具体分析如下: 选择排序法的基本思路:直接用案例来说明吧,比如有一个数组$arr = array(2,6,3,9),从大到小排序. 第一次大循环:它首先假设$arr[0]为最大值,然后分别跟$arr[1]~$arr[3]进行比较,如果比较它大,则进行交换,过程是这样(2,6,3,9)---2和6比 --->(6,2,3,9)---6和3比--->(6,2,3,9)---6和9比--->(9,2,3,6).注意,这里下

Java使用选择排序法对数组排序实现代码

编写程序,实现将输入的字符串转换为一维数组,并使用选择排序法对数组进行排序. 思路如下: 点击"生成随机数"按钮,创建Random随机数对象:使用JTextArea的setText()方法清空文本域:创建一个整型一维数组,分配长度为10的空间:初始化数组元素,使用Random类的nextInt()方法生成50以内的随机数,使用JTextArea类的append()方法把数组元素显示在文本域控件中:点击"排序"按钮,使用JTextArea类的setText()方法清空

java数据结构之二分查找法 binarySearch的实例

java数据结构之二分查找法 binarySearch的实例 折半查找法,前提是已经排好序的数组才可查找 实例代码: public class BinarySearch { int[] bArr; public void setArr(int[] bArr){ this.bArr=bArr; } public static void main(String[] args) { int arrLength=16; int[] bArr=new int[arrLength]; System.out.

Java 选择排序、插入排序、希尔算法实例详解

1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu

Python龙贝格法求积分实例

我就废话不多说了,直接上代码吧! # 龙贝格法求积分 import math a=0 # 积分下限 b=1 # 积分上限 eps=10**-5 # 精度 T=[] # 复化梯形序列 S=[] # Simpson序列 C=[] # Cotes序列 R=[] # Romberg序列 def func(x): # 被积函数 y=math.exp(-x) return y def Romberg(a,b,eps,func): h = b - a T.append(h * (func(a) + func(

java使用IO流对数组排序实例讲解

在学会了java中io流的使用后,我们对于数组的排序,又多了一种使用方法.大家知道流处理数据的效率是比较理想的,那么在具体操作数组排序上,很多人对于排序的方法还没有明确.下面我们先java使用流对数组排序的思路为大家进行梳理,然后带来对应的实例代码方法. 1.排序思路 (1)从字符输入流中读取文本,缓冲各个字符,从而实现字符.数组和行的高效读取 (2)询问用户需要多少位数的数组 (3)转换为数字类型 (4)将用户输入数字存入数组 (5)把数组按排序需求并打印出来 2.实例 public stat

PHP排序算法之直接插入排序(Straight Insertion Sort)实例分析

本文实例讲述了PHP排序算法之直接插入排序(Straight Insertion Sort).分享给大家供大家参考,具体如下: 算法引入: 在这里我们依然使用<大话数据结构>里面的一个例子: 扑克牌是我们几乎每个人都玩过的游戏.平时我们开始的时候一般都是一个人发牌,其他人都是一边摸牌,一边理牌,假如你摸上的第一张牌是 5,第二张牌是 3,自然而然的我们把 3 插到 5 的前面:第三张牌是 4,查到 3 和 5 的中间:第四张牌是 6,放到 5 的后面:第五张牌是 2,插到 3 的前面:--.最

C#冒泡法排序算法实例分析

本文实例讲述了C#冒泡法排序算法.分享给大家供大家参考.具体实现方法如下: static void BubbleSort(IComparable[] array) { int i, j; IComparable temp; for (i = array.Length - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (array[j].CompareTo(array[j + 1]) > 0) { temp = array[j]; array[

C#使用回溯法解决背包问题实例分析

本文实例讲述了C#使用回溯法解决背包问题的方法.分享给大家供大家参考.具体如下: 背包问题描述: 给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高 实现代码: using System; using System.Collections.Generic; using System.Text; namespace BackRack { //要装入书包的货物节点 class BagNode { public int mark;//货物编号,从0开始