深入PHP中的HashTable结构详解

hashtable是zend引擎中最重要、使用最广泛的数据结构，它被用来存储几乎所有的东西。
1.2.1 数据结构
hashtable数据结构定义如下：

typedef struct bucket {
 ulong h;    // 存放hash
 uint nkeylength;
 void *pdata;   // 指向value，是用户数据的副本
 void *pdataptr;
 struct bucket *plistnext; // plistnext和plistlast组成
 struct bucket *plistlast; // 整个hashtable的双链表
 struct bucket *pnext;  // pnext和plast用于组成某个hash对应
 struct bucket *plast;  // 的双链表
 char arkey[1];    // key
} bucket;

typedef struct _hashtable {
 uint ntablesize;
 uint ntablemask;
 uint nnumofelements;
 ulong nnextfreeelement;
 bucket *pinternalpointer; /* used for element traversal */
 bucket *plisthead;
 bucket *plisttail;
 bucket **arbuckets;   // hash数组
 dtor_func_t pdestructor; // hashtable初始化时指定，销毁bucket时调用
 zend_bool persistent;  // 是否采用c的内存分配例程
 unsigned char napplycount;
 zend_bool bapplyprotection;
#if zend_debug
 int inconsistent;
#endif
} hashtable;

总的来说，zend的hashtable是一种链表散列，同时也为线性遍历进行了优化，图示如下：

hashtable中包含两种数据结构，一个链表散列和一个双向链表，前者用于进行快速键-值查询，后者方便线性遍历和排序，一个bucket同时存在于这两个数据结构中。
关于该数据结构的几点解释：
链表散列中为什么使用双向链表？
一般的链表散列只需要按key进行操作，只需要单链表就够了。但是，zend有时需要从链表散列中删除给定的bucket，使用双链表可以非常高效的实现。
ntablemask是干什么的？
这个值用于hash值到arbuckets数组下标的转换。当初始化一个hashtable，zend首先为arbuckets数组分配ntablesize大小的内存，ntablesize取不小于用户指定大小的最小的2^n，即二进制的10*。ntablemask = ntablesize – 1，即二进制的01*，此时h & ntablemask就恰好落在 [0, ntablesize – 1] 里，zend就以其为index来访问arbuckets数组。
pdataptr是干什么的？
通常情况下，当用户插入一个键值对时，zend会将value复制一份，并将pdata指向value副本。复制操作需要调用zend内部例程 emalloc来分配内存，这是个非常耗时的操作，并且会消耗比value大的一块内存（多出的内存用于存放cookie），如果value很小的话，将会造成较大的浪费。考虑到hashtable多用于存放指针值，于是zend引入pdataptr，当value小到和指针一样长时，zend就直接将其复制到pdataptr里，并且将pdata指向pdataptr。这就避免了emalloc操作，同时也有利于提高cache命中率。
arkey大小为什么只有1？为什么不使用指针管理key？
arkey是存放key的数组，但其大小却只有1，并不足以放下key。在hashtable的初始化函数里可以找到如下代码：

  p = (bucket *) pemalloc(sizeof(bucket) - 1 + nkeylength, ht->persistent);

可见，zend为一个bucket分配了一块足够放下自己和key的内存，上半部分是bucket，下半部分是key，而arkey“恰好”是bucket的最后一个元素，于是就可以使用arkey来访问key了。这种手法在内存管理例程中最为常见，当分配内存时，实际上是分配了比指定大小要大的内存，多出的上半部分通常被称为cookie，它存储了这块内存的信息，比如块大小、上一块指针、下一块指针等，baidu的transmit程序就使用了这种方法。
不用指针管理key，是为了减少一次emalloc操作，同时也可以提高cache命中率。另一个必需的理由是，key绝大部分情况下是固定不变的，不会因为key变长了而导致重新分配整个bucket。这同时也解释了为什么不把value也一起作为数组分配了——因为value是可变的。

1.2.2 php数组
关于hashtable还有一个疑问没有回答，就是nnextfreeelement是干什么的？
不同于一般的散列，zend的hashtable允许用户直接指定hash值，而忽略key，甚至可以不指定key（此时，nkeylength为0）。同时，hashtable也支持append操作，用户连hash值也不用指定，只需要提供value，此时，zend就用nnextfreeelement作为hash，之后将nnextfreeelement递增。
hashtable的这种行为看起来很奇怪，因为这将无法按key访问value，已经完全不是个散列了。理解问题的关键在于，php数组就是使用hashtable实现的——关联数组使用正常的k-v映射将元素加入hashtable，其key为用户指定的字符串；非关联数组则直接使用数组下标作为hash值，不存在key；而当在一个数组中混合使用关联和非关联时，或者使用array_push操作时，就需要用nnextfreeelement了。
再来看value，php数组的value直接使用了zval这个通用结构，pdata指向的是zval*，按照上一节的介绍，这个zval*将直接存储在pdataptr里。由于直接使用了zval，数组的元素可以是任意php类型。
数组的遍历操作，即foreach、each等，是通过hashtable的双向链表来进行的，pinternalpointer作为游标记录了当前位置。

1.2.3 变量符号表
除了数组，hashtable还被用来存储许多其他数据，比如，php函数、变量符号、加载的模块、类成员等。
一个变量符号表就相当于一个关联数组，其key是变量名（可见，使用很长的变量名并不是个好主意），value是zval*。
在任一时刻php代码都可以看见两个变量符号表——symbol_table和active_symbol_table——前者用于存储全局变量，称为全局符号表；后者是个指针，指向当前活动的变量符号表，通常情况下就是全局符号表。但是，当每次进入一个php函数时（此处指的是用户使用php代码创建的函数），zend都会创建函数局部的变量符号表，并将active_symbol_table指向局部符号表。zend总是使用active_symbol_table来访问变量，这样就实现了局部变量的作用域控制。
但如果在函数局部访问标记为global的变量，zend会进行特殊处理——在active_symbol_table中创建symbol_table中同名变量的引用，如果symbol_table中没有同名变量则会先创建。

1.3 内存和文件
程序拥有的资源一般包括内存和文件，对于通常的程序，这些资源是面向进程的，当进程结束后，操作系统或c库会自动回收那些我们没有显式释放的资源。
但是，php程序有其特殊性，它是基于页面的，一个页面运行时同样也会申请内存或文件这样的资源，然而当页面运行结束后，操作系统或c库也许不会知道需要进行资源回收。比如，我们将php作为模块编译到apache里，并且以prefork或worker模式运行apache。这种情况下apache进程或线程是复用的，php页面分配的内存将永驻内存直到出core。
为了解决这种问题，zend提供了一套内存分配api，它们的作用和c中相应函数一样，不同的是这些函数从zend自己的内存池中分配内存，并且它们可以实现基于页面的自动回收。在我们的模块中，为页面分配的内存应该使用这些api，而不是c例程，否则zend会在页面结束时尝试efree掉我们的内存，其结果通常就是crush。
emalloc()
efree()
estrdup()
estrndup()
ecalloc()
erealloc()
另外，zend还提供了一组形如vcwd_xxx的宏用于替代c库和操作系统相应的文件api，这些宏能够支持php的虚拟工作目录，在模块代码中应该总是使用它们。宏的具体定义参见php源代码”tsrm/tsrm_virtual_cwd.h”。可能你会注意到，所有那些宏中并没有提供close操作，这是因为close的对象是已打开的资源，不涉及到文件路径，因此可以直接使用c或操作系统例程；同理，read/write之类的操作也是直接使用c或操作系统的例程。