À propos de l'analyse de Zend HashTable dans le code source PHP-tutoriel php-php.cn

Cet article présente principalement l'analyse de Zend HashTable dans le code source PHP. Maintenant, je le partage avec tout le monde. Les amis dans le besoin peuvent s'y référer

J'ai vu cet article depuis longtemps. il y a l'article, mon intérêt s'est récemment déplacé vers le code source PHP, j'ai cherché sur Internet et j'ai trouvé l'adresse de cet article sur think in code : http://www.blankyao.cn/index.php/php-zend-hashtable. html
[Texte]

Dans le moteur Zend de PHP, il existe une structure de données qui est très importante. Elle est partout et constitue le cœur du stockage des données PHP, comprenant diverses constantes, variables et fonctions. , classes, objets, etc. Ils sont tous organisés en utilisant cette structure de données est HashTable.

HashTable est également appelée table de hachage ou table de hachage dans les manuels courants sur la structure des données. Le principe de base est relativement simple (si vous ne le connaissez pas, veuillez consulter n'importe quel manuel sur la structure des données ou effectuer une recherche en ligne), mais l'implémentation de PHP a ses propres caractéristiques uniques. Comprendre la structure de stockage des données de HashTable nous est très utile lors de l'analyse du code source de PHP, en particulier l'implémentation de la machine virtuelle dans Zend Engine. Cela nous aide à simuler l’image d’une machine virtuelle complète dans notre cerveau. C'est également la base de l'implémentation d'autres structures de données en PHP telles que les tableaux.

L'implémentation de Zend HashTable combine les avantages de deux structures de données : des listes doublement chaînées et des vecteurs (tableaux), offrant à PHP un mécanisme de stockage et de requête de données très efficace.

Commençons !

1. La structure des données de HashTable

Le code d'implémentation de HashTable dans Zend Engine comprend principalement les deux fichiers zend_hash.h et zend_hash.c . Zend HashTable comprend deux structures de données principales, l'une est la structure Bucket et l'autre est la structure HashTable. La structure Bucket est un conteneur utilisé pour enregistrer des données, et la structure HashTable fournit un mécanisme pour gérer tous ces buckets (ou colonnes de 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;

Copier après la connexion

Dans Zend HashTable, chaque élément de données (Bucket) a un nom de clé (key), qui est unique dans l'ensemble de la HashTable et ne peut pas être répété. Les éléments de données du HashTable peuvent être déterminés de manière unique en fonction du nom de la clé. Il existe deux manières de représenter les noms de clés. La première méthode utilise la chaîne arKey comme nom de clé et la longueur de la chaîne est nKeyLength. Notez que dans la structure de données ci-dessus, bien que arKey ne soit qu'un tableau de caractères d'une longueur de 1, cela ne signifie pas que la clé ne peut contenir qu'un seul caractère. En fait, Bucket est une structure de longueur variable puisque arKey est la dernière variable membre de Bucket, une clé d'une longueur de nKeyLength peut être déterminée en combinant arKey avec nKeyLength. Il s'agit d'une technique relativement courante dans la programmation en langage C. Une autre méthode de représentation du nom de clé est la méthode d'index. Dans ce cas, nKeyLength est toujours 0 et le champ entier long h représente le nom de clé de l'élément de données. Pour faire simple, si nKeyLength=0, le nom de la clé est h ; sinon, le nom de la clé est arKey et la longueur du nom de la clé est nKeyLength.

Lorsque nKeyLength > 0, cela ne signifie pas que la valeur h à ce moment n'a aucun sens. En fait, ce qu'il enregistre à ce moment-là, c'est la valeur de hachage correspondant à arKey. Quelle que soit la façon dont la fonction de hachage est conçue, les conflits sont inévitables, ce qui signifie que différentes arKeys peuvent avoir la même valeur de hachage. Les buckets avec la même valeur de hachage sont stockés dans la colonne bucket correspondant au même index dans le tableau arBuckets de HashTable (reportez-vous à l'explication ci-dessous). Cette colonne de compartiment est une liste doublement chaînée, et ses éléments avant et arrière sont représentés respectivement par pLast et pNext. Le bucket nouvellement inséré est placé à l’avant de la colonne du bucket.

Dans Bucket, les données réelles sont stockées dans le bloc mémoire pointé par le pointeur pData. Habituellement, ce bloc mémoire est alloué séparément par le système. Mais il y a une exception, c'est-à-dire que lorsque les données enregistrées par le Bucket sont un pointeur, le HashTable ne demandera pas au système d'allouer de l'espace pour enregistrer le pointeur, mais enregistrera directement le pointeur sur pDataPtr, puis pointera pData vers le membre de cette structure. Cela améliore l’efficacité et réduit la fragmentation de la mémoire. De là, nous pouvons voir les subtilités de la conception de PHP HashTable. Si les données du bucket ne sont pas un pointeur, pDataPtr est NULL.

Tous les buckets de HashTable forment une liste doublement chaînée via pListNext et pListLast. Le dernier bucket inséré est placé à la fin de cette liste doublement chaînée.

Notez qu'en général, Bucket ne peut pas fournir d'informations sur la taille des données qu'il stocke. Par conséquent, dans l’implémentation de PHP, les données enregistrées dans le Bucket doivent avoir la capacité de gérer leur propre taille.

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_DEBUGint inconsistent;
#endif
} HashTable;

Copier après la connexion

Dans la structure HashTable, nTableSize spécifie la taille du HashTable et limite le nombre maximum de compartiments pouvant être enregistrés dans le HashTable. Plus le nombre est grand, plus le système alloue de mémoire. la table de hachage. Afin d'améliorer l'efficacité du calcul, le système ajuste automatiquement nTableSize à la plus petite puissance entière de 2 qui n'est pas inférieure à nTableSize. En d’autres termes, si vous spécifiez un nTableSize qui n’est pas une puissance entière de 2 lors de l’initialisation du HashTable, le système ajustera automatiquement la valeur de nTableSize. Autrement dit,

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

Par exemple, si nTableSize = est spécifié lorsque initialisation de HashTable 11. L'initialiseur HashTable augmentera automatiquement nTableSize à 16.

arBuckets是HashTable的关键，HashTable初始化程序会自动申请一块内存，并将其地址赋值给arBuckets，该内存大小正好能容纳nTableSize个指针。我们可以将arBuckets看作一个大小为nTableSize的数组，每个数组元素都是一个指针，用于指向实际存放数据的Bucket。当然刚开始时每个指针均为NULL。

nTableMask的值永远是nTableSize – 1，引入这个字段的主要目的是为了提高计算效率，是为了快速计算Bucket键名在arBuckets数组中的索引。

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;

Copier après la connexion

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

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

À propos de lanalyse de Zend HashTable dans le code source PHP

二、 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;
}

Copier après la connexion

在以前的版本中，可以使用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_DEBUGif (p->pData == pData) {
ZEND_PUTS(”Fatal error in zend_hash_update: p->pData == pData\n”);
HANDLE_UNBLOCK_INTERRUPTIONS();
return FAILURE;}
#endifif (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;}

Copier après la connexion

因为这个函数是使用字符串作为键名来插入数据的，因此它首先检查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;}

Copier après la connexion

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);}

Copier après la connexion

因为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, …);

Copier après la connexion

除了上面提供的几种提供外，还有许多其它操作HashTable的API。如排序、HashTable的拷贝与合并等等。只要充分理解了上述HashTable的数据结构，理解这些代码并不困难。

以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP中文网！