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ù)、類、對(duì)象等都用它來組織，這個(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ù)次方。也就是說，如果在初始化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)然剛開始時(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ò)展為原來的兩倍大小。
nNextFreeElement記錄HashTable中下一個(gè)可用于插入數(shù)據(jù)元素的arBuckets的索引。
pListHead, pListTail則分別表示Bucket雙向鏈表的第一個(gè)和最后一個(gè)元素，這些數(shù)據(jù)元素通常是根據(jù)插入的順序排列的。也可以通過各種排序函數(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為TRUE，則使用操作系統(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名稱 */
uint nKeyLength; /* hash 元素key長(zhǎng)度 */
ulong h; /* key計(jì)算出的hash值或直接指定的數(shù)值下標(biāo) */
} zend_hash_key;
現(xiàn)在來看zend_hash_key結(jié)構(gòu)就比較容易理解了。它通過arKey, nKeyLength, h三個(gè)字段唯一確定了HashTable中的一個(gè)元素。
根據(jù)上面對(duì)HashTable相關(guān)數(shù)據(jù)結(jié)構(gòu)的解釋，我們可以畫出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宏來完成HashTable的初始化操作。實(shí)際上它是通過下面的內(nèi)部函數(shù)來實(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來指定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)鍵名的解釋，我們可以知道有兩種方式向HashTable添加一個(gè)新的元素。第一種方法是使用字符串作為鍵名來插入Bucket；第二種方法是使用索引作為鍵名來插入Bucket。第二種方法具體又可以分為兩種情況：指定索引或不指定索引，指定索引指的是強(qiáng)制將Bucket插入到指定的索引位置中；不指定索引則將Bucket插入到nNextFreeElement對(duì)應(yīng)的索引位置中。這幾種插入數(shù)據(jù)的方法實(shí)現(xiàn)比較類似，不同的只是定位Bucket的方法。
修改HashTable中的數(shù)據(jù)的方法與增加數(shù)據(jù)的方法也很類似。
我們先看第一種使用字符串作為鍵名增加或修改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ì)原來的數(shù)據(jù)進(jìn)行析構(gòu)操作 */
ht->pDestructor(p->pData);
}
/* 用新的數(shù)據(jù)來更新原來的數(shù)據(jù) */
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p->pData;
}
HANDLE_UNBLOCK_INTERRUPTIONS();
return SUCCESS;
}
}
p = p->pNext;
}
/* HashTable中沒有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已滿，重新調(diào)整HashTable的大小。
ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
return SUCCESS;
}
您可能感興趣的文章:
- Zend Framework教程之Zend_Db_Table用法詳解
- Zend?Framework框架db類select查詢器join鏈表使用示例
- Zend Framework入門知識(shí)點(diǎn)小結(jié)
- Zend Framework緩存Cache用法簡(jiǎn)單實(shí)例
- Zend Framework連接Mysql數(shù)據(jù)庫(kù)實(shí)例分析
- Zend Framework+smarty用法實(shí)例詳解
- Zend Framework教程之Application和Bootstrap用法詳解
- Zend Framework教程之Loader以及PluginLoader用法詳解
- Zend Framework教程之Autoloading用法詳解
- Zend Framework教程之Resource Autoloading用法實(shí)例
- Zend Framework教程之MVC框架的Controller用法分析
- Zend Framework教程之路由功能Zend_Controller_Router詳解
- Zend Framework教程之Zend_Controller_Plugin插件用法詳解
- Zend Framework教程之Zend_Db_Table_Row用法實(shí)例分析
相關(guān)文章
PHP Session 變量的使用方法詳解與實(shí)例代碼
在php中Session經(jīng)常用來驗(yàn)證用戶注冊(cè)或登錄之后的驗(yàn)證了，下面我來總結(jié)session變量的一些常用實(shí)例與用法介紹2013-09-09
使用PHP快捷查詢關(guān)鍵字在搜索引擎中的排名位置, 原理很簡(jiǎn)單,不講了2010-01-01
對(duì)"鉤子"這個(gè)概念其實(shí)不熟悉，最近看到一個(gè)php框架中用到這種機(jī)制來擴(kuò)展項(xiàng)目，所以大概來了解下。 所謂Hook機(jī)制，是從Windows編程中流行開的一種技術(shù)2023-01-01
PHP中call_user_func_array回調(diào)函數(shù)的用法示例
這篇文章主要給大家介紹了PHP中call_user_func_array回調(diào)函數(shù)的用法，文中給出了詳細(xì)的示例代碼，相信對(duì)大家的理解和學(xué)習(xí)很有幫助，有需要的朋友們可以參考借鑒，下面來一起學(xué)習(xí)學(xué)習(xí)吧。2016-11-11
php基于socket實(shí)現(xiàn)SMTP發(fā)送郵件的方法
這篇文章主要介紹了php基于socket實(shí)現(xiàn)SMTP發(fā)送郵件的方法,實(shí)例分析了php采用socket實(shí)現(xiàn)smtp發(fā)送郵件的原理與技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-03-03
php實(shí)現(xiàn)數(shù)組中索引關(guān)聯(lián)數(shù)據(jù)轉(zhuǎn)換成json對(duì)象的方法
這篇文章主要介紹了php實(shí)現(xiàn)數(shù)組中索引關(guān)聯(lián)數(shù)據(jù)轉(zhuǎn)換成json對(duì)象的方法,基于Yii框架分析了php數(shù)組與json格式數(shù)據(jù)的轉(zhuǎn)換技巧,需要的朋友可以參考下2015-07-07
在本篇文章里小編給大家分享的是一篇關(guān)于PHP高并發(fā)和大流量解決方案內(nèi)容，有興趣的朋友們可以參考下。2019-12-12
這篇文章主要介紹了PHP生成圖表pChart的示例解析，文中通過解析pChartd 工作流程和不同圖表的代碼展示，講解的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考價(jià)值，有需要的來和小編一起學(xué)習(xí)把吧2020-07-07
PHP實(shí)現(xiàn)變色驗(yàn)證碼實(shí)例
驗(yàn)證碼想必大家都有見到過吧，在本文為大家介紹下PHP如何實(shí)現(xiàn)變色驗(yàn)證碼，感興趣的朋友可以參考下2014-01-01
這篇文章主要介紹了PHP文件與目錄操作,涉及php針對(duì)文件與目錄的遍歷、判斷與排序相關(guān)操作技巧,注釋中備有較為詳細(xì)的說明,需要的朋友可以參考下2016-12-12