|
|
HashTable是Zend引擎中最重要、使用最廣泛的數(shù)據(jù)結(jié)構(gòu)，它被用來存儲(chǔ)幾乎所有的東西。
1.2.1 數(shù)據(jù)結(jié)構(gòu)
HashTable數(shù)據(jù)結(jié)構(gòu)定義如下：
復(fù)制代碼 代碼如下:
typedef struct bucket {
ulong h; // 存放hash
uint nKeyLength;
void *pData; // 指向value，是用戶數(shù)據(jù)的副本
void *pDataPtr;
struct bucket *pListNext; // pListNext和pListLast組成
struct bucket *pListLast; // 整個(gè)HashTable的雙鏈表
struct bucket *pNext; // pNext和pLast用于組成某個(gè)hash對(duì)應(yīng)
struct bucket *pLast; // 的雙鏈表
char arKey[1]; // key
} Bucket;
typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer; /* Used for element traversal */
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets; // hash數(shù)組
dtor_func_t pDestructor; // HashTable初始化時(shí)指定，銷毀Bucket時(shí)調(diào)用
zend_bool persistent; // 是否采用C的內(nèi)存分配例程
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
HashTable中包含兩種數(shù)據(jù)結(jié)構(gòu)，一個(gè)鏈表散列和一個(gè)雙向鏈表，前者用于進(jìn)行快速鍵-值查詢，后者方便線性遍歷和排序，一個(gè)Bucket同時(shí)存在于這兩個(gè)數(shù)據(jù)結(jié)構(gòu)中。
關(guān)于該數(shù)據(jù)結(jié)構(gòu)的幾點(diǎn)解釋：
鏈表散列中為什么使用雙向鏈表？
一般的鏈表散列只需要按key進(jìn)行操作，只需要單鏈表就夠了。但是，Zend有時(shí)需要從鏈表散列中刪除給定的Bucket，使用雙鏈表可以非常高效的實(shí)現(xiàn)。
nTableMask是干什么的？
這個(gè)值用于hash值到arBuckets數(shù)組下標(biāo)的轉(zhuǎn)換。當(dāng)初始化一個(gè)HashTable，Zend首先為arBuckets數(shù)組分配nTableSize大小的內(nèi)存，nTableSize取不小于用戶指定大小的最小的2^n，即二進(jìn)制的10*。nTableMask = nTableSize