一切都是 哈希 表：了解 PHP 中的数组实现

一切都是 哈希 表

基本上 PHP 中的一切都是 哈希 表。不仅在下面的 PHP 数组实现中，它们还用于存储对象属性、方法、函数、变量和几乎任何其他内容。

由于 哈希 Table 对于 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** arBucket s;

dtor_func_t pDestructor;

zend_bool permanent;

unsigned char nApplyCount;

zend_bool bApplyProtection;

#if ZEND_DEBUG

int 不一致;

# endif

} HashTable ;

快速浏览一下：

nNumOfElements 标识当前存储在数组中的值的数量。这也是 count($array) 函数返回的值。

nTableSize代表哈希表的容量。它通常是大于或等于 nNumOfElements 的下一个 2 次方。例如，如果数组存储了 32 个元素，那么 哈希 表的容量也为 32。但是如果再添加一个元素，即数组现在有 33 个元素，那么 哈希 表的容量就会变为 64。这是为了保持哈希表在空间和时间上始终有效。如果哈希表太小，显然会出现很多冲突，性能会下降。另一方面，如果 哈希 表太大，则会浪费内存。 2 的幂是一个很好的折衷方案。

nTableMask 是 哈希 表的容量减一。该掩码用于根据当前表大小调整生成的 哈希 值。例如，“foo”的真实哈希值（使用DJBX33A 哈希函数）是193491849。现在如果我们有一个64容量的哈希表，我们显然不能将其用作数组下标。相反，这是通过应用 哈希 表掩码然后仅获取 哈希 表的低部分来完成的。 3哈希 | 193491849 | 0B10111000100001100111001001

nextFreeElement 是下一个可以使用的数字键值。当您使用 $array[] = xyz 时，您就被使用了。

pInternalPointer 存储数组的当前位置。可以在 foreach 遍历期间使用 reset()、current()、key()、next()、prev() 和 end() 函数访问该值。

pListHead 和 pListTail 标识数组的第一个和最后一个元素的位置。请记住：PHP 数组是有序集合。例如，两个数组 ['foo' => 'bar', 'bar' => 'foo'] 和 ['bar' => 'foo', 'foo' => 'bar'] 包含相同的元素。 ，但顺序不同。

arBucket的就是我们常说的“哈希表（内部C数组）”。它是用 Bucket** 定义的，所以你可以把它想象成一个指向数组的桶指针（我们稍后会讨论 Bucket 是什么）。

pDestructor 是值的析构函数。当从 HT 中删除一个值时，会调用此函数。常见的析构函数是 zval_ptr_dtor。zval_ptr_dtor会减少对zval的引用次数，如果遇到o则销毁并释放。

最后四个变量对我们来说并不那么重要。简单来说，持久标识符表可以经受住多次请求，nApplyCount 和 bApplyProtection 可以防止多次递归，而不一致的表则用于捕获调试模式下对 哈希 表的非法使用。

我们来看第二个重要的结构： Bucket：

typedef struct bucket {

ulong h;

uint nKeyLength ;

void * pData ;

void * pDat aPtr ; 结构桶 * pListNext;

结构桶 * pListLast;

结构桶 * pNext;

结构桶 * pLast;一个 哈希 值（应用掩码值分配之前的值）。

arKey 用于存储字符串键值。 nKeyLength是对应的长度。如果它是数字键值，则不使用这两个变量。

pData 和 pDataPtr 用于存储实际值。对于 PHP 数组，该值是 zval 结构（但它也在其他地方使用）。不用担心为什么有两个属性。两者的区别在于谁负责释放该值。

pListNext 和 pListLast 标识数组元素的下一个和上一个元素。如果 PHP 要顺序遍历数组，就会从 pListHead 桶（HashTable 结构中）开始，然后使用 pListNext 桶作为遍历指针。以相反的顺序进行同样的操作，从 pListTail 指针开始，然后使用 pListLast 指针作为变量指针。 （可以通过在用户代码中调用 end() 函数，然后调用 prev() 函数来实现此效果。）

pNext 和 pLast 生成我上面提到的“潜在冲突值列表”。 arBucket 数组存储第一个可能值的桶。如果存储桶没有正确的密钥，PHP 将查找 pNext 指向的存储桶。它不断指向后续的存储桶，直到找到正确的存储桶。同样的原理反过来也适用于 pLast。

正如你所看到的，PHP 哈希 表的实现相当复杂。这是使用超级灵活的数组类型所付出的代价。

哈希手表如何使用？

Zend Engine 定义了大量 API 函数供 哈希 表使用。低级 哈希 表函数的示例可以在 zend_hash.h 文件中找到。此外，Zend Engine 在 zend_API.h 文件中定义了一个稍微高级的 API。

我们没有足够的时间来讨论所有功能，但我们至少可以看一下一些示例功能，看看它是如何工作的。我们将使用 array_fill_keys 作为实例函数。

使用第 2 部分中的技巧，您可以轻松找到 ext/standard/array.c 文件中定义的函数。现在让我们快速浏览一下此功能。

和大多数函数一样，函数顶部有一些变量定义，然后调用 zend_parse_parameters 函数：

zval *keys , * val , **entry ;

HashPosition pos ;

（zend_parse_parameters（zend_num_args（）tsrmls_cc，“ az”，＆key's和＆val）==失败）{

return; reTurn;

}

prearly，az parameter表示第一个参数类型为一个数组（即变量键），第二个参数是任意 zval（即变量 val）。

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

/* 初始化返回数组 */

array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(keys)));

该行包含数组 API。共有三个重要步骤：

1。宏 Z_ARRVAL_P 将 zval 中的值提取到 哈希 表中。

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

3。 array_init_size 使用变量大小来初始化数组。

因此，这一行初始化了 return_value 变量中的数组，其大小与键值数组相同。

这里的尺寸只是一个优化方案。该函数还可以简单地调用 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 ) {

//代码

zend_hash_move_forward_ex ( Z_ARRVAL_P (keys ), & pos );

}

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

reset($-keys);

while ( null !== $entry = current ($-keys)) {

//一段代码

next($keys);

}

同下：

foreach($keys as $entry){

//一个代码

}

只有一个不同的是，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 = * * 条目 ;

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 != *条目）{

zval_dtor(&键);

}

首先使用convert_to_string将键值转换为字符串（除非它已经是字符串）。为此，输入将被复制到新的键变量。线路键 = **输入已实现。另外，还要调用zval_copy_ctor函数，否则复杂结构（如字符串或数组）将无法正确复制。

上面的复制操作对于保证类型转换不会改变原数组是非常有必要的。如果没有复制操作，强制转换不仅会更改局部变量，还会更改键值数组中的值（这对于用户来说显然非常令人惊讶）。

显然，循环结束后，需要再次去掉复制操作，而zval_dtor(&key)就是做这个工作的。zval_ptr_dtor 和 zval_dtor 的区别在于，zval_ptr_dtor 仅当 refcount 变量为 0 时才会销毁 zval 变量，而 zval_dtor 会立即销毁它，而不依赖于 refcount 的值。这就是为什么您会看到 zval_pte_dtor 使用“普通”变量，而 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 = (数组) $obj;

var_dump ($arr [123]); // 未定义的偏移量：123

var_dump ($arr [ "123" ]); // 未定义的偏移量：123

对象属性始终使用字符串键存储，即使它们是数字。因此 $obj->{123} = 'foo' 行实际上将变量 'foo' 存储在索引 '123' 中。使用数组强制转换时，该值不会更改。但是当 $arr[123] 和 $arr["123"] 都尝试访问 123 下标的值（不是现有的“123”下标）时，会抛出错误。恭喜，您已经创建了一个隐藏的数组元素。