要完全了解清楚这个问题, 我想首先应该要大家了解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的意义, 我们可以通过一个例子来了解:
$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结构示意图
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系列函数来遍历的时候, 也是通过移动数组的内部指针而实现了顺序遍历, 这里有一个问题, 比如:
$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
所以, 如果你想在数字索引的数组中按照索引大小遍历, 那么你就应该使用for, 而不是foreach
for($i=0,$l=count($arr); $i<$l; $i++) {
//这个时候,不能认为是顺序遍历(线性遍历)
有个问题想问下，当数组很大时，比如100万，要在其中查询一个值是否存在，in_array需要的时间比较久，当用array_flip键值互换，再用isset则会快很多，不太明白原因，arBuckets中“h是元素的Hash值”“索引值保存在arKey中”，我的感觉是in_array是根据h来判断元素是否存在，isset使用arKey来判断，这两个并没有实质性的差别，为啥时间会差很多呢？可能我的理解方式不对，希望能得到解答，谢谢~~~
Ⅰf уоᥙ сɑtϲɦ
ɑny оf yoᥙr ᥱmⲣlοуeеѕ plaуіng
thе caгⅾ ցɑmе Cօгρоrаtе СҺаоѕ (үeѕ, it’ѕ
геɑl) in tһе cafetегіа, ʏߋս mɑү Ье tоo lɑte.
Ⲏееге iѕ mү ѡebⅼоց –
Mithaftungen
您好，请原谅无知的我再次刷屏：
经过几次测试，我想跟您确认下，是不是如果将一个数组赋值给另一个变量后，该数组会使用reset()调整自身的指针，重新指向第一个位置？
希望能看到您关于《深入理解PHP之数组(赋值)》的内容。
您好，非常抱歉，请忽略我的这三条评论：
当我在current($array)前使用reset()后又正常了！（明明记得昨天还不正常的）
正如文章中说的，使用foreach遍历过数组后，需要reset()将指针重定向到第一个位置，方可使用current()得到数组中的第一个值
您好，我刚刚又可以重现上条留言中提到的现象了：当将数组A又赋值给另一个新变量B时，使用current()可以取得该数组A的当前值了，否则为false。
以下代码是涉及到问题的代码，请赐教。
//uni_accounts()返回一个多维数组
$accounts = uni_accounts();//使用current()无法获取当前值（第一个值）
//$_accounts = $accounts = uni_accounts();//使用current()可以获取当前值（第一个值）
print_r($accounts);
print_r(current($accounts));
exit;
您好，想请教个问题：
什么样的一个数组会出现使用print_r()可以打印出它的内容，但使用current()获取不到它的当前值（也是第一个值，即使在current()前使用了reset() ，结果依然是false），但使用array_shift却可以？
（昨天在写某段代码时遇到的这个现象，百思不得解，今天读了您这文章后，想再研究下，发现又可以通过current()获得值了，所以更奇怪了）
希望您能帮我一下，谢谢！
[…] 深入理解PHP之数组(遍历顺序 26 Sep 09 PHP文件上传源码分析(RFC1867) 08 Jun 10 深悉正则(pcre)最大回溯/递归限制 […]
[…] 两个双向的链表：第一个双向链表是数组的每个元素（桶bucket）是一个双向链表，这样做是为了解决hash冲突；第二个双向链表是数组将每一个桶(bucket)连接起来，这里要连接的也就是第一个双向链表的链表头，这样做是为了遍历整个hash表用的,鸟哥有篇blog是讲php的foreach的，这里这样设计就是给foreach用的==>《深入理解PHP之数组(遍历顺序)》 […]
“增加元素的时候, 元素会插在相同Hash元素链的头部和线性列表的尾部. 也就是说, 元素在线性遍历的时候是根据插入的先后顺序来遍历的, 这个特殊的设计使得在PHP中,当使用数字索引时, 元素的先后顺序是由添加的顺序决定的,而不是索引顺序.”
这里提到“相同Hash元素链的头部”和“线性列表的尾部”，这里不是太明白，还望楼主讲解一下。
深入了解php变量内核原理及变量内存管理系列文章 | pitaya's blog | 专注与LAMP很多年，Nginx,Linux,PHP,MySQL,Apache,Redis,Memcache,MongoDB,Oracle,Jquery,CentOS,Hadoop,weibo.com
[…] Separation)
http://www.laruence.com/2008/09/19/520.html
6、 深入理解PHP之数组(遍历顺序)
http://www.laruence.com/2009/08/23/1065.html
[…]
[…] 本文地址: http://www.laruence.com/2009/08/23/1065.html 经常会有人问我, PHP的数组, 如果用foreach来访问, 遍历的顺序是固定的么? 以什么顺序遍历呢? 比如: […]
[…] php程序员使用最多的数据结构应该就是数组(array)了吧，不管是实现个列表、队列、哈希还是别的什么数据集，都会先想到用array模拟，因为它既方便使用又功能强大(很多函数支持)。你甚至会不由得感叹，php的array真是万能啊！(php中array的底层实现方式可以参考深入理解PHP之数组) […]
[…] 今天，趁项目暂时不用冒烟赶进度的上来look look，总算是有些弄清楚这个问题了，这里要特别感谢鸟哥的数篇PHP内核级文章，例如：《PHP中的Hash算法》、《深入理解PHP之数组(遍历顺序)》等等。先来段测试代码： […]
[…] 如果想直接运行HashTable的一些简单操作，猛击PHP源码中HashTable的简单示例 如果想查看了解数组存储或遍历的方式，猛击鸟哥的深入理解PHP之数组(遍历顺序) […]
ZEND_END_MODULE_GLOBALS(sample4)
101 static void php_hello1_init_globals(zend_hello1_globals *hello1_globals TSRMLS_DC)
102 {
104 ALLOC_HASHTABLE(HELLO1_G(apps_config));
105 if(zend_hash_init(HELLO1_G(apps_config),
106 8, NULL, free_app_config, 0) == FAILURE)
107 {
108 FREE_HASHTABLE(HELLO1_G(apps_config));
109 }
110 char string[11] = “chenyujian”;
111 zval *app_name ;
113 MAKE_STD_ZVAL(app_name);
114 ZVAL_STRING(app_name, “chen”, 1);
116 if(zend_hash_add(HELLO1_G(apps_config), “bar”, sizeof(“bar”), &app_name, sizeof(zval*), NULL) == SUCCESS)
117 {
118 }
119 if(zend_hash_add(HELLO1_G(apps_config), string, sizeof(string), &app_name, sizeof(zval*), NULL) == SUCCESS)
120 {
121 php_printf(“size of:%s:%d\n”,string,sizeof(string));
122 }
123 zval **args;
124 if(zend_hash_find(HELLO1_G(apps_config), string, sizeof(string), (void **) &args) == SUCCESS)
125 {
127 char *m = Z_STRVAL_PP(args);
128 php_printf(“%s\n”,m);
129 }else
130 {
131 php_printf(“not found”);
132 }
133 }
134 static void php_hello1_globals_dtor(zend_hello1_globals *hello1_globals TSRMLS_DC)
135 {
136 zend_hash_destroy(HELLO1_G(apps_config));
137 /* Free the HashTable itself */
138 FREE_HASHTABLE(HELLO1_G(apps_config));
139 HELLO1_G(apps_config) = NULL;
140 }
PHP_MINIT()里面进行HASH初始化，这时候遇到了几个问题，一，在Module中初始化后，在MSHUTDOWN中进行进行释放（
136 zend_hash_destroy(HELLO1_G(apps_config));
137 /* Free the HashTable itself */
138 FREE_HASHTABLE(HELLO1_G(apps_config));）
出现了segment fault错误。
二：在rini中进行hashtable的hash_add出现了segmentfault错误。
这让我百思不得其解，当然在rini中进行 hash_init 再进行 hash_add是没有问题的。不知道究竟是什么原因。
