PHP数组是如何在C级实现的?

PHP关联数组实际上是 HashTables .

如果将它们合并,则为关联数组。

在数字数组中,它与C非常相似。你有一个指向ZVAL结构的指针数组。

在PHP中,类型是ZVAL结构(因为这样它实现了动态类型),但在关联数组中也有帮助,因为可以假定固定长度。因此,即使直接访问阵列的速度较慢,它仍然被认为是O(1)。

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

在数值数组和关联数组中搜索效率相似,因为它们在内部都是数值的。

由于附加级别(哈希函数),只有直接访问数组键的速度较慢。

在阅读了zend/zend\u hash.h和ext/standard/array.c之后,我想我已经找到了答案(感谢Chris和gumbo的建议)。

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

接球手 array_rand 功能是为了确保密钥是真正随机的 数组\u rand rand(0, count($array)) 次数(O(n))。这是因为无法在O(c)时间内移动到哈希表中的某个偏移量,因为无法保证该范围内没有丢失键。

这个发现让我有些困扰,因为这意味着PHP中没有具有正常C数组特征的数据类型。现在大多数情况下这是可以的,因为散列查找速度非常快,但是在这样的情况下它的错误会显示出来 数组\u rand .

array_key_exists 和 in_array . 在\u数组中 必须线性搜索散列(O(n))。

考虑下面的两个例子:

阵列内版本

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

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

我希望zend HashTable数据结构中有一个透明的标志,在使用 array_push array[] = $value 这将允许像C数组而不是链表那样进行扩展。

因为PHP数组 are ordered maps (即使使用连续整数索引) array_rand()

因为你的 rand(... length ...)

看一看 zend/zend_hash.c 和 zend/zend_hash.h

请参阅文档中的这条评论,确认您的两难处境:数组\u rand虽然对于小型数组来说速度很快,但可扩展性非常差。

我修改了fake_array_rand,使其始终只返回1个元素,并对调用第二个参数为1的array_rand进行了一些基准测试。我为每个函数的每个元素数运行了100个样本,并取平均结果。虽然对于少量元素,内部数组的速度更快,但它的伸缩性非常差。

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]; 
} 
?>

http://us.php.net/manual/en/function.array-rand.php#22360