PHP7扩展开发教程[9] – 如何使用哈希表?

确保你已阅读《PHP7扩展开发教程[8] – 如何访问超级全局变量?》。

哈希表即zend_array数据结构,它是zval的底层数据类型之一,也是最为复杂的一个结构。

在PHP中的array()即可以表达数组,又可以表达字典,这样的灵活性在zend_array中都有对应的代码实现。

理论先行

鉴于已经有很不错的博客介绍了PHP7的zend_array,所以本章开始前请先自己学习一下这篇文章:

PHP 7中新的Hashtable实现和性能改进》。

这里盗用一张网上的图片,是一张比较清晰的PHP7 hashtable结构示意图:

从图片来看,arData左侧部分是uint32的哈希桶,右侧是按插入顺序排列的Bucket元素列表,整体来看还是很清晰的。

下面,我将根据上述博客中的几个知识点,对相关的核心代码进行展开讲解,希望可以作为一个补充帮助你进一步理解zend_array的实现原理。

先看数据结构:

分别讲解一下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。

上面的方法完成”懒惰”初始化,arData并没有分配实际内存,并且这个zend_array的类型也没有确定。

接下来,当我们调用任意插入/更新zend_array的函数时,它们的函数头部都会检查zend_array是否已经”真正”初始化,如果没有则立即初始化。这个检查方法是这样的:

它是通过判断zend_array的flags里是否有HASH_FLAG_INITIALIZED来判定的,最终通过zend_hash_real_init_ex完成”真正”的初始化:

第一个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:

第2个函数用于向zend_array插入/更新”下标-值”,它接受zend_ulong的key:

以第2个函数为例,它非常能说明zend_array的背后原理:

在第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的转换原理很简单:

通过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。

这样初始化数组(懒惰初始化),其底层实现我们已经见过:

其中资源销毁函数传递了ZVAL_PTR_DTOR,其实就是zval_ptr_dtor,在之前的章节也提到过。

向array添加键值类型的数据,可以通过add_assoc_xxx系列便捷函数实现,它们底层最终调用了:

zend_hash_str_exists用于判断一个key是否存在,对应的zend_hash_index_exists用于判断整形下标是否存在。

向下一个整形下标添加一条数据:

zend_array内部维护了我们最后一个整形下标的大小,键值类型不会影响整形下标的自增,所以”hahaha”被保存在了整形下标0。

像这样获取数组的元素个数,就和PHP的count一样:

接下来遍历zend_array,根据我们对zend_array数据结构的了解,只需要遍历Bucket *arData数组即可。需要注意的是,删除的元素会留下空白的槽位,其类型是IS_UNDEF,我们需要跳过:

在遍历的过程中,我们判断Bucket.key=NULL说明是整形下标关联的数据(下标保存在h字段),否则说明是字符串索引的数据,我们将其内容分别输出。

那么,IS_INDIRECT又是什么呢?这是一个特殊类型的zval,叫做”间接zval”。据鸟哥说明,这种zval主要用在Zend引擎内部,zval.value.zv中保存了另外一个zval的地址,其实我也知道什么情况下会碰到这种zval,你大可先不实现这段代码,等到遇到了再加上也不迟。

查找一个key:

删除一个key:

删除一个下标:

最后,记得释放arr自身,它会对每个保存的value调用pDestructor回调方法释放资源,默认行为就是释放一个引用计数,所以你就不必事必躬亲了。

你会发现,packed array这个优化对于开发者来说是完全透明的,我们并不需要在意它的存在。

结语

本章你应该掌握:

  • zend_array的数据结构与原理。
  • zend_array常见的API用法。

One response to “PHP7扩展开发教程[9] – 如何使用哈希表?

发表评论

电子邮件地址不会被公开。