快捷導(dǎo)航

PHP 源代碼分析 Zend HashTable詳解第2/3頁(yè)

更新時(shí)間：2009年08月10日 10:51:09 作者：

在PHP的Zend引擎中，有一個(gè)數(shù)據(jù)結(jié)構(gòu)非常重要，它無(wú)處不在，是PHP數(shù)據(jù)存儲(chǔ)的核心，各種常量、變量、函數(shù)、類(lèi)、對(duì)象等都用它來(lái)組織，這個(gè)數(shù)據(jù)結(jié)構(gòu)就是HashTable。

在HashTable結(jié)構(gòu)中，nTableSize指定了HashTable的大小，同時(shí)它限定了HashTable中能保存Bucket的最大數(shù)量，此數(shù)越大，系統(tǒng)為HashTable分配的內(nèi)存就越多。為了提高計(jì)算效率，系統(tǒng)自動(dòng)會(huì)將nTableSize調(diào)整到最小一個(gè)不小于nTableSize的2的整數(shù)次方。也就是說(shuō)，如果在初始化HashTable時(shí)指定一個(gè)nTableSize不是2的整數(shù)次方，系統(tǒng)將會(huì)自動(dòng)調(diào)整nTableSize的值。即
nTableSize = 2ceil(log(nTableSize, 2)) 或 nTableSize = pow(ceil(log(nTableSize,2)))
例如，如果在初始化HashTable的時(shí)候指定nTableSize = 11，HashTable初始化程序會(huì)自動(dòng)將nTableSize增大到16。
arBuckets是HashTable的關(guān)鍵，HashTable初始化程序會(huì)自動(dòng)申請(qǐng)一塊內(nèi)存，并將其地址賦值給arBuckets，該內(nèi)存大小正好能容納nTableSize個(gè)指針。我們可以將arBuckets看作一個(gè)大小為nTableSize的數(shù)組，每個(gè)數(shù)組元素都是一個(gè)指針，用于指向?qū)嶋H存放數(shù)據(jù)的Bucket。當(dāng)然剛開(kāi)始時(shí)每個(gè)指針均為NULL。
nTableMask的值永遠(yuǎn)是nTableSize – 1，引入這個(gè)字段的主要目的是為了提高計(jì)算效率，是為了快速計(jì)算Bucket鍵名在arBuckets數(shù)組中的索引。
nNumberOfElements記錄了HashTable當(dāng)前保存的數(shù)據(jù)元素的個(gè)數(shù)。當(dāng)nNumberOfElement大于nTableSize時(shí)，HashTable將自動(dòng)擴(kuò)展為原來(lái)的兩倍大小。
nNextFreeElement記錄HashTable中下一個(gè)可用于插入數(shù)據(jù)元素的arBuckets的索引。
pListHead, pListTail則分別表示Bucket雙向鏈表的第一個(gè)和最后一個(gè)元素，這些數(shù)據(jù)元素通常是根據(jù)插入的順序排列的。也可以通過(guò)各種排序函數(shù)對(duì)其進(jìn)行重新排列。pInternalPointer則用于在遍歷HashTable時(shí)記錄當(dāng)前遍歷的位置，它是一個(gè)指針，指向當(dāng)前遍歷到的Bucket，初始值是pListHead。
pDestructor是一個(gè)函數(shù)指針，在HashTable的增加、修改、刪除Bucket時(shí)自動(dòng)調(diào)用，用于處理相關(guān)數(shù)據(jù)的清理工作。
persistent標(biāo)志位指出了Bucket內(nèi)存分配的方式。如果persisient為T(mén)RUE，則使用操作系統(tǒng)本身的內(nèi)存分配函數(shù)為Bucket分配內(nèi)存，否則使用PHP的內(nèi)存分配函數(shù)。具體請(qǐng)參考PHP的內(nèi)存管理。
nApplyCount與bApplyProtection結(jié)合提供了一個(gè)防止在遍歷HashTable時(shí)進(jìn)入遞歸循環(huán)時(shí)的一種機(jī)制。
inconsistent成員用于調(diào)試目的，只在PHP編譯成調(diào)試版本時(shí)有效。表示HashTable的狀態(tài)，狀態(tài)有四種：
狀態(tài)值含義
HT_IS_DESTROYING 正在刪除所有的內(nèi)容，包括arBuckets本身
HT_IS_DESTROYED 已刪除，包括arBuckets本身
HT_CLEANING 正在清除所有的arBuckets指向的內(nèi)容，但不包括arBuckets本身
HT_OK 正常狀態(tài)，各種數(shù)據(jù)完全一致

復(fù)制代碼代碼如下:

typedef struct _zend_hash_key { 
char *arKey; /* hash元素key名稱(chēng) */ 
uint nKeyLength; /* hash 元素key長(zhǎng)度 */ 
ulong h; /* key計(jì)算出的hash值或直接指定的數(shù)值下標(biāo) */ 
} zend_hash_key; 

現(xiàn)在來(lái)看zend_hash_key結(jié)構(gòu)就比較容易理解了。它通過(guò)arKey, nKeyLength, h三個(gè)字段唯一確定了HashTable中的一個(gè)元素。
根據(jù)上面對(duì)HashTable相關(guān)數(shù)據(jù)結(jié)構(gòu)的解釋?zhuān)覀兛梢援?huà)出HashTable的內(nèi)存結(jié)構(gòu)圖：

二、 Zend HashTable的實(shí)現(xiàn)
本節(jié)具體介紹一下PHP中HashTable的實(shí)現(xiàn)。以下函數(shù)均取自于zend_hash.c。只要充分理解了上述數(shù)據(jù)結(jié)構(gòu)，HashTable實(shí)現(xiàn)的代碼并不難理解。
1 HashTable初始化
HashTable提供了一個(gè)zend_hash_init宏來(lái)完成HashTable的初始化操作。實(shí)際上它是通過(guò)下面的內(nèi)部函數(shù)來(lái)實(shí)現(xiàn)的：

復(fù)制代碼代碼如下:

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 >= 0x80000000) { 
/* prevent overflow */ 
ht->nTableSize = 0x80000000; 
} else { 
while ((1U << i) < nSize) { /* 自動(dòng)調(diào)整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; 
/* 根據(jù)persistent使用不同方式分配arBuckets內(nèi)存，并將其所有指針初始化為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來(lái)指定hash函數(shù)。但現(xiàn)PHP已強(qiáng)制使用DJBX33A算法，因此實(shí)際上pHashFunction這個(gè)參數(shù)并不會(huì)用到，保留在這里只是為了與以前的代碼兼容。
2 增加、插入和修改元素
向HashTable中添加一個(gè)新的元素最關(guān)鍵的就是要確定將這個(gè)元素插入到arBuckets數(shù)組中的哪個(gè)位置。根據(jù)上面對(duì)Bucket結(jié)構(gòu)鍵名的解釋?zhuān)覀兛梢灾烙袃煞N方式向HashTable添加一個(gè)新的元素。第一種方法是使用字符串作為鍵名來(lái)插入Bucket；第二種方法是使用索引作為鍵名來(lái)插入Bucket。第二種方法具體又可以分為兩種情況：指定索引或不指定索引，指定索引指的是強(qiáng)制將Bucket插入到指定的索引位置中；不指定索引則將Bucket插入到nNextFreeElement對(duì)應(yīng)的索引位置中。這幾種插入數(shù)據(jù)的方法實(shí)現(xiàn)比較類(lèi)似，不同的只是定位Bucket的方法。
修改HashTable中的數(shù)據(jù)的方法與增加數(shù)據(jù)的方法也很類(lèi)似。
我們先看第一種使用字符串作為鍵名增加或修改Bucket的方法：

復(fù)制代碼代碼如下:

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); // 調(diào)試信息輸出 
if (nKeyLength <= 0) { 
#if ZEND_DEBUG 
ZEND_PUTS("zend_hash_update: Can't put in empty key\n"); 
#endif 
return FAILURE; 
} 
/* 使用hash函數(shù)計(jì)算arKey的hash值 */ 
h = zend_inline_hash_func(arKey, nKeyLength); 
/* 將hash值和nTableMask按位與后生成該元素在arBuckets中的索引。讓它和 
* nTableMask按位與是保證不會(huì)產(chǎn)生一個(gè)使得arBuckets越界的數(shù)組下標(biāo)。 
*/ 
nIndex = h & ht->nTableMask; 
p = ht->arBuckets[nIndex]; /* 取得相應(yīng)索引對(duì)應(yīng)的Bucket的指針 */ 
/* 檢查對(duì)應(yīng)的桶列中是否包含有數(shù)據(jù)元素(key, hash) */ 
while (p != NULL) { 
if ((p->h == h) && (p->nKeyLength == nKeyLength)) { 
if (!memcmp(p->arKey, arKey, nKeyLength)) { 
if (flag & HASH_ADD) { 
return FAILURE; // 對(duì)應(yīng)的數(shù)據(jù)元素已存在，不能進(jìn)行插入操作 
} 
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) { 
/* 如果數(shù)據(jù)元素存在，對(duì)原來(lái)的數(shù)據(jù)進(jìn)行析構(gòu)操作 */ 
ht->pDestructor(p->pData); 
} 
/* 用新的數(shù)據(jù)來(lái)更新原來(lái)的數(shù)據(jù) */ 
UPDATE_DATA(ht, p, pData, nDataSize); 
if (pDest) { 
*pDest = p->pData; 
} 
HANDLE_UNBLOCK_INTERRUPTIONS(); 
return SUCCESS; 
} 
} 
p = p->pNext; 
} 

/* HashTable中沒(méi)有key對(duì)應(yīng)的數(shù)據(jù)，新增一個(gè)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加入到相應(yīng)的桶列中 
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已滿(mǎn)，重新調(diào)整HashTable的大小。 
ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ 
return SUCCESS; 
}