PHP是PHP的核心功能之一。它是稀疏的，允许在同一数组中使用多类型键，并支持集，字典，数组，堆栈/队列和迭代功能。array
但是在使用PHP一段时间后，我发现相当多的函数比你第一眼想象的要慢得多。就像在非常大的数组（10000 +）上一样。 实际上非常慢，以至于在您使用php数组作为索引数组的情况下，像这样的函数的运行速度比快得多。array_*array_randarray_randrand( 0, array_length( $array ) - 1 )array_rand
现在进入我的问题。
PHP数组如何在C级实现？这对于预测大量使用 PHP 数组数据类型的不同功能的函数的大 O 非常有帮助。
在阅读了zend/zend_hash.h和ext/standard/array.c之后，我想我已经找到了答案（感谢Chris和gumbo的建议）。
PHP 数组是一个链式哈希表（在键冲突时查找 O（c） 和 O（n）），它允许使用 int 键和字符串键。它使用 2 种不同的哈希算法将两种类型拟合到同一哈希密钥空间中。此外，存储在哈希中的每个值都链接到它之前存储的值和存储在它之后的值（链接列表）。它还具有一个临时指针，用于保存当前项，以便可以迭代哈希。
该函数的捕获点是，为了确保键是真正随机的，该函数必须迭代数组时间（O（n））。这是因为无法在 O（c） 时间内移动到哈希表中的偏移量，因为无法保证该范围内没有缺少键。array_randarray_randrand(0, count($array))
这一发现有点困扰我，因为这意味着PHP中没有具有正常C数组特征的数据类型。现在大多数时候这是可以的，因为哈希查找非常快，但是在这样的情况下，它的错误会显示出来。array_rand
另一件同样困扰我的是 和 的实现之间的差异。 使用哈希查找（大多数情况下为 O（c））来查看数组中是否有键，而必须线性搜索哈希 （O（n））。array_key_existsin_arrayarray_key_existsin_array
请考虑以下两个示例：
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数据结构中有一个透明标志，可以在使用数组创建的情况下设置，或者允许像C数组而不是链表一样扩展。array_pusharray[] = $value
PHP 关联数组实际上是 HashTables 的实现。
在内部，可以创建数字数组或关联数组。如果将它们组合在一起，则它是关联数组。
在数字数组中，它与C非常相似。您有指向 ZVAL 结构的指针数组。
由于指针具有固定长度（我们称之为 n），因此偏移量 （x） 计算很容易：x * n。
在PHP类型中是ZVAL结构（因为它以这种方式实现动态类型），但它也有助于关联数组，因为您可以假设固定长度。因此，即使直接访问数组的速度较慢，它仍然被认为是O（1）。
那么字符串键中会发生什么呢？PHP使用哈希函数将它们转换为intergers。
在数字和关联数组中搜索具有相似的效率，因为在内部它们都是数字。
只有对数组键的直接访问速度较慢，因为具有额外的级别（哈希函数）。
