Detaillierte Erklärung der PHP-Quellcode-Analyse von Zend HashTable

Ich habe kürzlich einen Artikel über Hashtable in PHP gelesen, das den Kern der PHP-Datenspeicherung darstellt und zum Organisieren verschiedener Konstanten, Variablen, Funktionen, Klassen, Objekte usw. verwendet wird. Die Nachdruckadresse lautet http://www.phppan.com/2009/12/zend-hashtable/. Nachdem ich die Logikerklärung im ersten Teil gelesen habe, werde ich sie zuerst erneut drucken 🎜>

HashTable wird in gängigen Lehrbüchern zur Datenstruktur verwendet. Wird auch als Hash-Tabelle oder Hash-Tabelle bezeichnet. Das Grundprinzip ist relativ einfach (wenn Sie damit nicht vertraut sind, konsultieren Sie bitte ein Lehrbuch zur Datenstruktur oder suchen Sie online), aber die Implementierung von PHP weist ihre eigenen einzigartigen Funktionen auf. Das Verständnis der Datenspeicherstruktur von HashTable ist für uns bei der Analyse des Quellcodes von PHP, insbesondere der Implementierung der virtuellen Maschine in Zend Engine, sehr hilfreich. Es hilft uns, das Bild einer vollständigen virtuellen Maschine in unserem Gehirn zu simulieren. Es ist auch die Grundlage für die Implementierung anderer Datenstrukturen in PHP wie beispielsweise Arrays.

Die Implementierung von Zend HashTable kombiniert die Vorteile zweier Datenstrukturen: doppelt verknüpfte Listen und Vektoren (Arrays) und bietet PHP einen sehr effizienten Datenspeicher- und Abfragemechanismus.

1. Datenstruktur von HashTable

Der Implementierungscode von HashTable in Zend Engine umfasst hauptsächlich die beiden Dateien zend_hash.h und zend_hash.c. Zend HashTable enthält zwei Hauptdatenstrukturen, eine ist die Bucket-Struktur und die andere ist die HashTable-Struktur. Die Bucket-Struktur ist ein Container zum Speichern von Daten, und die HashTable-Struktur bietet einen Mechanismus zum Verwalten aller dieser Buckets (oder Bucket-Spalten).

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;

In Zend HashTable hat jedes Datenelement (Bucket) einen Schlüsselnamen (Key), der in der gesamten HashTable eindeutig ist und nicht wiederholt werden kann. Die Datenelemente in der HashTable können anhand des Schlüsselnamens eindeutig bestimmt werden. Es gibt zwei Möglichkeiten, Schlüsselnamen auszudrücken. Die erste Methode verwendet die Zeichenfolge arKey als Schlüsselnamen und die Länge der Zeichenfolge beträgt nKeyLength. Beachten Sie, dass arKey in der obigen Datenstruktur zwar nur ein Zeichenarray mit der Länge 1 ist, dies jedoch nicht bedeutet, dass der Schlüssel nur ein Zeichen sein kann. Tatsächlich ist Bucket eine Struktur mit variabler Länge. Da arKey die letzte Mitgliedsvariable von Bucket ist, kann ein Schlüssel mit einer Länge von nKeyLength durch Kombination von arKey mit nKeyLength ermittelt werden. Dies ist eine relativ häufige Technik in der C-Sprachprogrammierung. Eine weitere Methode zur Darstellung des Schlüsselnamens ist die Indexmethode. In diesem Fall ist nKeyLength immer 0 und das lange Ganzzahlfeld h repräsentiert den Schlüsselnamen des Datenelements. Einfach ausgedrückt: Wenn nKeyLength = 0, ist der Schlüsselname h; andernfalls ist der Schlüsselname arKey und die Länge des Schlüsselnamens ist nKeyLength.

Wenn nKeyLength > 0 ist, bedeutet dies nicht, dass der h-Wert zu diesem Zeitpunkt bedeutungslos ist. Tatsächlich wird zu diesem Zeitpunkt der Hash-Wert gespeichert, der arKey entspricht. Unabhängig davon, wie die Hash-Funktion gestaltet ist, sind Konflikte unvermeidlich, was bedeutet, dass verschiedene arKeys möglicherweise denselben Hash-Wert haben. Buckets mit demselben Hash-Wert werden in der Bucket-Spalte gespeichert, die demselben Index im arBuckets-Array von HashTable entspricht (siehe Erklärung unten). Diese Bucket-Spalte ist eine doppelt verknüpfte Liste und ihre Vorwärts- und Rückwärtselemente werden durch pLast bzw. pNext dargestellt. Der neu eingefügte Bucket wird an der Vorderseite der Bucket-Säule platziert.

In Bucket werden die tatsächlichen Daten in dem Speicherblock gespeichert, auf den der pData-Zeiger zeigt. Normalerweise wird dieser Speicherblock vom System separat zugewiesen. Es gibt jedoch eine Ausnahme: Wenn die vom Bucket gespeicherten Daten ein Zeiger sind, fordert HashTable das System nicht auf, Speicherplatz zum Speichern des Zeigers zuzuweisen, sondern speichert den Zeiger direkt in pDataPtr und zeigt dann pData auf das Mitglied dieser Struktur. Dies verbessert die Effizienz und reduziert die Speicherfragmentierung. Daraus können wir die Feinheiten des PHP HashTable-Designs erkennen. Wenn die Daten im Bucket kein Zeiger sind, ist pDataPtr NULL.

Alle Buckets in HashTable bilden eine doppelt verknüpfte Liste über pListNext und pListLast. Der zuletzt eingefügte Bucket wird am Ende dieser doppelt verknüpften Liste platziert.

Beachten Sie, dass Bucket im Allgemeinen keine Informationen über die Größe der gespeicherten Daten bereitstellen kann. Daher müssen bei der Implementierung von PHP die im Bucket gespeicherten Daten ihre eigene Größe verwalten können.

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;

In der HashTable-Struktur gibt nTableSize die Größe der HashTable an und begrenzt die maximale Anzahl von Buckets, die in der HashTable gespeichert werden können. Je größer die Anzahl, desto mehr Speicher reserviert das System die HashTable. Um die Berechnungseffizienz zu verbessern, passt das System nTableSize automatisch an die kleinste ganzzahlige Potenz von 2 an, die nicht kleiner als nTableSize ist. Mit anderen Worten: Wenn Sie beim Initialisieren der HashTable eine nTableSize angeben, die keine ganzzahlige Potenz von 2 ist, passt das System den Wert von nTableSize automatisch an. Das heißt,

nTableSize = 2ceil(log(nTableSize, 2)) oder nTableSize = pow(ceil(log(nTableSize,2)))

Zum Beispiel, wenn nTableSize = angegeben wird, wenn Initialisieren von HashTable 11. Der HashTable-Initialisierer erhöht nTableSize automatisch auf 16.

arBuckets ist der Schlüssel zu HashTable. Das HashTable-Initialisierungsprogramm beantragt automatisch einen Teil des Speichers und weist seine Adresse arBuckets zu. Die Speichergröße kann nTableSize-Zeiger aufnehmen. Wir können uns arBuckets als ein Array der Größe nTableSize vorstellen. Jedes Array-Element ist ein Zeiger, der auf den Bucket zeigt, in dem die Daten tatsächlich gespeichert sind. Natürlich ist jeder Zeiger am Anfang NULL.

Der Wert von nTableMask ist immer nTableSize – 1. Der Hauptzweck der Einführung dieses Feldes besteht darin, die Berechnungseffizienz zu verbessern und den Index des Bucket-Schlüsselnamens im arBuckets-Array schnell zu berechnen.

nNumberOfElements记录了HashTable当前保存的数据元素的个数。当nNumberOfElement大于nTableSize时，HashTable将自动扩展为原来的两倍大小。

nNextFreeElement记录HashTable中下一个可用于插入数据元素的arBuckets的索引。

pListHead, pListTail则分别表示Bucket双向链表的第一个和最后一个元素，这些数据元素通常是根据插入的顺序排列的。也可以通过各种排序函数对其进行重 新排列。pInternalPointer则用于在遍历HashTable时记录当前遍历的位置，它是一个指针，指向当前遍历到的Bucket，初始值是 pListHead。

pDestructor是一个函数指针，在HashTable的增加、修改、删除Bucket时自动调用，用于处理相关数据的清理工作。

persistent标志位指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。具体请参考PHP的内存管理。

nApplyCount与bApplyProtection结合提供了一个防止在遍历HashTable时进入递归循环时的一种机制。

inconsistent成员用于调试目的，只在PHP编译成调试版本时有效。表示HashTable的状态，状态有四种：

状态值 含义
HT_IS_DESTROYING 正在删除所有的内容，包括arBuckets本身
HT_IS_DESTROYED 已删除，包括arBuckets本身
HT_CLEANING 正在清除所有的arBuckets指向的内容，但不包括arBuckets本身
HT_OK 正常状态，各种数据完全一致

typedef struct _zend_hash_key {
char *arKey;      /* hash元素key名称 */
uint nKeyLength;     /* hash 元素key长度 */
ulong h;       /* key计算出的hash值或直接指定的数值下标 */
} zend_hash_key;

现在来看zend_hash_key结构就比较容易理解了。它通过arKey, nKeyLength, h三个字段唯一确定了HashTable中的一个元素。

根据上面对HashTable相关数据结构的解释，我们可以画出HashTable的内存结构图：

Detaillierte Erklärung der PHP-Quellcode-Analyse von Zend HashTable

二、 Zend HashTable的实现

本节具体介绍一下PHP中HashTable的实现。以下函数均取自于zend_hash.c。只要充分理解了上述数据结构，HashTable实现的代码并不难理解。

1 HashTable初始化

HashTable提供了一个zend_hash_init宏来完成HashTable的初始化操作。实际上它是通过下面的内部函数来实现的：

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
uint i = 3;
Bucket **tmp;
 
SET_INCONSISTENT(HT_OK);
 
if (nSize >= 0×80000000) {
/* prevent overflow */
ht->nTableSize = 0×80000000;
} else {
while ((1U << i) < nSize) { /* 自动调整nTableSize至2的n次方 */ i++; } ht->nTableSize = 1 << i;     
/* i的最小值为3，因此HashTable大小最小为8 */ } ht->nTableMask = ht->nTableSize - 1;
ht->pDestructor = pDestructor;
ht->arBuckets = NULL;
ht->pListHead = NULL;
ht->pListTail = NULL;
ht->nNumOfElements = 0;
ht->nNextFreeElement = 0;
ht->pInternalPointer = NULL;
ht->persistent = persistent;
ht->nApplyCount = 0;
ht->bApplyProtection = 1;
 
/* 根据persistent使用不同方式分配arBuckets内存，并将其所有指针初始化为NULL*/
/* Uses ecalloc() so that Bucket* == NULL */
if (persistent) {
tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
if (!tmp) {
return FAILURE;
}
ht->arBuckets = tmp;
} else {
tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
if (tmp) {
ht->arBuckets = tmp;
}
}
 
return SUCCESS;
}

在以前的版本中，可以使用pHashFunction来指定hash函数。但现PHP已强制使用DJBX33A算法，因此实际上pHashFunction这个参数并不会用到，保留在这里只是为了与以前的代码兼容。

2 增加、插入和修改元素

向HashTable中添加一个新的元素最关键的就是要确定将这个元素插入到arBuckets数组中的哪个位置。根据上面对Bucket结构键名 的解释，我们可以知道有两种方式向HashTable添加一个新的元素。第一种方法是使用字符串作为键名来插入Bucket；第二种方法是使用索引作为键 名来插入Bucket。第二种方法具体又可以分为两种情况：指定索引或不指定索引，指定索引指的是强制将Bucket插入到指定的索引位置中；不指定索引 则将Bucket插入到nNextFreeElement对应的索引位置中。这几种插入数据的方法实现比较类似，不同的只是定位Bucket的方法。

修改HashTable中的数据的方法与增加数据的方法也很类似。

我们先看第一种使用字符串作为键名增加或修改Bucket的方法：

ZEND_API int _zend_hash_add_or_update(HashTable *ht, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
ulong h;
uint nIndex;
Bucket *p;
 
IS_CONSISTENT(ht);     // 调试信息输出
 
if (nKeyLength <= 0) { 
#if ZEND_DEBUG ZEND_PUTS(”zend_hash_update: Can’t put in empty key\n”); 
#endif return FAILURE; } 
/* 
使用hash函数计算arKey的hash值 
*/ 
h = zend_inline_hash_func(arKey, nKeyLength); 
/* 
将hash值和nTableMask按位与后生成该元素在arBuckets中的索引。让它和 * nTableMask按位与是保证不会产生一个使得arBuckets越界的数组下标。 
*/ 
nIndex = h & ht->nTableMask;
 
p = ht->arBuckets[nIndex];   
/* 
取得相应索引对应的Bucket的指针 
*/
 
/* 检查对应的桶列中是否包含有数据元素(key, hash) */
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
if (!memcmp(p->arKey, arKey, nKeyLength)) {
if (flag & HASH_ADD) {
return FAILURE; // 对应的数据元素已存在，不能进行插入操作
}
HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
if (p->pData == pData) {
ZEND_PUTS(”Fatal error in zend_hash_update: p->pData == pData\n”);
HANDLE_UNBLOCK_INTERRUPTIONS();
return FAILURE;
}
#endif
if (ht->pDestructor) {
/* 如果数据元素存在，对原来的数据进行析构操作 */
ht->pDestructor(p->pData);
}
/* 用新的数据来更新原来的数据 */
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p->pData;
}
HANDLE_UNBLOCK_INTERRUPTIONS();
return SUCCESS;
}
}
p = p->pNext;
}
 
/* HashTable中没有key对应的数据，新增一个Bucket　*/
p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
if (!p) {
return FAILURE;
}
memcpy(p->arKey, arKey, nKeyLength);
p->nKeyLength = nKeyLength;
INIT_DATA(ht, p, pData, nDataSize);
p->h = h;
//　将Bucket加入到相应的桶列中
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
if (pDest) {
*pDest = p->pData;
}
 
HANDLE_BLOCK_INTERRUPTIONS();
//　将Bucket 加入到HashTable的双向链表中
CONNECT_TO_GLOBAL_DLLIST(p, ht);
ht->arBuckets[nIndex] = p;
HANDLE_UNBLOCK_INTERRUPTIONS();
 
ht->nNumOfElements++;
// 如果HashTable已满，重新调整HashTable的大小。
ZEND_HASH_IF_FULL_DO_RESIZE(ht);   /* If the Hash table is full, resize it */
return SUCCESS;
}

因为这个函数是使用字符串作为键名来插入数据的，因此它首先检查nKeyLength的值是否大于0，如果不是的话就直接退出。然后计算arKey对应的 hash值h，将其与nTableMask按位与后得到一个无符号整数nIndex。这个nIndex就是将要插入的Bucket在arBuckets数 组中的索引位置。

现在已经有了arBuckets数组的一个索引，我们知道它包括的数据是一个指向Bucket的双向链表的指针。如果这个双向链表不为空的话我们首先检查 这个双向链表中是否已经包含了用字符串arKey指定的键名的Bucket，这样的Bucket如果存在，并且我们要做的操作是插入新Bucket(通过 flag标识)，这时就应该报错 – 因为在HashTable中键名不可以重复。如果存在，并且是修改操作，则使用在HashTable中指定了析构函数pDestructor对原来的 pData指向的数据进行析构操作；然后将用新的数据替换原来的数据即可成功返回修改操作。
如果在HashTable中没有找到键名指定的数据，就将该数据封装到Bucket中，然后插入HashTable。这里要注意的是如下的两个宏：
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex])
CONNECT_TO_GLOBAL_DLLIST(p, ht)
前者是将该Bucket插入到指定索引的Bucket双向链表中，后者是插入到整个HashTable的Bucket双向链表中。两者的插入方式也不同，前者是将该Bucket插入到双向链表的最前面，后者是插入到双向链表的最末端。

下面是第二种插入或修改Bucket的方法，即使用索引的方法：

ZEND_API int _zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
uint nIndex;
Bucket *p;
 
IS_CONSISTENT(ht);
 
if (flag & HASH_NEXT_INSERT) {
h = ht->nNextFreeElement;
}
nIndex = h & ht->nTableMask;
 
p = ht->arBuckets[nIndex];
 
// 检查是否含有相应的数据
while (p != NULL) {
if ((p->nKeyLength == 0) && (p->h == h)) {
if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
return FAILURE;
}
//
//　…… 修改Bucket数据，略
//
if ((long)h >= (long)ht->nNextFreeElement) {
ht->nNextFreeElement = h + 1;
}
if (pDest) {
*pDest = p->pData;
}
return SUCCESS;
}
p = p->pNext;
}
p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);
if (!p) {
return FAILURE;
}
p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
p->h = h;
INIT_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p->pData;
}
 
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
 
HANDLE_BLOCK_INTERRUPTIONS();
ht->arBuckets[nIndex] = p;
CONNECT_TO_GLOBAL_DLLIST(p, ht);
HANDLE_UNBLOCK_INTERRUPTIONS();
 
if ((long)h >= (long)ht->nNextFreeElement) {
ht->nNextFreeElement = h + 1;
}
ht->nNumOfElements++;
ZEND_HASH_IF_FULL_DO_RESIZE(ht);
return SUCCESS;
}

flag标志指明当前操作是HASH_NEXT_INSERT(不指定索引插入或修改), HASH_ADD(指定索引插入)还是HASH_UPDATE(指定索引修改)。由于这些操作的实现代码基本相同，因此统一合并成了一个函数，再用flag加以区分。
本函数基本与前一个相同，不同的是如果确定插入到arBuckets数组中的索引的方法。如果操作是HASH_NEXT_INSERT，则直接使用nNextFreeElement作为插入的索引。注意nNextFreeElement的值是如何使用和更新的。
3 访问元素
同样，HashTable用两种方式来访问元素，一种是使用字符串arKey的zend_hash_find()；另一种是使用索引的访问方式zend_hash_index_find()。由于其实现的代码很简单，分析工作就留给读者自已完成。
4 删除元素
HashTable删除数据均使用zend_hash_del_key_or_index()函数来完成，其代码也较为简单，这里也不再详细分析。需要的是注意如何根据arKey或h来计算出相应的下标，以及两个双向链表的指针的处理。
5 遍历元素

/* This is used to recurse elements and selectively delete certain entries
* from a hashtable. apply_func() receives the data and decides if the entry
* should be deleted or recursion should be stopped. The following three
* return codes are possible:
* ZEND_HASH_APPLY_KEEP   - continue
* ZEND_HASH_APPLY_STOP   - stop iteration
* ZEND_HASH_APPLY_REMOVE - delete the element, combineable with the former
*/
 
ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
{
Bucket *p;
 
IS_CONSISTENT(ht);
 
HASH_PROTECT_RECURSION(ht);
p = ht->pListHead;
while (p != NULL) {
int result = apply_func(p->pData TSRMLS_CC);
 
if (result & ZEND_HASH_APPLY_REMOVE) {
p = zend_hash_apply_deleter(ht, p);
} else {
p = p->pListNext;
}
if (result & ZEND_HASH_APPLY_STOP) {
break;
}
}
HASH_UNPROTECT_RECURSION(ht);
}

因为HashTable中所有Bucket都可以通过pListHead指向的双向链表来访问，因此遍历HashTable的实现也比较简单。这里值得一 提的是对当前遍历到的Bucket的处理使用了一个apply_func_t类型的回调函数。根据实际需要，该回调函数返回下面值之一：

ZEND_HASH_APPLY_KEEP
ZEND_HASH_APPLY_STOP
ZEND_HASH_APPLY_REMOVE

它们分别表示继续遍历，停止遍历或删除相应元素后继续遍历。

还有一个要注意的问题就是遍历时的防止递归的问题，也就是防止对同一个HashTable同时进行多次遍历。这是用下面两个宏来实现的：
HASH_PROTECT_RECURSION(ht)
HASH_UNPROTECT_RECURSION(ht)
其主要原理是如果遍历保护标志bApplyProtection为真，则每次进入遍历函数时将nApplyCount值加1，退出遍历函数时将nApplyCount值减1。开始遍历之前如果发现nApplyCount > 3就直接报告错误信息并退出遍历。

上面的apply_func_t不带参数。HashTable还提供带一个参数或可变参数的回调方式，对应的遍历函数分别为:

typedef int (*apply_func_arg_t)(void *pDest,void *argument TSRMLS_DC);
void zend_hash_apply_with_argument(HashTable *ht,
apply_func_arg_t apply_func, void *data TSRMLS_DC);
 
typedef int (*apply_func_args_t)(void *pDest,
int num_args, va_list args, zend_hash_key *hash_key);
void zend_hash_apply_with_arguments(HashTable *ht,
apply_func_args_t apply_func, int numargs, …);

除了上面提供的几种提供外，还有许多其它操作HashTable的API。如排序、HashTable的拷贝与合并等等。

 

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung der PHP-Quellcode-Analyse von Zend HashTable. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!