PHP7扩展开发教程[9] – 如何使用哈希表？
确保你已阅读《PHP7扩展开发教程[8] – 如何访问超级全局变量？》。
哈希表即zend_array数据结构，它是zval的底层数据类型之一，也是最为复杂的一个结构。
在PHP中的array()即可以表达数组，又可以表达字典，这样的灵活性在zend_array中都有对应的代码实现。
理论先行
鉴于已经有很不错的博客介绍了PHP7的zend_array，所以本章开始前请先自己学习一下这篇文章：
这里盗用一张网上的图片，是一张比较清晰的PHP7 hashtable结构示意图：
从图片来看，arData左侧部分是uint32的哈希桶，右侧是按插入顺序排列的Bucket元素列表，整体来看还是很清晰的。
下面，我将根据上述博客中的几个知识点，对相关的核心代码进行展开讲解，希望可以作为一个补充帮助你进一步理解zend_array的实现原理。
先看数据结构：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
typedef struct _Bucket { zval val; zend_ulong h; /* hash value (or numeric index) */ zend_string *key; /* string key or NULL for numerics */ } Bucket; typedef struct _zend_array HashTable; struct _zend_array { zend_refcounted_h gc; union { struct { ZEND_ENDIAN_LOHI_4( zend_uchar flags, zend_uchar nApplyCount, zend_uchar nIteratorsCount, zend_uchar consistency) } v; uint32_t flags; } u; uint32_t nTableMask; Bucket *arData; uint32_t nNumUsed; uint32_t nNumOfElements; uint32_t nTableSize; uint32_t nInternalPointer; zend_long nNextFreeElement; dtor_func_t pDestructor; }; |
分别讲解一下zend_array各个字段的含义，这对于理解它极为重要。
- gc：引用计数字段，和zend_string等都一样。
- u：各种标记位，主要关注flags，例如：是否分配持久化内存HASH_FLAG_PERSISTENT，是否完成初始化HASH_FLAG_INITIALIZED，是否为压缩数组HASH_FLAG_PACKED。
- nTableMask：哈希桶的个数。
- arData：顺序数据存储空间。
- nNumUsed：arData已使用的槽位数量，可能中间有空槽。
- nNumOfElements：arData实际存储的有效数据个数。
- nTableSize：arData的总槽位数量。
- nInternalPointer：遍历zend_array的迭代器指针，zend_array支持迭代器，我们不研究它了。
- nNextFreeElement：追加整形索引的数据时，它是下一个整形下标。
- pDestructor：一个回调函数，当覆盖/删除一个key或者释放zend_array时，用于释放Bucket中的val。
Bucket是arData顺序数组里的元素类型。
- val：存储的zval数据。
- h：当元素保存在整形下标时，下标保存在该字段，并且本身充当hash值，对其取模得到哈希表的槽位。
- key：当保存的key是字符串时，保存在该字段，通过某个哈希算法生成hash值保存到h字段，对h取模得到哈希表的槽位。
上面的罗列的信息主要是作为下面的参考，下面具体透过代码来看zend_array的几个核心设计。
zend_array采用了”懒惰”的初始化策略。举例来说，我们在PHP代码里的生成数组$arr = array()，在真正向其赋值内容之前，Zend并不知道我们要存储的内容是键值字典还是普通数组，或者是两者都有。
在zend_array的设计中，如果array是纯粹的整形下标数组，那么完全可以采用packed策略，免去哈希桶的存储空间和操作。下标h直接存储在arData[h]中，这种直接定位的性能非常高。
如果array是键值字典，那么就需要利用hash桶来索引键。下标h或者hashFunction(key)经过取模后定位到hash桶，通过遍历桶内的Bucket链表，最终找到要找的下标h或者键key对应的值，这种性能肯定慢于packed array。
“懒惰”初始化的原理，就是在用户首次操作zend_array的时候，根据其插入的是键值还是整形下标，决定zend_array的初始类型是hash array还是packed array。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC) { GC_REFCOUNT(ht) = 1; GC_TYPE_INFO(ht) = IS_ARRAY; ht->u.flags = (persistent ? HASH_FLAG_PERSISTENT : 0) | HASH_FLAG_APPLY_PROTECTION | HASH_FLAG_STATIC_KEYS; ht->nTableMask = HT_MIN_MASK; HT_SET_DATA_ADDR(ht, &uninitialized_bucket); ht->nNumUsed = 0; ht->nNumOfElements = 0; ht->nInternalPointer = HT_INVALID_IDX; ht->nNextFreeElement = 0; ht->pDestructor = pDestructor; ht->nTableSize = zend_hash_check_size(nSize); } |
上面的方法完成”懒惰”初始化，arData并没有分配实际内存，并且这个zend_array的类型也没有确定。
接下来，当我们调用任意插入/更新zend_array的函数时，它们的函数头部都会检查zend_array是否已经”真正”初始化，如果没有则立即初始化。这个检查方法是这样的：
|
1 2 3 4 5 6 7 8 9 10 |
static zend_always_inline void zend_hash_check_init(HashTable *ht, int packed) { HT_ASSERT(GC_REFCOUNT(ht) == 1); if (UNEXPECTED(!((ht)->u.flags & HASH_FLAG_INITIALIZED))) { zend_hash_real_init_ex(ht, packed); } } #define CHECK_INIT(ht, packed) \ zend_hash_check_init(ht, packed) |
它是通过判断zend_array的flags里是否有HASH_FLAG_INITIALIZED来判定的，最终通过zend_hash_real_init_ex完成”真正”的初始化：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
static zend_always_inline void zend_hash_real_init_ex(HashTable *ht, int packed) { HT_ASSERT(GC_REFCOUNT(ht) == 1); ZEND_ASSERT(!((ht)->u.flags & HASH_FLAG_INITIALIZED)); if (packed) { HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT)); (ht)->u.flags |= HASH_FLAG_INITIALIZED | HASH_FLAG_PACKED; HT_HASH_RESET_PACKED(ht); } else { (ht)->nTableMask = -(ht)->nTableSize; HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT)); (ht)->u.flags |= HASH_FLAG_INITIALIZED; if (EXPECTED(ht->nTableMask == (uint32_t)-8)) { Bucket *arData = ht->arData; HT_HASH_EX(arData, -8) = -1; HT_HASH_EX(arData, -7) = -1; HT_HASH_EX(arData, -6) = -1; HT_HASH_EX(arData, -5) = -1; HT_HASH_EX(arData, -4) = -1; HT_HASH_EX(arData, -3) = -1; HT_HASH_EX(arData, -2) = -1; HT_HASH_EX(arData, -1) = -1; } else { HT_HASH_RESET(ht); } } } |
第一个if分支是初始化为packed array，首先通过pemalloc分配一大段内存，它包含左侧2个uint32的hash桶（这2个hash桶对packed array实际上没有任何用处），以及右侧的nTableSize个Bucket槽位。
再通过宏HT_SET_DATA_ADDR把Bucket起始的内存地址赋值给arData，而arData左侧的内存就是2个uint32的hash桶。
第二个If分支初始化为hash array，首先令hash桶个数nTableMask等于Bucket数据槽位个数nTableSize。然后通过pemalloc分配一个包含nTableSize个uint32的hash桶 + nTableSize个Bucket的数据槽位的内存段。
最终，通过宏HT_SET_DATA_ADDR把Bucket的起始内存地址赋值给arData，并将所有hash桶的链表next初始化为-1。
zend_array的各种插入与更新方法，最终都依靠如下2个函数实现。
第1个函数用于向zend_array插入/更新”键-值”，它接受zend_string的key：
|
1 |
static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag ZEND_FILE_LINE_DC) |
第2个函数用于向zend_array插入/更新”下标-值”，它接受zend_ulong的key：
|
1 |
static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag ZEND_FILE_LINE_DC) |
以第2个函数为例，它非常能说明zend_array的背后原理：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag ZEND_FILE_LINE_DC) { uint32_t nIndex; uint32_t idx; Bucket *p; IS_CONSISTENT(ht); HT_ASSERT(GC_REFCOUNT(ht) == 1); if (UNEXPECTED(!(ht->u.flags & HASH_FLAG_INITIALIZED))) { CHECK_INIT(ht, h < ht->nTableSize); if (h < ht->nTableSize) { p = ht->arData + h; goto add_to_packed; } goto add_to_hash; } else if (ht->u.flags & HASH_FLAG_PACKED) { if (h < ht->nNumUsed) { p = ht->arData + h; if (Z_TYPE(p->val) != IS_UNDEF) { if (flag & HASH_ADD) { return NULL; } if (ht->pDestructor) { ht->pDestructor(&p->val); } ZVAL_COPY_VALUE(&p->val, pData); if ((zend_long)h >= (zend_long)ht->nNextFreeElement) { ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX; } return &p->val; } else { /* we have to keep the order :( */ goto convert_to_hash; } } else if (EXPECTED(h < ht->nTableSize)) { |
在第1个if分支中，判断zend_array没有”真正”初始化，那么就调用CHECK_INIT宏完成”真正”初始化。
到底是初始化为packed or hash array，是根据插入的下标zend_ulong h和zend_array的arData空间总大小决定的。
这个判定道理很简单，假设传入的zend_ulong h = 10000，那么packed array就要分配10000个Bucket并把这个数据存储到arData[9999]，显然packed array并不适合这种存储场景，所以在这种场景下代码会将array初始化为hash array。
在第2个分支中，判断zend_array本身就是一个packed array。紧接着，代码判断h位置是此前已经使用过的槽位（nNumUsed之前）还是尚未使用的槽位（nNumUsed之后）。对于后者的处理非常简单，只需要将值填充到尚未使用的槽位中并令nNumUsed后移即可。对于前者，我们需要特别的来看一看。
它首先判断这个旧槽位是否有值占用，如果有旧值占用，那么先释放旧值，再填充新值。如果没有值占用，说明这个槽位之前填充过数据后来又被删除了，此时代码并没有直接将新值填充进去，这是为什么呢？
代码中注释： we have to keep the order ，其实这涉及到zend_array的一个语义保证。zend_array要求自身，新插入的新值，总是可以在遍历数组时最后一个遇到，我们的PHP数组就是这样工作的，你可以自己试试。
我们知道，遍历zend_array的方法就是顺序扫描arData，如果我们直接将新值填充到一个旧槽位arData[h]中，那么假设arData[h + 1]中本来也已经填充了数据，那么遍历zend_array时最后一个元素就是arData[h+1]而不是我们的arData[h]，这显然违背了语义。
正因为这个问题，代码中立即跳转到convert_to_hash位置，调用了zend_hash_packed_to_hash方法将这个packed array转换成了等效的hash array。我们知道，hash array总是在arData + nNumUsed位置追加新值，并在hash桶中建立索引，所以保障了后插入后遍历的语义。
packed array向hash array的转换原理很简单：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
ZEND_API void ZEND_FASTCALL zend_hash_packed_to_hash(HashTable *ht) { void *new_data, *old_data = HT_GET_DATA_ADDR(ht); Bucket *old_buckets = ht->arData; HT_ASSERT(GC_REFCOUNT(ht) == 1); ht->u.flags &= ~HASH_FLAG_PACKED; new_data = pemalloc(HT_SIZE_EX(ht->nTableSize, -ht->nTableSize), (ht)->u.flags & HASH_FLAG_PERSISTENT); ht->nTableMask = -ht->nTableSize; HT_SET_DATA_ADDR(ht, new_data); memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed); pefree(old_data, (ht)->u.flags & HASH_FLAG_PERSISTENT); zend_hash_rehash(ht); } |
通过pemalloc重新分配一个内存段，它包含左侧nTableSize个uint32组成的hash桶，以及右侧nTableSize个Bucket组成的arData，最后调用zend_hash_rehash根据当前的Bucket元素，重建左侧的hash索引。
另外，通过上面的代码也能够看出另外一件事实：packed array只适合连续的向末尾追加整形下标数据，向前赋值或者插入非整形下标数据都将导致packed array蜕化为性能更差的hash array。
实践环节
zend_array的API实在太多了（Zend/zend_hash.h），因此在本章我着重的介绍了zend_array的原理，而不是罗列大篇幅的API。
现在请打开代码：https://github.com/owenliang/php7-extension-explore/tree/master/course9-how-to-work-with-zend-array。
为了帮助大家快速上手zend_array，我还是准备了几个简短的例子给大家。
我注册了一个全局函数：zif_myext_test_array，下面拆解开来，简单的讲一下常用的一些zend_array API。
|
1 2 3 |
// init arr zval arr_zval; assert(array_init(&arr_zval) == SUCCESS); |
这样初始化数组（懒惰初始化），其底层实现我们已经见过：
|
1 2 3 4 5 6 |
ZEND_API int _array_init(zval *arg, uint32_t size ZEND_FILE_LINE_DC) /* {{{ */ { ZVAL_NEW_ARR(arg); _zend_hash_init(Z_ARRVAL_P(arg), size, ZVAL_PTR_DTOR, 0 ZEND_FILE_LINE_RELAY_CC); return SUCCESS; } |
其中资源销毁函数传递了ZVAL_PTR_DTOR，其实就是zval_ptr_dtor，在之前的章节也提到过。
|
1 2 3 |
// add k-v add_assoc_long(&arr_zval, "date", 20170811); assert(zend_hash_str_exists(arr_zval.value.arr, "date", sizeof("date") - 1)); |
向array添加键值类型的数据，可以通过add_assoc_xxx系列便捷函数实现，它们底层最终调用了：
|
1 2 3 4 5 6 7 8 |
ZEND_API int add_assoc_long_ex(zval *arg, const char *key, size_t key_len, zend_long n) /* {{{ */ { zval *ret, tmp; ZVAL_LONG(&tmp, n); ret = zend_symtable_str_update(Z_ARRVAL_P(arg), key, key_len, &tmp); return ret ? SUCCESS : FAILURE; } |
zend_hash_str_exists用于判断一个key是否存在，对应的zend_hash_index_exists用于判断整形下标是否存在。
向下一个整形下标添加一条数据：
|
1 2 |
// add v assert(add_next_index_string(&arr_zval, "hahaha") == SUCCESS); |
zend_array内部维护了我们最后一个整形下标的大小，键值类型不会影响整形下标的自增，所以”hahaha”被保存在了整形下标0。
像这样获取数组的元素个数，就和PHP的count一样：
|
1 2 |
// arr count assert(zend_hash_num_elements(arr_zval.value.arr) == 2); |
接下来遍历zend_array，根据我们对zend_array数据结构的了解，只需要遍历Bucket *arData数组即可。需要注意的是，删除的元素会留下空白的槽位，其类型是IS_UNDEF，我们需要跳过：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// traversal arr zend_array *arr = arr_zval.value.arr; int i; for (i = 0; i < arr->nNumUsed; ++i) { zval *val = &(arr->arData[i].val); // handle indirect zval if (Z_TYPE_P(val) == IS_INDIRECT) { val = Z_INDIRECT_P(val); } // empty slots if (Z_TYPE_P(val) == IS_UNDEF) { continue; } if (arr->arData[i].key) { // must be array["date"] TRACE("arr['%.*s']=%ld", arr->arData[i].key->len, arr->arData[i].key->val, val->value.lval); } else { // must be array[0] TRACE("arr[%ld]=%.*s", arr->arData[i].h, val->value.str->len, val->value.str->val); } } |
在遍历的过程中，我们判断Bucket.key=NULL说明是整形下标关联的数据（下标保存在h字段），否则说明是字符串索引的数据，我们将其内容分别输出。
那么，IS_INDIRECT又是什么呢？这是一个特殊类型的zval，叫做”间接zval”。据鸟哥说明，这种zval主要用在Zend引擎内部，zval.value.zv中保存了另外一个zval的地址，其实我也知道什么情况下会碰到这种zval，你大可先不实现这段代码，等到遇到了再加上也不迟。
查找一个key：
|
1 2 3 |
// find key zval *zv_in_arr = zend_hash_str_find_ind(arr_zval.value.arr, "date", sizeof("date") - 1); assert(zv_in_arr->value.lval == 20170811); |
删除一个key：
|
1 2 |
// del string key assert(zend_hash_str_del(arr_zval.value.arr, "date", sizeof("date") - 1) == SUCCESS); |
删除一个下标：
|
1 2 |
// del index key assert(zend_hash_index_del(arr_zval.value.arr, 0) == SUCCESS); |
最后，记得释放arr自身，它会对每个保存的value调用pDestructor回调方法释放资源，默认行为就是释放一个引用计数，所以你就不必事必躬亲了。
|
1 2 |
// release arr zval_ptr_dtor(&arr_zval); |
你会发现，packed array这个优化对于开发者来说是完全透明的，我们并不需要在意它的存在。
结语
本章你应该掌握：
- zend_array的数据结构与原理。
- zend_array常见的API用法。
如果文章帮助您解决了工作难题，您可以帮我点击屏幕上的任意广告，或者赞助少量费用来支持我的持续创作，谢谢~
1