PHPソースコード解析のZend HashTableについて詳しく解説

最近、PHP のハッシュテーブルに関する記事を読みました。これは PHP データ ストレージの中核であり、さまざまな定数、変数、関数、クラス、オブジェクトなどを整理するために使用されます。転載アドレス http://www.phppan.com/2009/12/zend-hashtable/ 、ソースコードはまだ読んでいませんが、前編のロジック説明を読んでから、先に転載させていただきます

HashTable一般的なデータ構造の教科書ではハッシュテーブル、ハッシュテーブルとも呼ばれます。基本原理は比較的単純ですが (詳しくない場合は、データ構造の教科書を参照するか、オンラインで検索してください)、PHP の実装には独自の特徴があります。 HashTable のデータ ストレージ構造を理解することは、PHP のソース コード、特に Zend Engine での仮想マシンの実装を分析するときに非常に役立ちます。これは、脳内で完全な仮想マシンのイメージをシミュレートするのに役立ちます。これは、配列などの PHP の他のデータ構造の実装の基礎でもあります。

Zend HashTable の実装は、二重リンク リストとベクトル (配列) という 2 つのデータ構造の利点を組み合わせて、PHP に非常に効率的なデータ ストレージとクエリ メカニズムを提供します。

1. HashTable のデータ構造

Zend Engine の HashTable の実装コードには、主に zend_hash.h と zend_hash.c の 2 つのファイルが含まれています。 Zend HashTable には 2 つの主要なデータ構造が含まれており、1 つは Bucket 構造、もう 1 つは 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) にキー名 (key) があり、これは HashTable 全体で一意であり、繰り返すことはできません。 HashTable 内のデータ要素は、キー名に基づいて一意に決定できます。キー名を表す方法は 2 つあります。最初の方法では、文字列 arKey をキー名として使用し、文字列の長さは nKeyLength です。上記のデータ構造では、arKey は長さ 1 の単なる文字配列ですが、キーが 1 文字のみであることを意味するわけではないことに注意してください。実際、Bucket は可変長構造体であるため、arKey は Bucket の最後のメンバー変数であるため、nKeyLength の長さのキーは arKey と nKeyLength を組み合わせることで決定できます。これは、C 言語プログラミングでは比較的一般的なテクニックです。別のキー名表現方法はインデックス方法です。この場合、nKeyLength は常に 0 であり、長整数フィールド h はデータ要素のキー名を表します。簡単に言うと、nKeyLength=0 の場合、キー名は h であり、それ以外の場合、キー名は arKey であり、キー名の長さは nKeyLength です。

nKeyLength > 0の場合、この時のhの値が無意味というわけではありません。実はこのとき保存されるのはarKeyに対応するハッシュ値です。ハッシュ関数がどのように設計されていても、競合は避けられません。つまり、異なる arKey が同じハッシュ値を持つ可能性があります。同じハッシュ値を持つバケットは、HashTable の arBuckets 配列の同じインデックスに対応するバケット列に格納されます (以下の説明を参照)。このバケット列は二重リンクリストであり、その前方要素と後方要素はそれぞれ pLast と pNext で表されます。新しく挿入されたバケットは、バケット列の前面に配置されます。

Bucket では、実際のデータは pData ポインタが指すメモリ ブロックに格納されます。通常、このメモリ ブロックはシステムによって個別に割り当てられます。ただし、例外があります。つまり、バケットによって保存されたデータがポインターの場合、HashTable はシステムにポインターを保存するためのスペースの割り当てを要求せず、ポインターを pDataPtr に直接保存し、pData をメンバーにポイントします。この構造体のアドレス。これにより効率が向上し、メモリの断片化が軽減されます。このことから、PHP HashTable の設計の微妙な点がわかります。 Bucket 内のデータがポインターでない場合、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_DEBUG
int inconsistent;
#endif
} HashTable;

HashTable 構造では、nTableSize は HashTable のサイズを指定すると同時に、HashTable に保存できるバケットの最大数を制限します。この数が大きいほど、システムはより多くのメモリを HashTable に割り当てます。 。計算効率を向上させるために、システムは nTableSize を nTableSize 以上の最小の 2 の整数乗に自動的に調整します。つまり、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 の配列と考えることができます。各配列要素は、データが実際に格納されるバケットを指すポインターです。もちろん、各ポインタは最初は NULL です。

nTableMask の値は常に nTableSize – 1 です。このフィールドを導入する主な目的は、計算効率を向上させ、arBuckets 配列内の Bucket キー名のインデックスを迅速に計算することです。

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_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的拷贝与合并等等。

 

以上がPHPソースコード解析のZend HashTableについて詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。