首頁  >  文章  >  後端開發  >  hashtable PHP 原始碼分析 Zend HashTable詳解第1/3頁

hashtable PHP 原始碼分析 Zend HashTable詳解第1/3頁

WBOY
WBOY原創
2016-07-29 08:40:33789瀏覽

HashTable在通常的資料結構教材中也稱作散列表,哈希表。其基本原理比較簡單(如果你對其不熟悉,請查閱隨便一本數據結構教材或在網上搜索),但PHP的實現有其獨特的地方。了解HashTable的資料儲存結構,對我們分析PHP的原始程式碼,特別是Zend Engine中的虛擬機器的實作時,有很重要的幫助。它可以幫助我們在大腦中模擬一個完整的虛擬機器的圖像。它也是PHP中其它一些資料結構如數組實現的基礎。
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 numericindexing *
uint nKeyLength; /* key 長度*/
void *pData; /* 指向Bucket中儲存的資料的指標*/
void *pDataPtr; /* 指標資料*/
bstructucket * 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 nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer;
Bucket *pListHead;
Bucket *pListTail;
Bucket; ;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable 1/3頁 123下一頁

以上就介紹了hashtable PHP 原始碼分析 Zend HashTable詳解第1/3頁,包含了hashtable方面的內容,希望對PHP教學有興趣的朋友有幫助。


陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn