首頁 > 文章 > 後端開發 > 關於PHP原始碼中Zend HashTable的解析

關於PHP原始碼中Zend HashTable的解析

不言原創: 2018-06-28 16:08:172569瀏覽

這篇文章主要介紹了關於PHP原始碼中Zend HashTable的解析，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

很久以前就看到這篇文章，最近興趣轉移到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的内存结构图：

關於PHP原始碼中Zend 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中文网！

關於PHP原始碼中Zend HashTable的解析

相關文章