庆亮的博客

PHP源代码分析之HashTable

从PHP的zval结构体可以看出PHP使用HashTable来保存数组信息，PHP的HashTable使用了一些技巧，这些技巧是PHP高效数组操作的直接原因，源代码在PHP源代码目录的Zend/zend_hash.h  Zend/zend_hash.c 中。先来看看Zend HashTable的定义：

参数解释：

nTableSize  哈希表的大小

nTableMask  数值上等于nTableSize -1 

nNumOfElements 记录了当前HashTable中保存的记录数

nNextFreeElement  指向下一个空闲的Bucket（之后有解释）

pInternalPointer 

pListHead  指向Bucket列表头部

pListTail    指向Bucket列表尾部

arBuckets

pDestructor   一个函数指针，在HashTable发生增、删、改时自动调用，以完成某些清理工作。

persistent   是否是持久

nApplyCount

aApplyProtection 这两个参数用于放置在遍历时发生无限递归

 

 

可以看到Bucket是一个双向链表，参数解释：

h  当元素使用数字索引时使用

nKeyLength  当使用字符串索引时，该选项表示字符串索引的长度，而字符串则保存在Bucket结构体的最后一个元素arKey中。尽管arKey被声明为一个只有一个元素的数组，但是这并不妨碍我们在其中保存字符串，因为数组名可以看做指针，将arKey作为结构体的最后一个元素则Bucket结构体就成了变长结构体，而该变长结构体的长度则需要nKeyLength的辅助才能确定，这是C语言中的常见技巧。

pNext指向具有相同hash值的下一个bucket元素，无论HashTable设计的如何完美，冲突都是难免的。当采用字符串索引时，h成员变量存放的就是字符串索引的hash值。

pData指向保存的数据，如果数据本身又为指针，则用pDataPtr来保存对应的指针，而辞此时pData则指向自身结构体的pDataPtr。

接着看Zend HashTable的一些相关函数:

#define HASH_PROTECT_RECURSION(ht) \

if ((ht)->bApplyProtection) { \

if ((ht)->nApplyCount++ >= 3) { \

zend_error(E_ERROR, "Nesting level too deep - recursive dependency?"); \

} \

}

这个宏用于防止循环引用。

#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \

if ((ht)->nNumOfElements > (ht)->nTableSize) { \

zend_hash_do_resize(ht); \

}

该宏用于判断HashTable中的元素是否超过了HashTable表的大小，如果超过则扩展HashTable的大小，查看zend_hash_do_resize的代码可以看到每次扩展大小都是成倍的。

看看Zend 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; //这里可以看出数组默认的初始化为8

Bucket **tmp;

SET_INCONSISTENT(HT_OK);   // 用于调试 

if (nSize >= 0×80000000) {

/* prevent overflow */

ht->nTableSize = 0×80000000;

} else {

while ((1U << i) < nSize) {

i++;

}

ht->nTableSize = 1 << i;

}

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;

/* 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;

}

可以看到HashTable的大小被自动的初始化为2的n次方，persistent参数用于指示是否是“永久”方式分配内存，如果是则采用系统分配内存方法，否则采用ZendMM的内存分配方式，关于ZendMM请搜索PHP内存管理的相关内容。

申请得到的bucket指针内存块都放在HashTable的arBucket中，可以把这段内存块看成一个数组，数组中的每个元素都指向一个实际的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值

h = zend_inline_hash_func(arKey, nKeyLength);

//用hash值和nTableMask进行按位于运算，用于索引的快速定位

//按位于后的结果不可能大于nTableMask的值

//结合下面的代码，可以看出这段代码的巧妙

nIndex = h & ht->nTableMask;

p = ht->arBuckets[nIndex];

//如果p不为NULL，则产生了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_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;

}

//来到这里说明是增加元素操作

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;

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 CONNECT_TO_BUCKET_DLLIST(element, list_head) \

(element)->pNext = (list_head); \

(element)->pLast = NULL; \

if ((element)->pNext) { \

(element)->pNext->pLast = (element); \

}

这个宏用于将一个bucket加入到bucket链表中

#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); \

}

该宏用于将一个bucket加入到HashTable的链表中

 

下面列出zend 封装好的函数或者宏：

zend_hash_add_empty_element   给数组增加一个空元素

zend_hash_do_resize  扩大哈希表的大小

_zend_hash_index_update_or_next_insert 插入或者更新指定数字索引的元素

zend_hash_del_key_or_index  根据索引删除HashTable中的元素

zend_hash_apply   遍历HashTable，注意当中使用了两个宏HASH_PROTECT_RECURSION 和 HASH_UNPROTECT_RECURSION来防止遍历陷入死循环。

#define HASH_PROTECT_RECURSION(ht) \

if ((ht)->bApplyProtection) { \

if ((ht)->nApplyCount++ >= 3) { \

zend_error(E_ERROR, "Nesting level too deep - recursive dependency?"); \

} \

}

#define HASH_UNPROTECT_RECURSION(ht) \

if ((ht)->bApplyProtection) { \

(ht)->nApplyCount–; \

}

zend_hash_reverse_apply  反向遍历HashTable

zend_hash_copy  拷贝

_zend_hash_merge  合并

zend_hash_find  字符串索引方式查找

zend_hash_index_find  数值索引方法查找

zend_hash_quick_find   上面两个函数的封装

zend_hash_exists  是否存在索引

zend_hash_index_exists 是否存在索引

zend_hash_quick_exists  上面两个方法的封装

ZEND_API int zend_hash_num_elements(HashTable *ht)

{

IS_CONSISTENT(ht);

return ht->nNumOfElements;

}

获得数组大小

 

为了更加方便的操作HashTable，Zend将上面的宏做了进一步的封装。

（上述内容截自 http://devzone.zend.com/node/view/id/1022#Heading5）

 

呵呵，非常方便的操作数组的方式。