【翻訳】PHP における配列の内部実装を理解する (PHP 開発者のための PHP ソースコード - パート 4)

「PHP 開発者のための PHP ソース コード」シリーズの第 4 部へようこそ。この部では、PHP 配列が内部でどのように表現され、コード ベースで使用されるかについて説明します。

前の記事を見逃した場合は、こちらのリンクを参照してください:

パート 1: PHP 開発者のための PHP ソース コード - ソース コードの構造

パート 2: PHP 内部関数の定義を理解する

パート 3: PHP 変数の実装

すべてはハッシュ テーブルです

基本的に、PHP のすべてはハッシュ テーブルです。以下の PHP 配列の実装だけでなく、オブジェクトのプロパティ、メソッド、関数、変数など、ほとんどすべてのものを保存するために使用されます。

ハッシュ テーブルは PHP にとって非常に基本的なものであるため、その仕組みを詳しく調べる価値は十分にあります。

それで、ハッシュ テーブルとは何ですか?

C では、配列は添字を介してアクセスできるメモリのブロックであることを思い出してください。したがって、C の配列では、整数キーと順序付きキーのみを使用できます (つまり、キー 0 の後にキー 1332423442 を使用することはできません)。 C には連想配列のようなものはありません。

ハッシュ テーブルは次のようなものです: ハッシュ関数を使用して文字列キーを通常の整数キーに変換します。ハッシュされた結果は、通常の C 配列キー (別名メモリ ブロック) として使用できます。現在の問題は、ハッシュ関数が競合する可能性があること、つまり、複数の文字列キー値が同じハッシュ値を生成する可能性があることです。たとえば、PHP では、64 要素を超える配列では、文字列「foo」と「oof」は同じハッシュ値を持ちます。

この問題は、生成された添え字に値を直接保存するのではなく、競合する可能性のある値をリンク リストに保存することで解決できます。

HashTable と Bucket

ハッシュ テーブルの基本概念が明確になったので、PHP 内部で実装されているハッシュ テーブル構造を見てみましょう:

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;

簡単に見てみましょう:

nNumOfElementsフラグは配列内の値の数を格納するようになりました。これは関数 count($array) によって返される値でもあります。

nTableSize はハッシュ テーブルの容量を表します。通常は、nNumOfElements 以上の 2 のべき乗の値です。たとえば、配列に 32 個の要素が格納されている場合、ハッシュ テーブルの容量も 32 個の要素になります。ただし、要素が 1 つ追加された場合、つまり配列の要素が 33 個になった場合、ハッシュ テーブルの容量は 64 に調整されます。 これは、ハッシュ テーブルを空間的および時間的に常に有効に保つためです。明らかに、ハッシュ テーブルが小さすぎると、衝突が多くなり、パフォーマンスが低下します。一方、ハッシュ テーブルが大きすぎると、メモリが無駄に消費されます。 2 のべき乗は適切な妥協点です。

nTableMask は、ハッシュ テーブルの容量から 1 を引いた値です。このマスクは、現在のテーブル サイズに基づいて生成されたハッシュ値を調整するために使用されます。たとえば、「foo」の実際のハッシュ値 (DJBX33A ハッシュ関数を使用) は 193491849 です。容量が 64 のハッシュ テーブルがある場合、明らかにそれを配列の添字として使用できません。代わりに、ハッシュ テーブル マスクを適用し、ハッシュ テーブルの下位ビットのみを取得することによって行われます。

hash           |        193491849 |     0b1011100010000111001110001001& mask         | &             63 | &   0b0000000000000000000000111111---------------------------------------------------------= index        | = 9              | =   0b0000000000000000000000001001

nNextFreeElement は、次に使用できる数値キーの値で、$array[] = xyz を使用するときに使用されます。

pInternalPointer は配列の現在位置を保存します。この値は、foreach トラバーサル中に、reset()、current()、key()、next()、prev()、および end() 関数を使用してアクセスできます。

pListHead と pListTail は、配列の最初と最後の要素の位置を識別します。覚えておいてください: PHP 配列は順序付けされたコレクションです。たとえば、2 つの配列 ['foo' => 'bar', 'bar' => 'foo'] および ['bar' => 'foo' =>同じ要素ですが、順序が異なります。

arBuckets は、私たちがよく話す「ハッシュ テーブル (内部 C 配列)」です。これは Bucket ** で定義されているため、配列へのバケット ポインターと考えることができます (Bucket が何であるかについては後ほど説明します)。

pDestructor は値のデストラクターです。この関数は、HT から値が削除された場合に呼び出されます。一般的なデストラクターは zval_ptr_dtor です。 zval_ptr_dtor は zval への参照の数を減らし、o に遭遇した場合はそれを破棄して解放します。

最後の 4 つの変数は、私たちにとってそれほど重要ではありません。つまり、簡単に言えば、永続的な識別ハッシュ テーブルは複数のリクエストに耐えることができ、nApplyCount と bApplyProtection は複数の再帰を防止し、inconsistent はデバッグ モードでのハッシュ テーブルの不正使用を検出するために使用されます。

2 番目の重要な構造に移りましょう: Bucket:

typedef struct bucket {    ulong h;    uint nKeyLength;    void *pData;    void *pDataPtr;    struct bucket *pListNext;    struct bucket *pListLast;    struct bucket *pNext;    struct bucket *pLast;    const char *arKey;} Bucket;

h はハッシュ値 (マスク値マッピングを適用する前の値) です。

arKey は文字列キー値を保存するために使用されます。 nKeyLength は対応する長さです。数値キー値の場合、どちらの変数も使用されません。

pData と pDataPtr は実数値を保存するために使用されます。 PHP 配列の場合、その値は zval 構造体です (ただし、他の場所でも使用されます)。なぜ 2 つのプロパティがあるのか​​については心配しないでください。 2 つの違いは、誰が値を解放する責任があるかです。

pListNext和 pListLast标识数组元素的下一个元素和上一个元素。如果PHP想顺序遍历数组它会从pListHead这个bucket开始（在HashTable结构里面），然后使用pListNext bucket作为遍历指针。在逆序也是一样，从pListTail指针开始，然后使用pListLast指针作为变量指针。（你可以在用户代码里调用end()然后调用prev()函数达到这个效果。）

pNext和 pLast生成我上面提到的“可能冲突的值链表”。arBucket数组存储第一个可能值的bucket。如果该bucket没有正确的键值，PHP会查找pNext指向的bucket。它会一直指向后面的bucket直到找到正确的bucket。pLast在逆序中也是一样的原理。

你可以看到，PHP的哈希表实现相当复杂。这是它使用超灵活的数组类型要付出的代价。

哈希表是怎么被使用的？

Zend Engine定义了大量的API函数供哈希表使用。低级的哈希表函数预览可以在 zend_hash.h文件里面找到。另外Zend Engine在 zend_API.h文件定义了稍微高级一些的API。

我们没有足够的时间去讲所有的函数，但是我们至少可以查看一些实例函数，看看它是如何工作的。我们将使用 array_fill_keys作为实例函数。

使用第二部分提到的技巧你可以很容易地找到函数在 ext/standard/array.c文件里面定义了。现在，让我们来快速查看这个函数。

跟大部分函数一样，函数的顶部有一堆变量的定义，然后调用 zend_parse_parameters函数：

zval *keys, *val, **entry;HashPosition pos;if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "az", &keys, &val) == FAILURE) {    return;}

很明显， az参数说明第一个参数类型是数组（即变量 keys），第二个参数是任意的zval（即变量 val）。

解析完参数后，返回数组就被初始化了：

/* Initialize return array */array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(keys)));

这一行包含了array API里面存在的三步重要的部分：

1、Z_ARRVAL_P宏从zval里面提取值到哈希表。

2、zend_hash_num_elements提取哈希表元素的个数（nNumOfElements属性）。

3、array_init_size使用size变量初始化数组。

因此，这一行使用与键值数组一样大小来初始化数组到 return_value变量里。

这里的size只是一种优化方案。函数也可以只调用 array_init(return_value)，这样随着越来越多的元素添加到数组里，PHP就会多次重置数组的大小。通过指定特定的大小，PHP会在一开始就分配正确的内存空间。

数组被初始化并返回后，函数用跟下面大致相同的代码结构，使用while循环变量keys数组：

zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(keys), &pos);while (zend_hash_get_current_data_ex(Z_ARRVAL_P(keys), (void **)&entry, &pos) == SUCCESS) {    // some code    zend_hash_move_forward_ex(Z_ARRVAL_P(keys), &pos);}

这可以很容易地翻译成PHP代码：

reset($keys);while (null !== $entry = current($keys)) {    // some code    next($keys);}

跟下面的一样：

foreach ($keys as $entry) {    // some code}

唯一不同的是，C的遍历并没有使用内部的数组指针，而使用它自己的pos变量来存储当前的位置。

在循环里面的代码分为两个分支：一个是给数字键值，另一个是其他键值。数字键值的分支只有下面的两行代码：

zval_add_ref(&val);zend_hash_index_update(Z_ARRVAL_P(return_value), Z_LVAL_PP(entry), &val, sizeof(zval *), NULL);

这看起来太直接了：首先值的引用增加了（添加值到哈希表意味着增加另一个指向它的引用），然后值被插入到哈希表中。 zend_hash_index_update宏的参数分别是，需要更新的哈希表 Z_ARRVAL_P(return_value)，整型下标 Z_LVAL_PP(entry)，值 &val，值的大小 sizeof(zval *)以及目标指针(这个我们不关注，因此是 NULL）。

非数字下标的分支就稍微复杂一点：

zval key, *key_ptr = *entry;if (Z_TYPE_PP(entry) != IS_STRING) {    key = **entry;    zval_copy_ctor(&key);    convert_to_string(&key);    key_ptr = &key;}zval_add_ref(&val);zend_symtable_update(Z_ARRVAL_P(return_value), Z_STRVAL_P(key_ptr), Z_STRLEN_P(key_ptr) + 1, &val, sizeof(zval *),             NULL);if (key_ptr != *entry) {    zval_dtor(&key);}

首先，使用 convert_to_string将键值转换为字符串（除非它已经是字符串了）。在这之前， entry被复制到新的 key变量。 key = **entry这一行实现。另外， zval_copy_ctor函数会被调用，不然复杂的结构（比如字符串或数组）不会被正确地复制。

上面的复制操作非常有必要，因为要保证类型转换不会改变原来的数组。如果没有copy操作，强制转换不仅仅修改局部的变量，而且也修改了在键值数组中的值（显然，这对用户来说非常意外）。

显然，循环结束之后，复制操作需要再次被移除， zval_dtor(&key)做的就是这个工作。 zval_ptr_dtor和 zval_dtor的不同是 zval_ptr_dtor只会在 refcount变量为0时销毁zval变量，而 zval_dtor会马上销毁它，而不是依赖 refcount的值。这就为什么你看到 zval_pte_dtor使用”normal”变量而 zval_dtor使用临时变量，这些临时变量不会在其他地方使用。而且， zval_ptr_dtor会在销毁之后释放zval的内容而 zval_dtor不会。因为我们没有 malloc()任何东西，因此我们也不需要 free()，因此在这方面， zval_dtor做了正确的选择。

现在来看看剩下的两行（重要的两行^^）：

zval_add_ref(&val);zend_symtable_update(Z_ARRVAL_P(return_value), Z_STRVAL_P(key_ptr), Z_STRLEN_P(key_ptr) + 1, &val, sizeof(zval *), NULL);

这跟数字键值分支完成后的操作非常相似。不同的是，现在调用的是 zend_symtable_update而不是 zend_hash_index_update，而传递的是键值字符串和它的长度。

符号表

“正常的”插入字符串键值到哈希表的函数是 zend_hash_update，但这里却使用了 zend_symtable_update。它们有什么不同呢？

符号表简单地说就是哈希表的特殊的类型，这种类型使用在数组里。它跟原始的哈希表不同的是他如何处理数字型的键值：在符号表里，”123”和123被看作是相同的。因此，如果你在$array[“123”]存储一个值，你可以在后面使用$array[123]获取它。

底层可以使用两种方式实现：要么使用”123”来保存123和”123”，要么使用123来保存这两种键值。显然PHP选择了后者（因为整型比字符串类型更快和占用更少的空间）。

如果你不小心使用”123”而不是强制转换为123后插入数据，你会发现符号表一些有趣的事情。一个利用数组到对象的强制转换如下：

$obj = new stdClass;$obj->{123} = "foo";$arr = (array) $obj;var_dump($arr[123]); // Undefined offset: 123var_dump($arr["123"]); // Undefined offset: 123

对象属性总是使用字符串键值来保存，尽管它们是数字。因此 $obj->{123} = 'foo'这行代码实际上保存’foo’变量到”123”下标里。当使用数组强制转换的时候，这个值不会给改变。但当 $arr[123]和 $arr["123"]都想访问123下标的值（不是已有的”123”下标）时，都抛出了错误。因此，恭喜，你创建了一个隐藏的数组元素。

下一部分 下一部分会再次在ircmaxell的博客发表。下一篇会介绍对象和类在内部是如何工作的。