程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> 關於PHP編程 >> 深入PHP中的HashTable結構詳解

深入PHP中的HashTable結構詳解

編輯:關於PHP編程

HashTable是Zend引擎中最重要、使用最廣泛的數據結構,它被用來存儲幾乎所有的東西。
1.2.1 數據結構
HashTable數據結構定義如下:
復制代碼 代碼如下:
typedef struct bucket {
 ulong h;    // 存放hash
 uint nKeyLength;
 void *pData;   // 指向value,是用戶數據的副本
 void *pDataPtr;
 struct bucket *pListNext; // pListNext和pListLast組成
 struct bucket *pListLast; // 整個HashTable的雙鏈表
 struct bucket *pNext;  // pNext和pLast用於組成某個hash對應
 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數組
 dtor_func_t pDestructor; // HashTable初始化時指定,銷毀Bucket時調用
 zend_bool persistent;  // 是否采用C的內存分配例程
 unsigned char nApplyCount;
 zend_bool bApplyProtection;
#if ZEND_DEBUG
 int inconsistent;
#endif
} HashTable;

總的來說,Zend的HashTable是一種鏈表散列,同時也為線性遍歷進行了優化,圖示如下:


HashTable中包含兩種數據結構,一個鏈表散列和一個雙向鏈表,前者用於進行快速鍵-值查詢,後者方便線性遍歷和排序,一個Bucket同時存在於這兩個數據結構中。
關於該數據結構的幾點解釋:
鏈表散列中為什麼使用雙向鏈表?
一般的鏈表散列只需要按key進行操作,只需要單鏈表就夠了。但是,Zend有時需要從鏈表散列中刪除給定的Bucket,使用雙鏈表可以非常高效的實現。
nTableMask是干什麼的?
這個值用於hash值到arBuckets數組下標的轉換。當初始化一個HashTable,Zend首先為arBuckets數組分配nTableSize大小的內存,nTableSize取不小於用戶指定大小的最小的2^n,即二進制的10*。nTableMask = nTableSize – 1,即二進制的01*,此時h & nTableMask就恰好落在 [0, nTableSize – 1] 裡,Zend就以其為index來訪問arBuckets數組。
pDataPtr是干什麼的?
通常情況下,當用戶插入一個鍵值對時,Zend會將value復制一份,並將pData指向value副本。復制操作需要調用Zend內部例程 emalloc來分配內存,這是個非常耗時的操作,並且會消耗比value大的一塊內存(多出的內存用於存放cookie),如果value很小的話,將會造成較大的浪費。考慮到HashTable多用於存放指針值,於是Zend引入pDataPtr,當value小到和指針一樣長時,Zend就直接將其復制到pDataPtr裡,並且將pData指向pDataPtr。這就避免了emalloc操作,同時也有利於提高Cache命中率。
arKey大小為什麼只有1?為什麼不使用指針管理key?
arKey是存放key的數組,但其大小卻只有1,並不足以放下key。在HashTable的初始化函數裡可以找到如下代碼:
復制代碼 代碼如下:
  p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);

可見,Zend為一個Bucket分配了一塊足夠放下自己和key的內存,上半部分是Bucket,下半部分是key,而arKey“恰好”是Bucket的最後一個元素,於是就可以使用arKey來訪問key了。這種手法在內存管理例程中最為常見,當分配內存時,實際上是分配了比指定大小要大的內存,多出的上半部分通常被稱為cookie,它存儲了這塊內存的信息,比如塊大小、上一塊指針、下一塊指針等,baidu的Transmit程序就使用了這種方法。
不用指針管理key,是為了減少一次emalloc操作,同時也可以提高Cache命中率。另一個必需的理由是,key絕大部分情況下是固定不變的,不會因為key變長了而導致重新分配整個Bucket。這同時也解釋了為什麼不把value也一起作為數組分配了——因為value是可變的。

1.2.2 PHP數組
關於HashTable還有一個疑問沒有回答,就是nNextFreeElement是干什麼的?
不同於一般的散列,Zend的HashTable允許用戶直接指定hash值,而忽略key,甚至可以不指定key(此時,nKeyLength為0)。同時,HashTable也支持append操作,用戶連hash值也不用指定,只需要提供value,此時,Zend就用nNextFreeElement作為hash,之後將nNextFreeElement遞增。
HashTable的這種行為看起來很奇怪,因為這將無法按key訪問value,已經完全不是個散列了。理解問題的關鍵在於,PHP數組就是使用HashTable實現的——關聯數組使用正常的k-v映射將元素加入HashTable,其key為用戶指定的字符串;非關聯數組則直接使用數組下標作為hash值,不存在key;而當在一個數組中混合使用關聯和非關聯時,或者使用array_push操作時,就需要用nNextFreeElement了。
再來看value,PHP數組的value直接使用了zval這個通用結構,pData指向的是zval*,按照上一節的介紹,這個zval*將直接存儲在pDataPtr裡。由於直接使用了zval,數組的元素可以是任意PHP類型。
數組的遍歷操作,即foreach、each等,是通過HashTable的雙向鏈表來進行的,pInternalPointer作為游標記錄了當前位置。

1.2.3 變量符號表
除了數組,HashTable還被用來存儲許多其他數據,比如,PHP函數、變量符號、加載的模塊、類成員等。
一個變量符號表就相當於一個關聯數組,其key是變量名(可見,使用很長的變量名並不是個好主意),value是zval*。
在任一時刻PHP代碼都可以看見兩個變量符號表——symbol_table和active_symbol_table——前者用於存儲全局變量,稱為全局符號表;後者是個指針,指向當前活動的變量符號表,通常情況下就是全局符號表。但是,當每次進入一個PHP函數時(此處指的是用戶使用PHP代碼創建的函數),Zend都會創建函數局部的變量符號表,並將active_symbol_table指向局部符號表。Zend總是使用active_symbol_table來訪問變量,這樣就實現了局部變量的作用域控制。
但如果在函數局部訪問標記為global的變量,Zend會進行特殊處理——在active_symbol_table中創建symbol_table中同名變量的引用,如果symbol_table中沒有同名變量則會先創建。

1.3 內存和文件
程序擁有的資源一般包括內存和文件,對於通常的程序,這些資源是面向進程的,當進程結束後,操作系統或C庫會自動回收那些我們沒有顯式釋放的資源。
但是,PHP程序有其特殊性,它是基於頁面的,一個頁面運行時同樣也會申請內存或文件這樣的資源,然而當頁面運行結束後,操作系統或C庫也許不會知道需要進行資源回收。比如,我們將php作為模塊編譯到apache裡,並且以prefork或worker模式運行apache。這種情況下apache進程或線程是復用的,php頁面分配的內存將永駐內存直到出core。
為了解決這種問題,Zend提供了一套內存分配API,它們的作用和C中相應函數一樣,不同的是這些函數從Zend自己的內存池中分配內存,並且它們可以實現基於頁面的自動回收。在我們的模塊中,為頁面分配的內存應該使用這些API,而不是C例程,否則Zend會在頁面結束時嘗試efree掉我們的內存,其結果通常就是crush。
emalloc()
efree()
estrdup()
estrndup()
ecalloc()
erealloc()
另外,Zend還提供了一組形如VCWD_xxx的宏用於替代C庫和操作系統相應的文件API,這些宏能夠支持PHP的虛擬工作目錄,在模塊代碼中應該總是使用它們。宏的具體定義參見PHP源代碼”TSRM/tsrm_virtual_cwd.h”。可能你會注意到,所有那些宏中並沒有提供close操作,這是因為close的對象是已打開的資源,不涉及到文件路徑,因此可以直接使用C或操作系統例程;同理,read/write之類的操作也是直接使用C或操作系統的例程。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved