四虎精品视频-四虎精品成人免费网站-四虎黄色网-四虎国产视频-国产免费91-国产蜜臀97一区二区三区

PHP 源代碼分析 Zend HashTable詳解第1/3頁

HashTable在通常的數(shù)據(jù)結(jié)構(gòu)教材中也稱作散列表,哈希表。其基本原理比較簡單(如果你對其不熟悉,請查閱隨便一本數(shù)據(jù)結(jié)構(gòu)教材或在網(wǎng)上搜索),但php的實現(xiàn)有其獨特的地方。理解了HashTable的數(shù)據(jù)存儲結(jié)構(gòu),對我們分析php的源代碼,特別是Zend Engine中的虛擬機的實現(xiàn)時,有很重要的幫助。它可以幫助我們在大腦中模擬一個完整的虛擬機的形象。它也是php中其它一些數(shù)據(jù)結(jié)構(gòu)如數(shù)組實現(xiàn)的基礎(chǔ)。
Zend HashTable的實現(xiàn)結(jié)合了雙向鏈表和向量(數(shù)組)兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點,為php提供了非常高效的數(shù)據(jù)存儲和查詢機制。
Let's begin!
一、 HashTable的數(shù)據(jù)結(jié)構(gòu)
在Zend Engine中的HashTable的實現(xiàn)代碼主要包括zend_hash.h, zend_hash.c這兩個文件中。Zend HashTable包括兩個主要的數(shù)據(jù)結(jié)構(gòu),其一是Bucket(桶)結(jié)構(gòu),另一個是HashTable結(jié)構(gòu)。Bucket結(jié)構(gòu)是用于保存數(shù)據(jù)的容器,而HashTable結(jié)構(gòu)則提供了對所有這些Bucket(或桶列)進行管理的機制。
復(fù)制代碼 代碼如下:
typedef struct bucket {
ulong h; /* Used for numeric indexing */
uint nKeyLength; /* key 長度 */
void *pData; /* 指向Bucket中保存的數(shù)據(jù)的指針 */
void *pDataPtr; /* 指針數(shù)據(jù) */
struct bucket *pListNext; /* 指向HashTable桶列中下一個元素 */
struct bucket *pListLast; /* 指向HashTable桶列中前一個元素 */
struct bucket *pNext; /* 指向具有同一個hash值的桶列的后一個元素 */
struct bucket *pLast; /* 指向具有同一個hash值的桶列的前一個元素 */
char arKey[1]; /* 必須是最后一個成員,key名稱*/
} Bucket;

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


php技術(shù)PHP 源代碼分析 Zend HashTable詳解第1/3頁,轉(zhuǎn)載需保留來源!

鄭重聲明:本文版權(quán)歸原作者所有,轉(zhuǎn)載文章僅為傳播更多信息之目的,如作者信息標記有誤,請第一時間聯(lián)系我們修改或刪除,多謝。

主站蜘蛛池模板: 云上的宝石| 鬼娃娃花子| hunger game| 美女亲热视频| 散文诗二首批注| 成年黄色在线观看| 徐一航的电视剧叫什么| 陈芷琰演过哪些电视剧名字| 男上女下动态视频| 宋晓飞| 燃冬海报| 小学五年级研究报告| 樱花悠| 水中生孩子视频| 男生女生向前冲2014| 儿童眼轴长度正常范围 | 竹内纱里奈全部aⅴ在线看| 男生帅气动漫头像| 美丽的错误| 高规格| 浪人街| 香港之夜在线观看完整版| 囚徒 电影| 道东道西| 小崔会客| 凤凰电视台| 孙东杓| 许良| 电影《三体》| 美国禁事| 贝弗利山人| 749局演员表| i性感美女视频| 房东电影| 命运简谱| 人流后饮食| 电视剧《惊蛰》演员表| 陈诗雅韩国演员| 抖音视频下载网站| 浙江卫视节目表(全部)| 诱惑的艺术|