很久以前就看到这篇文章，最近兴趣转移到php源码，在网上找一圈，在think in code 上找到了这篇地址：http://www.blankyao.cn/index.php/php-zend-hashtable.html
【正文】
在php的zend引擎中，有一个数据结构非常重要，它无处不在，是php数据存储的核心，各种常量、变量、函数、类、对象等都用它来组织，这个数据结构就是hashtable。
hashtable在通常的数据结构教材中也称作散列表，哈希表。其基本原理比较简单(如果你对其不熟悉，请查阅随便一本数据结构教材或在网上搜 索)，但php的实现有其独特的地方。理解了hashtable的数据存储结构，对我们分析php的源代码，特别是zend engine中的虚拟机的实现时，有很重要的帮助。它可以帮助我们在大脑中模拟一个完整的虚拟机的形象。它也是php中其它一些数据结构如数组实现的基 础。
zend hashtable的实现结合了双向链表和向量（数组）两种数据结构的优点，为php提供了非常高效的数据存储和查询机制。
let’s begin!
一、 hashtable的数据结构
在zend engine中的hashtable的实现代码主要包括zend_hash.h, zend_hash.c这两个文件中。zend hashtable包括两个主要的数据结构，其一是bucket（桶）结构，另一个是hashtable结构。bucket结构是用于保存数据的容器，而 hashtable结构则提供了对所有这些bucket(或桶列)进行管理的机制。
typedef struct bucket {ulong h; /* used for numeric indexing */uint nkeylength; /* key 长度 */void *pdata; /* 指向bucket中保存的数据的指针 */void *pdataptr; /* 指针数据 */struct bucket *plistnext; /* 指向hashtable桶列中下一个元素 */struct bucket *plistlast; /* 指向hashtable桶列中前一个元素 */struct bucket *pnext; /* 指向具有同一个hash值的桶列的后一个元素 */struct bucket *plast; /* 指向具有同一个hash值的桶列的前一个元素 */char arkey[1]; /* 必须是最后一个成员，key名称*/} bucket;
在zend hashtable中，每个数据元素(bucket)有一个键名(key)，它在整个hashtable中是唯一的，不能重复。根据键名可以唯一确定 hashtable中的数据元素。键名有两种表示方式。第一种方式使用字符串arkey作为键名，该字符串的长度为nkeylength。注意到在上面的 数据结构中arkey虽然只是一个长度为1的字符数组，但它并不意味着key只能是一个字符。实际上bucket是一个可变长的结构体，由于arkey是 bucket的最后一个成员变量，通过arkey与nkeylength结合可确定一个长度为nkeylength的key。这是c语言编程中的一个比较 常用的技巧。另一种键名的表示方式是索引方式，这时nkeylength总是0，长整型字段h就表示该数据元素的键名。简单的来说，即如果 nkeylength=0，则键名为h；否则键名为arkey, 键名的长度为nkeylength。
当nkeylength > 0时，并不表示这时的h值就没有意义。事实上，此时它保存的是arkey对应的hash值。不管hash函数怎么设计，冲突都是不可避免的，也就是说不同 的arkey可能有相同的hash值。具有相同hash值的bucket保存在hashtable的arbuckets数组(参考下面的解释)的同一个索 引对应的桶列中。这个桶列是一个双向链表，其前向元素，后向元素分别用plast, pnext来表示。新插入的bucket放在该桶列的最前面。
在bucket中，实际的数据是保存在pdata指针指向的内存块中，通常这个内存块是系统另外分配的。但有一种情况例外，就是当bucket保存 的数据是一个指针时，hashtable将不会另外请求系统分配空间来保存这个指针，而是直接将该指针保存到pdataptr中，然后再将pdata指向 本结构成员的地址。这样可以提高效率，减少内存碎片。由此我们可以看到php hashtable设计的精妙之处。如果bucket中的数据不是一个指针，pdataptr为null。
hashtable中所有的bucket通过plistnext, plistlast构成了一个双向链表。最新插入的bucket放在这个双向链表的最后。
注意在一般情况下，bucket并不能提供它所存储的数据大小的信息。所以在php的实现中，bucket中保存的数据必须具有管理自身大小的能力。
typedef struct _hashtable {uint ntablesize;uint ntablemask;uint nnumofelements;ulong nnextfreeelement;bucket *pinternalpointer;bucket *plisthead;bucket *plisttail;bucket **arbuckets;dtor_func_t pdestructor;zend_bool persistent;unsigned char napplycount;zend_bool bapplyprotection; #if zend_debugint inconsistent;#endif} hashtable;
在hashtable结构中，ntablesize指定了hashtable的大小，同时它限定了hashtable中能保存bucket的最大数量，此 数越大，系统为hashtable分配的内存就越多。为了提高计算效率，系统自动会将ntablesize调整到最小一个不小于ntablesize的2 的整数次方。也就是说，如果在初始化hashtable时指定一个ntablesize不是2的整数次方，系统将会自动调整ntablesize的值。即
ntablesize = 2ceil(log(ntablesize, 2)) 或 ntablesize = pow(ceil(log(ntablesize,2)))
例如，如果在初始化hashtable的时候指定ntablesize = 11，hashtable初始化程序会自动将ntablesize增大到16。
arbuckets是hashtable的关键，hashtable初始化程序会自动申请一块内存，并将其地址赋值给arbuckets，该内存大 小正好能容纳ntablesize个指针。我们可以将arbuckets看作一个大小为ntablesize的数组，每个数组元素都是一个指针，用于指向 实际存放数据的bucket。当然刚开始时每个指针均为null。
ntablemask的值永远是ntablesize – 1，引入这个字段的主要目的是为了提高计算效率，是为了快速计算bucket键名在arbuckets数组中的索引。
nnumberofelements记录了hashtable当前保存的数据元素的个数。当nnumberofelement大于ntablesize时，hashtable将自动扩展为原来的两倍大小。
nnextfreeelement记录hashtable中下一个可用于插入数据元素的arbuckets的索引。
plisthead, plisttail则分别表示bucket双向链表的第一个和最后一个元素，这些数据元素通常是根据插入的顺序排列的。也可以通过各种排序函数对其进行重 新排列。pinternalpointer则用于在遍历hashtable时记录当前遍历的位置，它是一个指针，指向当前遍历到的bucket，初始值是 plisthead。
pdestructor是一个函数指针，在hashtable的增加、修改、删除bucket时自动调用，用于处理相关数据的清理工作。
persistent标志位指出了bucket内存分配的方式。如果persisient为true，则使用操作系统本身的内存分配函数为bucket分配内存，否则使用php的内存分配函数。具体请参考php的内存管理。
napplycount与bapplyprotection结合提供了一个防止在遍历hashtable时进入递归循环时的一种机制。
inconsistent成员用于调试目的，只在php编译成调试版本时有效。表示hashtable的状态，状态有四种：
状态值 含义
ht_is_destroying 正在删除所有的内容，包括arbuckets本身
ht_is_destroyed 已删除，包括arbuckets本身
ht_cleaning 正在清除所有的arbuckets指向的内容，但不包括arbuckets本身
ht_ok 正常状态，各种数据完全一致
typedef struct _zend_hash_key {char *arkey; /* hash元素key名称 */uint nkeylength; /* hash 元素key长度 */ulong h; /* key计算出的hash值或直接指定的数值下标 */} zend_hash_key;
现在来看zend_hash_key结构就比较容易理解了。它通过arkey, nkeylength, h三个字段唯一确定了hashtable中的一个元素。
根据上面对hashtable相关数据结构的解释，我们可以画出hashtable的内存结构图：
hashtable结构
二、 zend hashtable的实现
本节具体介绍一下php中hashtable的实现。以下函数均取自于zend_hash.c。只要充分理解了上述数据结构，hashtable实现的代码并不难理解。
1 hashtable初始化
hashtable提供了一个zend_hash_init宏来完成hashtable的初始化操作。实际上它是通过下面的内部函数来实现的：
zend_api 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;bucket **tmp; set_inconsistent(ht_ok); if (nsize >= 0×80000000) {/* prevent overflow */ht->ntablesize = 0×80000000;} else {while ((1u << i) < nsize) { /* 自动调整ntablesize至2的n次方 */ i++; } ht->ntablesize = 1 << i;/* i的最小值为3，因此hashtable大小最小为8 */ } ht->ntablemask = ht->ntablesize - 1;ht->pdestructor = pdestructor;ht->arbuckets = null;ht->plisthead = null;ht->plisttail = null;ht->nnumofelements = 0;ht->nnextfreeelement = 0;ht->pinternalpointer = null;ht->persistent = persistent;ht->napplycount = 0;ht->bapplyprotection = 1; /* 根据persistent使用不同方式分配arbuckets内存，并将其所有指针初始化为null*//* uses ecalloc() so that bucket* == null */if (persistent) {tmp = (bucket **) calloc(ht->ntablesize, sizeof(bucket *));if (!tmp) {return failure;}ht->arbuckets = tmp;} else {tmp = (bucket **) ecalloc_rel(ht->ntablesize, sizeof(bucket *));if (tmp) {ht->arbuckets = tmp;}} return success;}
在以前的版本中，可以使用phashfunction来指定hash函数。但现php已强制使用djbx33a算法，因此实际上phashfunction这个参数并不会用到，保留在这里只是为了与以前的代码兼容。
2 增加、插入和修改元素
向hashtable中添加一个新的元素最关键的就是要确定将这个元素插入到arbuckets数组中的哪个位置。根据上面对bucket结构键名 的解释，我们可以知道有两种方式向hashtable添加一个新的元素。第一种方法是使用字符串作为键名来插入bucket；第二种方法是使用索引作为键 名来插入bucket。第二种方法具体又可以分为两种情况：指定索引或不指定索引，指定索引指的是强制将bucket插入到指定的索引位置中；不指定索引 则将bucket插入到nnextfreeelement对应的索引位置中。这几种插入数据的方法实现比较类似，不同的只是定位bucket的方法。
修改hashtable中的数据的方法与增加数据的方法也很类似。
我们先看第一种使用字符串作为键名增加或修改bucket的方法：
zend_api int _zend_hash_add_or_update(hashtable *ht, 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 <= 0) { #if zend_debug zend_puts(”zend_hash_update: can’t put in empty key\n”); #endif return failure; } /* 使用hash函数计算arkey的hash值 */ h = zend_inline_hash_func(arkey, nkeylength); /* 将hash值和ntablemask按位与后生成该元素在arbuckets中的索引。让它和 * ntablemask按位与是保证不会产生一个使得arbuckets越界的数组下标。 */ nindex = h & ht->ntablemask; p = ht->arbuckets[nindex]; /* 取得相应索引对应的bucket的指针 */ /* 检查对应的桶列中是否包含有数据元素(key, hash) */while (p != null) {if ((p->h == h) && (p->nkeylength == nkeylength)) {if (!memcmp(p->arkey, arkey, nkeylength)) {if (flag & hash_add) {return failure; // 对应的数据元素已存在，不能进行插入操作}handle_block_interruptions();#if zend_debugif (p->pdata == pdata) {zend_puts(”fatal error in zend_hash_update: p->pdata == pdata\n”);handle_unblock_interruptions();return failure;}#endifif (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;} /* hashtable中没有key对应的数据，新增一个bucket */p = (bucket *) pemalloc(sizeof(bucket) - 1 + nkeylength, ht->persistent);if (!p) {return failure;}memcpy(p->arkey, arkey, nkeylength);p->nkeylength = nkeylength;init_data(ht, p, pdata, ndatasize);p->h = h;// 将bucket加入到相应的桶列中connect_to_bucket_dllist(p, ht->arbuckets[nindex]);if (pdest) {*pdest = p->pdata;} handle_block_interruptions();// 将bucket 加入到hashtable的双向链表中connect_to_global_dllist(p, ht);ht->arbuckets[nindex] = p;handle_unblock_interruptions(); ht->nnumofelements++;// 如果hashtable已满，重新调整hashtable的大小。zend_hash_if_full_do_resize(ht); /* if the hash table is full, resize it */return success;}
因为这个函数是使用字符串作为键名来插入数据的，因此它首先检查nkeylength的值是否大于0，如果不是的话就直接退出。然后计算arkey对应的 hash值h，将其与ntablemask按位与后得到一个无符号整数nindex。这个nindex就是将要插入的bucket在arbuckets数 组中的索引位置。
现在已经有了arbuckets数组的一个索引，我们知道它包括的数据是一个指向bucket的双向链表的指针。如果这个双向链表不为空的话我们首先检查 这个双向链表中是否已经包含了用字符串arkey指定的键名的bucket，这样的bucket如果存在，并且我们要做的操作是插入新bucket(通过 flag标识)，这时就应该报错 – 因为在hashtable中键名不可以重复。如果存在，并且是修改操作，则使用在hashtable中指定了析构函数pdestructor对原来的 pdata指向的数据进行析构操作；然后将用新的数据替换原来的数据即可成功返回修改操作。
如果在hashtable中没有找到键名指定的数据，就将该数据封装到bucket中，然后插入hashtable。这里要注意的是如下的两个宏：
connect_to_bucket_dllist(p, ht->arbuckets[nindex])
connect_to_global_dllist(p, ht)
前者是将该bucket插入到指定索引的bucket双向链表中，后者是插入到整个hashtable的bucket双向链表中。两者的插入方式也不同，前者是将该bucket插入到双向链表的最前面，后者是插入到双向链表的最末端。
下面是第二种插入或修改bucket的方法，即使用索引的方法：
zend_api int _zend_hash_index_update_or_next_insert(hashtable *ht, ulong h, void *pdata, uint ndatasize, void **pdest, int flag zend_file_line_dc){uint nindex;bucket *p; is_consistent(ht); if (flag & hash_next_insert) {h = ht->nnextfreeelement;}nindex = h & ht->ntablemask; p = ht->arbuckets[nindex]; // 检查是否含有相应的数据while (p != null) {if ((p->nkeylength == 0) && (p->h == h)) {if (flag & hash_next_insert || flag & hash_add) {return failure;}//// …… 修改bucket数据，略//if ((long)h >= (long)ht->nnextfreeelement) {ht->nnextfreeelement = h + 1;}if (pdest) {*pdest = p->pdata;}return success;}p = p->pnext;}p = (bucket *) pemalloc_rel(sizeof(bucket) - 1, ht->persistent);if (!p) {return failure;}p->nkeylength = 0; /* numeric indices are marked by making the nkeylength == 0 */p->h = h;init_data(ht, p, pdata, ndatasize);if (pdest) {*pdest = p->pdata;} connect_to_bucket_dllist(p, ht->arbuckets[nindex]); handle_block_interruptions();ht->arbuckets[nindex] = p;connect_to_global_dllist(p, ht);handle_unblock_interruptions(); if ((long)h >= (long)ht->nnextfreeelement) {ht->nnextfreeelement = h + 1;}ht->nnumofelements++;zend_hash_if_full_do_resize(ht);return success;}
flag标志指明当前操作是hash_next_insert(不指定索引插入或修改), hash_add(指定索引插入)还是hash_update(指定索引修改)。由于这些操作的实现代码基本相同，因此统一合并成了一个函数，再用flag加以区分。
本函数基本与前一个相同，不同的是如果确定插入到arbuckets数组中的索引的方法。如果操作是hash_next_insert，则直接使用nnextfreeelement作为插入的索引。注意nnextfreeelement的值是如何使用和更新的。
3 访问元素
同样，hashtable用两种方式来访问元素，一种是使用字符串arkey的zend_hash_find()；另一种是使用索引的访问方式zend_hash_index_find()。由于其实现的代码很简单，分析工作就留给读者自已完成。
4 删除元素
hashtable删除数据均使用zend_hash_del_key_or_index()函数来完成，其代码也较为简单，这里也不再详细分析。需要的是注意如何根据arkey或h来计算出相应的下标，以及两个双向链表的指针的处理。
5 遍历元素
/* this is used to recurse elements and selectively delete certain entries* from a hashtable. apply_func() receives the data and decides if the entry* should be deleted or recursion should be stopped. the following three* return codes are possible:* zend_hash_apply_keep - continue* zend_hash_apply_stop - stop iteration* zend_hash_apply_remove - delete the element, combineable with the former*/ zend_api void zend_hash_apply(hashtable *ht, apply_func_t apply_func tsrmls_dc){bucket *p; is_consistent(ht); hash_protect_recursion(ht);p = ht->plisthead;while (p != null) {int result = apply_func(p->pdata tsrmls_cc); if (result & zend_hash_apply_remove) {p = zend_hash_apply_deleter(ht, p);} else {p = p->plistnext;}if (result & zend_hash_apply_stop) {break;}}hash_unprotect_recursion(ht);}
因为hashtable中所有bucket都可以通过plisthead指向的双向链表来访问，因此遍历hashtable的实现也比较简单。这里值得一 提的是对当前遍历到的bucket的处理使用了一个apply_func_t类型的回调函数。根据实际需要，该回调函数返回下面值之一：
zend_hash_apply_keep
zend_hash_apply_stop
zend_hash_apply_remove
它们分别表示继续遍历，停止遍历或删除相应元素后继续遍历。
还有一个要注意的问题就是遍历时的防止递归的问题，也就是防止对同一个hashtable同时进行多次遍历。这是用下面两个宏来实现的：
hash_protect_recursion(ht)
hash_unprotect_recursion(ht)
其主要原理是如果遍历保护标志bapplyprotection为真，则每次进入遍历函数时将napplycount值加1，退出遍历函数时将napplycount值减1。开始遍历之前如果发现napplycount > 3就直接报告错误信息并退出遍历。
上面的apply_func_t不带参数。hashtable还提供带一个参数或可变参数的回调方式，对应的遍历函数分别为:
typedef int (*apply_func_arg_t)(void *pdest,void *argument tsrmls_dc);void zend_hash_apply_with_argument(hashtable *ht,apply_func_arg_t apply_func, void *data tsrmls_dc); typedef int (*apply_func_args_t)(void *pdest,int num_args, va_list args, zend_hash_key *hash_key);void zend_hash_apply_with_arguments(hashtable *ht,apply_func_args_t apply_func, int numargs, …);
除了上面提供的几种提供外，还有许多其它操作hashtable的api。如排序、hashtable的拷贝与合并等等。只要充分理解了上述hashtable的数据结构，理解这些代码并不困难。
以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注！
相关推荐：
php实现负载均衡下的session共用功能php技巧
php-app开发接口加密详解_php技巧
以上就是关于php源代码中zend hashtable的解析的详细内容。