PHP数组如何在C级别上实现？

Question

PHP array是PHP的核心功能之一。它是稀疏的，允许在同一数组中使用多类型键，并支持集合，字典，数组，堆栈/队列和迭代功能。但是在使用PHP一段时间之后，我发现相当多的array_*功能比您乍看之下要慢得多。就像在array_rand非常大的数组（10000+）的情况下一样。array_rand实际上，它是如此之慢，以至于在您将php数组用作索引数组的情况下，像这样的函数rand( 0, array_length( $array ) - 1 )运行MUCH的速度比快array_rand。现在到我的问题。PHP数组如何在C级别上实现？这对于预测大量使用PHP数组数据类型的不同功能的函数的Big O很有帮助。

Answer 1

PHP关联数组实际上是HashTables的实现。

在内部，可以制作数字数组或关联数组。如果将它们组合在一起，则它是关联数组。

在数字数组中，它与C非常相似。您具有指向ZVAL结构的指针数组。

因为指针具有固定长度（我们称其为n），所以偏移（x）的计算很容易：x * n。

在PHP中，类型为ZVAL结构（因为它实现了动态类型），但它也有助于关联数组，因为您可以假定定长。因此，即使直接访问数组的速度较慢，仍将其视为O（1）。

那么字符串键会发生什么呢？PHP使用哈希函数将其转换为整数。

在数字和关联数组中搜索具有相似的效率，因为在内部它们都是数字。

由于具有附加级别（散列功能），因此仅直接访问阵列键的速度较慢。

Answer 2

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

该array_rand函数的要点是，为了确保键是真正随机的，该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）或close）。

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

Answer 3

由于PHP数组是有序的映射（即使使用连续的整数索引），array_rand()可能也必须包含一个键列表以从中选择一个元素。我猜想，缓存（频繁失效的）密钥列表在空间和时间上都是无效的，因此每个调用都将至少产生O（n）遍历和构造成本。

因为您的rand(... length ...)实现利用了特殊知识，即键是连续的整数，所以将获得O（log n）查找成本。这似乎与Chacha102的数据一致。