详解php中array结构hashtable
我们知道php中的array在内部是以hash的结构进行存储的。本文主要重点也是对php中array的静态结构和动态结构进行分析和记录。
这里的静态结构，是指存储php中array数据时使用的数据结构，即所谓的hashtable。
动态结构，是指程序在运行过程中，array数据的存储状态。
?
首先php中的hashtable的结构如下：
typedef struct bucket { ulong h; /* used for numeric indexing */ uint nkeylength; void *pdata; void *pdataptr; struct bucket *plistnext; struct bucket *plistlast; struct bucket *pnext; struct bucket *plast; char *arkey;} bucket;typedef struct _hashtable { uint ntablesize; uint ntablemask; uint nnumofelements; ulong nnextfreeelement; bucket *pinternalpointer; /* used for element traversal */ 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;
?
一个php中的array在内部对应一个hashtable,hashtable内部的四个bucket类型的指针数据记录着数组实际存储的元素内容的地址。具体的内容，各字段名都可以自解释，不做多说明了。
?
?
如果只看这几行代码，可能无法理解php数组实际的工作原理，接下来，我们可以手工模拟一下php数组中的一些最简单的操作。
?
1. 从无到有
hashtable的初始化，首先需要给一个hashtable构造一个内存空间，具体代码如下：
?
//hash_func_t在函数内用不到，hash函数在php范围内都是固定的int _zend_hash_init(hashtable *ht, uint nsize, hash_func_t phashfunction, dtor_func_t pdestructor, zend_bool persistent zend_file_line_dc){ uint i = 3; set_inconsistent(ht_ok); if (nsize >= 0x80000000) { /* prevent overflow */ ht->ntablesize = 0x80000000; } else { while ((1u ntablesize = 1 ntablemask = 0; /* 0 means that ht->arbuckets is uninitialized */ ht->pdestructor = pdestructor; ht->arbuckets = (bucket**)&uninitialized_bucket; ? //实际的数据存储空间还未创建 ht->plisthead = null; ht->plisttail = null; ht->nnumofelements = 0; ? ? ? ? ? ? ? ? ? //表示数组内还没有一个元素， ht->nnextfreeelement = 0; ht->pinternalpointer = null; ht->persistent = persistent; ht->napplycount = 0; ht->bapplyprotection = 1; return success;}
?上述代码可以理解为，为数组构造了一个总的大门，数据都可以经由这个门进入到自己对应的内存块中。当然现在门里还没有“座位”呢。
?
2. 数据插入
对于一个一无所有的空间，怎么给它加点东西呢？这就是数据的插入，即数据是如何保存到这个hashtable中的。
php的数组索引可以是数值或字符串，我们首先看字符串的索引如何存储，代码如下：
int _zend_hash_add_or_update(hashtable *ht, const char *arkey, uint nkeylength, void *pdata, uint ndatasize, void **pdest, int flag zend_file_line_dc){ ulong h; uint nindex; bucket *p; is_consistent(ht); if (nkeylength ntablemask; p = ht->arbuckets[nindex]; while (p != null) { if (p->arkey == arkey || ((p->h == h) && (p->nkeylength == nkeylength) && !memcmp(p->arkey, arkey, nkeylength))) { if (flag & hash_add) { return failure; } handle_block_interruptions();#if zend_debug if (p->pdata == pdata) { zend_puts(fatal error in zend_hash_update: p->pdata == pdata\n); handle_unblock_interruptions(); return failure; }#endif if (ht->pdestructor) { ht->pdestructor(p->pdata); } update_data(ht, p, pdata, ndatasize); if (pdest) { *pdest = p->pdata; } handle_unblock_interruptions(); return success; ?//更新之后直接退出 } p = p->pnext; } if (is_interned(arkey)) { p = (bucket *) pemalloc(sizeof(bucket), ht->persistent); if (!p) { return failure; } p->arkey = (char*)arkey; } else { p = (bucket *) pemalloc(sizeof(bucket) + nkeylength, ht->persistent); if (!p) { return failure; } p->arkey = (char*)(p + 1); memcpy(p->arkey, arkey, nkeylength); } p->nkeylength = nkeylength; init_data(ht, p, pdata, ndatasize); p->h = h; connect_to_bucket_dllist(p, ht->arbuckets[nindex]); if (pdest) { *pdest = p->pdata; } handle_block_interruptions(); connect_to_global_dllist(p, ht); ht->arbuckets[nindex] = p; handle_unblock_interruptions(); ht->nnumofelements++; zend_hash_if_full_do_resize(ht); /* if the hash table is full, resize it */ return success;}
首先，检查数组空间是否初始化，代码如下：
?
#define check_init(ht) do { \ if (unexpected((ht)->ntablemask == 0)) { \ (ht)->arbuckets = (bucket **) pecalloc((ht)->ntablesize, sizeof(bucket *), (ht)->persistent); \ (ht)->ntablemask = (ht)->ntablesize - 1; \ } \} while (0)
??
然后计算要插入的字符串索引的hash值，并与ntablemask做按位与，得到nindex，这个nindex就是对应的bucket*在二维数组arbucket**中的偏移量。根据代码逻辑，如果nindex位置不为空，则说明当前计算得到的hash值之前存在。如果连key也相同并且flag为hash_add则失败，否则就是更新操作。如果是更新操作则不会对现有数组结构有任何影响，更新了对应的值之后直接退出即可。
?
在需要有新元素插入到hashtable时，构造好的新元素会经过两步来链入该hashtable
?
第一步代码如下：
?
#define connect_to_bucket_dllist(element, list_head) \ (element)->pnext = (list_head); \ (element)->plast = null; \ if ((element)->pnext) { \ (element)->pnext->plast = (element); \ }
?
在这一步中如果新元素的key的hash值之前存在过，则list_head为hashtable.arbucket[nindex],nindex怎么来的前面已经说过了。在这一步过后会将hashtable.arbucket[nindex]赋值为当前的新元素，你懂得。
?
如果新元素的key对应的hash之前没有存在过，则list_head就为null，因为hashtable.arbucket[nindex]为null。你也懂得。
?
第二步代码如下：
?
#define connect_to_global_dllist(element, ht) \ (element)->plistlast = (ht)->plisttail; \ (ht)->plisttail = (element); \ (element)->plistnext = null; \ if ((element)->plistlast != null) { \ (element)->plistlast->plistnext = (element); \ } \ if (!(ht)->plisthead) { \ (ht)->plisthead = (element); \ } \ if ((ht)->pinternalpointer == null) { \ (ht)->pinternalpointer = (element); \ }
?关于这一步会对hashtable的内容有什么样的影响，请参看下面的动态示例。相信你也懂得。
?
?
?
动态示例：
现在我们假设数组中没有任何元素，则进行插入操作。现在我们按照代码的逻辑，手动模拟一下数据插入的过程：
?
1.
插入第一个元素a,假设其key对应的hash值为1
则插入之后，内存中的状态如下：
?
hashtable.arbucket[1]=a;
hashtable.plisthead = a
hashtable.plisttail = a
hashtable.pinternalpointer = a
a.pnext = null
a.plast = null
a.plistlast = null
a.plistnext = null
?
2.
插入第二个元素b，假设其key对应的hash值为2
则插入之后内存的状态如下：
hashtable.arbucket[2] = b;
hashtable.plisthead = a
hashtable.plisttail = b
hashtable.pinternalpointer = a //这个只在第一次的时候设置
a.pnext=null
a.plast = null
a.plistnext = b
a.plistlast = null
b.plistlast = a
b.plistnext = null
b.pnext = null
b.plast = null
?
3.
插入第三个元素c，假设其key的hash值为1，和a相同
则插入之后内存状态如下：
hashtable.arbucket[1] = c;
hashtable.plisthead = a
hashtable.plisttail =c
hashtable.pinternalpointer = a //这个只在第一次的时候设置
a.pnext=null
a.plast = c
a.plistnext = b
a.plistlast = null
?
b.pnext = null
b.plast = null
b.plistlast = a
b.plistnext = c
c.pnext = a
c.plast = null
c.plistnext = null
c.plistlast = b
?
插入a，b，c三个值之后的内存中状态即为：
hashtable.arbucket[1] = c;
hashtable.plisthead = a
hashtable.plisttail =c
hashtable.pinternalpointer = a
a.pnext=null
a.plast = c
a.plistnext = b
a.plistlast = null
?
b.pnext = null
b.plast = null
b.plistlast = a
b.plistnext = c
c.pnext = a
c.plast = null
c.plistnext = null
c.plistlast = b
?
ok，a、b、c三个元素都已插入了，现在我们要实现两个任务：
?
1.
查找某key的元素值(value)：
如果我们要访问a元素，则提供a的key：key_a,得到对应的hash值为1
然后找hasttable.arbucket[1]。这时hasttable.arbucket[1]其实为c不是a，但由于c的key不等于a的key，因此，要沿着pnext的指针找下去，直到null，而此时c.pnext就是a，即找到了key_a对应的值a。
总之由key查找一个元素时，首先要hash，然后顺着hash后的索引位置的pnext指针一直找下去，直到null，如果遇到了和要查找的key相同的值，则找到，否则找不到。
?
2.
遍历数组：
由于我们的例子中的key是字符串类型的，全部循环遍历不能用for。只能用foreach，那foreach的遍历是如何实现的呢？
?
简单，根据最后的hashtable的状态，我们从hasttable.plisthead开始沿着plistnext指针顺序找下去即可了。以本文例子为例，则结果为：
?
?
hashtable.plisthead====>a
a.plistnext ====>b
b.plistnext ====>c
?
则最后的遍历顺序就是a，b，c，发现foreach的遍历顺序是和元素插入到数组的顺序相关的。
?
?
如果插入的元素的key不是字符串，而是数值。则可以省去做计算hash值这一步，直接拿数值的key做为hash值使用。
这样就不存在hash冲突的问题，这样也就不会用到每个元素的pnext、plast两个指针了，这两个指针都只会是null。
?
这样我们可以通过使用for循环来遍历数组了，因为不存在hash冲突。
?
同样，如果我们使用foreach来遍历数组的话，遍历顺序还是元素的插入顺序，这个你当然懂得。
?
?
ps：
本文并未对zend中的hash结够做全面的记录，只是对本文主题涉及到的逻辑的重点代码进行了分析和演示。同时也为了能抓住重点。有些代码并未列出，如：再hash的逻辑，和索引为数值类型数据的代码等。这些可在代码文件zend/zend_hash.c中找到详细内容。
?