PHP 소스 코드의 Zend HashTable 분석에 대해-PHP 튜토리얼-php.cn

이 글은 주로 PHP 소스코드에 있는 Zend HashTable의 분석을 소개하고 있는데, 이제 도움이 필요한 친구들이 참고할 수 있도록 공유합니다. 최근 인터넷에서 PHP 소스 코드를 검색한 결과 Think in code에서 이 주소를 찾았습니다: http://www.blankyao.cn/index.php/php-zend-hashtable.html

[Text]

PHP에는 매우 중요한 데이터 구조가 있는데, 이는 PHP 데이터 저장의 핵심이며 이를 이용하여 다양한 상수, 변수, 클래스, 객체 등을 구성합니다. .

HashTable은 일반적인 자료 구조 교과서에서는 해시 테이블(Hash Table) 또는 해시 테이블(Hash Table)이라고도 합니다. 기본 원리는 비교적 간단하지만(익숙하지 않은 경우 데이터 구조 교과서를 참조하거나 온라인으로 검색하세요), PHP 구현에는 고유한 기능이 있습니다. HashTable의 데이터 저장 구조를 이해하는 것은 PHP 소스 코드, 특히 Zend 엔진의 가상 머신 구현을 분석할 때 매우 도움이 됩니다. 이는 우리 두뇌에서 완전한 가상 머신의 이미지를 시뮬레이션하는 데 도움이 됩니다. 이는 또한 배열과 같은 PHP의 다른 데이터 구조 구현을 위한 기초이기도 합니다.

Zend HashTable의 구현은 이중 연결 목록과 벡터(배열)라는 두 가지 데이터 구조의 장점을 결합하여 PHP에 매우 효율적인 데이터 저장 및 쿼리 메커니즘을 제공합니다.

시작하겠습니다!

1. HashTable의 데이터 구조

Zend Engine의 HashTable 구현 코드에는 주로 zend_hash.h와 zend_hash.c 두 파일이 포함되어 있습니다. Zend HashTable에는 두 가지 주요 데이터 구조가 포함되어 있습니다. 하나는 Bucket 구조이고 다른 하나는 HashTable 구조입니다. Bucket 구조는 데이터를 저장하는 데 사용되는 컨테이너이며 HashTable 구조는 이러한 모든 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;

로그인 후 복사

Zend HashTable에서 각 데이터 요소(Bucket)에는 전체 HashTable에서 고유하고 반복될 수 없는 키 이름(key)이 있습니다. HashTable의 데이터 요소는 키 이름을 기반으로 고유하게 결정될 수 있습니다. 키 이름을 표현하는 방법에는 두 가지가 있습니다. 첫 번째 방법은 arKey 문자열을 키 이름으로 사용하고 문자열 길이는 nKeyLength입니다. 위의 데이터 구조에서 arKey는 길이가 1인 문자 배열이지만 키가 한 문자만 될 수 있다는 의미는 아닙니다. 실제로 Bucket은 가변 길이 구조이기 때문에 arKey와 nKeyLength를 결합하면 nKeyLength 길이의 키를 결정할 수 있습니다. 이는 C 언어 프로그래밍에서 비교적 일반적인 기술입니다. 또 다른 키 이름 표현 방법은 인덱스 방법입니다. 이 경우 nKeyLength는 항상 0이고 긴 정수 필드 h는 데이터 요소의 키 이름을 나타냅니다. 간단히 말하면 nKeyLength=0이면 키 이름은 h이고, 그렇지 않으면 키 이름은 arKey이고 키 이름의 길이는 nKeyLength입니다.

nKeyLength > 0이라고 해서 이때의 h값이 의미가 없다는 뜻은 아닙니다. 실제로 이때 저장되는 것은 arKey에 해당하는 해시값이다. 해시 함수가 어떻게 설계되든 충돌은 불가피합니다. 즉, 서로 다른 arKeys가 동일한 해시 값을 가질 수 있음을 의미합니다. 동일한 해시 값을 갖는 버킷은 HashTable의 arBuckets 배열에서 동일한 인덱스에 해당하는 버킷 컬럼에 저장됩니다(아래 설명 참조). 이 버킷 컬럼은 이중 연결 리스트이며, 순방향 요소와 역방향 요소는 각각 pLast와 pNext로 표시됩니다. 새로 삽입된 Bucket은 버킷 컬럼의 앞쪽에 배치됩니다.

버킷에서는 pData 포인터가 가리키는 메모리 블록에 실제 데이터가 저장됩니다. 일반적으로 이 메모리 블록은 시스템에서 별도로 할당됩니다. 그러나 예외가 있습니다. 즉, Bucket에 저장된 데이터가 포인터인 경우 HashTable은 시스템에 포인터를 저장하기 위한 공간 할당을 요청하지 않고 포인터를 pDataPtr에 직접 저장한 다음 pData가 해당 멤버를 가리킵니다. 이 구조의. 이는 효율성을 향상시키고 메모리 조각화를 줄입니다. 이것으로부터 우리는 PHP HashTable 디자인의 미묘함을 볼 수 있습니다. 버킷의 데이터가 포인터가 아닌 경우 pDataPtr은 NULL입니다.

HashTable의 모든 버킷은 pListNext 및 pListLast를 통해 이중 연결 목록을 구성합니다. 가장 최근에 삽입된 버킷은 이 이중 연결 목록의 끝에 배치됩니다.

일반적인 상황에서는 Bucket이 저장하는 데이터의 크기에 대한 정보를 제공할 수 없습니다. 따라서 PHP 구현 시 Bucket에 저장된 데이터는 자체 크기를 관리할 수 있는 기능을 가지고 있어야 합니다.

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;

로그인 후 복사

HashTable 구조에서 nTableSize는 HashTable의 크기를 지정하는 동시에 HashTable에 저장할 수 있는 최대 버킷 수를 제한합니다. 숫자가 클수록 시스템이 HashTable에 더 많은 메모리를 할당합니다. . 계산 효율성을 높이기 위해 시스템은 nTableSize보다 작지 않은 가장 작은 정수 거듭제곱인 2로 nTableSize를 자동으로 조정합니다. 즉, HashTable을 초기화할 때 2의 정수 거듭제곱이 아닌 nTableSize를 지정하면 시스템이 자동으로 nTableSize 값을 조정합니다. 즉,

nTableSize = 2ceil(log(nTableSize, 2)) 또는 nTableSize = pow(ceil(log(nTableSize,2)))

예를 들어 HashTable 초기화 시 nTableSize = 11을 지정한 경우 HashTable 초기화 프로그램은 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;

로그인 후 복사

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

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

PHP 소스 코드의 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_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;}

로그인 후 복사

因为这个函数是使用字符串作为键名来插入数据的，因此它首先检查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的拷贝与合并等等。只要充分理解了上述HashTable的数据结构，理解这些代码并不困难。

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