快捷導(dǎo)航

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

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

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

HashTable在通常的數(shù)據(jù)結(jié)構(gòu)教材中也稱作散列表，哈希表。其基本原理比較簡(jiǎn)單(如果你對(duì)其不熟悉，請(qǐng)查閱隨便一本數(shù)據(jù)結(jié)構(gòu)教材或在網(wǎng)上搜索)，但PHP的實(shí)現(xiàn)有其獨(dú)特的地方。理解了HashTable的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，對(duì)我們分析PHP的源代碼，特別是Zend Engine中的虛擬機(jī)的實(shí)現(xiàn)時(shí)，有很重要的幫助。它可以幫助我們?cè)诖竽X中模擬一個(gè)完整的虛擬機(jī)的形象。它也是PHP中其它一些數(shù)據(jù)結(jié)構(gòu)如數(shù)組實(shí)現(xiàn)的基礎(chǔ)。
Zend HashTable的實(shí)現(xiàn)結(jié)合了雙向鏈表和向量（數(shù)組）兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)，為PHP提供了非常高效的數(shù)據(jù)存儲(chǔ)和查詢機(jī)制。
Let's begin!
一、 HashTable的數(shù)據(jù)結(jié)構(gòu)
在Zend Engine中的HashTable的實(shí)現(xiàn)代碼主要包括zend_hash.h, zend_hash.c這兩個(gè)文件中。Zend HashTable包括兩個(gè)主要的數(shù)據(jù)結(jié)構(gòu)，其一是Bucket（桶）結(jié)構(gòu)，另一個(gè)是HashTable結(jié)構(gòu)。Bucket結(jié)構(gòu)是用于保存數(shù)據(jù)的容器，而HashTable結(jié)構(gòu)則提供了對(duì)所有這些Bucket(或桶列)進(jìn)行管理的機(jī)制。

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

typedef struct bucket { 
ulong h; /* Used for numeric indexing */ 
uint nKeyLength; /* key 長(zhǎng)度 */ 
void *pData; /* 指向Bucket中保存的數(shù)據(jù)的指針 */ 
void *pDataPtr; /* 指針數(shù)據(jù) */ 
struct bucket *pListNext; /* 指向HashTable桶列中下一個(gè)元素 */ 
struct bucket *pListLast; /* 指向HashTable桶列中前一個(gè)元素 */ 
struct bucket *pNext; /* 指向具有同一個(gè)hash值的桶列的后一個(gè)元素 */ 
struct bucket *pLast; /* 指向具有同一個(gè)hash值的桶列的前一個(gè)元素 */ 
char arKey[1]; /* 必須是最后一個(gè)成員，key名稱*/ 
} Bucket; 

在Zend HashTable中，每個(gè)數(shù)據(jù)元素(Bucket)有一個(gè)鍵名(key)，它在整個(gè)HashTable中是唯一的，不能重復(fù)。根據(jù)鍵名可以唯一確定HashTable中的數(shù)據(jù)元素。鍵名有兩種表示方式。第一種方式使用字符串a(chǎn)rKey作為鍵名，該字符串的長(zhǎng)度為nKeyLength。注意到在上面的數(shù)據(jù)結(jié)構(gòu)中arKey雖然只是一個(gè)長(zhǎng)度為1的字符數(shù)組，但它并不意味著key只能是一個(gè)字符。實(shí)際上Bucket是一個(gè)可變長(zhǎng)的結(jié)構(gòu)體，由于arKey是Bucket的最后一個(gè)成員變量，通過(guò)arKey與nKeyLength結(jié)合可確定一個(gè)長(zhǎng)度為nKeyLength的key。這是C語(yǔ)言編程中的一個(gè)比較常用的技巧。另一種鍵名的表示方式是索引方式，這時(shí)nKeyLength總是0，長(zhǎng)整型字段h就表示該數(shù)據(jù)元素的鍵名。簡(jiǎn)單的來(lái)說(shuō)，即如果nKeyLength=0，則鍵名為h；否則鍵名為arKey, 鍵名的長(zhǎng)度為nKeyLength。
當(dāng)nKeyLength > 0時(shí)，并不表示這時(shí)的h值就沒(méi)有意義。事實(shí)上，此時(shí)它保存的是arKey對(duì)應(yīng)的hash值。不管hash函數(shù)怎么設(shè)計(jì)，沖突都是不可避免的，也就是說(shuō)不同的arKey可能有相同的hash值。具有相同hash值的Bucket保存在HashTable的arBuckets數(shù)組(參考下面的解釋)的同一個(gè)索引對(duì)應(yīng)的桶列中。這個(gè)桶列是一個(gè)雙向鏈表，其前向元素，后向元素分別用pLast, pNext來(lái)表示。新插入的Bucket放在該桶列的最前面。
在Bucket中，實(shí)際的數(shù)據(jù)是保存在pData指針指向的內(nèi)存塊中，通常這個(gè)內(nèi)存塊是系統(tǒng)另外分配的。但有一種情況例外，就是當(dāng)Bucket保存的數(shù)據(jù)是一個(gè)指針時(shí)，HashTable將不會(huì)另外請(qǐng)求系統(tǒng)分配空間來(lái)保存這個(gè)指針，而是直接將該指針保存到pDataPtr中，然后再將pData指向本結(jié)構(gòu)成員的地址。這樣可以提高效率，減少內(nèi)存碎片。由此我們可以看到PHP HashTable設(shè)計(jì)的精妙之處。如果Bucket中的數(shù)據(jù)不是一個(gè)指針，pDataPtr為NULL。
HashTable中所有的Bucket通過(guò)pListNext, pListLast構(gòu)成了一個(gè)雙向鏈表。最新插入的Bucket放在這個(gè)雙向鏈表的最后。
注意在一般情況下，Bucket并不能提供它所存儲(chǔ)的數(shù)據(jù)大小的信息。所以在PHP的實(shí)現(xiàn)中，Bucket中保存的數(shù)據(jù)必須具有管理自身大小的能力。

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

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_DEBUG 
int inconsistent; 
#endif 
} HashTable; 