php - PHP数组在C层面是如何实现的？

Question

PHP 数组 是PHP 的核心功能之一。它是稀疏的，允许在同一个数组中使用多种类型的键，并支持集合、字典、数组、堆栈/队列和迭代功能。

但是在使用 PHP 一段时间后，我发现很多 array_* 函数比您乍一看要慢得多。就像 array_rand 在一个非常大的数组(10000+)上的情况一样。 array_rand 实际上太慢了，以至于在您使用 php 数组作为索引数组的情况下，类似 rand( 0, array_length( $array ) - 1 ) 的函数运行速度比 array_rand 快得多。

现在谈谈我的问题。

PHP 数组是如何在 C 级别实现的？这对于预测大量使用 PHP 数组数据类型的不同功能的函数的 Big O 非常有帮助。

Answer 1

在阅读了 zend/zend_hash.h 和 ext/standard/array.c 之后，我想我找到了答案(谢谢 Chris 和 gumbo 的建议)。

PHP 数组是一个链式哈希表(在键冲突时查找 O(c) 和 O(n))，它允许使用 int 和 string 键。它使用 2 种不同的哈希算法将两种类型放入相同的哈希键空间。此外，存储在散列中的每个值都链接到存储在它之前的值和存储在它之后的值(链表)。它还有一个临时指针，用于保存当前项，以便可以迭代散列。

array_rand 函数的问题在于，为了确保 key 是真正随机的，array_rand 函数必须遍历数组 rand(0, count($array)) 次 (O(n))。这是因为无法在 O(c) 时间内移动到哈希表中的偏移量，因为无法保证范围内没有丢失的键。

这个发现让我有些困扰，因为这意味着在 PHP 中没有数据类型具有正常的 C 数组特征。现在大多数情况下这是可以的，因为哈希查找速度非常快，但在 array_rand 等情况下会显示错误。

另一件同样困扰我的事情是 array_key_exists 和 in_array 的实现之间的区别。 array_key_exists 使用散列查找(大部分时间 O(c))来查看数组中是否有键，而 in_array 必须线性搜索散列(O( n)).

考虑下面的两个例子:

in_array 版本

$array = range(0, 100000);
if( in_array( $random_key, $array ) ) {
   //we found a value
}

array_key_exists 版本

$array = array_fill_keys( range(0, 100000), NULL );
if( array_key_exists( $random_key, $array ) ) {
   //we found a value, err key
}

虽然 in_array 版本看起来更清晰、更容易理解，但它在大型数组 (O(n)) 上实际上非常慢，其中 array_key_exists(尽管名称长得令人讨厌)非常快(O(c) 或接近)。

总结:我希望 zend HashTable 数据结构中有一个透明标志，在使用 array_push 或 array[] = $value 创建数组的情况下设置该标志允许像 C 数组而不是链表那样缩放。