在C级别上如何实现PHP数组？
PHP array是PHP的核心功能之一。 它很稀疏，允许在同一个数组中使用多类型键，并且支持集合，字典，数组，堆栈/队列和迭代功能。
但是现在使用PHP一段时间后，我发现相当array_*函数比乍看起来要慢得多。 就像array_rand在一个非常大的数组（10000+）上一样。 array_rand实际上很慢，在使用php数组作为索引数组的情况下，类似rand( 0, array_length( $array ) - 1 )的函数比array_rand运行速度快得多。
现在到我的问题。
在C级别上如何实现PHP数组？ 这对于预测大量使用PHP数组数据类型的不同功能的函数的大O很有帮助。
PHP关联数组实际上是HashTables的实现。
在内部，可以制作数字数组或关联数组。 如果将它们结合起来，它就是关联数组。
在数值数组中，它与C非常相似。您有指向ZVAL结构体的指针数组。
因为指针具有固定长度（我们称它为n），所以偏移量（x）的计算很简单：x * n。
在PHP中，类型是ZVAL结构体（因为它实现了动态类型），但它也有助于关联数组，因为您可以假定为固定长度。 所以即使直接访问数组速度较慢，它仍然被认为是O（1）。
那么在字符串键中会发生什么？ PHP使用散列函数将它们转换为整数。
在数字和关联数组中搜索具有相似的效率，因为它们在内部都是数字的。
由于额外的级别（散列函数），只能直接访问数组键。
在阅读了zend / zend_hash.h和ext / standard / array.c之后，我想我已经找到了答案（Thankyou 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）或close）。
总之：我希望zend HashTable数据结构中有一个透明标志，在数组使用array_push或array[] = $value创建的情况下设置，这将允许像C数组那样扩展而不是链接名单。
由于PHP数组是有序的映射（即使使用连续的整数索引）， array_rand()可能必须提供一个键列表以从中选择一个元素。 我猜测，如果缓存（通常是无效的）密钥列表会导致空间和时间过于缩短，所以每次调用至少需要O（n）遍历和建设成本。
因为你的rand(... length ...)实现利用了你所拥有的关键是连续整数的特殊知识，所以你会得到O（log n）查找成本。 这似乎与Chacha102的数据一致。