深入理解PHP之数组遍历顺序

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

$arr['laruence'] = 'huixinchen';


$arr['yahoo']    = 2007;


$arr['baidu']    = 2008;


foreach ($arr as $key => $val) {

//结果是什么?
}

又比如:

$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; /* 下个空闲可用位置的数字索引,执行$arr[]='xxx'时使用这个值 */


Bucket *pInternalPointer;   /* 内部位置指针, 会被reset, current这些遍历函数使用 */


Bucket *pListHead;      /* 头元素, 用于线性遍历 */


Bucket *pListTail;      /* 尾元素, 用于线性遍历 */


Bucket **arBuckets;     /* 实际的存储容器（Bucket **arBuckets定义一个指针数组的另一种方式） */


dtor_func_t pDestructor;/* 元素的析构函数(指针) */


zend_bool persistent;


unsigned char nApplyCount; /* 循环遍历保护 */


zend_bool bApplyProtection;


#if ZEND_DEBUG

int inconsistent;

#endif

} HashTable;

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

    $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;                    /* 数据，指向zval结构 */


void *pDataPtr;                 /* 数据指针 */


struct bucket *pListNext;               /* 下一个元素, 用于线性遍历 */


struct bucket *pListLast;       /* 上一个元素, 用于线性遍历 */


struct bucket *pNext;                   /* 处于同一个拉链中的下一个元素 */


struct bucket *pLast;                   /* 处于同一拉链中的上一个元素 */


char arKey[1]; /* 节省内存,方便初始化的技巧 */


} Bucket;

我们注意到, 最后一个元素, 这个是flexible array技巧, 可以节省内存,和方便初始化的一种做法, 有兴趣的朋友可以google flexible array.There are a couple of things it could refer to. The only place I've seen that precise wording used much is C99 though.A flexible array member is the official C99 name for what used to (usually) be called the "struct hack". The basic idea is that you define a struct something like this:struct x { int a; // whatever members you want here. size_t size; int x[]; // no size, last member only }; This is used primarily (or exclusively) with dynamic allocation. When you want to allocate an object of this type, you