|
|
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_DEBUG
int inconsistent;
#endif
} HashTable;
php技術：PHP 源代碼分析 Zend HashTable詳解第1/3頁，轉載需保留來源！
鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。
