如何在C级别上实现PHP数组？
PHP array是PHP的核心function之一。 它是稀疏的，可以在同一个数组中使用多types的键，并支持集合，字典，数组，堆栈/队列和迭代function。
但是在使用PHP一段时间之后，我发现相当多的array_*函数比乍看起来要慢得多。 就像array_rand在一个非常大的数组（10000+）上一样。 array_rand实际上太慢了，在使用php数组作为索引数组的情况下，类似rand( 0, array_length( $array ) - 1 )的函数比array_rand快得多。
现在到我的问题。
PHP数组如何在C级上实现？ 这对预测大量使用PHP数组数据types的不同function的函数的大O很有帮助。
PHP关联数组实际上是HashTable的实现。
在内部，可以制作数字数组或关联数组。 如果你把它们结合起来，那就是关联数组。
在数值数组中，它与C非常类似。您有指向ZVAL结构体的指针数组。
因为指针具有固定长度（我们称之为n），所以偏移（x）计算很容易：x * n。
在PHPtypes中，ZVAL结构体（因为它实现了dynamictypes），但是它也有助于关联数组，因为您可以假定为固定长度。 所以即使直接访问数组速度较慢，仍然被认为是O（1）。
那么在string键中会发生什么？ PHP使用散列函数将它们转换为整数。
在数字和关联数组中search具有相似的效率，因为它们在内部都是数字的。
只有直接访问数组键的速度较慢，因为附加的级别（散列函数）。
读过zend / zend_hash.h和ext / standard / array.c后，我想我已经find了答案（谢谢Chris和gumbo的build议）。
PHP数组是一个链式哈希表（在关键冲突中查找O（c）和O（n）），允许int和string键。 它使用2种不同的哈希algorithm将两种types合并到相同的哈希键空间中。 此外，存储在散列中的每个值都链接到存储在其之前的值和（链接列表）之后存储的值。 它也有一个临时指针，用来保存当前项目，所以哈希可以迭代。
array_rand函数的捕获是为了确保key是真正随机的， array_rand函数必须遍历数组rand(0, count($array))次（O（n））。 这是因为无法在O（c）时间移动到哈希表中的偏移量，因为不能保证范围内没有丢失键。
这个发现有点困扰我，因为这意味着在PHP中没有数据types具有正常的C数组特性。 现在大多数情况下这是可以的，因为哈希查找速度非常快，但是在array_rand情况下会显示错误。
另一件令我困扰的事情是array_key_exists和in_array之间的区别。 array_key_exists使用散列查找（大部分时间O（c））来查看一个键是否在数组中，而in_array必须线性search散列（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（尽pipe名字很长）很快（O（c）或close）。
总之：我希望在zend HashTable数据结构中有一个透明标志，在数组使用array_push或array[] = $value创build的情况下，将会设置这个标志，这样可以像C数组一样进行缩放，而不是链接名单。
由于PHP数组是有序的映射 （即使使用连续的整数索引）， array_rand()可能必须提供一个键列表来select一个元素。 我猜测，如果caching（通常是无效的）密钥列表，那么每个调用至less会产生O（n）的遍历和构build成本将会是空间和时间上的无效。
因为你的rand(... length ...)实现利用了你所拥有的关键是连续整数的特殊知识，所以你会得到O（log n）查找开销。 这似乎与Chacha102的数据一致。
在文档中看到这个评论，确认array_rand的两难处境，而对于小数组来说，很快就会缩小。
我修改了fake_array_rand总是只返回1个元素，并且做了一些基准来调用array_rand，第二个参数是1.我为每个元素的每个元素运行100个样本，并取平均值。 虽然内部array_rand对于less数元素来说速度更快，但是其比例很差。
1 elements: 2.0619630813599E-05 sec. for array_rand,8.4352493286133E-05 sec. for fake_array_rand 10 elements: 2.1675825119019E-05 sec. for array_rand,8.427619934082E-05 sec. for fake_array_rand 100 elements: 2.9319524765015E-05 sec. for array_rand,8.4599256515503E-05 sec. for fake_array_rand 1000 elements: 0.0001157283782959 sec. for array_rand,8.5572004318237E-05 sec. for fake_array_rand 10000 elements: 0.0016669762134552 sec. for array_rand,8.5201263427734E-05 sec. for fake_array_rand 100000 elements: 0.015599734783173 sec. for array_rand,8.5580348968506E-05 sec. for fake_array_rand 1000000 elements: 0.18011983394623 sec. for array_rand,8.6690187454224E-05 sec. for fake_array_rand <?php function fake_array_rand ($array) { $count = count ($array); # Help keep the number generator random :) $randval and usleep ("0.$randval"); # Seed the random number generator # Generate a random number srand ((double) microtime() * 10000000); $randval = rand(); # Use the random value to 'pick' an entry from the array # Count the number of times that the entry is picked ++$index[$randval % $count]; return $array[$randval % $count]; } ?>
看看zend / zend_hash.c和zend / zend_hash.h
我不知道C，但对我来说，它看起来像一个链式哈希表。
